Bug Summary

File:src/of_killp.c
Warning:line 224, column 2
Value stored to 'locals' 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_killp.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_killp.c
1/*****************************************************************************
2 *
3 * of_killp.c: Pointer crushing
4 *
5 * Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
6 *
7 ****************************************************************************/
8
9/*
10 ****************************************************************************
11 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
12 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
13 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
14 ****************************************************************************
15 * This code is still quite buggy and seems to interfere with TextWriter
16 * output. Compiling the test suite with -Qkillp highlights tests that
17 * fail with this enabled. It was written as a quick experiment and ought
18 * not to be used for serious work. At the moment it can only be enabled
19 * by explicitly typing -Qkillp: don't allow it to be included when the
20 * user types -Q4 or something similar.
21 ****************************************************************************
22 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
23 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
24 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
25 ****************************************************************************
26 *
27 * Pointer crushing: ensure that temporaries are reset to a neutral
28 * value after their last use. This prevents the GC from using them
29 * as roots because it doesn't know any better.
30 *
31 * Refer to of_deada.c for more details - most of this code is
32 * exactly the same as in that file (that's where it came from ;)
33 *
34 * We apply the following algorithm to each prog in turn: flatten
35 * the prog so that the arguments to all eligible calls are either
36 * literals or variables. Then we dataflow to identify killable
37 * references before generating the kills. Eligible calls are those
38 * which are top-level calls and those on the RHS of a Set.
39 *
40 * To do:
41 * - Only flatten calls which contain killable references. An initial
42 * dataflow pass is required for this.
43 * - Consider LHS of Sets: deal with (Values)
44 * - Consider If, Repeat etc.
45 */
46
47#include "axlobs.h"
48#include "debug.h"
49#include "dflow.h"
50#include "flog.h"
51#include "format.h"
52#include "of_deada.h"
53#include "of_killp.h"
54#include "of_util.h"
55#include "opttools.h"
56#include "optfoam.h"
57#include "syme.h"
58#include "table.h"
59#include "strops.h"
60
61Bool kpDebug = false((int) 0);
62
63#define kpDEBUGif (!kpDebug) { } else afprintf DEBUG_IF(kp)if (!kpDebug) { } else afprintf
64
65/****************************************************************************
66 *
67 * Type definitions
68 *
69 ****************************************************************************/
70
71/****************************************************************************
72 *
73 * Global Data Structures
74 *
75 ****************************************************************************/
76
77static int kpFlogCutOff = 700;
78
79static BitvClass kpBitvClass;
80static FlowGraph kpThisFlog;
81
82static Table kpKillTbl;
83static Table kpUseTbl;
84static Bitv kpLive;
85static Bitv kpOut;
86
87/****************************************************************************
88 *
89 * Local declarations
90 *
91 ****************************************************************************/
92
93localstatic Foam kpProg (Foam);
94localstatic Bool kpFlog0 (int, FlowGraph);
95localstatic void kpFillDefRef (FlowGraph, BBlock);
96localstatic void kpFillStmt (Foam, BBlock);
97localstatic void kpFillExpr (Foam, BBlock);
98localstatic void kpFixBBlock (BBlock);
99localstatic void kpFixSet (Bitv, Foam);
100localstatic void kpFixExpr (Bitv, Foam);
101
102localstatic void kpKillBBlock (BBlock);
103localstatic void kpProcessExpr (int, Foam);
104localstatic void kpProcessSet (int, Foam);
105localstatic void kpMarkAsDead (Foam, int);
106localstatic AIntList kpKillEventsAfter (int, AInt);
107localstatic AIntList kpUseEventsAfter (int, AInt);
108localstatic AIntList kpEventsAfter (int, AIntList l);
109
110localstatic void kpInitTempSets (BBlock);
111localstatic void kpFillSetsExpr (int, Foam);
112localstatic void kpFillKillSet (int, Foam);
113localstatic void kpFiniTempSets (void);
114
115localstatic void kpPreprocessProg (Foam);
116localstatic void kpPostprocessProg (Foam);
117
118localstatic int kpBitvSize (Foam prog);
119localstatic int kpBitvIndex (Foam foam);
120
121/****************************************************************************
122 *
123 * :: External functions
124 *
125 ****************************************************************************/
126
127void
128kpSetCutOff(int n)
129{
130 kpFlogCutOff = n;
131}
132
133void
134killPointers(Foam unit)
135{
136 Foam ddef, def, rhs;
137 int i;
138 Length conc;
139 Foam *conv;
140 DEBUG_DECL(Foam lhs)Foam lhs;
141 DEBUG_DECL(int j)int j;
142 DEBUG_DECL(String progName)String progName;
143
144 conc = foamDDeclArgc(foamUnitConstants(unit))(((((((unit)->foamUnit.formats)->foamGen.argv)[1].code)
)->hdr.argc) - (1));
145 conv = foamUnitConstants(unit)((((unit)->foamUnit.formats)->foamGen.argv)[1].code)->foamDDecl.argv;
146
147 ddef = unit->foamUnit.defs;
148 for (i = 0; i<foamArgc(ddef)((ddef)->hdr.argc); i++) {
149 def = ddef->foamDDef.argv[i];
150 assert(foamTag(def) == FOAM_Def)do { if (!(((def)->hdr.tag) == FOAM_Def)) _do_assert(("foamTag(def) == FOAM_Def"
),"of_killp.c",150); } while (0);
151
152 if (DEBUG(kp)kpDebug) {
153 lhs = def->foamDef.lhs;
154 j = lhs->foamConst.index;
155 if (j < conc)
156 progName = conv[j]->foamDecl.id;
157 else
158 progName = "???";
159 fprintf(dbOut, "Function: %s\n", progName);
160 }
161
162 rhs = def->foamDef.rhs;
163 if (foamTag(rhs)((rhs)->hdr.tag) == FOAM_Prog)
164 def->foamDef.rhs = kpProg(rhs);
165 }
166 assert(foamAudit(unit))do { if (!(foamAudit(unit))) _do_assert(("foamAudit(unit)"),"of_killp.c"
,166); } while (0);
167}
168
169void
170killProgPointers(Foam prog)
171{
172 assert(foamTag(prog) == FOAM_Prog)do { if (!(((prog)->hdr.tag) == FOAM_Prog)) _do_assert(("foamTag(prog) == FOAM_Prog"
),"of_killp.c",172); } while (0);
173 kpDEBUGif (!kpDebug) { } else afprintf(dbOut, "Function: %s\n", "<unknown>");
174 kpProg(prog);
175}
176
177/****************************************************************************
178 *
179 * :: Simple accessors
180 *
181 ****************************************************************************/
182
183localstatic int
184kpBitvSize(Foam prog)
185{
186 return foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1))
187 + foamDDeclArgc(prog->foamProg.params)(((prog->foamProg.params)->hdr.argc) - (1));
188}
189
190localstatic int
191kpBitvIndex(Foam foam)
192{
193 switch (foamTag(foam)((foam)->hdr.tag)) {
194 case FOAM_Loc:
195 return foam->foamLoc.index;
196 case FOAM_Par:
197 return foam->foamPar.index +
198 foamDDeclArgc(kpThisFlog->prog->foamProg.locals)(((kpThisFlog->prog->foamProg.locals)->hdr.argc) - (
1));
199 default:
200 return -1;
201 }
202}
203
204/****************************************************************************
205 *
206 * Compute and kill...
207 *
208 ****************************************************************************/
209
210localstatic Foam
211kpProg(Foam prog)
212{
213 FlowGraph flog;
214 Foam locals, ret;
215 int nbits;
216
217 if (DEBUG(kp)kpDebug) {
218 fprintf(dbOut, "--> Before:\n");
219 foamWrSExpr(dbOut, prog,int0((int) 0));
220 }
221
222 kpPreprocessProg(prog);
223
224 locals = prog->foamProg.locals;
Value stored to 'locals' is never read
225
226 nbits = kpBitvSize(prog);
227
228 if (!nbits) return prog;
229
230 flog = flogFrProg(prog, FLOG_UniqueExit);
231
232 kpFlog0(nbits, flog);
233
234 ret = flogToProg(flog);
235 kpPostprocessProg(ret);
236
237 if (DEBUG(kp)kpDebug) {
238 fprintf(dbOut, "<-- After:\n");
239 foamWrSExpr(dbOut, ret,int0((int) 0));
240 fnewline(dbOut);
241 }
242 kpBitvClass = NULL((void*)0);
243 return ret;
244}
245
246localstatic Bool
247kpFlog0(int nLocals, FlowGraph flog)
248{
249 BBlock bb;
250 int i, count;
251
252 kpBitvClass = bitvClassCreate(nLocals);
253 flogBitvClass(flog)((flog)->bitvClass) = kpBitvClass;
254 kpThisFlog = flog;
255
256 for (i=0; i<flogBlockC(flog)((flog)->blocks->pos); i++) {
257 bb = flogBlock(flog, i)bbufBlockFn((flog)->blocks,i);
258 dflowNewBlockInfo(bb, nLocals, kpFillDefRef);
259 }
260
261 i = dflowRevIterate(flog, DFLOW_Union, kpFlogCutOff, &count, NULL((void*)0));
262
263 if (i != 0)
264 return false((int) 0);
265
266 for (i=0; i<flogBlockC(flog)((flog)->blocks->pos); i++) {
267 if (!flogBlock(flog,i)bbufBlockFn((flog)->blocks,i)) continue;
268 kpFixBBlock(flogBlock(flog, i)bbufBlockFn((flog)->blocks,i));
269 }
270
271 kpThisFlog = NULL((void*)0);
272 return true1;
273}
274
275localstatic void
276kpFillDefRef(FlowGraph flog, BBlock bb)
277{
278 Foam seq = bb->code;
279 Foam stmt;
280 BitvClass class = flogBitvClass(flog)((flog)->bitvClass);
281 int i;
282
283 /* clear the vectors */
284 bitvClearAll(class, dfRevKill(bb)((bb)->dfinfo->exit[0].kill));
285 bitvClearAll(class, dfRevGen(bb)((bb)->dfinfo->gen));
286
287 for (i=0; i<foamArgc(seq)((seq)->hdr.argc); i++) {
288 stmt = seq->foamSeq.argv[i];
289 kpFillStmt(stmt, bb);
290 }
291}
292
293localstatic void
294kpFillStmt(Foam stmt, BBlock bb)
295{
296 Foam *argv;
297 int idx, argc, i;
298
299 if (!otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) {
300 kpFillExpr(stmt, bb);
301 return;
302 }
303
304 kpFillExpr(stmt->foamSet.rhs, bb);
305
306 switch(foamTag(stmt->foamSet.lhs)((stmt->foamSet.lhs)->hdr.tag)) {
307 case FOAM_Values:
308 argv = stmt->foamSet.lhs->foamValues.argv;
309 argc = foamArgc(stmt->foamSet.lhs)((stmt->foamSet.lhs)->hdr.argc);
310 break;
311 default:
312 argv = &stmt->foamSet.lhs;
313 argc = 1;
314 break;
315 }
316
317 for (i=0; i<argc; i++) {
318 idx = kpBitvIndex(argv[i]);
319 if (idx != -1) {
320 if (!bitvTest(kpBitvClass, dfRevGen(bb)((bb)->dfinfo->gen), idx))
321 bitvSet(kpBitvClass, dfRevKill(bb)((bb)->dfinfo->exit[0].kill), idx);
322 } else
323 kpFillExpr(argv[i], bb);
324 }
325}
326
327localstatic void
328kpFillExpr(Foam foam, BBlock bb)
329{
330 int idx;
331
332 idx = kpBitvIndex(foam);
333 if (idx != -1) {
334 if (!bitvTest(kpBitvClass, dfRevKill(bb)((bb)->dfinfo->exit[0].kill), idx))
335 bitvSet(kpBitvClass, dfRevGen(bb)((bb)->dfinfo->gen), idx);
336 }
337 else
338 foamIter(foam, arg, kpFillExpr(*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; { kpFillExpr(*arg, bb); }; } } }; };
339}
340
341localstatic void
342kpFixBBlock(BBlock bb)
343{
344 Foam seq = bb->code;
345 Foam stmt;
346 Bitv bitv;
347 int i;
348
349 /* Do dataflow by hand backwards through the BB */
350 /* Start with the 'out' set and work upwards */
351 /* when complete, out will be a subset of "in" */
352 if (DEBUG(kp)kpDebug) {
353 fprintf(dbOut, "(Fixing: Out\n");
354 bitvPrint(dbOut, kpBitvClass, dfRevOut(bb)((bb)->dfinfo->exit[0].out));
355 fprintf(dbOut, "\nIn\n");
356 bitvPrint(dbOut, kpBitvClass, dfRevIn(bb)((bb)->dfinfo->in));
357 fprintf(dbOut, "\nFoam\n");
358 foamWrSExpr(dbOut, seq, int0((int) 0));
359 }
360 bitv = bitvNew(kpBitvClass);
361 bitvCopy(kpBitvClass, bitv, dfRevOut(bb)((bb)->dfinfo->exit[0].out));
362
363 for (i=foamArgc(seq)((seq)->hdr.argc) - 1; i >= 0 ; i--) {
364 stmt = seq->foamSeq.argv[i];
365
366 if (otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
))
367 kpFixSet(bitv, stmt);
368 else
369 kpFixExpr(bitv, stmt);
370 }
371
372 /*
373 * This is the part that we have been waiting for. All
374 * the stuff before this call is to compute whether or
375 * not locals are live at the BB entry and exit.
376 */
377 kpKillBBlock(bb);
378
379 if (DEBUG(kp)kpDebug) {
380 bitvPrint(dbOut, kpBitvClass, bitv);
381 fprintf(dbOut, "\nDone fix)\n");
382 }
383
384}
385
386localstatic void
387kpFixSet(Bitv bitv, Foam set)
388{
389 Foam lhs = set->foamSet.lhs;
390 Foam rhs = set->foamSet.rhs;
391 Foam *argv;
392 int argc;
393 Bool isLive;
394 int i, idx;
395
396 switch(foamTag(lhs)((lhs)->hdr.tag)) {
397 case FOAM_Values:
398 argv = lhs->foamValues.argv;
399 argc = foamArgc(lhs)((lhs)->hdr.argc);
400 break;
401 default:
402 argv = &lhs;
403 argc = 1;
404 break;
405 }
406
407 isLive = false((int) 0);
408 for (i=0; i<argc; i++) {
409 idx = kpBitvIndex(argv[i]);
410 if (idx == -1) {
411 isLive = true1;
412 kpFixExpr(bitv, argv[i]);
413 }
414 else {
415 isLive |= bitvTest(kpBitvClass, bitv, idx);
416 bitvClear(kpBitvClass, bitv, idx);
417 }
418 }
419
420 if (isLive || (foamTag(rhs)((rhs)->hdr.tag) == FOAM_MFmt))
421 kpFixExpr(bitv, rhs);
422 else
423 {
424 if (foamHasSideEffect(rhs))
425 kpFixExpr(bitv, rhs);
426 }
427}
428
429localstatic void
430kpFixExpr(Bitv bitv, Foam expr)
431{
432 int idx;
433
434 idx = kpBitvIndex(expr);
435 if (idx != -1)
436 bitvSet(kpBitvClass, bitv, idx);
437 else
438 foamIter(expr, arg, kpFixExpr(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; { kpFixExpr(bitv, *arg); }; } } }; };
439}
440
441
442/****************************************************************************
443 *
444 * The core of the optimisation: determine which locals are dead.
445 *
446 ****************************************************************************/
447
448localstatic void
449kpKillBBlock(BBlock bb)
450{
451 Foam seq, stmt;
452 int i;
453
454 /* Compute uses and kills of all locals */
455 kpInitTempSets(bb);
456
457
458 seq = bb->code;
459 for (i=0; i<foamArgc(seq)((seq)->hdr.argc); i++) {
460 stmt = seq->foamSeq.argv[i];
461
462 switch (foamTag(stmt)((stmt)->hdr.tag)) {
463 case FOAM_Def:
464 case FOAM_Set:
465 kpProcessSet(i, stmt);
466 break;
467 default:
468 kpProcessExpr(i, stmt);
469 }
470 }
471
472 kpFiniTempSets();
473}
474
475localstatic void
476kpProcessExpr(int stmtId, Foam expr)
477{
478 AIntList kills, uses;
479 Bool liveAfter;
480 int id;
481
482 foamIter(expr, arg, kpProcessExpr(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; { kpProcessExpr(stmtId, *arg); }; } } }; };
483
484 if (foamTag(expr)((expr)->hdr.tag) != FOAM_Loc) return;
485
486 id = kpBitvIndex(expr);
487
488 if (bitvTest(kpBitvClass, kpLive, id))
489 {
490 /* Determine if this is the last use of this local */
491 uses = kpUseEventsAfter(stmtId + 1, id);
492 kills = kpKillEventsAfter(stmtId, id);
493
494 liveAfter = bitvTest(kpBitvClass, kpOut, id);
495
496 kpDEBUGif (!kpDebug) { } else afprintf(dbOut,
497 "Checking %d var: %d next use: %d next kill: %d used later: %s\n",
498 stmtId, id,
499 uses ? (int)car(uses)((uses)->first): 999999,
500 kills ? (int)car(kills)((kills)->first): 999999,
501 liveAfter ? "Yes" : "No");
502
503 if (!uses && !liveAfter)
504 kpMarkAsDead(expr, id);
505 else if (uses && kills && (car(uses)((uses)->first) > car(kills)((kills)->first)))
506 kpMarkAsDead(expr, id);
507 }
508}
509
510localstatic void
511kpProcessSet(int stmtId, Foam set)
512{
513 AInt id;
514 Foam lhs = set->foamSet.lhs;
515 Foam rhs = set->foamSet.rhs;
516
517 kpProcessExpr(stmtId, rhs);
518
519 if (foamTag(lhs)((lhs)->hdr.tag) == FOAM_Loc)
520 {
521 /* Mark as live (could tighten this up) */
522 id = lhs->foamLoc.index;
523 bitvSet(kpBitvClass, kpLive, id);
524 }
525 else
526 kpProcessExpr(stmtId, lhs);
527}
528
529localstatic void
530kpMarkAsDead(Foam foam, int id)
531{
532 foamDvMark(foam)((foam)->hdr.dvMark) = 1;
533 bitvClear(kpBitvClass, kpLive, id);
534 if (DEBUG(kp)kpDebug) {
535 fprintf(dbOut, " Killable: ");
536 foamPrintDb(foam);
537 }
538}
539
540localstatic AIntList
541kpKillEventsAfter(int stmt, AInt id)
542{
543 AIntList kills;
544 kills = (AIntList) tblElt(kpKillTbl, (TblKey) id,
545 (TblElt) listNil(AInt)((AIntList) 0));
546 return kpEventsAfter(stmt, kills);
547}
548
549localstatic AIntList
550kpUseEventsAfter(int stmt, AInt id)
551{
552 AIntList uses;
553 uses = (AIntList) tblElt(kpUseTbl, (TblKey) id,
554 (TblElt) listNil(AInt)((AIntList) 0));
555
556 uses = kpEventsAfter(stmt, uses);
557 return uses;
558}
559
560
561localstatic AIntList
562kpEventsAfter(int id, AIntList l)
563{
564 while (l && car(l)((l)->first) < (AInt) id)
565 l = cdr(l)((l)->rest);
566 return l;
567}
568
569/****************************************************************************
570 *
571 * Pre- and post-processing of FOAM progs
572 *
573 ****************************************************************************/
574
575localstatic FoamList kpFlattenSetOrDef(Foam);
576/* local FoamList kpFlattenBCall(Foam); */
577localstatic FoamList kpFlattenCCall(Foam);
578localstatic FoamList kpFlattenOCall(Foam);
579localstatic FoamList kpFlattenPCall(Foam);
580localstatic FoamList kpFlattenCall(int, Foam *);
581localstatic FoamList kpFlattenReturn(Foam);
582localstatic FoamList kpKillsForSetOrDef(Foam);
583/* local FoamList kpKillsForBCall(Foam); */
584localstatic FoamList kpKillsForCCall(Foam);
585localstatic FoamList kpKillsForOCall(Foam);
586localstatic FoamList kpKillsForPCall(Foam);
587localstatic FoamList kpKillsForCall(int, Foam *);
588localstatic Foam kpNewTemporary(AInt);
589
590static AInt kpNextTemp;
591static AIntList kpTemporaries;
592
593localstatic void
594kpPreprocessProg(Foam prog)
595{
596 /*
597 * Flatten calls and strip out any existing Kills - they were
598 * probably put there by us during a previous pass over the
599 * FOAM and don't want to have an explosion of them.
600 * Notes: *Calls might be buried inside casts ...
601 */
602 AInt i, ntemps;
603 Foam foam = prog->foamProg.body;
604 Length locc, parc;
605 Foam *locv, *parv;
606 FoamList seqbody, extra;
607
608 assert(foamTag(foam) == FOAM_Seq)do { if (!(((foam)->hdr.tag) == FOAM_Seq)) _do_assert(("foamTag(foam) == FOAM_Seq"
),"of_killp.c",608); } while (0);
609
610 locc = foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1));
611 locv = prog->foamProg.locals->foamDDecl.argv;
612
613 parc = foamDDeclArgc(prog->foamProg.params)(((prog->foamProg.params)->hdr.argc) - (1));
614 parv = prog->foamProg.params->foamDDecl.argv;
615
616 /* Prepare the way of the addition of new locals */
617 /* !!! Will use fbox when we figure out what it does */
618 kpNextTemp = locc;
619 kpTemporaries = listNil(AInt)((AIntList) 0);
620
621
622 /* Start with an empty list of statements */
623 seqbody = listNil(Foam)((FoamList) 0);
624
625
626 if (DEBUG(kp)kpDebug) {
627 fprintf(dbOut, "------------------------ (before flattening) --------------------\n");
628 foamPrintDb(foam);
629 fprintf(dbOut, "-----------------------------------------------------------------\n\n");
630 }
631
632 /* Construct a new sequence based on the original */
633 for (i = 0;i < foamArgc(foam)((foam)->hdr.argc); i++)
634 {
635 Foam stmt = foam->foamSeq.argv[i];
636
637 switch (foamTag(stmt)((stmt)->hdr.tag))
638 {
639 case FOAM_Def:
640 /* Fall through */
641 case FOAM_Set:
642 extra = kpFlattenSetOrDef(stmt);
643 break;
644/***************************************
645 case FOAM_BCall:
646 extra = kpFlattenBCall(stmt);
647 break;
648 ***************************************/
649 case FOAM_CCall:
650 extra = kpFlattenCCall(stmt);
651 break;
652 case FOAM_OCall:
653 extra = kpFlattenOCall(stmt);
654 break;
655 case FOAM_PCall:
656 extra = kpFlattenPCall(stmt);
657 break;
658 case FOAM_Return:
659 extra = kpFlattenReturn(stmt);
660 break;
661 case FOAM_Loose:
662 stmt = foamNewNOp()foamNew(FOAM_NOp, (int) 0);
663 /* Fall through */
664 default:
665 seqbody = listCons(Foam)(Foam_listPointer->Cons)(stmt, seqbody);
666 continue;
667 }
668
669
670 /* Add in the extra statements (if any) */
671 seqbody = listNConcat(Foam)(Foam_listPointer->NConcat)(extra, seqbody);
672
673
674 /* Add in the original statement */
675 seqbody = listCons(Foam)(Foam_listPointer->Cons)(stmt, seqbody);
676 }
677
678
679 /* Put the statements back in the correct order */
680 seqbody = listNReverse(Foam)(Foam_listPointer->NReverse)(seqbody);
681
682
683 /* Create a new sequence */
684 foam = foamNewOfList(FOAM_Seq, seqbody);
685
686
687 if (DEBUG(kp)kpDebug) {
688 fprintf(dbOut, "----------------------- (after flattening) ----------------------\n");
689 foamPrintDb(foam);
690 fprintf(dbOut, "-----------------------------------------------------------------\n\n");
691 }
692
693
694 /* Release our temporary storage */
695 listFree(Foam)(Foam_listPointer->Free)(seqbody);
696
697
698 /* Update the prog with its new body */
699 prog->foamProg.body = foam;
700
701
702 /* Now deal with the addition of new locals (if any) */
703 ntemps = listLength(AInt)(AInt_listPointer->_Length)(kpTemporaries);
704 if (ntemps)
705 {
706 Foam ddecl = foamNewEmpty(FOAM_DDecl, 1 + locc + ntemps);
707
708
709 /* Define the usage of these declarations */
710 ddecl->foamDDecl.usage = FOAM_DDecl_Local;
711
712
713 /* Copy over the existing locals */
714 for (i = 0;i < locc; i++)
715 ddecl->foamDDecl.argv[i] = locv[i];
716
717
718 /* Put the new locals in the correct order */
719 kpTemporaries = listNReverse(AInt)(AInt_listPointer->NReverse)(kpTemporaries);
720
721
722 /* Add in the new locals */
723 i = locc;
724 listIter(AInt, type, kpTemporaries, {{ { AIntList _l0; AInt type; for (_l0 = (kpTemporaries); _l0;
_l0 = ((_l0)->rest)) { type = ((_l0)->first); { { String
id = strCopy(""); Foam decl = foamNew(FOAM_Decl,4,(AInt)(type
),id, (AInt) (0x7FFF), 4); ddecl->foamDDecl.argv[i++] = decl
; }; }; } }; }
725 String id = strCopy("");{ { AIntList _l0; AInt type; for (_l0 = (kpTemporaries); _l0;
_l0 = ((_l0)->rest)) { type = ((_l0)->first); { { String
id = strCopy(""); Foam decl = foamNew(FOAM_Decl,4,(AInt)(type
),id, (AInt) (0x7FFF), 4); ddecl->foamDDecl.argv[i++] = decl
; }; }; } }; }
726 Foam decl = foamNewDecl(type, id, emptyFormatSlot);{ { AIntList _l0; AInt type; for (_l0 = (kpTemporaries); _l0;
_l0 = ((_l0)->rest)) { type = ((_l0)->first); { { String
id = strCopy(""); Foam decl = foamNew(FOAM_Decl,4,(AInt)(type
),id, (AInt) (0x7FFF), 4); ddecl->foamDDecl.argv[i++] = decl
; }; }; } }; }
727
728 ddecl->foamDDecl.argv[i++] = decl;{ { AIntList _l0; AInt type; for (_l0 = (kpTemporaries); _l0;
_l0 = ((_l0)->rest)) { type = ((_l0)->first); { { String
id = strCopy(""); Foam decl = foamNew(FOAM_Decl,4,(AInt)(type
),id, (AInt) (0x7FFF), 4); ddecl->foamDDecl.argv[i++] = decl
; }; }; } }; }
729 }){ { AIntList _l0; AInt type; for (_l0 = (kpTemporaries); _l0;
_l0 = ((_l0)->rest)) { type = ((_l0)->first); { { String
id = strCopy(""); Foam decl = foamNew(FOAM_Decl,4,(AInt)(type
),id, (AInt) (0x7FFF), 4); ddecl->foamDDecl.argv[i++] = decl
; }; }; } }; };
730
731
732 /* Replace the existing locals declaration */
733 prog->foamProg.locals = ddecl;
734 }
735}
736
737localstatic FoamList
738kpFlattenSetOrDef(Foam foam)
739{
740 Foam rhs = foam->foamSet.rhs; /* Assumes Def/Set are similar */
741
742 /* Skip past any casts */
743 while (foamTag(rhs)((rhs)->hdr.tag) == FOAM_Cast)
744 rhs = rhs->foamCast.expr;
745
746 switch (foamTag(rhs)((rhs)->hdr.tag))
747 {
748/***************************************
749 case FOAM_BCall:
750 return kpFlattenBCall(rhs);
751 ***************************************/
752 case FOAM_CCall:
753 return kpFlattenCCall(rhs);
754 case FOAM_OCall:
755 return kpFlattenOCall(rhs);
756 case FOAM_PCall:
757 return kpFlattenPCall(rhs);
758 default:
759 break;
760 }
761
762 return listNil(Foam)((FoamList) 0);
763}
764
765
766#if 0
767localstatic FoamList
768kpFlattenBCall(Foam call)
769{
770 int argc = foamArgc(call)((call)->hdr.argc) - 1;
771 Foam *argv = call->foamBCall.argv;
772
773 return kpFlattenCall(argc, argv);
774}
775#endif
776
777localstatic FoamList
778kpFlattenCCall(Foam call)
779{
780 int argc = foamArgc(call)((call)->hdr.argc) - 2;
781 Foam *argv = call->foamCCall.argv;
782
783 return kpFlattenCall(argc, argv);
784}
785
786localstatic FoamList
787kpFlattenOCall(Foam call)
788{
789 int argc = foamArgc(call)((call)->hdr.argc) - 3;
790 Foam *argv = call->foamOCall.argv;
791
792 return kpFlattenCall(argc, argv);
793}
794
795localstatic FoamList
796kpFlattenPCall(Foam call)
797{
798 int argc = foamArgc(call)((call)->hdr.argc) - 3;
799 Foam *argv = call->foamPCall.argv;
800
801 return kpFlattenCall(argc, argv);
802}
803
804localstatic FoamList
805kpFlattenCall(int argc, Foam argv[])
806{
807 int i;
808 AInt type;
809 Foam tmp, set;
810 FoamList extra, result = listNil(Foam)((FoamList) 0);
811
812 for (i = 0; i < argc; i++)
813 {
814 Foam *slot = &argv[i];
815 Foam arg = *slot;
816
817
818 /* Skip past any casts */
819 while (foamTag(arg)((arg)->hdr.tag) == FOAM_Cast)
820 {
821 slot = &(arg->foamCast.expr);
822 arg = *slot;
823 }
824
825 switch (foamTag(arg)((arg)->hdr.tag))
826 {
827/***************************************
828 case FOAM_BCall:
829 extra = kpFlattenBCall(arg);
830 type = (AInt)(foamBValRetType(arg->foamBCall.op));
831 break;
832 ***************************************/
833 case FOAM_CCall:
834 extra = kpFlattenCCall(arg);
835 type = arg->foamCCall.type;
836 break;
837 case FOAM_OCall:
838 extra = kpFlattenOCall(arg);
839 type = arg->foamCCall.type;
840 break;
841 case FOAM_PCall:
842 extra = kpFlattenPCall(arg);
843 type = arg->foamCCall.type;
844 break;
845 default:
846 /* Ignored - try next argument */
847 continue;
848 }
849
850
851 /* Extra statements to add to our list? */
852 if (extra)
853 result = listNConcat(Foam)(Foam_listPointer->NConcat)(extra, result);
854
855
856 /* Create a temporary for the result of this call */
857 tmp = kpNewTemporary(type);
858
859
860 /* Create the set for the call */
861 set = foamNewSet(tmp, arg)foamNew(FOAM_Set, 2, tmp, arg);
862
863
864 /* Add to the list of statements */
865 result = listCons(Foam)(Foam_listPointer->Cons)(set, result);
866
867
868 /* Replace the call site with the temporary */
869 /* argv[i] = foamCopy(tmp); */
870 *slot = foamCopy(tmp);
871 }
872
873 return result;
874}
875
876localstatic FoamList
877kpFlattenReturn(Foam ret)
878{
879 Foam foam = ret->foamReturn.value;
880
881 switch (foamTag(foam)((foam)->hdr.tag))
882 {
883/***************************************
884 case FOAM_BCall:
885 return kpFlattenBCall(foam);
886 ***************************************/
887 case FOAM_CCall:
888 return kpFlattenCCall(foam);
889 case FOAM_OCall:
890 return kpFlattenOCall(foam);
891 case FOAM_PCall:
892 return kpFlattenPCall(foam);
893 default:
894 break;
895 }
896
897 return listNil(Foam)((FoamList) 0);
898}
899
900localstatic void
901kpPostprocessProg(Foam prog)
902{
903 /*
904 * Add Kill instructions where required.
905 *
906 * Things to be aware of:
907 * - locals used in Return are marked as killable. This
908 * means that statements of the form (Return (Loc 0))
909 * must not generate a kill for (Loc 0). However, if
910 * the return value is a call then the arguments to
911 * that call could be killed.
912 * - parameters are not marked as killable yet
913 * - CCalls might be buried inside casts ...
914 */
915 AInt i;
916 Foam foam = prog->foamProg.body;
917 FoamList seqbody, extra;
918
919 assert(foamTag(foam) == FOAM_Seq)do { if (!(((foam)->hdr.tag) == FOAM_Seq)) _do_assert(("foamTag(foam) == FOAM_Seq"
),"of_killp.c",919); } while (0);
920
921
922 /*
923 * Process the flattened sequence for killable locals. Note
924 * that we only examine Set and *Call instructions - any other
925 * type of statement that contained killable references will
926 * have been converted into a Set.
927 */
928 seqbody = listNil(Foam)((FoamList) 0);
929 for (i = 0;i < foamArgc(foam)((foam)->hdr.argc); i++)
930 {
931 Foam stmt = foam->foamSeq.argv[i];
932
933 switch (foamTag(stmt)((stmt)->hdr.tag))
934 {
935 case FOAM_Def:
936 /* Fall through */
937 case FOAM_Set:
938 extra = kpKillsForSetOrDef(stmt);
939 break;
940/***************************************
941 case FOAM_BCall:
942 extra = kpKillsForBCall(stmt);
943 break;
944 ***************************************/
945 case FOAM_CCall:
946 extra = kpKillsForCCall(stmt);
947 break;
948 case FOAM_OCall:
949 extra = kpKillsForOCall(stmt);
950 break;
951 case FOAM_PCall:
952 extra = kpKillsForPCall(stmt);
953 break;
954 default:
955 extra = listNil(Foam)((FoamList) 0);
956 break;
957 }
958
959
960 /* Add the statement */
961 seqbody = listCons(Foam)(Foam_listPointer->Cons)(stmt, seqbody);
962
963
964 /* Add any kills */
965 listIter(Foam, killstmt, extra, {{ { FoamList _l0; Foam killstmt; for (_l0 = (extra); _l0; _l0
= ((_l0)->rest)) { killstmt = ((_l0)->first); { { seqbody
= (Foam_listPointer->Cons)(killstmt, seqbody);}; }; } }; }
966 seqbody = listCons(Foam)(killstmt, seqbody);}){ { FoamList _l0; Foam killstmt; for (_l0 = (extra); _l0; _l0
= ((_l0)->rest)) { killstmt = ((_l0)->first); { { seqbody
= (Foam_listPointer->Cons)(killstmt, seqbody);}; }; } }; };
967 }
968
969
970 /* Put the statements back in the correct order */
971 seqbody = listNReverse(Foam)(Foam_listPointer->NReverse)(seqbody);
972
973
974 /* Create a new sequence */
975 foam = foamNewOfList(FOAM_Seq, seqbody);
976
977
978 if (DEBUG(kp)kpDebug) {
979 fprintf(dbOut, "-------------------------- (after kills) ------------------------\n");
980 foamPrintDb(foam);
981 fprintf(dbOut, "-----------------------------------------------------------------\n\n");
982 }
983
984
985 /* Release our temporary storage */
986 listFree(Foam)(Foam_listPointer->Free)(seqbody);
987
988
989 /* Update the prog with its new body */
990 prog->foamProg.body = foam;
991}
992
993localstatic FoamList
994kpKillsForSetOrDef(Foam foam)
995{
996 Foam rhs = foam->foamSet.rhs; /* Assumes Def/Set are similar */
997
998 /* Skip past any casts */
999 while (foamTag(rhs)((rhs)->hdr.tag) == FOAM_Cast)
1000 rhs = rhs->foamCast.expr;
1001
1002 switch (foamTag(rhs)((rhs)->hdr.tag))
1003 {
1004/***************************************
1005 case FOAM_BCall:
1006 return kpKillsForBCall(rhs);
1007 ***************************************/
1008 case FOAM_CCall:
1009 return kpKillsForCCall(rhs);
1010 case FOAM_OCall:
1011 return kpKillsForOCall(rhs);
1012 case FOAM_PCall:
1013 return kpKillsForPCall(rhs);
1014 case FOAM_Loc:
1015 if (foamDvMark(rhs)((rhs)->hdr.dvMark))
1016 {
1017 Foam tmp = foamNewLoose(foamCopy(rhs))foamNew(FOAM_Loose, 1, foamCopy(rhs));
1018 return listCons(Foam)(Foam_listPointer->Cons)(tmp, listNil(Foam)((FoamList) 0));
1019 }
1020 break;
1021 default:
1022 break;
1023 }
1024
1025 return listNil(Foam)((FoamList) 0);
1026}
1027
1028#if 0
1029localstatic FoamList
1030kpKillsForBCall(Foam call)
1031{
1032 int argc = foamArgc(call)((call)->hdr.argc) - 1;
1033 Foam *argv = call->foamBCall.argv;
1034
1035 return kpKillsForCall(argc, argv);
1036}
1037#endif
1038
1039localstatic FoamList
1040kpKillsForCCall(Foam call)
1041{
1042 int argc = foamArgc(call)((call)->hdr.argc) - 2;
1043 Foam *argv = call->foamCCall.argv;
1044
1045 return kpKillsForCall(argc, argv);
1046}
1047
1048localstatic FoamList
1049kpKillsForOCall(Foam call)
1050{
1051 int argc = foamArgc(call)((call)->hdr.argc) - 3;
1052 Foam *argv = call->foamOCall.argv;
1053
1054 return kpKillsForCall(argc, argv);
1055}
1056
1057localstatic FoamList
1058kpKillsForPCall(Foam call)
1059{
1060 int argc = foamArgc(call)((call)->hdr.argc) - 3;
1061 Foam *argv = call->foamPCall.argv;
1062
1063 return kpKillsForCall(argc, argv);
1064}
1065
1066localstatic FoamList
1067kpKillsForCall(int argc, Foam argv[])
1068{
1069 int i;
1070 FoamList result = listNil(Foam)((FoamList) 0);
1071
1072 for (i = 0;i < argc;i++)
1073 {
1074 Foam tmp, arg = argv[i];
1075
1076 /* Skip past any casts */
1077 while (foamTag(arg)((arg)->hdr.tag) == FOAM_Cast)
1078 arg = arg->foamCast.expr;
1079
1080
1081 /* Only interested in top-level locals */
1082 if (foamTag(arg)((arg)->hdr.tag) != FOAM_Loc) continue;
1083
1084
1085 /* Only interested in killable locals */
1086 if (!foamDvMark(arg)((arg)->hdr.dvMark)) continue;
1087
1088
1089 /* Create a new kill and add to the list */
1090 tmp = foamNewLoose(foamCopy(arg))foamNew(FOAM_Loose, 1, foamCopy(arg));
1091 result = listCons(Foam)(Foam_listPointer->Cons)(tmp, result);
1092 }
1093
1094 /* Return the list of kills at this level */
1095 return result;
1096}
1097
1098localstatic Foam
1099kpNewTemporary(AInt type)
1100{
1101 /* Add the details of this temporary to our database */
1102 kpTemporaries = listCons(AInt)(AInt_listPointer->Cons)(type, kpTemporaries);
1103
1104
1105 /* Return the new temporary */
1106 return foamNewLoc(kpNextTemp++)foamNew(FOAM_Loc, 1, (AInt)(kpNextTemp++));
1107}
1108
1109
1110/****************************************************************************
1111 *
1112 * Initialisation for killing in bblocks
1113 *
1114 ****************************************************************************/
1115
1116localstatic void
1117kpInitTempSets(BBlock bb)
1118{
1119 Foam seq, stmt;
1120 int i;
1121
1122 kpKillTbl = tblNew(NULL((void*)0), NULL((void*)0));
1123 kpUseTbl = tblNew(NULL((void*)0), NULL((void*)0));
1124
1125 seq = bb->code;
1126 /* First find all uses and kills */
1127 for (i=foamArgc(seq)((seq)->hdr.argc)-1; i>=0; i--) {
1128 stmt = seq->foamSeq.argv[i];
1129 kpFillSetsExpr(i, stmt);
1130 }
1131
1132 /* Current live variables */
1133 kpLive = dfRevIn(bb)((bb)->dfinfo->in);
1134 kpOut = dfRevOut(bb)((bb)->dfinfo->exit[0].out);
1135}
1136
1137localstatic void
1138kpFillSetsExpr(int stmtId, Foam foam)
1139{
1140 AIntList ids;
1141 AInt loc;
1142
1143 switch (foamTag(foam)((foam)->hdr.tag)) {
1144 case FOAM_Set:
1145 case FOAM_Def:
1146 kpFillKillSet(stmtId, foam->foamDef.lhs);
1147 foam = foam->foamDef.rhs;
1148 default:
1149 break;
1150 }
1151
1152 foamIter(foam, arg, kpFillSetsExpr(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; { kpFillSetsExpr(stmtId, *arg); }; } } }; };
1153
1154
1155 if (foamTag(foam)((foam)->hdr.tag) != FOAM_Loc)
1156 return;
1157
1158 loc = foam->foamLoc.index;
1159 ids = (AIntList) tblElt(kpUseTbl, (TblKey) loc, listNil(AInt)((AIntList) 0));
1160
1161 tblSetElt(kpUseTbl, (TblKey) loc,
1162 (TblElt) listCons(AInt)(AInt_listPointer->Cons)(stmtId, ids));
1163}
1164
1165localstatic void
1166kpFillKillSet(int stmtId, Foam foam)
1167{
1168 Foam *argv;
1169 AIntList ids;
1170 AInt loc;
1171 int i, argc;
1172
1173 switch (foamTag(foam)((foam)->hdr.tag)) {
1174 case FOAM_Values:
1175 argv = foam->foamValues.argv;
1176 argc = foamArgc(foam)((foam)->hdr.argc);
1177 break;
1178 default:
1179 argv = &foam;
1180 argc = 1;
1181 }
1182
1183 for (i = 0; i<argc; i++) {
1184 if (foamTag(argv[i])((argv[i])->hdr.tag) == FOAM_Loc)
1185 {
1186 loc = argv[i]->foamLoc.index;
1187 ids = (AIntList) tblElt(kpKillTbl, (TblElt)loc,
1188 listNil(AInt)((AIntList) 0));
1189 tblSetElt(kpKillTbl, (TblKey) loc,
1190 (TblElt) listCons(AInt)(AInt_listPointer->Cons)(stmtId, ids));
1191 }
1192 else
1193 kpFillSetsExpr(stmtId, argv[i]);
1194 }
1195}
1196
1197localstatic void
1198kpFiniTempSets()
1199{
1200
1201}
1202