| File: | src/yldlocs.c |
| Warning: | line 100, column 2 Value stored to 'i' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | |
| 2 | #include "axlobs.h" |
| 3 | #include "bitv.h" |
| 4 | #include "debug.h" |
| 5 | #include "dflow.h" |
| 6 | #include "flog.h" |
| 7 | #include "foam.h" |
| 8 | #include "store.h" |
| 9 | #include "yldlocs.h" |
| 10 | |
| 11 | Bool ylDebug = false((int) 0); |
| 12 | #define ylDEBUGif (!ylDebug) { } else afprintf DEBUG_IF(yl)if (!ylDebug) { } else afprintf |
| 13 | |
| 14 | #define ylDF_CUTOFF(100) (100) |
| 15 | /* |
| 16 | * Local splitting for yields. |
| 17 | * We want to identify locals whose definition/use does not cross a yield statement |
| 18 | * Basic idea is dataflow analysis. |
| 19 | * |
| 20 | * Loc 1 --> Yld --> Usage |
| 21 | * |
| 22 | * 1. Assign a number to each local assignment |
| 23 | * 2. Associate an implied bit vector to each statement |
| 24 | * - The bitvector will mean 'From this point, assignment X is visible' and concurrently, 'assignment X has hit a yield' |
| 25 | * 3. Iterate over by bblock and statement |
| 26 | * - from an empty bitvector, |
| 27 | * - assignment X will set bit 'X_s', and clear other sets of that local + yields |
| 28 | * - yield => set yld flag for that local |
| 29 | * 4. Magic of dataflow; hd and tl of each BB will give source of each assignment, plus if a yield was encountered for that source. |
| 30 | * |
| 31 | * Simple version: |
| 32 | * For each BB find candidates (Def/Use in same BB, dropping yields), and fails (fail == use without set, use after yield). |
| 33 | * If a given local is always a candidate, then mark as local |
| 34 | */ |
| 35 | |
| 36 | typedef struct ylState { |
| 37 | BitvClass bitvClass; |
| 38 | Foam prog; |
| 39 | FlowGraph flog; |
| 40 | Bitv result; |
| 41 | int nLocals; |
| 42 | } *YlState; |
| 43 | |
| 44 | static YlState ylProgState; |
| 45 | |
| 46 | localstatic void ylFlowInitBlock0(FlowGraph flog); |
| 47 | localstatic void ylFlowFillGenKillBB(FlowGraph flog, BBlock bb); |
| 48 | localstatic void ylFlowFillGenKillStmt(BBlock bb, Foam stmt, Bitv gen, Bitv kill); |
| 49 | localstatic void ylSet(BBlock bb, Foam lhs, Bitv gen, Bitv kill); |
| 50 | localstatic void ylYield(BBlock bb, Foam lhs, Bitv gen, Bitv kill); |
| 51 | localstatic void ylComputeResult(BBlock bb); |
| 52 | localstatic void ylFindUses(BBlock bb, Bitv bitv, Foam foam); |
| 53 | localstatic void ylFindUsesLhs(BBlock bb, Bitv bitv, Foam foam); |
| 54 | localstatic void ylCheckLoc(BBlock bb, Bitv bitv, AInt idx); |
| 55 | localstatic void ylMarkLoc(YlState state, AInt idx); |
| 56 | |
| 57 | localstatic YlState ylStateNew(Foam prog, FlowGraph flog, int nLocals); |
| 58 | localstatic void ylStateFree(YlState); |
| 59 | localstatic void ylStateToResult(YlState); |
| 60 | localstatic YldLocResult ylLocResultFrState(YlState state); |
| 61 | |
| 62 | YldLocResult |
| 63 | ylProg0(Foam prog) |
| 64 | { |
| 65 | AInt locCount = foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1)); |
| 66 | AIntList reclocs = listNil(AInt)((AIntList) 0); |
| 67 | YldLocResult result = (YldLocResult) stoAlloc(OB_Other0, sizeof(*result)); |
| 68 | |
| 69 | for (int i=0; i<locCount; i++) { |
| 70 | reclocs = listCons(AInt)(AInt_listPointer->Cons)(i, reclocs); |
| 71 | } |
| 72 | |
| 73 | result->locs = listNil(AInt)((AIntList) 0); |
| 74 | result->reclocs = listNReverse(AInt)(AInt_listPointer->NReverse)(reclocs); |
| 75 | return result; |
| 76 | |
| 77 | } |
| 78 | |
| 79 | YldLocResult |
| 80 | ylProg(Foam prog) |
| 81 | { |
| 82 | FlowGraph flog; |
| 83 | BBlock bb; |
| 84 | AInt locCount = foamDDeclArgc(prog->foamProg.locals)(((prog->foamProg.locals)->hdr.argc) - (1)); |
| 85 | int i, k; |
| 86 | |
| 87 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, "Starting\n %pFoam\n", prog); |
| 88 | |
| 89 | flog = flogFrProg(prog, FLOG_UniqueExit); |
| 90 | ylProgState = ylStateNew(prog, flog, locCount); |
| 91 | |
| 92 | flogBitvClass(flog)((flog)->bitvClass) = bitvClassCreate(locCount * 2); |
| 93 | |
| 94 | for (i = 0; i < flogBlockC(flog)((flog)->blocks->pos); i++) { |
| 95 | bb = flogBlock(flog, i)bbufBlockFn((flog)->blocks,i); |
| 96 | dflowNewBlockInfo(bb, locCount * 2, ylFlowFillGenKillBB); |
| 97 | } |
| 98 | |
| 99 | // Run dflow... |
| 100 | i = dflowFwdIterate(flog, DFLOW_Union, ylDF_CUTOFF(100), &k, |
Value stored to 'i' is never read | |
| 101 | (DFlowInitFun) ylFlowInitBlock0); |
| 102 | |
| 103 | // Find the result |
| 104 | for (i = 0; i < flogBlockC(flog)((flog)->blocks->pos); i++) { |
| 105 | bb = flogBlock(flog, i)bbufBlockFn((flog)->blocks,i); |
| 106 | if (bb != NULL((void*)0)) |
| 107 | ylComputeResult(bb); |
| 108 | } |
| 109 | |
| 110 | YldLocResult result = ylLocResultFrState(ylProgState); |
| 111 | // Back to Prog mode |
| 112 | flogToProg(flog); |
| 113 | ylStateFree(ylProgState); |
| 114 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, "Locs %pAIntList\n", result->locs); |
| 115 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, "Record %pAIntList\n", result->reclocs); |
| 116 | return result; |
| 117 | } |
| 118 | |
| 119 | localstatic void |
| 120 | ylFlowInitBlock0(FlowGraph flog) |
| 121 | { |
| 122 | // All zeros to start |
| 123 | return; |
| 124 | } |
| 125 | |
| 126 | |
| 127 | localstatic void |
| 128 | ylFlowFillGenKillBB(FlowGraph flog, BBlock bb) |
| 129 | { |
| 130 | Foam seq, stmt; |
| 131 | int i; |
| 132 | seq = bb->code; |
| 133 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, "(BB Starts %pFoam\n", seq); |
| 134 | |
| 135 | bitvClearAll(ylProgState->bitvClass, dfFwdIn(bb)((bb)->dfinfo->in)); |
| 136 | bitvClearAll(ylProgState->bitvClass, dfFwdGen(bb)((bb)->dfinfo->gen)); |
| 137 | bitvClearAll(ylProgState->bitvClass, dfFwdKill(bb, int0)((bb)->dfinfo->exit[((int) 0)].kill)); |
| 138 | |
| 139 | for (i=0; i<foamArgc(seq)((seq)->hdr.argc); i++) { |
| 140 | Foam stmt = seq->foamSeq.argv[i]; |
| 141 | ylFlowFillGenKillStmt(bb, stmt, dfFwdGen(bb)((bb)->dfinfo->gen), dfFwdKill(bb, int0)((bb)->dfinfo->exit[((int) 0)].kill)); |
| 142 | |
| 143 | Bitv chk = bitvNew(ylProgState->bitvClass); |
| 144 | bitvClearAll(ylProgState->bitvClass, chk); |
| 145 | bitvAnd(ylProgState->bitvClass, chk, dfFwdGen(bb)((bb)->dfinfo->gen), dfFwdKill(bb, int0)((bb)->dfinfo->exit[((int) 0)].kill)); |
| 146 | assert(0 == bitvCount(ylProgState->bitvClass, chk))do { if (!(0 == bitvCount(ylProgState->bitvClass, chk))) _do_assert (("0 == bitvCount(ylProgState->bitvClass, chk)"),"yldlocs.c" ,146); } while (0); |
| 147 | bitvFree(chk); |
| 148 | } |
| 149 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, " BB Done - Gen %pAIntList\n", bitvToAIntList(ylProgState->bitvClass, dfFwdGen(bb)((bb)->dfinfo->gen))); |
| 150 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, " BB Done - Kill %pAIntList)\n", bitvToAIntList(ylProgState->bitvClass, dfFwdKill(bb, int0)((bb)->dfinfo->exit[((int) 0)].kill))); |
| 151 | } |
| 152 | |
| 153 | localstatic void |
| 154 | ylFlowFillGenKillStmt(BBlock bb, Foam stmt, Bitv gen, Bitv kill) |
| 155 | { |
| 156 | switch (foamTag(stmt)((stmt)->hdr.tag)) { |
| 157 | case FOAM_Set: |
| 158 | case FOAM_Def: |
| 159 | ylSet(bb, stmt->foamSet.lhs, gen, kill); |
| 160 | break; |
| 161 | case FOAM_Yield: |
| 162 | ylYield(bb, stmt, gen, kill); |
| 163 | break; |
| 164 | default: |
| 165 | break; |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | localstatic void |
| 170 | ylSet(BBlock bb, Foam lhs, Bitv gen, Bitv kill) |
| 171 | { |
| 172 | if (foamTag(lhs)((lhs)->hdr.tag) == FOAM_Values) { |
| 173 | foamIter(lhs, v, {{ { String argf = (foamInfoTable [(int)(((lhs)->hdr.tag))- (int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((lhs )->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if (*argf == 'C') { Foam *v = (Foam *) ((lhs)->foamGen.argv) +_i; { { ylSet(bb, *v, gen, kill); }; }; } } }; } |
| 174 | ylSet(bb, *v, gen, kill);{ { String argf = (foamInfoTable [(int)(((lhs)->hdr.tag))- (int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((lhs )->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if (*argf == 'C') { Foam *v = (Foam *) ((lhs)->foamGen.argv) +_i; { { ylSet(bb, *v, gen, kill); }; }; } } }; } |
| 175 | }){ { String argf = (foamInfoTable [(int)(((lhs)->hdr.tag))- (int)FOAM_START]).argf; Length _i; for (_i = 0; _i < ((lhs )->hdr.argc); _i++, argf++) { if (*argf == '*') argf--; if (*argf == 'C') { Foam *v = (Foam *) ((lhs)->foamGen.argv) +_i; { { ylSet(bb, *v, gen, kill); }; }; } } }; }; |
| 176 | } |
| 177 | if (foamTag(lhs)((lhs)->hdr.tag) == FOAM_Loc) { |
| 178 | bitvClear(bbBitvClass(bb)((((bb)->graph)->bitvClass)), kill, lhs->foamLoc.index); |
| 179 | bitvSet(bbBitvClass(bb)((((bb)->graph)->bitvClass)), gen, lhs->foamLoc.index); |
| 180 | bitvClear(bbBitvClass(bb)((((bb)->graph)->bitvClass)), gen, ylProgState->nLocals + lhs->foamLoc.index); |
| 181 | bitvSet(bbBitvClass(bb)((((bb)->graph)->bitvClass)), kill, ylProgState->nLocals + lhs->foamLoc.index); |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | localstatic void |
| 186 | ylYield(BBlock bb, Foam stmt, Bitv gen, Bitv kill) |
| 187 | { |
| 188 | AInt count = ylProgState->nLocals; |
| 189 | for (int i = count; i < 2*count; i++) { |
| 190 | bitvClear(bbBitvClass(bb)((((bb)->graph)->bitvClass)), kill, i); |
| 191 | bitvSet(bbBitvClass(bb)((((bb)->graph)->bitvClass)), gen, i); |
| 192 | } |
| 193 | } |
| 194 | |
| 195 | localstatic void |
| 196 | ylComputeResult(BBlock bb) |
| 197 | { |
| 198 | Foam code = bb->code; |
| 199 | Bitv bitv = dfFwdIn(bb)((bb)->dfinfo->in); |
| 200 | |
| 201 | for (int i=0; i<foamArgc(code)((code)->hdr.argc); i++) { |
| 202 | Foam stmt = code->foamSeq.argv[i]; |
| 203 | ylFindUses(bb, bitv, stmt); |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | localstatic void |
| 208 | ylFindUses(BBlock bb, Bitv bitv, Foam foam) |
| 209 | { |
| 210 | switch (foamTag(foam)((foam)->hdr.tag)) { |
| 211 | case FOAM_Set: |
| 212 | case FOAM_Def: |
| 213 | // NB: Evaluation order |
| 214 | ylFindUses(bb, bitv, foam->foamSet.rhs); |
| 215 | ylFindUsesLhs(bb, bitv, foam->foamSet.lhs); |
| 216 | break; |
| 217 | case FOAM_Loc: |
| 218 | ylCheckLoc(bb, bitv, foam->foamLoc.index); |
| 219 | break; |
| 220 | case FOAM_Yield: |
| 221 | ylFindUses(bb, bitv, foam->foamYield.value); |
| 222 | for (int i=0; i<ylProgState->nLocals; i++) { |
| 223 | bitvSet(bbBitvClass(bb)((((bb)->graph)->bitvClass)), bitv, ylProgState->nLocals + i); |
| 224 | } |
| 225 | break; |
| 226 | default: |
| 227 | foamIter(foam, expr, ylFindUses(bb, bitv, *expr)){ { 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 *expr = (Foam *) ((foam)->foamGen.argv )+_i; { ylFindUses(bb, bitv, *expr); }; } } }; }; |
| 228 | } |
| 229 | } |
| 230 | |
| 231 | localstatic void |
| 232 | ylFindUsesLhs(BBlock bb, Bitv bitv, Foam foam) |
| 233 | { |
| 234 | switch (foamTag(foam)((foam)->hdr.tag)) { |
| 235 | case FOAM_Values: |
| 236 | foamIter(foam, e, ylFindUsesLhs(bb, bitv, *e)){ { 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 *e = (Foam *) ((foam)->foamGen.argv )+_i; { ylFindUsesLhs(bb, bitv, *e); }; } } }; }; |
| 237 | break; |
| 238 | case FOAM_Loc: |
| 239 | bitvSet(ylProgState->bitvClass, bitv, foam->foamLoc.index); |
| 240 | bitvClear(ylProgState->bitvClass, bitv, ylProgState->nLocals + foam->foamLoc.index); |
| 241 | break; |
| 242 | default: |
| 243 | foamIter(foam, expr, ylFindUses(bb, bitv, *expr)){ { 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 *expr = (Foam *) ((foam)->foamGen.argv )+_i; { ylFindUses(bb, bitv, *expr); }; } } }; }; |
| 244 | } |
| 245 | } |
| 246 | |
| 247 | |
| 248 | localstatic void |
| 249 | ylCheckLoc(BBlock bb, Bitv bitv, AInt idx) |
| 250 | { |
| 251 | Bool live = bitvTest(ylProgState->bitvClass, bitv, idx); |
| 252 | Bool yld = bitvTest(ylProgState->bitvClass, bitv, idx + ylProgState->nLocals); |
| 253 | |
| 254 | if (live && yld) { |
| 255 | ylMarkLoc(ylProgState, idx); |
| 256 | } |
| 257 | } |
| 258 | |
| 259 | localstatic void |
| 260 | ylMarkLoc(YlState state, AInt idx) |
| 261 | { |
| 262 | ylDEBUGif (!ylDebug) { } else afprintf(dbOut, "Marking loc %d\n", idx); |
| 263 | bitvSet(state->bitvClass, state->result, idx); |
| 264 | } |
| 265 | |
| 266 | localstatic YlState |
| 267 | ylStateNew(Foam prog, FlowGraph flog, int nLocals) |
| 268 | { |
| 269 | YlState state = (YlState) stoAlloc(OB_Other0, sizeof(*state)); |
| 270 | state->nLocals = nLocals; |
| 271 | state->prog = prog; |
| 272 | state->flog = flog; |
| 273 | state->bitvClass = bitvClassCreate(2*nLocals); |
| 274 | state->result = bitvNew(state->bitvClass); |
| 275 | bitvClearAll(state->bitvClass, state->result); |
| 276 | return state; |
| 277 | } |
| 278 | |
| 279 | localstatic void |
| 280 | ylStateFree(YlState state) |
| 281 | { |
| 282 | bitvClassDestroy(state->bitvClass); |
| 283 | stoFree(state); |
| 284 | } |
| 285 | |
| 286 | localstatic YldLocResult |
| 287 | ylLocResultFrState(YlState state) |
| 288 | { |
| 289 | YldLocResult result = (YldLocResult) stoAlloc(OB_Other0, sizeof(*result)); |
| 290 | AIntList reclocs = listNil(AInt)((AIntList) 0); |
| 291 | AIntList locs = listNil(AInt)((AIntList) 0); |
| 292 | |
| 293 | for (int i=0; i<state->nLocals; i++) { |
| 294 | if (bitvTest(state->bitvClass, state->result, i)) |
| 295 | reclocs = listCons(AInt)(AInt_listPointer->Cons)(i, reclocs); |
| 296 | else |
| 297 | locs = listCons(AInt)(AInt_listPointer->Cons)(i, locs); |
| 298 | } |
| 299 | result->reclocs = listNReverse(AInt)(AInt_listPointer->NReverse)(reclocs); |
| 300 | result->locs = listNReverse(AInt)(AInt_listPointer->NReverse)(locs); |
| 301 | |
| 302 | return result; |
| 303 | } |
| 304 | |
| 305 | void |
| 306 | ylLocResultFree(YldLocResult result) |
| 307 | { |
| 308 | listFree(AInt)(AInt_listPointer->Free)(result->locs); |
| 309 | listFree(AInt)(AInt_listPointer->Free)(result->reclocs); |
| 310 | stoFree(result); |
| 311 | } |