#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;
struct LoopList *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) {
                    CError_ASSERT(462, 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) {
                    CError_ASSERT(474, 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 {
                    CError_ASSERT(505, 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 & fIsBranch) &&
            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 & fIsRead) {
                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 & fIsWrite) {
                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);
}