Bug Summary

File:src/of_deada.c
Warning:line 576, column 3
Value stored to 'lhs' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name of_deada.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/kfp/aldor/aldor/aldor/src -fcoverage-compilation-dir=/home/kfp/aldor/aldor/aldor/src -resource-dir /usr/local/lib/clang/18 -D PACKAGE_NAME="aldor" -D PACKAGE_TARNAME="aldor" -D PACKAGE_VERSION="1.4.0" -D PACKAGE_STRING="aldor 1.4.0" -D PACKAGE_BUGREPORT="aldor@xinutec.org" -D PACKAGE_URL="" -D PACKAGE="aldor" -D VERSION="1.4.0" -D YYTEXT_POINTER=1 -D HAVE_STDIO_H=1 -D HAVE_STDLIB_H=1 -D HAVE_STRING_H=1 -D HAVE_INTTYPES_H=1 -D HAVE_STDINT_H=1 -D HAVE_STRINGS_H=1 -D HAVE_SYS_STAT_H=1 -D HAVE_SYS_TYPES_H=1 -D HAVE_UNISTD_H=1 -D STDC_HEADERS=1 -D HAVE_LIBREADLINE=1 -D HAVE_READLINE_READLINE_H=1 -D HAVE_READLINE_HISTORY=1 -D HAVE_READLINE_HISTORY_H=1 -D USE_GLOOP_SHELL=1 -D GENERATOR_COROUTINES=0 -D HAVE_DLFCN_H=1 -D LT_OBJDIR=".libs/" -I . -D VCSVERSION="2c53e759f1e00e345f8b172e7139debda72fda13" -internal-isystem /usr/local/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wno-empty-body -Wno-enum-compare -Wno-missing-field-initializers -Wno-unused -Wno-unused-parameter -Wno-error=format -Wno-error=type-limits -Wno-error=strict-aliasing -Wno-sign-compare -Wno-error=shift-negative-value -Wno-error=clobbered -std=c99 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2026-01-15-223856-845667-1 -x c of_deada.c
1/*****************************************************************************
2 *
3 * of_deada.c: Dead Assignment Elimination
4 *
5 * Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
6 *
7 ****************************************************************************/
8
9/*
10 * Dead assignment elimination:
11 * Remove any assignments whose value is nowhere used:
12 *
13 * Example:
14 *l0:
15 * f(x)
16 * x := 1;
17 * if C then l1;
18 * ...
19 *l1:
20 * x := 2;
21 * goto l0;
22 *
23 * The first assignment to x can be killed.
24 * Done using reverse dataflow, with
25 * In(B) == { v: v is live before B }
26 * Out(B) == { v: v is live after B }
27 * Gen(B) == { v: v is used before set within B }
28 * Kill(B) == { v: v is set before used within B }
29 *
30 * Eliminating within a BB is a matter of applying these rules
31 * to the Out Set within the BB, starting from the last stmt.
32 */
33
34#include "axlobs.h"
35#include "debug.h"
36#include "dflow.h"
37#include "flog.h"
38#include "of_deada.h"
39#include "of_util.h"
40#include "optfoam.h"
41#include "optinfo.h"
42#include "opttools.h"
43#include "store.h"
44#include "table.h"
45
46Bool daDebug = false((int) 0);
47
48#define daDEBUGif (!daDebug) { } else afprintf DEBUG_IF(da)if (!daDebug) { } else afprintf
49
50/****************************************************************************
51 *
52 * Type definitions
53 *
54 ****************************************************************************/
55
56/****************************************************************************
57 *
58 * Global Data Structures
59 *
60 ****************************************************************************/
61
62static int daFlogCutOff = 700;
63
64static BitvClass daBitvClass;
65static Bool daChanged;
66static LiveVars daLiveVars;
67static FlowGraph daThisFlog;
68
69/****************************************************************************
70 *
71 * Local declarations
72 *
73 ****************************************************************************/
74
75localstatic Foam daProg (Foam);
76localstatic Bool daFlog0 (int, FlowGraph);
77localstatic void daFillDefRef (FlowGraph, BBlock);
78localstatic void daFillStmt (Foam, BBlock);
79localstatic void daFillExpr (Foam, BBlock);
80localstatic void daFixBBlock (BBlock);
81localstatic Foam daFixSet (Bitv, Foam);
82localstatic void daFixExpr (Bitv, Foam);
83
84localstatic int daBitvSize (Foam prog);
85localstatic int daBitvIndex (Foam foam);
86
87void daReduceTemps (BBlock bb);
88
89localstatic LiveInfoList daAddLiveChanges (LiveInfoList, int, Bitv);
90localstatic LiveVars daMakeInitLiveVars (FlowGraph);
91
92/****************************************************************************
93 *
94 * :: External functions
95 *
96 ****************************************************************************/
97
98void
99daSetCutOff(int n)
100{
101 daFlogCutOff = n;
102}
103
104void
105deadAssign(Foam unit)
106{
107 Foam ddef, def, rhs;
108 int i;
109
110 ddef = unit->foamUnit.defs;
111 for (i = 0; i<foamArgc(ddef)((ddef)->hdr.argc); i++) {
112 def = ddef->foamDDef.argv[i];
113 assert(foamTag(def) == FOAM_Def)do { if (!(((def)->hdr.tag) == FOAM_Def)) _do_assert(("foamTag(def) == FOAM_Def"
),"of_deada.c",113); } while (0);
114
115 rhs = def->foamDef.rhs;
116 if (foamTag(rhs)((rhs)->hdr.tag) == FOAM_Prog)
117 def->foamDef.rhs = daProg(rhs);
118 }
119 assert(foamAudit(unit))do { if (!(foamAudit(unit))) _do_assert(("foamAudit(unit)"),"of_deada.c"
,119); } while (0);
120}
121
122void
123daFlog(FlowGraph flog, LiveVars *pVars)
124{
125 int nlocals = daBitvSize(flog->prog);
126
127 if (pVars)
128 daLiveVars = daMakeInitLiveVars(flog);
129 else
130 daLiveVars = NULL((void*)0);
131
132 daFlog0(nlocals, flog);
133
134 if (pVars) {
135 *pVars = daLiveVars;
136 (*pVars)->bvClass = bitvClassCreate(nlocals);
137 }
138}
139
140
141void
142daFreeVars(LiveVars vars)
143{
144}
145
146/****************************************************************************
147 *
148 * :: Simple accessors
149 *
150 ****************************************************************************/
151
152localstatic int
153daBitvSize(Foam prog)
154{
155 return foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1))
156 + foamDDeclArgc(prog->foamProg.params)(((prog->foamProg.params)->hdr.argc) - (1));
157}
158
159localstatic int
160daBitvIndex(Foam foam)
161{
162 switch (foamTag(foam)((foam)->hdr.tag)) {
163 case FOAM_Loc:
164 return foam->foamLoc.index;
165 case FOAM_Par:
166 return foam->foamPar.index +
167 foamDDeclArgc(daThisFlog->prog->foamProg.locals)(((daThisFlog->prog->foamProg.locals)->hdr.argc) - (
1));
168 default:
169 return -1;
170 }
171}
172
173/****************************************************************************
174 *
175 * Compute and eliminate...
176 *
177 ****************************************************************************/
178
179localstatic Foam
180daProg(Foam prog)
181{
182 FlowGraph flog;
183 Foam locals, ret;
184 int nbits;
185
186 if (DEBUG(da)daDebug) {
187 fprintf(dbOut, "(Before:\n");
188 foamWrSExpr(dbOut, prog,int0((int) 0));
189 }
190 locals = prog->foamProg.locals;
191
192 nbits = daBitvSize(prog);
193
194 if (nbits == 0)
195 return prog;
196
197 flog = flogFrProg(prog, FLOG_UniqueExit);
198
199 daLiveVars = NULL((void*)0);
200 daFlog0(nbits, flog);
201
202 ret = flogToProg(flog);
203 if (DEBUG(da)daDebug) {
204 foamWrSExpr(dbOut, ret,int0((int) 0));
205 fprintf(dbOut, "After)\n");
206 }
207 daBitvClass = NULL((void*)0);
208
209 return ret;
210}
211
212localstatic Bool
213daFlog0(int nLocals, FlowGraph flog)
214{
215 BBlock bb;
216 int i, count;
217 Bool changed = false((int) 0);
218
219 daBitvClass = bitvClassCreate(nLocals);
220 flogBitvClass(flog)((flog)->bitvClass) = daBitvClass;
221 daThisFlog = flog;
222
223 daChanged = true1;
224
225 while (daChanged) {
226 daChanged = false((int) 0);
227
228 for (i=0; i<flogBlockC(flog)((flog)->blocks->pos); i++) {
229 bb = flogBlock(flog, i)bbufBlockFn((flog)->blocks,i);
230 dflowNewBlockInfo(bb, nLocals, daFillDefRef);
231 }
232
233 i = dflowRevIterate(flog, DFLOW_Union,
234 daFlogCutOff, &count, NULL((void*)0));
235
236 if (i != 0)
237 return false((int) 0);
238
239 for (i=0; i<flogBlockC(flog)((flog)->blocks->pos); i++) {
240 if (!flogBlock(flog,i)bbufBlockFn((flog)->blocks,i)) continue;
241 if (flogBlock(flog, i)bbufBlockFn((flog)->blocks,i))
242 daFixBBlock(flogBlock(flog, i)bbufBlockFn((flog)->blocks,i));
243 }
244
245 if (daChanged) changed = true1;
246 }
247
248 /* Killing assignments may simplify cse/flow/cprop analysis */
249 if (changed) {
250 optSetCsePending(flog->prog)(((flog->prog)->hdr.info.opt)->optMask |= (1 <<
2));
251 optSetJFlowPending(flog->prog)(((flog->prog)->hdr.info.opt)->optMask |= (1 <<
1));
252 optSetCPropPending(flog->prog)(((flog->prog)->hdr.info.opt)->optMask |= (1 <<
0));
253 }
254
255 daThisFlog = NULL((void*)0);
256 return true1;
257}
258
259localstatic void
260daFillDefRef(FlowGraph flog, BBlock bb)
261{
262 Foam seq = bb->code;
263 Foam stmt;
264 BitvClass class = flogBitvClass(flog)((flog)->bitvClass);
265 int i;
266
267 /* clear the vectors */
268 bitvClearAll(class, dfRevKill(bb)((bb)->dfinfo->exit[0].kill));
269 bitvClearAll(class, dfRevGen(bb)((bb)->dfinfo->gen));
270
271 for (i=0; i<foamArgc(seq)((seq)->hdr.argc); i++) {
272 stmt = seq->foamSeq.argv[i];
273 daFillStmt(stmt, bb);
274 }
275}
276
277localstatic void
278daFillStmt(Foam stmt, BBlock bb)
279{
280 Foam *argv;
281 int idx, argc, i;
282
283 if (!otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) {
284 daFillExpr(stmt, bb);
285 return;
286 }
287
288 daFillExpr(stmt->foamSet.rhs, bb);
289
290 switch(foamTag(stmt->foamSet.lhs)((stmt->foamSet.lhs)->hdr.tag)) {
291 case FOAM_Values:
292 argv = stmt->foamSet.lhs->foamValues.argv;
293 argc = foamArgc(stmt->foamSet.lhs)((stmt->foamSet.lhs)->hdr.argc);
294 break;
295 default:
296 argv = &stmt->foamSet.lhs;
297 argc = 1;
298 break;
299 }
300
301 for (i=0; i<argc; i++) {
302 idx = daBitvIndex(argv[i]);
303 if (idx != -1) {
304 if (!bitvTest(daBitvClass, dfRevGen(bb)((bb)->dfinfo->gen), idx))
305 bitvSet(daBitvClass, dfRevKill(bb)((bb)->dfinfo->exit[0].kill), idx);
306 } else
307 daFillExpr(argv[i], bb);
308 }
309}
310
311localstatic void
312daFillExpr(Foam foam, BBlock bb)
313{
314 int idx;
315
316 idx = daBitvIndex(foam);
317 if (idx != -1) {
318 if (!bitvTest(daBitvClass, dfRevKill(bb)((bb)->dfinfo->exit[0].kill), idx))
319 bitvSet(daBitvClass, dfRevGen(bb)((bb)->dfinfo->gen), idx);
320 }
321 else
322 foamIter(foam, arg, daFillExpr(*arg, bb)){ { String argf = (foamInfoTable [(int)(((foam)->hdr.tag))
-(int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((foam
)->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if
(*argf == 'C') { Foam *arg = (Foam *) ((foam)->foamGen.argv
)+_i; { daFillExpr(*arg, bb); }; } } }; };
323}
324
325localstatic void
326daFixBBlock(BBlock bb)
327{
328 LiveInfoList lst = listNil(LiveInfo)((LiveInfoList) 0);
329 Foam seq = bb->code;
330 Foam stmt, newstmt;
331 Bitv bitv;
332 int i;
333
334 /* Do dataflow by hand backwards through the BB */
335 /* Start with the 'out' set and work upwards */
336 /* when complete, out will be a subset of "in" */
337 if (DEBUG(da)daDebug) {
338 fprintf(dbOut, "(Fixing: Out\n");
339 bitvPrint(dbOut, daBitvClass, dfRevOut(bb)((bb)->dfinfo->exit[0].out));
340 fprintf(dbOut, "\nIn\n");
341 bitvPrint(dbOut, daBitvClass, dfRevIn(bb)((bb)->dfinfo->in));
342 fprintf(dbOut, "\nFoam\n");
343 foamWrSExpr(dbOut, seq, int0((int) 0));
344 }
345 bitv = bitvNew(daBitvClass);
346 bitvCopy(daBitvClass, bitv, dfRevOut(bb)((bb)->dfinfo->exit[0].out));
347
348 for (i=foamArgc(seq)((seq)->hdr.argc) - 1; i >= 0 ; i--) {
349 stmt = seq->foamSeq.argv[i];
350
351 if (daLiveVars != NULL((void*)0))
352 lst = daAddLiveChanges(lst, i, bitv);
353
354 if (!otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
))
355 daFixExpr(bitv, stmt);
356 else {
357 newstmt = daFixSet(bitv, stmt);
358 seq->foamSeq.argv[i] = newstmt;
359 }
360
361 }
362
363 if (daLiveVars != NULL((void*)0)) {
364 lst = daAddLiveChanges(lst, i, bitv);
365 daLiveVars->vars[bb->label] = lst;
366 }
367
368#if 0
369 daReduceTemps(bb);
370#endif
371 if (DEBUG(da)daDebug) {
372 bitvPrint(dbOut, daBitvClass, bitv);
373 fprintf(dbOut, "\nDone fix)\n");
374 }
375
376}
377
378localstatic Foam
379daFixSet(Bitv bitv, Foam set)
380{
381 Foam lhs = set->foamSet.lhs;
382 Foam rhs = set->foamSet.rhs;
383 Foam *argv;
384 int argc;
385 Bool isLive;
386 int i, idx;
387
388 switch(foamTag(lhs)((lhs)->hdr.tag)) {
389 case FOAM_Values:
390 argv = lhs->foamValues.argv;
391 argc = foamArgc(lhs)((lhs)->hdr.argc);
392 break;
393 default:
394 argv = &lhs;
395 argc = 1;
396 break;
397 }
398
399 isLive = false((int) 0);
400 for (i=0; i<argc; i++) {
401 idx = daBitvIndex(argv[i]);
402 if (idx == -1) {
403 isLive = true1;
404 daFixExpr(bitv, argv[i]);
405 }
406 else {
407 isLive |= bitvTest(daBitvClass, bitv, idx);
408 bitvClear(daBitvClass, bitv, idx);
409 }
410 }
411
412 if (isLive) {
413 daFixExpr(bitv, rhs);
414 return set;
415 }
416
417 /* !! GenC should deal with MFmt without a Set */
418 if (foamTag(rhs)((rhs)->hdr.tag) == FOAM_MFmt) {
419 daFixExpr(bitv, rhs);
420 return set;
421 }
422
423 if (foamHasSideEffect(rhs)) {
424 daFixExpr(bitv, rhs);
425 foamFree(lhs);
426 foamFreeNode(set);
427 return rhs;
428 }
429
430 foamFree(set);
431 daChanged = true1;
432 return foamNewNOp()foamNew(FOAM_NOp, (int) 0);
433}
434
435localstatic void
436daFixExpr(Bitv bitv, Foam expr)
437{
438 int idx;
439
440 idx = daBitvIndex(expr);
441 if (idx != -1)
442 bitvSet(daBitvClass, bitv, idx);
443 else
444 foamIter(expr, arg, daFixExpr(bitv, *arg)){ { String argf = (foamInfoTable [(int)(((expr)->hdr.tag))
-(int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((expr
)->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if
(*argf == 'C') { Foam *arg = (Foam *) ((expr)->foamGen.argv
)+_i; { daFixExpr(bitv, *arg); }; } } }; };
445}
446
447
448/****************************************************************************
449 *
450 * :: Temporary Reduction
451 *
452 ****************************************************************************/
453
454typedef struct {
455 AIntList vars;
456 Foam temps;
457 int lastStmt;
458} *FreeTempSet;
459
460localstatic void trRenameBlock (BBlock);
461localstatic Foam trRenameExpr (int, Foam);
462localstatic Foam trRenameSet (int, Foam);
463localstatic AInt trRenameId (int, AInt);
464localstatic void trAddTemporary (FreeTempSet, int, AInt);
465localstatic AInt trAllocateTemporary (int, AInt);
466localstatic void trSetName (AInt, AInt);
467localstatic AInt trGetName (AInt);
468localstatic void trInitTempSets (BBlock);
469localstatic void trFillSetsExpr (int, Foam);
470localstatic void trFillKillSet (int, Foam);
471localstatic void trFiniTempSets (void);
472localstatic void trInitFreeVars (BBlock);
473localstatic AIntList trKillEventsAfter (int, AInt);
474localstatic AIntList trUseEventsAfter (int, AInt);
475localstatic AIntList trEventsAfter (int, AIntList l);
476localstatic void trCollectNonLocalTemps (FreeTempSet, FlowGraph, BBlock);
477localstatic Bool trVarsCompatible (FreeTempSet, AInt, AInt);
478localstatic void trUseName (AInt);
479localstatic Bool trIsUseable (int stmt, AInt newVar);
480
481static Table trKillTbl;
482static Table trUseTbl;
483static Table trRenameTbl;
484static Bitv trLive;
485static Bitv trOut;
486
487static FreeTempSet trFreeTemps;
488
489void
490daReduceTemps(BBlock bb)
491{
492 trInitTempSets(bb);
493
494 trRenameBlock(bb);
495
496 trFiniTempSets();
497}
498
499localstatic void
500trRenameBlock(BBlock bb)
501{
502 Foam seq, stmt;
503 int i;
504
505 seq = bb->code;
506 for (i=0; i<foamArgc(seq)((seq)->hdr.argc); i++) {
507 stmt = seq->foamSeq.argv[i];
508
509 switch (foamTag(stmt)((stmt)->hdr.tag)) {
510 case FOAM_Def:
511 case FOAM_Set:
512 seq->foamSeq.argv[i] = trRenameSet(i, stmt);
513 break;
514 default:
515 trRenameExpr(i, stmt);
516 }
517 }
518}
519
520localstatic Foam
521trRenameExpr(int stmtId, Foam expr)
522{
523 AIntList kills, uses;
524 Bool liveAfter;
525 int id;
526
527 foamIter(expr, arg, *arg = trRenameExpr(stmtId, *arg)){ { String argf = (foamInfoTable [(int)(((expr)->hdr.tag))
-(int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((expr
)->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if
(*argf == 'C') { Foam *arg = (Foam *) ((expr)->foamGen.argv
)+_i; { *arg = trRenameExpr(stmtId, *arg); }; } } }; };
528
529 if (foamTag(expr)((expr)->hdr.tag) != FOAM_Loc)
530 return expr;
531
532 id = daBitvIndex(expr);
533
534 if (bitvTest(daBitvClass, trLive, id)) {
535 /* Determine if this is the last use of this local */
536 uses = trUseEventsAfter(stmtId + 1, id);
537 kills = trKillEventsAfter(stmtId, id);
538
539 liveAfter = bitvTest(daBitvClass, trOut, id);
540
541 daDEBUGif (!daDebug) { } else afprintf(dbOut,
542 "Checking %d var: %d next use: %d next kill: %d used later: %s\n",
543 stmtId, id,
544 uses ? (int)car(uses)((uses)->first): 999999,
545 kills ? (int)car(kills)((kills)->first): 999999,
546 liveAfter ? "Yes" : "No");
547
548 if (uses == listNil(AInt)((AIntList) 0)) {
549 if (!liveAfter)
550 trAddTemporary(trFreeTemps, stmtId, id);
551 }
552 else if (kills != listNil(AInt)((AIntList) 0) && (car(uses)((uses)->first) > car(kills)((kills)->first)))
553 trAddTemporary(trFreeTemps, stmtId, id);
554
555 bitvClear(daBitvClass, trLive, id);
556 }
557
558 id = trGetName(id);
559
560 expr->foamLoc.index = id;
561
562 return expr;
563
564}
565
566localstatic Foam
567trRenameSet(int stmtId, Foam set)
568{
569 Foam lhs = set->foamSet.lhs;
570 Foam rhs = set->foamSet.rhs;
571 AInt lhsId;
572
573 rhs = trRenameExpr(stmtId, rhs);
574
575 if (foamTag(lhs)((lhs)->hdr.tag) != FOAM_Loc) {
576 lhs = trRenameExpr(stmtId, lhs);
Value stored to 'lhs' is never read
577 return set;
578 }
579
580 lhsId = trRenameId(stmtId, lhs->foamLoc.index);
581 lhs->foamLoc.index = lhsId;
582
583 return set;
584}
585
586localstatic AInt
587trRenameId(int stmtId, AInt id)
588{
589 Bool liveAfter;
590
591 /* Mark as live (could tighten this up) */
592 bitvSet(daBitvClass, trLive, id);
593 /* Determine if it is safe to rename */
594
595 liveAfter = bitvTest(daBitvClass, trOut, id);
596 if (liveAfter) {
597 AIntList kills;
598 kills = trKillEventsAfter(stmtId+1, id);
599 if (kills == listNil(AInt)((AIntList) 0)) {
600 /* forget the previous name */
601 trUseName(id);
602 return id;
603 }
604 }
605
606 return trAllocateTemporary(stmtId, id);
607}
608
609
610localstatic void
611trAddTemporary(FreeTempSet set, int stmt, AInt id)
612{
613 assert(stmt >= set->lastStmt)do { if (!(stmt >= set->lastStmt)) _do_assert(("stmt >= set->lastStmt"
),"of_deada.c",613); } while (0);
614
615 if (set->lastStmt < stmt) {
616 set->vars = listCons(AInt)(AInt_listPointer->Cons)((AInt) -1, set->vars);
617 set->lastStmt = stmt;
618 }
619 if (id == -1)
620 return;
621
622 set->vars = listCons(AInt)(AInt_listPointer->Cons)(id, set->vars);
623
624 daDEBUGif (!daDebug) { } else afprintf(dbOut, "Stmt: %d free: %d\n", stmt, (int)id);
625}
626
627localstatic AInt
628trAllocateTemporary(int stmtId, AInt oldId)
629{
630 AIntList *vars = &trFreeTemps->vars;
631 AInt actual, id = -1;
632
633 if (DEBUG(da)daDebug) {
634 AIntList lst;
635 lst = trFreeTemps->vars;
636 fprintf(dbOut, "Before: [");
637 while (lst) {
638 fprintf(dbOut, "%d", (int)car(lst)((lst)->first));
639 lst = cdr(lst)((lst)->rest);
640 if (lst) fprintf(dbOut, " ");
641 }
642 fprintf(dbOut, "]\n");
643 }
644 actual = trGetName(oldId);
645
646 while (*vars != listNil(AInt)((AIntList) 0)) {
647 AIntList *fallback = NULL((void*)0);
648 AInt var;
649
650 while ( (var = car(*vars)((*vars)->first)) != (AInt) -1) {
651 if ( var == actual) {
652 id = actual;
653 break;
654 }
655 if (fallback == NULL((void*)0)
656 && trVarsCompatible(trFreeTemps, oldId, var)
657 && trIsUseable(stmtId, var))
658 fallback = vars;
659 vars = &cdr(*vars)((*vars)->rest);
660 }
661
662 if (id != -1)
663 break;
664 if (fallback != NULL((void*)0)) {
665 vars = fallback;
666 id = car(*fallback)((*fallback)->first);
667 break;
668 }
669 vars = &cdr(*vars)((*vars)->rest);
670 }
671
672 assert(*vars)do { if (!(*vars)) _do_assert(("*vars"),"of_deada.c",672); } while
(0);
673 /* Remove this element from the list [memleak!]*/
674 *vars = cdr(*vars)((*vars)->rest);
675 daDEBUGif (!daDebug) { } else afprintf(dbOut, "Rename: %d -> %d, ", (int)oldId, (int)id);
676 if (DEBUG(da)daDebug) {
677 AIntList lst;
678 lst = trFreeTemps->vars;
679 fprintf(dbOut, "[");
680 while (lst) {
681 fprintf(dbOut, "%d", (int)car(lst)((lst)->first));
682 lst = cdr(lst)((lst)->rest);
683 if (lst) fprintf(dbOut, " ");
684 }
685 fprintf(dbOut, "]\n");
686 }
687
688 trSetName(oldId, id);
689 return id;
690}
691
692localstatic void
693trUseName(AInt id)
694{
695 AIntList *vars = &trFreeTemps->vars;
696 while (*vars != listNil(AInt)((AIntList) 0) && car(*vars)((*vars)->first) != id)
697 vars = &cdr(*vars)((*vars)->rest);
698
699 if (*vars != listNil(AInt)((AIntList) 0))
700 *vars = cdr(*vars)((*vars)->rest);
701
702}
703
704localstatic Bool
705trIsUseable(int stmtId, AInt newVar)
706{
707 Bool liveAfter;
708
709 /* Mark as live (could tighten this up) */
710 bitvSet(daBitvClass, trLive, newVar);
711 /* Determine if it is safe to rename */
712
713 liveAfter = bitvTest(daBitvClass, trOut, newVar);
714 if (liveAfter) {
715 AIntList kills;
716 kills = trKillEventsAfter(stmtId+1, newVar);
717 if (kills == listNil(AInt)((AIntList) 0)) {
718 return false((int) 0);
719 }
720 }
721
722 return true1;
723}
724
725localstatic Bool
726trVarsCompatible(FreeTempSet set, AInt old, AInt new)
727{
728 Foam odecl, ndecl;
729 Bool ok;
730
731 odecl = set->temps->foamDDecl.argv[old];
732 ndecl = set->temps->foamDDecl.argv[new];
733
734 if (odecl->foamDecl.type != ndecl->foamDecl.type)
735 return false((int) 0);
736
737 switch(odecl->foamDecl.type) {
738 case FOAM_Rec:
739 case FOAM_Arr:
740 ok = (odecl->foamDecl.format == ndecl->foamDecl.format);
741 break;
742 default:
743 ok = true1;
744 }
745 return ok;
746}
747
748
749localstatic void
750trSetName(AInt old, AInt new)
751{
752 tblSetElt(trRenameTbl, (TblKey) old, (TblElt) new);
753}
754
755localstatic AInt
756trGetName(AInt id)
757{
758 return (AInt) tblElt(trRenameTbl, (TblKey) id, (TblElt) id);
759}
760
761
762localstatic void
763trInitTempSets(BBlock bb)
764{
765 Foam seq, stmt;
766 int i;
767
768 trKillTbl = tblNew(NULL((void*)0), NULL((void*)0));
769 trUseTbl = tblNew(NULL((void*)0), NULL((void*)0));
770 trRenameTbl = tblNew(NULL((void*)0), NULL((void*)0));
771
772 seq = bb->code;
773 /* First find all uses and kills */
774 for (i=foamArgc(seq)((seq)->hdr.argc)-1; i>=0; i--) {
775 stmt = seq->foamSeq.argv[i];
776 trFillSetsExpr(i, stmt);
777 }
778
779 trInitFreeVars(bb);
780
781 /* Current live variables */
782 trLive = dfRevIn(bb)((bb)->dfinfo->in);
783 trOut = dfRevOut(bb)((bb)->dfinfo->exit[0].out);
784}
785
786localstatic void
787trInitFreeVars(BBlock bb)
788{
789 FreeTempSet fvs = (FreeTempSet) stoAlloc(OB_Other0,sizeof(*fvs));
790 TableIterator it;
791
792 fvs->vars = listNil(AInt)((AIntList) 0);
793 fvs->lastStmt = -3;
794 fvs->temps = daThisFlog->prog->foamProg.locals;
795
796 /* Mark initially killed variables as free */
797 for(tblITER(it,trKillTbl)_tblITER(&(it), trKillTbl); tblMORE(it)((it).curr <= (it).last); tblSTEP(it)((((it).link=(it).link->next))==0 ? _tblSTEP(&(it)) : 1
)) {
798 AInt id = (AInt) tblKEY(it)((it).link->key);
799 if (!bitvTest(daBitvClass, dfRevIn(bb)((bb)->dfinfo->in), id))
800 trAddTemporary(fvs, -2, id);
801 }
802 trCollectNonLocalTemps(fvs, daThisFlog, bb);
803 trAddTemporary(fvs, int0((int) 0), -1);
804
805 trFreeTemps = fvs;
806}
807
808localstatic void
809trCollectNonLocalTemps(FreeTempSet fvs, FlowGraph flog, BBlock bb)
810{
811 BBlock tbb;
812 Bitv lset;
813 int i;
814 /*
815 * Find all locals s.t. bb != thisBB,
816 * and In(bb_i).x == Out(bb_i) == false;
817 */
818 lset = bitvNew(daBitvClass);
819 bitvClearAll(daBitvClass, lset);
820 for (i=0; i<flogBlockC(flog)((flog)->blocks->pos); i++) {
821 tbb = flogBlock(flog, i)bbufBlockFn((flog)->blocks,i);
822 if (!tbb || bb == tbb) continue;
823
824 bitvOr(daBitvClass, lset, dfRevIn(tbb)((tbb)->dfinfo->in), lset);
825 bitvOr(daBitvClass, lset, dfRevOut(tbb)((tbb)->dfinfo->exit[0].out), lset);
826 }
827
828 for (i=0; i<bitvClassSize(daBitvClass)((daBitvClass)->nbits); i++) {
829 if (!bitvTest(daBitvClass, lset, i))
830 trAddTemporary(fvs, -1, (AInt) i);
831 }
832}
833
834localstatic void
835trFillSetsExpr(int stmtId, Foam foam)
836{
837 AIntList ids;
838 AInt loc;
839
840 switch (foamTag(foam)((foam)->hdr.tag)) {
841 case FOAM_Set:
842 case FOAM_Def:
843 trFillKillSet(stmtId, foam->foamDef.lhs);
844 foam = foam->foamDef.rhs;
845 default:
846 break;
847 }
848
849 foamIter(foam, arg, trFillSetsExpr(stmtId, *arg)){ { String argf = (foamInfoTable [(int)(((foam)->hdr.tag))
-(int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((foam
)->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if
(*argf == 'C') { Foam *arg = (Foam *) ((foam)->foamGen.argv
)+_i; { trFillSetsExpr(stmtId, *arg); }; } } }; };
850
851
852 if (foamTag(foam)((foam)->hdr.tag) != FOAM_Loc)
853 return;
854
855 loc = foam->foamLoc.index;
856
857 ids = (AIntList) tblElt(trUseTbl, (TblKey) loc, listNil(AInt)((AIntList) 0));
858
859 tblSetElt(trUseTbl, (TblKey) loc,
860 (TblElt) listCons(AInt)(AInt_listPointer->Cons)(stmtId, ids));
861}
862
863localstatic void
864trFillKillSet(int stmtId, Foam foam)
865{
866 Foam *argv;
867 AIntList ids;
868 AInt loc;
869 int i, argc;
870
871 switch (foamTag(foam)((foam)->hdr.tag)) {
872 case FOAM_Values:
873 argv = foam->foamValues.argv;
874 argc = foamArgc(foam)((foam)->hdr.argc);
875 break;
876 default:
877 argv = &foam;
878 argc = 1;
879 }
880
881 for (i = 0; i<argc; i++) {
882 if (foamTag(argv[i])((argv[i])->hdr.tag) != FOAM_Loc)
883 trFillSetsExpr(stmtId, argv[i]);
884 else {
885 loc = argv[i]->foamLoc.index;
886 ids = (AIntList) tblElt(trKillTbl, (TblElt)loc,
887 listNil(AInt)((AIntList) 0));
888 tblSetElt(trKillTbl, (TblKey) loc,
889 (TblElt) listCons(AInt)(AInt_listPointer->Cons)(stmtId, ids));
890 }
891 }
892}
893
894localstatic void
895trFiniTempSets()
896{
897
898}
899
900
901localstatic AIntList
902trKillEventsAfter(int stmt, AInt id)
903{
904 AIntList kills;
905 kills = (AIntList) tblElt(trKillTbl, (TblKey) id,
906 (TblElt) listNil(AInt)((AIntList) 0));
907 return trEventsAfter(stmt, kills);
908}
909
910localstatic AIntList
911trUseEventsAfter(int stmt, AInt id)
912{
913 AIntList uses;
914 uses = (AIntList) tblElt(trUseTbl, (TblKey) id,
915 (TblElt) listNil(AInt)((AIntList) 0));
916
917 uses = trEventsAfter(stmt, uses);
918 return uses;
919}
920
921
922localstatic AIntList
923trEventsAfter(int id, AIntList l)
924{
925 while (l && car(l)((l)->first) < (AInt) id)
926 l = cdr(l)((l)->rest);
927 return l;
928}
929
930/****************************************************************************
931 *
932 * Live variables
933 *
934 ****************************************************************************/
935
936CREATE_LIST(LiveInfo)struct LiveInfo_listOpsStruct const *LiveInfo_listPointer = (
struct LiveInfo_listOpsStruct const *) &ptrlistOps;
937
938localstatic LiveInfoList
939daAddLiveChanges(LiveInfoList lst, int stmt, Bitv bitv)
940{
941 LiveInfo info;
942
943 if (lst != listNil(LiveInfo)((LiveInfoList) 0)
944 && bitvEqual(daBitvClass, car(lst)((lst)->first)->live, bitv))
945 return lst;
946
947 info = (LiveInfo) stoAlloc(OB_Other0, sizeof(*info));
948 info->stmtId = stmt;
949 info->live = bitvNew(daBitvClass);
950 bitvCopy(daBitvClass, info->live, bitv);
951
952 return listCons(LiveInfo)(LiveInfo_listPointer->Cons)(info, lst);
953}
954
955localstatic LiveVars
956daMakeInitLiveVars(FlowGraph flog)
957{
958 LiveVars vars = (LiveVars) stoAlloc(OB_Other0, sizeof(*vars));
959 vars->bvClass = NULL((void*)0);
960 vars->vars = (LiveInfoList*)
961 stoAlloc(OB_Other0, flogBlockC(flog)((flog)->blocks->pos)*sizeof(LiveInfoList));
962
963 return vars;
964}
965
966Bitv
967daGetLiveVars(BBlock bb, LiveVars vars, int stmt)
968{
969 LiveInfoList lst = vars->vars[bb->label];
970 Bitv bits = NULL((void*)0);
971
972 assert(lst)do { if (!(lst)) _do_assert(("lst"),"of_deada.c",972); } while
(0);
973 while (stmt < car(lst)((lst)->first)->stmtId) {
974 bits = car(lst)((lst)->first)->live;
975 lst = cdr(lst)((lst)->rest);
976 }
977 return bits;
978}
979
980void
981daKillLiveVars(LiveVars vars)
982{
983}
984