Bug Summary

File:src/of_loops.c
Warning:line 349, column 4
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_loops.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_loops.c
1/*****************************************************************************
2 *
3 * of_loops.c: Loops Optimization
4 *
5 * Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
6 *
7 ****************************************************************************/
8/****************************************************************************
9 *
10 * Open Problems:
11 *
12 * - after a preheader is created, udInfoBlock() must be modified.
13 * Solutions:
14 * a- traverse the flog and check each ud list
15 * -
16 *
17 * - after a preheader is created, there should be a new bit in each
18 * loop->blockSet, and also loop->blockList(s) should be updated.
19 * Solutions:
20 * a- the problem should exist only for nested loops. If loops are
21 * sorted so that external loops are processed before internal ones,
22 * then a block > nbits is considered an external block
23 * b- all the loops that must be still examined are updated. Not so
24 * hard. A dirty trick could avoid alloc/free of each bitv.
25 *
26 ****************************************************************************/
27
28#include "debug.h"
29#include "flog.h"
30#include "loops.h"
31#include "of_loops.h"
32#include "opttools.h"
33#include "store.h"
34#include "usedef.h"
35
36/****************************************************************************
37 *
38 * :: Debug
39 *
40 ****************************************************************************/
41
42static Bool loopDebug = false((int) 0);
43
44#define loopDEBUGif (!loopDebug) { } else afprintf DEBUG_IF(loop)if (!loopDebug) { } else afprintf
45
46/****************************************************************************
47 *
48 * :: Macros
49 *
50 ****************************************************************************/
51#define loopDefNo(foam)((foam)->foamGen.hdr.info.defNo) ((foam)->foamGen.hdr.info.defNo)
52
53/****************************************************************************
54 *
55 * :: Type Definitions
56 *
57 ****************************************************************************/
58
59struct _InvInfo {
60 Foam * foamPtr; /* pointer to the definition */
61 BBlock block; /* block to which belong */
62};
63
64DECLARE_LIST(InvInfo)typedef struct InvInfoListCons { InvInfo first; struct InvInfoListCons
*rest; } *InvInfoList; struct InvInfo_listOpsStruct { InvInfoList
(*Cons) (InvInfo, InvInfoList); InvInfoList (*Singleton) (InvInfo
); InvInfoList (*List) (int n, ...); InvInfoList (*Listv) (va_list
argp); InvInfoList (*ListNull) (InvInfo, ...); Bool (*Equal)
(InvInfoList, InvInfoList, Bool (*f) (InvInfo, InvInfo)); InvInfo
(*Find) (InvInfoList, InvInfo, Bool(*eq)(InvInfo,InvInfo) , int
*); InvInfo (*Match) (InvInfoList, void *, Bool(*match)(InvInfo
, void *), int *); InvInfoList (*MatchAll) (InvInfoList, void
*, Bool(*match)(InvInfo, void *)); InvInfoList (*FreeCons) (
InvInfoList); void (*Free) (InvInfoList); InvInfoList (*FreeTo
) (InvInfoList, InvInfoList); void (*FreeDeeply) (InvInfoList
, void (*f)(InvInfo)); InvInfoList (*FreeDeeplyTo) (InvInfoList
, InvInfoList, void (*f) (InvInfo) ); InvInfoList (*FreeIfSat
) (InvInfoList, void (*f)(InvInfo), Bool (*s)(InvInfo)); InvInfo
(*Elt) (InvInfoList, Length); InvInfoList (*Drop) (InvInfoList
, Length); InvInfoList (*LastCons) (InvInfoList); Length (*_Length
) (InvInfoList); Bool (*IsLength) (InvInfoList, Length); Bool
(*IsShorter) (InvInfoList, Length); Bool (*IsLonger) (InvInfoList
, Length); InvInfoList (*Copy) (InvInfoList); InvInfoList (*CopyTo
) (InvInfoList, InvInfoList); InvInfoList (*CopyDeeply) (InvInfoList
, InvInfo (*)(InvInfo)); InvInfoList (*CopyDeeplyTo) (InvInfoList
, InvInfoList, InvInfo (*)(InvInfo)); InvInfoList (*Map) (InvInfo
(*f)(InvInfo), InvInfoList); InvInfoList (*NMap) (InvInfo (*
f)(InvInfo), InvInfoList); InvInfoList (*Reverse) (InvInfoList
); InvInfoList (*NReverse) (InvInfoList); InvInfoList (*Concat
) (InvInfoList, InvInfoList); InvInfoList (*NConcat) (InvInfoList
, InvInfoList); Bool (*Memq) (InvInfoList, InvInfo); Bool (*Member
) (InvInfoList, InvInfo, Bool(*eq)(InvInfo,InvInfo) ); Bool (
*ContainsAllq) (InvInfoList, InvInfoList); Bool (*ContainsAnyq
) (InvInfoList, InvInfoList); Bool (*ContainsAll) (InvInfoList
, InvInfoList, Bool (*eq)(InvInfo, InvInfo)); Bool (*ContainsAny
) (InvInfoList, InvInfoList, Bool (*eq)(InvInfo, InvInfo)); int
(*Posq) (InvInfoList, InvInfo); int (*Position) (InvInfoList
, InvInfo, Bool(*eq)(InvInfo,InvInfo) ); InvInfoList (*NRemove
) (InvInfoList, InvInfo, Bool(*eq)(InvInfo,InvInfo) ); void (
*FillVector) (InvInfo *, InvInfoList); int (*Print) (FILE *, InvInfoList
, int (*pr)(FILE *, InvInfo) ); int (*GPrint) (FILE *, InvInfoList
, int (*pr)(FILE *, InvInfo), char *l,char *m,char *r); int (
*Format) (OStream, CString, InvInfoList); }; extern struct InvInfo_listOpsStruct
const *InvInfo_listPointer;
65CREATE_LIST(InvInfo)struct InvInfo_listOpsStruct const *InvInfo_listPointer = (struct
InvInfo_listOpsStruct const *) &ptrlistOps;
66
67/****************************************************************************
68 *
69 * :: Global Data Structures
70 *
71 ****************************************************************************/
72
73struct {
74 Foam unit;
75 FlowGraph flog;
76 Dominators doms;
77
78 Bitv domExits;
79
80 int numLocs;
81 int numPars;
82
83 InvInfo * invInfov;
84 int numInv;
85 int numDefs;
86
87} loopInfo;
88
89/*****************************************************************************
90 *
91 * :: Local Prototypes
92 *
93 ****************************************************************************/
94
95localstatic void loopFindAndMoveInvariantsFrLoop (LoopList);
96
97localstatic void loopInvariantsFindFrLoop (Loop);
98localstatic Bool loopInvariantsFindFrBlock (BBlock, Loop);
99
100localstatic Bool loopIsInvariantExp (Foam, Loop);
101
102
103localstatic void loopInvariantsFilterFrLoop (Loop);
104
105localstatic BBlock loopInvariantsMoveFrLoop (Loop);
106localstatic Foam loopPreHeaderCodeCreate (Loop);
107
108localstatic int loopDefinitionsReset (Loop/* , Bitv*/);
109
110localstatic Bool loopBlockDominatesAllExits (BBlock, BBlockList);
111
112localstatic Bitv loopFindExitsDominators (Loop);
113
114localstatic InvInfo loopInvInfoNew (Foam *, BBlock);
115
116localstatic void loopInvariantsPrintDb (int);
117
118localstatic void loopUpdate (Loop, BBlock, LoopList);
119
120/****************************************************************************
121 *
122 * :: Main Entry Points
123 *
124 ****************************************************************************/
125
126void
127loopUnit(Foam foam)
128{
129 int i;
130 Foam defs = foam->foamUnit.defs, def, prog;
131 FlowGraph flog;
132
133 loopDebug = 1;
134
135 assert(foamTag(foam) == FOAM_Unit)do { if (!(((foam)->hdr.tag) == FOAM_Unit)) _do_assert(("foamTag(foam) == FOAM_Unit"
),"of_loops.c",135); } while (0);
136
137 loopInfo.unit = foam;
138
139 /* !! No loop optimization for const 0 */
140
141 for (i = 1; i < foamArgc(defs)((defs)->hdr.argc); i++) {
142
143 def = defs->foamDDef.argv[i];
144
145 if (foamTag(def->foamDef.rhs)((def->foamDef.rhs)->hdr.tag) != FOAM_Prog)
146 continue;
147
148 prog = def->foamDef.rhs;
149
150 loopInfo.numLocs = foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1));
151 loopInfo.numPars = foamDDeclArgc(prog->foamProg.params)(((prog->foamProg.params)->hdr.argc) - (1));
152
153 flog = flogFrProg(prog, FLOG_UniqueExit);
154
155 loopInvariantsMoveFrFlog(flog);
156
157 def->foamDef.rhs = flogToProg(flog);
158 }
159}
160
161
162/* !!! There is something that must be changed. Usedef must decide that
163 * he need a FLOG_Union, not the client.
164 */
165void
166loopInvariantsMoveFrFlog(FlowGraph flog)
167{
168 Dominators doms;
169 LoopList loops;
170
171 loopInfo.flog = flog;
172
173 /* ----- First step: Build usedef chains ------ */
174
175 if (!usedefChainsFrFlog(flog, UD_OUTPUT_UdList))
176 return;
177
178 /* ----- Second step: Find All the Natural Loops ------ */
179
180 loops = lpNaturalLoopsFrFlog(flog, &doms);
181
182 if (!loops) {
183 lpDominatorsFree(doms);
184 return;
185 }
186
187 loopInfo.doms = doms;
188
189 /* ----- Third step: unify loops with some header ------ */
190
191 loops = lpUnifyCommonHeaders(loops);
192
193 /* ----- Fourth step: Optimize each loop ------ */
194
195 for (; loops; loops = cdr(loops)((loops)->rest))
196 loopFindAndMoveInvariantsFrLoop(loops);
197
198 usedefChainsFreeFrFlog(flog);
199
200}
201
202
203/* Given a loopList , find all the invariant computations for the
204 * first element, create the preheader and modify the flowgraph, and update
205 * the dataflow info for the remaining loops.
206 */
207localstatic void
208loopFindAndMoveInvariantsFrLoop(LoopList loops)
209{
210 BBlock preHeader;
211 Loop loop = car(loops)((loops)->first);
212
213 otProgInfoInit(OT_ASSOCIATION_LIST0x0002,
214 loopInfo.numLocs, loopInfo.numPars, loopInfo.unit);
215
216 loopInvariantsFindFrLoop(loop);
217
218 assert(loopInfo.numInv)do { if (!(loopInfo.numInv)) _do_assert(("loopInfo.numInv"),"of_loops.c"
,218); } while (0);
219
220 if (loopInfo.numInv == 1) {
221 otProgInfoFini();
222 return;
223 }
224
225 loopInvariantsFilterFrLoop(loop);
226
227 otProgInfoFini();
228
229 assert(loopInfo.numInv)do { if (!(loopInfo.numInv)) _do_assert(("loopInfo.numInv"),"of_loops.c"
,229); } while (0);
230
231 if (loopInfo.numInv == 1) return;
232
233 preHeader = loopInvariantsMoveFrLoop(loop);
234
235 if (cdr(loops)((loops)->rest))
236 loopUpdate(loop, preHeader, cdr(loops)((loops)->rest));
237
238
239}
240
241/****************************************************************************
242 *
243 * :: Find Invariants
244 *
245 ****************************************************************************/
246
247localstatic void
248loopInvariantsFindFrLoop(Loop loop)
249{
250 int numDefs;
251 Bool changed;
252 BitvClass class = loop->bitvClass;
253
254 loopInfo.domExits = loopFindExitsDominators(loop);
255
256 /* First: reset all invariant info on definitions */
257
258 numDefs = loopDefinitionsReset(loop/*, domExits*/);
259
260 loopInfo.numInv = 1; /* NOTE: must start from 1 */
261
262 if (numDefs == 0) return; /* No potential invariants */
263
264 do {
265 changed = false((int) 0);
266 listIter(BBlock, bb, loop->blockList, {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
267
268 /* Consider only blocks which dominates exits */{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
269 if (!bitvTest(class, loopInfo.domExits, bb->label)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
270 continue;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
271
272 if (loopInvariantsFindFrBlock(bb, loop)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
273 changed = true;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; }
274
275 }){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (loopInvariantsFindFrBlock(bb, loop)) changed = 1; }; };
} }; };
276
277 } while (changed);
278
279 /* bitvFree(domExits); */
280
281 if (loopDebug) loopInvariantsPrintDb(numDefs);
282
283 return;
284}
285
286localstatic void
287loopInvariantsPrintDb(int numDefs)
288{
289 int i;
290
291 if (loopInfo.numInv == 0)
292 fprintf(dbOut, "No invariants found among %d definitions.\n",
293 numDefs);
294 else {
295 fprintf(dbOut, "Found %d invariants among %d definitions.\n",
296 loopInfo.numInv - 1, numDefs);
297
298 for (i = 1; i < loopInfo.numInv; i++) {
299 fprintf(dbOut, "Inv %d in block %d: ", i,
300 loopInfo.invInfov[i]->block->label);
301
302 foamPrintDb(*(loopInfo.invInfov[i]->foamPtr));
303 }
304 }
305
306}
307
308#define LOOP_InvState_Unknown0 0
309#define LOOP_InvState_Invalid-1 -1
310#define LOOP_InvState_Valid1 1
311
312localstatic Bool
313loopInvariantsFindFrBlock(BBlock bb, Loop loop)
314{
315 Foam lhs, rhs, stmt, seq = bb->code;
316 int i, state;
317 Bool found = false((int) 0);
318 InvInfo * invInfov = loopInfo.invInfov;
319 FoamList defs;
320
321 for (i = 0; i < foamArgc(seq)((seq)->hdr.argc); i++) {
322
323 stmt = seq->foamSeq.argv[i];
324
325 if (!otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) continue;
326
327 if (loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) != LOOP_InvState_Unknown0)
328 continue;
329
330 defs = (FoamList) otGetVarInfoList(stmt->foamDef.lhs);
331
332 assert(defs)do { if (!(defs)) _do_assert(("defs"),"of_loops.c",332); } while
(0);
333
334 if (!listIsSingleton(defs)((defs) && !((defs)->rest))) {
335 loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) = LOOP_InvState_Invalid-1;
336 continue;
337 }
338
339 rhs = stmt->foamDef.rhs;
340
341 state = loopIsInvariantExp(rhs, loop);
342
343 if (state == LOOP_InvState_Invalid-1)
344 loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) = LOOP_InvState_Invalid-1;
345 else if (state != LOOP_InvState_Unknown0) {
346
347 found = true1;
348
349 lhs = stmt->foamDef.lhs;
Value stored to 'lhs' is never read
350
351 loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) = loopInfo.numInv;
352 invInfov[loopInfo.numInv] =
353 loopInvInfoNew(&(seq->foamSeq.argv[i]), bb);
354
355 /* otAddVarInfo(invInfov[loopInfo.numInv], lhs); */
356
357 loopInfo.numInv += 1;
358
359 /* loopInvalidateNotUniqueDef0(stmt); */
360 }
361 }
362
363 return found;
364}
365
366localstatic int
367loopIsInvariantExp(Foam foam, Loop loop)
368{
369 foamIter(foam, 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; }
370 int state = loopIsInvariantExp(*arg, loop);{ { 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; }
371
372 if (state == LOOP_InvState_Unknown ||{ { 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; }
373 state == LOOP_InvState_Invalid){ { 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; }
374 return state;{ { 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; }
375 }){ { 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; { { int state = loopIsInvariantExp(*arg, loop); if (state
== 0 || state == -1) return state; }; }; } } }; };
376
377 if (otIsLocalVar(foam)(((foam)->hdr.tag) == FOAM_Loc || ((foam)->hdr.tag) == FOAM_Par
)) {
378 UdInfoList udInfol = udReachingDefs(foam)((foam)->foamGen.hdr.info.defList);
379
380 /* Has this var a unique reaching def. and is this def marked
381 * invariant ?
382 */
383
384 if (listIsSingleton(udInfol)((udInfol) && !((udInfol)->rest))) {
385 UdInfo ud = car(udInfol)((udInfol)->first);
386
387 if (!lpIsBlockInLoop(udInfoBlock(ud), loop)(bitvTest((loop)->bitvClass, (loop)->blockSet, (((ud)->
block))->label)))
388 return LOOP_InvState_Valid1;
389
390 if (loopDefNo(udInfoDef(ud))((((ud)->foam))->foamGen.hdr.info.defNo) == LOOP_InvState_Invalid-1)
391 return LOOP_InvState_Invalid-1;
392
393 if (loopDefNo(udInfoDef(ud))((((ud)->foam))->foamGen.hdr.info.defNo) == LOOP_InvState_Unknown0)
394 return LOOP_InvState_Unknown0;
395
396 return LOOP_InvState_Valid1;
397 }
398
399 listIter(UdInfo, ud, udInfol, {{ { UdInfoList _l0; UdInfo ud; for (_l0 = (udInfol); _l0; _l0
= ((_l0)->rest)) { ud = ((_l0)->first); { { if ((bitvTest
((loop)->bitvClass, (loop)->blockSet, (((ud)->block)
)->label))) return -1; }; }; } }; }
400 if (lpIsBlockInLoop(udInfoBlock(ud), loop)){ { UdInfoList _l0; UdInfo ud; for (_l0 = (udInfol); _l0; _l0
= ((_l0)->rest)) { ud = ((_l0)->first); { { if ((bitvTest
((loop)->bitvClass, (loop)->blockSet, (((ud)->block)
)->label))) return -1; }; }; } }; }
401 return LOOP_InvState_Invalid;{ { UdInfoList _l0; UdInfo ud; for (_l0 = (udInfol); _l0; _l0
= ((_l0)->rest)) { ud = ((_l0)->first); { { if ((bitvTest
((loop)->bitvClass, (loop)->blockSet, (((ud)->block)
)->label))) return -1; }; }; } }; }
402 }){ { UdInfoList _l0; UdInfo ud; for (_l0 = (udInfol); _l0; _l0
= ((_l0)->rest)) { ud = ((_l0)->first); { { if ((bitvTest
((loop)->bitvClass, (loop)->blockSet, (((ud)->block)
)->label))) return -1; }; }; } }; };
403
404 return LOOP_InvState_Valid1;
405 }
406
407 if (otIsNonLocalVar(foam)(((foam)->hdr.tag) == FOAM_Lex || ((foam)->hdr.tag) == FOAM_Glo
)) {
408 if (otIsConstSyme(foamSyme(foam)((foam)->hdr.syme)))
409 return LOOP_InvState_Valid1;
410 else
411 return LOOP_InvState_Invalid-1;
412 }
413
414 if (foamTag(foam)((foam)->hdr.tag) == FOAM_Cast) return LOOP_InvState_Valid1;
415 if (otIsMovableData(foam)) return LOOP_InvState_Valid1;
416 if (foamTag(foam)((foam)->hdr.tag) == FOAM_RRFmt) return LOOP_InvState_Valid1;
417
418 if (foamTag(foam)((foam)->hdr.tag) == FOAM_BCall &&
419 !foamBValInfo(foam->foamBCall.op)(foamBValInfoTable[(int)(foam->foamBCall.op)-(int)FOAM_BVAL_START
]).hasSideFx)
420 return LOOP_InvState_Valid1;
421
422 if (foamTag(foam)((foam)->hdr.tag) == FOAM_OCall)
423 /*!! Could check for non-side-effecting expressions here. */
424 return LOOP_InvState_Invalid-1;
425
426 if (foamTag(foam)((foam)->hdr.tag) == FOAM_CCall) {
427 if (otIsForcer(foam->foamCCall.op))
428 return LOOP_InvState_Valid1;
429
430 /*!! Could check for non-side-effecting expressions here. */
431 return LOOP_InvState_Invalid-1;
432 }
433
434 if (foamTag(foam)((foam)->hdr.tag) == FOAM_PCall)
435 return LOOP_InvState_Invalid-1;
436
437 return LOOP_InvState_Invalid-1;
438}
439
440/* Assign 0 to each def in the blocks in LOOP and build
441 * association lists: (Var in LOOP) -> (All definition of Var in LOOP)
442 * Return the number of defs found (== potential invariants)
443 */
444localstatic int
445loopDefinitionsReset(Loop loop /*, Bitv domExits $$*/ )
446{
447 int numDefs = 0, i;
448
449 listIter(BBlock, bb, loop->blockList, {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
450 int i;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
451 Foam seq = bb->code;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
452
453 /* if (!bitvTest(class, domExits, bb->label)) continue; */{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
454
455 for (i = 0; i < foamArgc(seq); i++) {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
456
457 Foam stmt = seq->foamSeq.argv[i];{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
458
459 if (otIsDef(stmt)) {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
460 loopDefNo(stmt) = 0;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
461 numDefs++;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
462
463 otAddVarInfo(stmt, stmt->foamDef.lhs);{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
464 }{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
465 }{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; }
466 }){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
int i; Foam seq = bb->code; for (i = 0; i < ((seq)->
hdr.argc); i++) { Foam stmt = seq->foamSeq.argv[i]; if (((
(stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) { ((stmt)->foamGen.hdr.info.defNo) = 0; numDefs++; otAddVarInfo0
((VarInfo) (stmt), stmt->foamDef.lhs); } } }; }; } }; };
467
468 if (numDefs) {
469 loopInfo.invInfov = (InvInfo *)
470 stoAlloc(OB_Other0,
471 sizeof(InvInfo) * (numDefs + 1));
472
473 for (i = 0; i < numDefs + 1; i++)
474 loopInfo.invInfov[i] = (InvInfo) 0;
475 }
476 loopInfo.numDefs = numDefs;
477
478 return numDefs;
479}
480/****************************************************************************
481 *
482 * :: Filter Invariants
483 *
484 ****************************************************************************/
485localstatic Bool loopFilterExp(Foam foam);
486/* local void loopInvalidateNotUniqueDef(void);*/
487
488localstatic Bool loopFilterDependencies(Foam foam);
489localstatic Bool loopIsStillInvariant(Foam foam);
490
491/* For each invariant x := (exp), check the following conditions:
492 *
493 * a) this must be the unique def. for x in LOOP.
494 * b) all uses of x in LOOP are reached only by this definition.
495 *
496 * How: build a vector: var -> invariant.
497 * (b) It's easy using usedef chains: traverse the loop, for each use look
498 * at the usedef
499 */
500localstatic void
501loopInvariantsFilterFrLoop(Loop loop)
502{
503 Bool removed = false((int) 0);
504 BitvClass class = loop->bitvClass;
505
506 /* 1) Check, for each inv x := ..., that all uses of x in LOOP
507 * can be reached only by the invariant.
508 */
509
510 listIter(BBlock, bb, loop->blockList, {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopFilterExp(bb->code)) removed = 1; }; }; } }; }
511
512 if (!loopFilterExp(bb->code)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopFilterExp(bb->code)) removed = 1; }; }; } }; }
513 removed = true;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopFilterExp(bb->code)) removed = 1; }; }; } }; }
514
515 }){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopFilterExp(bb->code)) removed = 1; }; }; } }; };
516
517 if (!removed) return;
518
519 /* 2) Check if other invariants must be removed
520 * due to removed invariants.
521 */
522
523
524 while (removed) {
525
526 removed = false((int) 0);
527
528 listIter(BBlock, bb, loop->blockList, {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
529
530 /* Consider only blocks which dominates exits */{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
531 if (!bitvTest(class, loopInfo.domExits, bb->label)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
532 continue;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
533
534 if (!loopFilterDependencies(bb->code)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
535 removed = true;{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; }
536
537 }){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!bitvTest(class, loopInfo.domExits, bb->label)) continue
; if (!loopFilterDependencies(bb->code)) removed = 1; }; }
; } }; };
538}
539
540}
541
542
543/* For each var use, look at the reaching defs:
544 * is there is an invariant among them, the list must be a singleton
545 * otherwise invalid invariant.
546 */
547localstatic Bool
548loopFilterExp(Foam foam)
549{
550 UdInfoList udInfol;
551 Bool removed = false((int) 0);
552 FoamList defs;
553 Foam invDef;
554
555 foamIter(foam, 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
556
557 if (otIsDef(*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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
558 if (!loopFilterExp((*arg)->foamDef.rhs)){ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
559 removed = true;{ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
560 }{ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
561 else{ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
562 if (!loopFilterExp(*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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
563 removed = true;{ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; }
564 }){ { 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; { { if ((((*arg)->hdr.tag) == FOAM_Set || ((*arg)->
hdr.tag) == FOAM_Def)) { if (!loopFilterExp((*arg)->foamDef
.rhs)) removed = 1; } else if (!loopFilterExp(*arg)) removed =
1; }; }; } } }; };
565
566 if (!otIsVar(foam)(((foam)->hdr.tag) == FOAM_Loc || ((foam)->hdr.tag) == FOAM_Par
|| ((foam)->hdr.tag) == FOAM_Lex || ((foam)->hdr.tag) ==
FOAM_Glo))
567 return removed;
568
569 /* Take all definition for this var inside the loop */
570 defs = (FoamList) otGetVarInfoList(foam);
571
572 if (!defs) return removed;
573
574 if (!listIsSingleton(defs)((defs) && !((defs)->rest))) return removed;
575
576 if (loopDefNo(car(defs))((((defs)->first))->foamGen.hdr.info.defNo) == LOOP_InvState_Invalid-1) return removed;
577
578 if (loopDefNo(car(defs))((((defs)->first))->foamGen.hdr.info.defNo) == LOOP_InvState_Unknown0) {
579 loopDefNo(car(defs))((((defs)->first))->foamGen.hdr.info.defNo) = LOOP_InvState_Unknown0;
580 return removed;
581 }
582
583 /* There is an invariant with this lhs. */
584
585 /* Is this the only reaching def for foam ? */
586
587 udInfol = udReachingDefs(foam)((foam)->foamGen.hdr.info.defList);
588 invDef = car(defs)((defs)->first);
589
590 if (!listIsSingleton(udInfol)((udInfol) && !((udInfol)->rest)) &&
591 udInfoDef(car(udInfol))((((udInfol)->first))->foam)->foamDef.lhs != foam) {
592
593 /* The invariant is marked invalid */
594
595 loopInfo.invInfov[loopDefNo(invDef)((invDef)->foamGen.hdr.info.defNo)] = (InvInfo) 0;
596 loopDefNo(invDef)((invDef)->foamGen.hdr.info.defNo) = LOOP_InvState_Invalid-1;
597
598 loopInfo.numInv--;
599
600 loopDEBUGif (!loopDebug) { } else afprintf(dbOut,"* Invariant rejected by loopFilterExp *\n");
601
602 removed = true1;
603
604 }
605
606 return removed;
607
608}
609
610localstatic Bool
611loopFilterDependencies(Foam foam)
612{
613 Foam stmt;
614 int i;
615 Bool changed = false((int) 0);
616
617 assert(foamTag(foam) == FOAM_Seq)do { if (!(((foam)->hdr.tag) == FOAM_Seq)) _do_assert(("foamTag(foam) == FOAM_Seq"
),"of_loops.c",617); } while (0);
618
619
620 for (i = 0; i < foamArgc(foam)((foam)->hdr.argc); i++) {
621
622 stmt = foam->foamSeq.argv[i];
623
624 if (!otIsDef(stmt)(((stmt)->hdr.tag) == FOAM_Set || ((stmt)->hdr.tag) == FOAM_Def
)) continue;
625
626 if (loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) == LOOP_InvState_Invalid-1) continue;
627
628 assert(loopDefNo(stmt))do { if (!(((stmt)->foamGen.hdr.info.defNo))) _do_assert((
"loopDefNo(stmt)"),"of_loops.c",628); } while (0);
629
630 /* Found an invariant. Is it still valid ? */
631
632 if (!loopIsStillInvariant(stmt->foamDef.rhs)) {
633
634 /* The invariant is marked invalid */
635
636 loopInfo.invInfov[loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo)] = (InvInfo) 0;
637 loopDefNo(stmt)((stmt)->foamGen.hdr.info.defNo) = LOOP_InvState_Invalid-1;
638
639 loopInfo.numInv--;
640
641 loopDEBUGif (!loopDebug) { } else afprintf(dbOut,"* Invariant rejected by loopFilterDependencies *\n");
642
643 changed = true1;
644 }
645
646 }
647
648 return changed;
649}
650
651
652localstatic Bool
653loopIsStillInvariant(Foam foam)
654{
655 UdInfoList udInfol;
656 UdInfo ud;
657
658 foamIter(foam, 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; { { if (!loopIsStillInvariant(*arg)) return ((int) 0); }
; }; } } }; }
659
660 if (!loopIsStillInvariant(*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; { { if (!loopIsStillInvariant(*arg)) return ((int) 0); }
; }; } } }; }
661 return false;{ { 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; { { if (!loopIsStillInvariant(*arg)) return ((int) 0); }
; }; } } }; }
662 }){ { 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; { { if (!loopIsStillInvariant(*arg)) return ((int) 0); }
; }; } } }; };
663
664 if (!otIsVar(foam)(((foam)->hdr.tag) == FOAM_Loc || ((foam)->hdr.tag) == FOAM_Par
|| ((foam)->hdr.tag) == FOAM_Lex || ((foam)->hdr.tag) ==
FOAM_Glo))
665 return true1;
666
667 udInfol = udReachingDefs(foam)((foam)->foamGen.hdr.info.defList);
668
669 /* Has this var still a unique reaching def. and is this def marked
670 * invariant ?
671 */
672
673 assert(listIsSingleton(udInfol))do { if (!(((udInfol) && !((udInfol)->rest)))) _do_assert
(("listIsSingleton(udInfol)"),"of_loops.c",673); } while (0);
674
675 ud = car(udInfol)((udInfol)->first);
676
677 assert(loopDefNo(udInfoDef(ud)))do { if (!(((((ud)->foam))->foamGen.hdr.info.defNo))) _do_assert
(("loopDefNo(udInfoDef(ud))"),"of_loops.c",677); } while (0);
678
679 if (loopDefNo(udInfoDef(ud))((((ud)->foam))->foamGen.hdr.info.defNo) == LOOP_InvState_Invalid-1)
680 return false((int) 0);
681
682 return true1;
683}
684
685/****************************************************************************
686 *
687 * :: Move Invariants in the Preheader
688 *
689 ****************************************************************************/
690
691
692localstatic BBlock
693loopInvariantsMoveFrLoop(Loop loop)
694{
695 int i, j;
696 BBlock bbPre, bbHeader = loop->header;
697 Length newLab;
698 FlowGraph flog = loopInfo.flog;
699
700 Foam newSeq = loopPreHeaderCodeCreate(loop);
701
702 flogFixEntries(flog); /* $$ !! */
703
704 /* Create a new block with PREHEADER as code .. */
705
706 newLab = flogReserveLabel(flog)bbufReserve1((flog)->blocks);
707
708 bbPre = bbNew(newSeq, newLab);
709
710 /* Attach it to the graph... */
711 flogSetBlock(flog, newLab, bbPre)((flog)->fixedEntries = ((int) 0), bbufSetBlockFn((flog)->
blocks,newLab,bbPre), (bbPre)->graph = (flog));
712
713 /* .. and set up entry and exit edges */
714
715 bbufNeed(bbPre->exits, 1);
716 bbSetExit(bbPre, int0, bbHeader)((bbPre)->graph->fixedEntries = ((int) 0), (bbPre)->
exits->argv[((int) 0)] = (bbHeader)); /* preheader -> header */
717 bbSetExitC(bbPre, 1)((bbPre)->exits->pos = (1));
718
719 bbufNeed(bbPre->entries, bbEntryC(bbHeader)((bbHeader)->entries->pos));
720
721 /* Modify each entry of bbHeader not from LOOP
722 * so that now are entries in bbPre
723 */
724
725 for (i = 0; i < bbEntryC(bbHeader)((bbHeader)->entries->pos); i++) {
726
727 BBlock entryBlock = bbEntry(bbHeader, i)((bbHeader)->entries->argv[i]);
728
729 if (lpIsBlockInLoop(entryBlock, loop)(bitvTest((loop)->bitvClass, (loop)->blockSet, (entryBlock
)->label))) continue;
730
731 for (j = 0; j < bbExitC(entryBlock)((entryBlock)->exits->pos); j++)
732 if (bbExit(entryBlock, j)((entryBlock)->exits->argv[j]) == bbHeader)
733 bbSetExit(entryBlock, j, bbPre)((entryBlock)->graph->fixedEntries = ((int) 0), (entryBlock
)->exits->argv[j] = (bbPre));
734 }
735
736 /* If bbHeader was the first, now bbPre will be the first */
737
738 if (bbHeader == flog->block0) flog->block0 = bbPre;
739
740 /* NOTE: entries have not been modified, but this isn't important,
741 * because they have been invalidated.
742 */
743
744 return bbPre;
745
746}
747
748localstatic Foam
749loopPreHeaderCodeCreate(Loop loop)
750{
751 Foam preHeader = foamNewEmpty(FOAM_Seq, loopInfo.numInv);
752 Foam foam;
753 InvInfo * invInfov = loopInfo.invInfov;
754 int j = 0, i;
755
756 for (i = 1; i < loopInfo.numDefs + 1; i++) {
757
758 if (!invInfov[i]) continue;
759
760 foam = *(invInfov[i]->foamPtr);
761
762 assert(loopDefNo(foam) > 0)do { if (!(((foam)->foamGen.hdr.info.defNo) > 0)) _do_assert
(("loopDefNo(foam) > 0"),"of_loops.c",762); } while (0);
763
764 *(invInfov[i]->foamPtr) = foamNewNOp()foamNew(FOAM_NOp, (int) 0);
765
766 preHeader->foamSeq.argv[j++] = foam;
767 }
768
769 assert(j == loopInfo.numInv - 1)do { if (!(j == loopInfo.numInv - 1)) _do_assert(("j == loopInfo.numInv - 1"
),"of_loops.c",769); } while (0);
770
771 /* Add: (Goto the header block) */
772 preHeader->foamSeq.argv[j] = foamNewGoto(loop->header->label)foamNew(FOAM_Goto, 1, (AInt)(loop->header->label));
773
774 if (DEBUG(loop)loopDebug) {
775 fprintf(dbOut, "New preheader: \n");
776 foamPrintDb(preHeader);
777 }
778
779 return preHeader;
780
781}
782
783/****************************************************************************
784 *
785 * :: Updated dflow info and loops
786 *
787 ****************************************************************************/
788
789localstatic void loopUpdateBlocks (Loop, BBlock, LoopList);
790localstatic void loopUpdateDominators (Loop, BBlock);
791localstatic void loopUpdateUseDefChains (void);
792
793/******************************************************************************
794 *
795 * :: Update dflow info and loops
796 *
797 *****************************************************************************/
798
799localstatic void
800loopUpdate(Loop loop, BBlock preHeader, LoopList loops)
801{
802
803 loopUpdateBlocks(loop, preHeader, loops);
804 loopUpdateDominators(loop, preHeader);
805 loopUpdateUseDefChains();
806}
807
808
809localstatic void
810loopUpdateBlocks(Loop loop, BBlock preHeader, LoopList loops)
811{
812 BitvClass oldClass, newClass;
813 Length newbit = bitvClassSize(loop->bitvClass)((loop->bitvClass)->nbits);
814
815 listIter(Loop, loop0, loops, {{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
816 oldClass = loop0->bitvClass;{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
817 newClass = bitvClassCreate(bitvClassSize(oldClass) + 1);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
818
819 assert(bitvClassSize(newClass) == preHeader->label + 1);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
820
821 loop0->blockSet ={ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
822 bitvResize(newClass, oldClass, loop0->blockSet);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
823
824 loop0->bitvClass = newClass;{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
825
826 if (lpIsBlockInLoop(loop->header, loop0)) {{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
827 bitvSet(newClass, loop0->blockSet, newbit);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
828 listPush(BBlock, preHeader, loop0->blockList);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
829 }{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
830
831 bitvClassDestroy(oldClass);{ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; }
832 }){ { LoopList _l0; Loop loop0; for (_l0 = (loops); _l0; _l0 = (
(_l0)->rest)) { loop0 = ((_l0)->first); { { oldClass = loop0
->bitvClass; newClass = bitvClassCreate(((oldClass)->nbits
) + 1); do { if (!(((newClass)->nbits) == preHeader->label
+ 1)) _do_assert(("bitvClassSize(newClass) == preHeader->label + 1"
),"of_loops.c",819); } while (0); loop0->blockSet = bitvResize
(newClass, oldClass, loop0->blockSet); loop0->bitvClass
= newClass; if ((bitvTest((loop0)->bitvClass, (loop0)->
blockSet, (loop->header)->label))) { bitvSet(newClass, loop0
->blockSet, newbit); (loop0->blockList = (BBlock_listPointer
->Cons)(preHeader, loop0->blockList)); } bitvClassDestroy
(oldClass); }; }; } }; };
833}
834
835localstatic void
836loopUpdateDominators(Loop loop, BBlock preHeader)
837{
838 Dominators doms = loopInfo.doms;
839 int i;
840 BitvClass newClass, oldClass;
841
842 oldClass = doms->bitvClass;
843 newClass = bitvClassCreate(bitvClassSize(oldClass)((oldClass)->nbits) + 1);
844
845 for (i = 0; i < doms->nBlocks; i++)
846 doms->doms[i] = bitvResize(newClass, oldClass, doms->doms[i]);
847
848 doms->nBlocks += 1;
849 bitvClassDestroy(doms->bitvClass);
850 doms->bitvClass = newClass;
851
852 assert(bitvClassSize(newClass) == doms->nBlocks)do { if (!(((newClass)->nbits) == doms->nBlocks)) _do_assert
(("bitvClassSize(newClass) == doms->nBlocks"),"of_loops.c"
,852); } while (0);
853 assert(bitvClassSize(newClass) == bitvClassSize(loop->bitvClass) + 1)do { if (!(((newClass)->nbits) == ((loop->bitvClass)->
nbits) + 1)) _do_assert(("bitvClassSize(newClass) == bitvClassSize(loop->bitvClass) + 1"
),"of_loops.c",853); } while (0);
854
855 /* 1) Each dominator of loop->header become a dominator of preheader.*/
856
857 flogIter(loopInfo.flog, bb, {{ { int _i; BBlock bb; for (_i = 0; _i < ((loopInfo.flog)->
blocks->pos); _i++) { bb = bbufBlockFn((loopInfo.flog)->
blocks,_i); if (!bb) continue; { { if (bb == preHeader) continue
; if (bitvTest((doms)->bitvClass, (doms)->doms[(loop->
header)->label], (bb)->label)) bitvSet((doms)->bitvClass
, (doms)->doms[(preHeader)->label], (bb)->label); };
}; } }; }
858
859 if (bb == preHeader) continue;{ { int _i; BBlock bb; for (_i = 0; _i < ((loopInfo.flog)->
blocks->pos); _i++) { bb = bbufBlockFn((loopInfo.flog)->
blocks,_i); if (!bb) continue; { { if (bb == preHeader) continue
; if (bitvTest((doms)->bitvClass, (doms)->doms[(loop->
header)->label], (bb)->label)) bitvSet((doms)->bitvClass
, (doms)->doms[(preHeader)->label], (bb)->label); };
}; } }; }
860
861 if (lpIsDom(doms, bb, loop->header)){ { int _i; BBlock bb; for (_i = 0; _i < ((loopInfo.flog)->
blocks->pos); _i++) { bb = bbufBlockFn((loopInfo.flog)->
blocks,_i); if (!bb) continue; { { if (bb == preHeader) continue
; if (bitvTest((doms)->bitvClass, (doms)->doms[(loop->
header)->label], (bb)->label)) bitvSet((doms)->bitvClass
, (doms)->doms[(preHeader)->label], (bb)->label); };
}; } }; }
862 lpSetDom(doms, bb, preHeader);{ { int _i; BBlock bb; for (_i = 0; _i < ((loopInfo.flog)->
blocks->pos); _i++) { bb = bbufBlockFn((loopInfo.flog)->
blocks,_i); if (!bb) continue; { { if (bb == preHeader) continue
; if (bitvTest((doms)->bitvClass, (doms)->doms[(loop->
header)->label], (bb)->label)) bitvSet((doms)->bitvClass
, (doms)->doms[(preHeader)->label], (bb)->label); };
}; } }; }
863 }){ { int _i; BBlock bb; for (_i = 0; _i < ((loopInfo.flog)->
blocks->pos); _i++) { bb = bbufBlockFn((loopInfo.flog)->
blocks,_i); if (!bb) continue; { { if (bb == preHeader) continue
; if (bitvTest((doms)->bitvClass, (doms)->doms[(loop->
header)->label], (bb)->label)) bitvSet((doms)->bitvClass
, (doms)->doms[(preHeader)->label], (bb)->label); };
}; } }; };
864
865 /* 2) Preheader become dominator of header. */
866
867 lpSetDom(doms, preHeader, loop->header)bitvSet((doms)->bitvClass, (doms)->doms[(loop->header
)->label], (preHeader)->label);
868
869}
870
871/* Now this operation is expensive, because all the ud-chains are recomputed
872 * again.
873 * ToDo:
874 * The UdInfo can be a pair (BB, index), where index is such that
875 * bb->code->foamSeq.argv[index] is the reaching def.
876 * In such way each (NOp) generated when a def is moved will have a UdInfo
877 * on it, (new-block, new-index), and the definition can be found
878 * dereferencing this chains.
879 */
880localstatic void
881loopUpdateUseDefChains()
882{
883 usedefChainsFreeFrFlog(loopInfo.flog);
884
885 flogReuse(loopInfo.flog, FLOG_UniqueExit);
886
887 usedefChainsFrFlog(loopInfo.flog, UD_OUTPUT_UdList);
888}
889
890/****************************************************************************
891 *
892 * :: Utility
893 *
894 ****************************************************************************/
895
896/* Return a bitv where are on only bits corresponding to blocks in LOOP which
897 * dominates all the loop exits
898 */
899localstatic Bitv
900loopFindExitsDominators(Loop loop)
901{
902 BitvClass bclass = loop->bitvClass;
903 Bitv bres = bitvNew(bclass);
904 BBlockList exitBlocks = lpExitBlocksFrLoop(loop);
905
906 bitvCopy(bclass, bres, loop->blockSet);
907
908 listIter(BBlock, bb, loop->blockList, {{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopBlockDominatesAllExits(bb, exitBlocks)) bitvClear(bclass
, bres, bb->label); }; }; } }; }
909
910 if (!loopBlockDominatesAllExits(bb, exitBlocks)){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopBlockDominatesAllExits(bb, exitBlocks)) bitvClear(bclass
, bres, bb->label); }; }; } }; }
911 bitvClear(bclass, bres, bb->label);{ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopBlockDominatesAllExits(bb, exitBlocks)) bitvClear(bclass
, bres, bb->label); }; }; } }; }
912
913 }){ { BBlockList _l0; BBlock bb; for (_l0 = (loop->blockList
); _l0; _l0 = ((_l0)->rest)) { bb = ((_l0)->first); { {
if (!loopBlockDominatesAllExits(bb, exitBlocks)) bitvClear(bclass
, bres, bb->label); }; }; } }; };
914
915 return bres;
916}
917
918
919/* Return true iif BB dominates all the blocks in EXITS */
920
921localstatic Bool
922loopBlockDominatesAllExits(BBlock bb, BBlockList exits)
923{
924 Dominators doms = loopInfo.doms;
925
926 listIter(BBlock, bbLoopExit, exits, {{ { BBlockList _l0; BBlock bbLoopExit; for (_l0 = (exits); _l0
; _l0 = ((_l0)->rest)) { bbLoopExit = ((_l0)->first); {
{ if (!bitvTest((doms)->bitvClass, (doms)->doms[(bbLoopExit
)->label], (bb)->label)) return ((int) 0); }; }; } }; }
927 if (!lpIsDom(doms, bb, bbLoopExit)){ { BBlockList _l0; BBlock bbLoopExit; for (_l0 = (exits); _l0
; _l0 = ((_l0)->rest)) { bbLoopExit = ((_l0)->first); {
{ if (!bitvTest((doms)->bitvClass, (doms)->doms[(bbLoopExit
)->label], (bb)->label)) return ((int) 0); }; }; } }; }
928 return false;{ { BBlockList _l0; BBlock bbLoopExit; for (_l0 = (exits); _l0
; _l0 = ((_l0)->rest)) { bbLoopExit = ((_l0)->first); {
{ if (!bitvTest((doms)->bitvClass, (doms)->doms[(bbLoopExit
)->label], (bb)->label)) return ((int) 0); }; }; } }; }
929 }){ { BBlockList _l0; BBlock bbLoopExit; for (_l0 = (exits); _l0
; _l0 = ((_l0)->rest)) { bbLoopExit = ((_l0)->first); {
{ if (!bitvTest((doms)->bitvClass, (doms)->doms[(bbLoopExit
)->label], (bb)->label)) return ((int) 0); }; }; } }; };
930
931 return true1;
932}
933
934/*****************************************************************************
935 *
936 * :: Constructors and Destructors
937 *
938 ****************************************************************************/
939
940localstatic InvInfo
941loopInvInfoNew(Foam * pstmt, BBlock bb)
942{
943 InvInfo invInfo = (InvInfo) stoAlloc(OB_Other0, sizeof(*invInfo));
944
945 invInfo->foamPtr = pstmt;
946 invInfo->block = bb;
947
948 return invInfo;
949}