From 25bab8b1fb2fc851ea3f1f630b3de65ca6afdc22 Mon Sep 17 00:00:00 2001 From: Ash Wolf Date: Wed, 14 Dec 2022 00:16:59 +0000 Subject: haha it's been a while since i last committed, hasn't it --- compiler_and_linker/unsorted/LoopDetection.c | 889 +++++++++++++++++++++++++++ 1 file changed, 889 insertions(+) (limited to 'compiler_and_linker/unsorted/LoopDetection.c') diff --git a/compiler_and_linker/unsorted/LoopDetection.c b/compiler_and_linker/unsorted/LoopDetection.c index e69de29..54bc180 100644 --- a/compiler_and_linker/unsorted/LoopDetection.c +++ b/compiler_and_linker/unsorted/LoopDetection.c @@ -0,0 +1,889 @@ +#include "compiler/LoopDetection.h" +#include "compiler/CFunc.h" +#include "compiler/PCode.h" +#include "compiler/TOC.h" +#include "compiler/UseDefChains.h" +#include "compiler/CompilerTools.h" +#include "compiler/BitVectors.h" +#include "compiler/enode.h" +#include "compiler/objects.h" + +Loop *loopsinflowgraph; +int loopdetection_nblocks; +static UInt32 **dominators; +static BlockList *loopheaders; +static int nloopheaders; +static PCodeBlock **loopstack; +BitVector *LoopTemp; +void *LoopList_First; + +static void computedominators(void) { + int i; + PCodeBlock *block; + int blockCount; + int flag; + UInt32 *myvec; + PCLink *link; + + blockCount = pcblockcount; + flag = 1; + + dominators = oalloc(sizeof(UInt32 *) * pcblockcount); + for (i = 0; i < pcblockcount; i++) + dominators[i] = oalloc(4 * ((blockCount + 31) >> 5)); + + myvec = oalloc(4 * ((blockCount + 31) >> 5)); + + bitvectorinitialize(dominators[pcbasicblocks->blockIndex], blockCount, 0); + //dominators[pcbasicblocks->blockIndex][0] |= 1; + bitvectorsetbit(0, dominators[pcbasicblocks->blockIndex]); + + for (block = pcbasicblocks->nextBlock; block; block = block->nextBlock) + bitvectorinitialize(dominators[block->blockIndex], blockCount, 0xFFFFFFFF); + + computedepthfirstordering(); + + while (flag) { + flag = 0; + for (i = 0; i < pcblockcount; i++) { + block = depthfirstordering[i]; + if (block && block->blockIndex != pcbasicblocks->blockIndex) { + bitvectorcopy(myvec, dominators[block->predecessors->block->blockIndex], blockCount); + for (link = block->predecessors->nextLink; link; link = link->nextLink) + bitvectorintersect(myvec, dominators[link->block->blockIndex], blockCount); + //myvec[block->blockIndex >> 5] |= 1 << (block->blockIndex & 31); + bitvectorsetbit(block->blockIndex, myvec); + + if (bitvectorchanged(dominators[block->blockIndex], myvec, blockCount)) + flag = 1; + } + } + } +} + +static BlockList *findloopheaders(void) { + PCodeBlock *block; + PCLink *link; + BlockList *list; + + loopheaders = NULL; + nloopheaders = 0; + + for (block = pcbasicblocks->nextBlock; block; block = block->nextBlock) { + for (link = block->predecessors; link; link = link->nextLink) { + //if ((1 << (block->blockIndex & 31)) & dominators[link->block->blockIndex][block->blockIndex >> 5]) + if (bitvectorgetbit(block->blockIndex, dominators[link->block->blockIndex])) + break; + } + + if (link) { + list = oalloc(sizeof(BlockList)); + list->block = block; + list->next = loopheaders; + loopheaders = list; + nloopheaders++; + } + } + + return loopheaders; +} + +void addblocktoloop(Loop *loop, PCodeBlock *block) { + BlockList *list = lalloc(sizeof(BlockList)); + + //loop->memberblocks[block->blockIndex >> 5] |= 1 << (block->blockIndex & 31); + bitvectorsetbit(block->blockIndex, loop->memberblocks); + + list->block = block; + list->next = loop->blocks; + loop->blocks = list; +} + +static void findnaturalloop(Loop *loop) { + BlockList *list; + BlockList *list2; + PCLink *link; + PCodeBlock *block; + int i; + + i = 0; + addblocktoloop(loop, loop->body); + for (link = loop->body->predecessors; link; link = link->nextLink) { + if (bitvectorgetbit(loop->body->blockIndex, dominators[link->block->blockIndex]) && link->block != loop->body) { + addblocktoloop(loop, link->block); + loopstack[i++] = link->block; + } + } + + while (i) { + link = loopstack[--i]->predecessors; + while (link) { + if (!bitvectorgetbit(link->block->blockIndex, loop->memberblocks)) { + addblocktoloop(loop, link->block); + loopstack[i++] = link->block; + } + link = link->nextLink; + } + } + + for (list = loop->blocks; list; list = list->next) { + block = list->block; + for (link = block->successors; link; link = link->nextLink) { + if (!bitvectorgetbit(link->block->blockIndex, loop->memberblocks)) { + bitvectorsetbit(block->blockIndex, loop->vec24); + break; + } + } + } + + for (list = loop->blocks; list; list = list->next) { + for (list2 = loop->blocks; list2; list2 = list2->next) { + if (bitvectorgetbit(list2->block->blockIndex, loop->vec24) && + !bitvectorgetbit(list->block->blockIndex, dominators[list2->block->blockIndex])) + break; + } + + if (!list2) + bitvectorsetbit(list->block->blockIndex, loop->vec28); + } + + for (list = loop->blocks; list; list = list->next) { + for (link = loop->body->predecessors; link; link = link->nextLink) { + if (bitvectorgetbit(link->block->blockIndex, loop->memberblocks) && + !bitvectorgetbit(list->block->blockIndex, dominators[link->block->blockIndex])) + break; + } + + if (!link) + bitvectorsetbit(list->block->blockIndex, loop->vec2C); + } +} + +static void addlooptolist(Loop *loop, Loop **list) { + Loop **scan; + Loop *scanloop; + + scan = list; + while ((scanloop = *scan)) { + if (bitvectorgetbit(loop->body->blockIndex, scanloop->memberblocks)) { + loop->parent = scanloop; + addlooptolist(loop, &scanloop->children); + return; + } + + if (bitvectorgetbit(scanloop->body->blockIndex, loop->memberblocks)) { + *scan = scanloop->nextSibling; + scanloop->parent = loop; + scanloop->nextSibling = loop->children; + loop->children = scanloop; + } else { + scan = &scanloop->nextSibling; + } + } + + loop->nextSibling = *list; + *list = loop; +} + +static void findnaturalloops(void) { + Loop *loop; + int size; + + loopdetection_nblocks = pcblockcount + 5 * nloopheaders; + loopstack = oalloc(sizeof(PCodeBlock *) * pcblockcount); + while (loopheaders) { + loop = lalloc(sizeof(Loop)); + loop->parent = loop->nextSibling = loop->children = NULL; + loop->body = loopheaders->block; + loop->preheader = NULL; + loop->blocks = NULL; + loop->basicInductionVars = NULL; + loop->footer = NULL; + loop->pc18 = NULL; + loop->loopWeight = loop->body->loopWeight; + + bitvectorinitialize(loop->memberblocks = lalloc(4 * ((loopdetection_nblocks + 31) >> 5)), loopdetection_nblocks, 0); + bitvectorinitialize(loop->vec24 = lalloc(4 * ((loopdetection_nblocks + 31) >> 5)), loopdetection_nblocks, 0); + bitvectorinitialize(loop->vec28 = lalloc(4 * ((loopdetection_nblocks + 31) >> 5)), loopdetection_nblocks, 0); + bitvectorinitialize(loop->vec2C = lalloc(4 * ((loopdetection_nblocks + 31) >> 5)), loopdetection_nblocks, 0); + + findnaturalloop(loop); + addlooptolist(loop, &loopsinflowgraph); + + loopheaders = loopheaders->next; + } +} + +static PCodeBlock *makepreheaderblock(void) { + PCodeLabel *label; + PCodeBlock *block; + + label = makepclabel(); + block = lalloc(sizeof(PCodeBlock)); + block->nextBlock = NULL; + block->prevBlock = NULL; + block->labels = NULL; + block->successors = NULL; + block->predecessors = NULL; + block->firstPCode = block->lastPCode = NULL; + block->pcodeCount = 0; + block->flags = 0; + block->blockIndex = pcblockcount++; + pclabel(block, label); + return block; +} + +static void insertpreheaderbefore(PCodeBlock *a, PCodeBlock *b) { + a->nextBlock = b; + a->prevBlock = b->prevBlock; + b->prevBlock->nextBlock = a; + b->prevBlock = a; +} + +void insertpreheaderblock(Loop *loop) { + PCodeBlock *preheader; + PCodeBlock *block29; + PCodeBlock *block28; + PCode *pcode27; + PCLink *link; // r26 + PCLink **linkptr; // r25 + PCodeLabel *newlabel; // r23 + PCLink *innerlink; + PCodeBlock *block; + PCodeArg *arg; + int i; + + preheader = loop->preheader = makepreheaderblock(); + block29 = NULL; + block28 = loop->body; + + if (!block28->labels) + pclabel(block28, makepclabel()); + + appendpcode(preheader, makepcode(PC_B, block28->labels)); + preheader->loopWeight = loop->parent ? loop->parent->loopWeight : 1; + + linkptr = &block28->predecessors; + while ((link = *linkptr)) { + if (bitvectorgetbit(link->block->blockIndex, loop->memberblocks)) { + linkptr = &link->nextLink; + } else { + if (link->block->pcodeCount) { + pcode27 = link->block->lastPCode; + if (pcode27->op == PC_B) { +#line 462 + CError_ASSERT(pcode27->args[0].kind == PCOp_LABEL); + if (pcode27->args[0].data.label.label->block == block28) + pcode27->args[0].data.label.label = preheader->labels; + } else if (pcode27->op == PC_BT || pcode27->op == PC_BF) { +#line 474 + CError_ASSERT(pcode27->args[2].kind == PCOp_LABEL); + if (pcode27->args[2].data.label.label->block == block28) + pcode27->args[2].data.label.label = preheader->labels; + } else if (pcode27->op == PC_BCTR) { + if (pcode27->argCount > 1 && pcode27->args[1].kind == PCOp_MEMORY) { + Object *obj = pcode27->args[1].data.mem.obj; + PCodeLabel **array = (PCodeLabel **) obj->u.data.u.switchtable.data; + int i; + for (i = 0; i < obj->u.data.u.switchtable.size; i++) { + if (array[i]->block == block28) + array[i] = preheader->labels; + } + } else { + CodeLabelList *cll; + for (cll = codelabellist; cll; cll = cll->next) { + if (cll->label->pclabel->block == block28) + cll->label->pclabel = preheader->labels; + } + } + } else { +#line 505 + CError_ASSERT(link->block->nextBlock == block28); + } + } + + for (innerlink = link->block->successors; innerlink; innerlink = innerlink->nextLink) { + if (innerlink->block == block28) + innerlink->block = preheader; + } + + *linkptr = link->nextLink;; + link->nextLink = preheader->predecessors; + preheader->predecessors = link; + } + } + + if (!bitvectorgetbit(block28->prevBlock->blockIndex, loop->memberblocks)) { + insertpreheaderbefore(preheader, block28); + + if ( + (!block28->nextBlock || !bitvectorgetbit(block28->nextBlock->blockIndex, loop->memberblocks)) && + block28->lastPCode && + (block28->lastPCode->flags & fPCodeFlag1) && + block28->lastPCode->op != PC_BDNZ + ) { + i = block28->lastPCode->argCount; + arg = block28->lastPCode->args; + while (i && arg->kind != PCOp_LABEL) { + arg++; + i--; + } + + if (i && arg->kind == PCOp_LABEL && arg->data.label.label->block == block28) { + block29 = makepreheaderblock(); + insertpreheaderbefore(block29, block28); + newlabel = makepclabel(); + pclabel(block29, newlabel); + arg->data.label.label = newlabel; + + link = lalloc(sizeof(PCLink)); + link->block = block28; + link->nextLink = block29->predecessors; + block29->predecessors = link; + + link = lalloc(sizeof(PCLink)); + link->block = block28; + link->nextLink = block29->successors; + block29->successors = link; + + for (link = block28->successors; link; link = link->nextLink) { + if (link->block == block28) + link->block = block29; + } + for (link = block28->predecessors; link; link = link->nextLink) { + if (link->block == block28) + link->block = block29; + } + + bitvectorsetbit(block29->blockIndex, loop->vec2C); + addblocktoloop(loop, block29); + } + } + } else { + for (block = pcbasicblocks; block; block = block->nextBlock) { + if (bitvectorgetbit(block->blockIndex, loop->memberblocks)) + break; + } + insertpreheaderbefore(preheader, block); + } + + link = lalloc(sizeof(PCLink)); + link->block = preheader; + link->nextLink = block28->predecessors; + block28->predecessors = link; + + link = lalloc(sizeof(PCLink)); + link->block = block28; + link->nextLink = preheader->successors; + preheader->successors = link; + + for (loop = loop->parent; loop; loop = loop->parent) { + addblocktoloop(loop, preheader); + if (bitvectorgetbit(block28->blockIndex, loop->vec28)) { + bitvectorsetbit(preheader->blockIndex, loop->vec28); + if (block29) + bitvectorsetbit(block29->blockIndex, loop->vec28); + } + if (bitvectorgetbit(block28->blockIndex, loop->vec2C)) { + bitvectorsetbit(preheader->blockIndex, loop->vec2C); + if (block29) + bitvectorsetbit(block29->blockIndex, loop->vec2C); + } + } +} + +static void insertpreheaderblocks(Loop *loop) { + while (loop) { + if (loop->children) + insertpreheaderblocks(loop->children); + insertpreheaderblock(loop); + loop = loop->nextSibling; + } +} + +void findloopsinflowgraph(void) { + loopsinflowgraph = NULL; + computedominators(); + if (findloopheaders()) { + findnaturalloops(); + insertpreheaderblocks(loopsinflowgraph); + } + freeoheap(); +} + +static int checklooplimits(SInt32 opcode, SInt32 condition, SInt32 c, SInt32 d, SInt32 addend, SInt32 *result) { + if (opcode == PC_BT) { + if (condition == 0) { + if (addend <= 0) + return 0; + if (c < d) + *result = (d - c + addend - 1) / addend; + else + *result = 0; + } else if (condition == 1) { + if (addend >= 0) + return 0; + if (c > d) + *result = (c - d - addend - 1) / -addend; + else + *result = 0; + } else { + return 0; + } + } else { + if (condition == 0) { + if (addend >= 0) + return 0; + if (c >= d) + *result = (c - d - addend) / -addend; + else + *result = 0; + } else if (condition == 1) { + if (addend <= 0) + return 0; + if (c <= d) + *result = (d - c + addend) / addend; + else + *result = 0; + } else if (c < d) { + if (addend <= 0) + return 0; + if ((d - c) % addend) + return 0; + *result = (d - c) / addend; + } else if (c > d) { + if (addend >= 0) + return 0; + if ((c - d) % -addend) + return 0; + *result = (c - d) / -addend; + } else { + *result = 0; + } + } + + return 1; +} + +static int checkunsignedlooplimits(SInt32 opcode, SInt32 condition, UInt32 c, UInt32 d, SInt32 addend, UInt32 *result) { + if (opcode == PC_BT) { + if (condition == 0) { + if (addend <= 0) + return 0; + if (c < d) + *result = (d - c + addend - 1) / addend; + else + *result = 0; + } else if (condition == 1) { + if (addend >= 0) + return 0; + if (c > d) + *result = (c - d - addend - 1) / -addend; + else + *result = 0; + } else { + return 0; + } + } else { + if (condition == 0) { + if (addend >= 0) + return 0; + if (c >= d) + *result = (c - d - addend) / -addend; + else + *result = 0; + } else if (condition == 1) { + if (addend <= 0) + return 0; + if (c <= d) + *result = (d - c + addend) / addend; + else + *result = 0; + } else if (c < d) { + if (addend <= 0) + return 0; + if ((d - c) % addend) + return 0; + *result = (d - c) / addend; + } else if (c > d) { + if (addend >= 0) + return 0; + if ((c - d) % -addend) + return 0; + *result = (c - d) / -addend; + } else { + *result = 0; + } + } + + return (*result & 0x80000000) == 0; +} + +static int checkunknownloop(int a, int b, int c, unsigned char *op) { + if (a == PC_BT) { + if (b == 0) { + if (c <= 0) + return 0; + *op = ELESS; + } else if (b == 1) { + if (c >= 0) + return 0; + *op = EGREATER; + } else { + return 0; + } + } else { + if (b == 0) { + if (c >= 0) + return 0; + *op = EGREATEREQU; + } else if (b == 1) { + if (c <= 0) + return 0; + *op = ELESSEQU; + } else if (c == 1) { + *op = ENOTEQU; + } else if (c == -1) { + *op = ENOTEQU; + } else { + return 0; + } + } + + return 1; +} + +static void checkcountingloop(Loop *loop) { + RegUseOrDef *list; + PCode *lastpcode; + PCode *prevpcode; + PCode *pc8; + PCode *check; + short op12; + short reg11; + SInt16 reg4; + short reg11b; + Loop *child; + + if (!(lastpcode = loop->body->lastPCode)) + return; + if (lastpcode->op != PC_BT && lastpcode->op != PC_BF) + return; + if (lastpcode->args[2].kind != PCOp_LABEL) + return; + + if (!bitvectorgetbit(lastpcode->args[2].data.label.label->block->blockIndex, loop->memberblocks)) + return; + if (bitvectorgetbit(loop->body->nextBlock->blockIndex, loop->memberblocks)) + return; + + reg11 = lastpcode->args[0].data.reg.reg; + reg4 = lastpcode->args[1].data.imm.value; + prevpcode = lastpcode->prevPCode; + if (!prevpcode) + return; + + op12 = prevpcode->op; + if (op12 == PC_ADDI && prevpcode->args[2].kind == PCOp_IMMEDIATE) { + pc8 = prevpcode; + prevpcode = prevpcode->prevPCode; + if (!prevpcode) + return; + + op12 = prevpcode->op; + if (pc8->args[0].data.reg.reg != pc8->args[1].data.reg.reg) + return; + if (op12 != PC_CMP && op12 != PC_CMPL && op12 != PC_CMPI && op12 != PC_CMPLI) + return; + if (prevpcode->args[1].data.reg.reg == pc8->args[0].data.reg.reg) + return; + if ((loop->step = pc8->args[2].data.imm.value) == 0) + return; + } + + if (op12 != PC_CMP && op12 != PC_CMPL && op12 != PC_CMPI && op12 != PC_CMPLI) + return; + + if (prevpcode->args[0].data.reg.reg != reg11) + return; + + reg11b = prevpcode->args[1].data.reg.reg; + if (reg11b < 32) + return; + + if (loop->preheader->nextBlock != lastpcode->args[2].data.label.label->block) + return; + + if (op12 == PC_CMPI) { + if (prevpcode->prevPCode) + return; + loop->upper = prevpcode->args[2].data.imm.value; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if (op12 == PC_CMPLI) { + if (prevpcode->prevPCode) + return; + loop->upper = prevpcode->args[2].data.imm.value & 0xFFFF; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if (op12 == PC_CMP || op12 == PC_CMPL) { + if (prevpcode->prevPCode) { + if ( + prevpcode->prevPCode->op == PC_LI && + prevpcode->prevPCode->args[1].kind == PCOp_IMMEDIATE && + prevpcode->prevPCode->args[0].data.reg.reg == prevpcode->args[2].data.reg.reg && + !prevpcode->prevPCode->prevPCode + ) { + loop->upper = prevpcode->prevPCode->args[1].data.imm.value; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if ( + prevpcode->prevPCode->op == PC_LIS && + prevpcode->prevPCode->args[1].kind == PCOp_IMMEDIATE && + prevpcode->prevPCode->args[0].data.reg.reg == prevpcode->args[2].data.reg.reg && + !prevpcode->prevPCode->prevPCode + ) { + loop->upper = prevpcode->prevPCode->args[1].data.imm.value << 16; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if ( + prevpcode->prevPCode->op == PC_ADDI && + prevpcode->prevPCode->args[2].kind == PCOp_IMMEDIATE && + prevpcode->prevPCode->args[0].data.reg.reg == prevpcode->args[2].data.reg.reg && + prevpcode->prevPCode->args[1].data.reg.reg == prevpcode->args[2].data.reg.reg && + prevpcode->prevPCode->prevPCode && + prevpcode->prevPCode->prevPCode->op == PC_LIS && + prevpcode->prevPCode->prevPCode->args[1].kind == PCOp_IMMEDIATE && + prevpcode->prevPCode->prevPCode->args[0].data.reg.reg == prevpcode->args[2].data.reg.reg && + !prevpcode->prevPCode->prevPCode->prevPCode + ) { + loop->upper = prevpcode->prevPCode->args[2].data.imm.value + + (prevpcode->prevPCode->prevPCode->args[1].data.imm.value << 16); + loop->upperType = LOOP_BOUND_CONSTANT; + } else { + return; + } + } else { + pc8 = NULL; + for (list = reg_Defs[RegClass_GPR][prevpcode->args[2].data.reg.reg]; list; list = list->next) { + if (bitvectorgetbit(Defs[list->id].pcode->block->blockIndex, loop->memberblocks)) + return; + } + for (list = reg_Defs[RegClass_GPR][prevpcode->args[2].data.reg.reg]; list; list = list->next) { + if (bitvectorgetbit(list->id, usedefinfo[loop->preheader->blockIndex].defvec8)) { + if (!pc8) { + pc8 = Defs[list->id].pcode; + if ( + pc8->op == PC_LI && + pc8->args[1].kind == PCOp_IMMEDIATE + ) { + loop->upper = pc8->args[1].data.imm.value; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if ( + pc8->op == PC_LIS && + pc8->args[1].kind == PCOp_IMMEDIATE + ) { + loop->upper = pc8->args[1].data.imm.value << 16; + loop->upperType = LOOP_BOUND_CONSTANT; + } else if ( + pc8->op == PC_ADDI && + pc8->args[2].kind == PCOp_IMMEDIATE && + pc8->args[1].data.reg.reg == prevpcode->args[2].data.reg.reg && + pc8->prevPCode && + pc8->prevPCode->op == PC_LIS && + pc8->prevPCode->args[1].kind == PCOp_IMMEDIATE && + pc8->prevPCode->args[0].data.reg.reg == prevpcode->args[2].data.reg.reg + ) { + loop->upper = pc8->args[2].data.imm.value + + (pc8->prevPCode->args[1].data.imm.value << 16); + loop->upperType = LOOP_BOUND_CONSTANT; + } else { + loop->upperType = LOOP_BOUND_VARIABLE; + break; + } + } else { + loop->upperType = LOOP_BOUND_VARIABLE; + break; + } + } + } + + if (loop->upperType == LOOP_BOUND_INDETERMINATE) + loop->upperType = LOOP_BOUND_VARIABLE; + } + } + + pc8 = NULL; + + for (list = reg_Defs[RegClass_GPR][reg11b]; list; list = list->next) { + check = Defs[list->id].pcode; + if (bitvectorgetbit(check->block->blockIndex, loop->memberblocks)) { + if (!pc8) { + pc8 = check; + if (check->op != PC_ADDI) + return; + if (check->args[1].data.reg.reg != reg11b) + return; + if (check->args[2].kind != PCOp_IMMEDIATE) + return; + if ((loop->step = check->args[2].data.imm.value) == 0) + return; + } else { + return; + } + } + } + + if (!pc8) + return; + + if (pc8->block != prevpcode->block && !bitvectorgetbit(prevpcode->block->blockIndex, loop->vec2C)) + return; + + if (loop->children) { + for (child = loop->children; child; child = child->nextSibling) { + if (bitvectorgetbit(pc8->block->blockIndex, child->memberblocks)) + return; + } + } + + loop->pc18 = pc8; + + pc8 = NULL; + + for (list = reg_Defs[RegClass_GPR][reg11b]; list; list = list->next) { + if (bitvectorgetbit(list->id, usedefinfo[loop->preheader->blockIndex].defvec8)) { + if (!pc8) { + pc8 = Defs[list->id].pcode; + if ( + pc8->op == PC_LI && + pc8->args[1].kind == PCOp_IMMEDIATE + ) { + loop->lower = pc8->args[1].data.imm.value; + loop->lowerType = LOOP_BOUND_CONSTANT; + } else if ( + pc8->op == PC_LIS && + pc8->args[1].kind == PCOp_IMMEDIATE + ) { + loop->lower = pc8->args[1].data.imm.value << 16; + loop->lowerType = LOOP_BOUND_CONSTANT; + } else if ( + pc8->op == PC_ADDI && + pc8->args[2].kind == PCOp_IMMEDIATE && + pc8->args[1].data.reg.reg == reg11b && + pc8->prevPCode && + pc8->prevPCode->op == PC_LIS && + pc8->prevPCode->args[1].kind == PCOp_IMMEDIATE && + pc8->prevPCode->args[0].data.reg.reg == reg11b + ) { + loop->lower = pc8->args[2].data.imm.value + + (pc8->prevPCode->args[1].data.imm.value << 16); + loop->lowerType = LOOP_BOUND_CONSTANT; + } else { + loop->lowerType = LOOP_BOUND_VARIABLE; + break; + } + } else { + loop->lowerType = LOOP_BOUND_INDETERMINATE; + break; + } + } + } + + if (loop->lowerType == LOOP_BOUND_INDETERMINATE) + loop->lowerType = LOOP_BOUND_VARIABLE; + + if (loop->lowerType == LOOP_BOUND_CONSTANT && loop->upperType == LOOP_BOUND_CONSTANT) { + if (op12 == PC_CMP || op12 == PC_CMPI) { + if (!checklooplimits(lastpcode->op, reg4, loop->lower, loop->upper, loop->step, &loop->iterationCount)) + return; + } else { + if (!checkunsignedlooplimits(lastpcode->op, reg4, loop->lower, loop->upper, loop->step, (UInt32 *) &loop->iterationCount)) + return; + } + loop->isKnownCountingLoop = 1; + } else if (loop->lowerType != LOOP_BOUND_INDETERMINATE || loop->upperType != LOOP_BOUND_INDETERMINATE) { + if (!checkunknownloop(lastpcode->op, reg4, loop->step, &loop->unknownCondition)) + return; + loop->isUnknownCountingLoop = 1; + } +} + +void analyzeForCountableLoops(Loop *loop) { + if (!loop) + return; + + while (loop) { + if (loop->children) + analyzeForCountableLoops(loop->children); + checkcountingloop(loop); + loop = loop->nextSibling; + } +} + +void analyzeloop(Loop *loop) { + BlockList *list; + PCodeBlock *block; + PCode *pcode; + + loop->bodySize = 0; + loop->x4D = 0; + loop->x4E = 0; + loop->x4F = 1; + loop->isKnownCountingLoop = 0; + loop->isUnknownCountingLoop = 0; + loop->lowerType = LOOP_BOUND_INDETERMINATE; + loop->upperType = LOOP_BOUND_INDETERMINATE; + loop->iterationCount = -1; + loop->x57 = 0; + loop->x52 = 0; + + for (list = loop->blocks; list; list = list->next) { + block = list->block; + if (!loop->children) + block->flags |= fPCBlockFlag2000; + loop->bodySize += block->pcodeCount; + + if (block != loop->body) { + if (!block->successors || !block->predecessors || block->successors->nextLink || block->predecessors->nextLink) + loop->x4F = 0; + } + + if ((block->flags & fPCBlockFlag4000) == fPCBlockFlag4000) + loop->x52 = 1; + + for (pcode = block->firstPCode; pcode; pcode = pcode->nextPCode) { + if (PCODE_FLAG_SET_T(pcode) & fLink) + loop->x4D = 1; + + if (pcode->op == PC_BCTRL || pcode->op == PC_BCTR || pcode->op == PC_BCCTR || pcode->op == PC_MTCTR || pcode->op == PC_MFCTR) { + loop->x4E = 1; + } else if (pcode->flags & fPCodeFlag2) { + if (pcode->op == PC_LBZX || pcode->op == PC_LHZX || pcode->op == PC_LHAX || pcode->op == PC_LWZX || pcode->op == PC_LFSX || pcode->op == PC_LFDX) + loop->x53 = 1; + } else if (pcode->flags & fPCodeFlag4) { + if (pcode->op == PC_STBX || pcode->op == PC_STHX || pcode->op == PC_STWX || pcode->op == PC_STFSX || pcode->op == PC_STFDX) + loop->x54 = 1; + } else { + if (pcode->op == PC_EIEIO || pcode->op == PC_SYNC || pcode->op == PC_ISYNC) + loop->x57 = 1; + } + } + } + + if (!loop->children && !loop->x4D && loop->bodySize < 32) { + for (list = loop->blocks; list; list = list->next) + list->block->flags |= fPCBlockFlag2000; + } +} + +static void analyzeloops(Loop *loop) { + while (loop) { + if (loop->children) + analyzeloops(loop->children); + analyzeloop(loop); + loop = loop->nextSibling; + } +} + +void analyzeloopsinflowgraph(void) { + if (loopsinflowgraph) + analyzeloops(loopsinflowgraph); +} + -- cgit v1.2.3