diff options
Diffstat (limited to 'compiler_and_linker/FrontEnd/Optimizer/IroLoop.c')
| -rw-r--r-- | compiler_and_linker/FrontEnd/Optimizer/IroLoop.c | 2324 |
1 files changed, 2324 insertions, 0 deletions
diff --git a/compiler_and_linker/FrontEnd/Optimizer/IroLoop.c b/compiler_and_linker/FrontEnd/Optimizer/IroLoop.c new file mode 100644 index 0000000..850146d --- /dev/null +++ b/compiler_and_linker/FrontEnd/Optimizer/IroLoop.c @@ -0,0 +1,2324 @@ +#include "IroLoop.h" +#include "IroCSE.h" +#include "IroDump.h" +#include "IroFlowgraph.h" +#include "IroLinearForm.h" +#include "IroPropagate.h" +#include "IroSubable.h" +#include "IroUtil.h" +#include "IroVars.h" +#include "compiler/CFunc.h" +#include "compiler/CInt64.h" +#include "compiler/CMachine.h" +#include "compiler/objects.h" +#include "compiler/types.h" + +IRONode *LoopNode; +Boolean ConditionalHeaderAtBottom; +IROLoopInd *FirstInd; +BitVector *InLoop; +IROList IRO_InitLList; +BitVector *InLoop_Exits; +BitVector *InLoop_Tails; +UInt32 LoopExitNumber; +UInt32 LoopTailNum; +IRONode *LoopExitSuccessor; +IRONode *LoopTail; +IROLoopMemRef *IRO_LoopMemRefFirst; +IROLoopMemRef *IRO_LoopMemRefCurrent; +static IROExpr *RisList; +static BitVector *AllKills; +static Boolean KnownBounds; +static SInt32 Times; +static IROLinear *PredInt; +static IROElmList *FirstAddendLinear; +static IROElmList *LastAddendLinear; +static int NoSubableSubs; + +// forward decls +static void MyHandleLoop_Vector(IRONode *fnode); +static void MyHandleLoop_Motion(IRONode *fnode); +static void CheckAllLoopAddresses(IRONode *fnode, BitVector *bv, Boolean *resultFlag); +static void MakeLoopEntry(IROLinear *nd, IROAddrRecord *rec, Boolean mustreach1, Boolean flag2); +static void MoveInvarianceInAddressExpr(void); +static IROLinear *RearrangeInvarianceInAddressExpr(IROLinear *nd, IROList *list); +static UInt32 IsAssignmentReductionCandidate(IROLinear *nd); + +void FindMustReach(void) { + IRONode *fnode; + IRONode *fnode2; + IRONode *pred; + int i; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + fnode->mustreach = 0; + if (Bv_IsBitSet(fnode->index, InLoop)) { + fnode->mustreach = 1; + + for (i = 0; i < LoopNode->numpred; i++) { + pred = IRO_NodeTable[LoopNode->pred[i]]; + if (Bv_IsBitSet(pred->index, InLoop) && !Bv_IsBitSet(fnode->index, pred->dom)) { + fnode->mustreach = 0; + break; + } + } + + for (fnode2 = IRO_FirstNode; fnode2; fnode2 = fnode2->nextnode) { + if (Bv_IsBitSet(fnode2->index, InLoop)) { + for (i = 0; i < fnode2->numsucc; i++) { + if (!Bv_IsBitSet(fnode2->succ[i], InLoop) && !Bv_IsBitSet(fnode->index, fnode2->dom)) { + fnode->mustreach = 0; + break; + } + } + + if (!fnode->mustreach) + break; + } + } + } + } +} + +void FindMustReach1(IRONode *checkfnode) { + IRONode *fnode; + IRONode *fnode2; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop)) { + fnode->mustreach1 = 1; + for (fnode2 = IRO_FirstNode; fnode2; fnode2 = fnode2->nextnode) { + if (Bv_IsBitSet(fnode2->index, InLoop)) { + if (Bv_IsBitSet(fnode2->index, InLoop_Tails) && !Bv_IsBitSet(fnode->index, fnode2->dom)) + fnode->mustreach1 = 0; + + if (Bv_IsBitSet(fnode2->index, InLoop_Exits) && fnode2 != checkfnode && !Bv_IsBitSet(fnode->index, fnode2->dom)) + fnode->mustreach1 = 0; + + if (!fnode->mustreach1) + break; + } + } + } + } +} + +static void IRO_FindLoopTailsAndExits(IRONode *fnode) { + IRONode *scan; + IRONode *succ; + int i; + + for (scan = IRO_FirstNode; scan; scan = scan->nextnode) { + if (Bv_IsBitSet(scan->index, InLoop)) { + for (i = 0; i < scan->numsucc; i++) { + succ = IRO_NodeTable[scan->succ[i]]; + if (succ == fnode) { + Bv_SetBit(scan->index, InLoop_Tails); + LoopTail = scan; + LoopTailNum++; + } + if (!Bv_IsBitSet(succ->index, InLoop)) { + LoopExitNumber++; + LoopExitSuccessor = succ; + Bv_SetBit(scan->index, InLoop_Exits); + } + } + } + } + + IRO_Dump("IRO_FindLoopTailsAndExits:For header %d, Loop exits and loop tails are \n", fnode->index); + IRO_DumpBits("Loop Exits: ", InLoop_Exits); + IRO_DumpBits("Loop Tails: ", InLoop_Tails); + IRO_Dump("LoopExitNum=%d: \n", LoopExitNumber); + if (LoopExitSuccessor) + IRO_Dump("LoopExitSuccessor node =%d: \n", LoopExitSuccessor->index); +} + +static int IsSafeTypcon(IROLinear *nd) { + Type *srcType; + Type *destType; + SInt32 srcSize; + SInt32 destSize; + Boolean srcUnsigned; + Boolean destUnsigned; + + srcType = nd->u.monadic->rtype; + destType = nd->rtype; + if (!IS_TYPE_INT(srcType) || !IS_TYPE_INT(destType)) + return 0; + + srcSize = srcType->size; + destSize = destType->size; + srcUnsigned = IRO_IsUnsignedType(srcType); + destUnsigned = IRO_IsUnsignedType(destType); + + if (srcUnsigned == destUnsigned && destSize >= srcSize) + return 1; + if (srcUnsigned == 1 && destUnsigned == 0 && destSize > srcSize) + return 1; + return 0; +} + +static int Reducable(IROLinear *nd, IROLinear **resultNd1, IROLinear **resultNd2, VarRecord **resultVar) { + IROLinear *indirect; + IROLinear *left; + IROLinear *right; + Boolean leftInvariant; + Boolean rightInvariant; + Boolean leftTypcon; + Boolean rightTypcon; + Object *obj; + ENode *enode; + IROLoopInd *ind; + CInt64 val64; + SInt32 val; + SInt32 div; + + leftInvariant = 0; + rightInvariant = 0; + leftTypcon = 0; + rightTypcon = 0; + + if (nd->type == IROLinearOp2Arg && nd->nodetype == EADD && (IS_TYPE_INT(nd->rtype) || IS_TYPE_POINTER_ONLY(nd->rtype))) { + left = nd->u.diadic.left; + right = nd->u.diadic.right; + if (left->type == IROLinearOp1Arg && left->nodetype == ETYPCON) { + leftTypcon = 1; + leftInvariant = (left->flags & IROLF_LoopInvariant) != 0; + left = left->u.monadic; + } + if (right->type == IROLinearOp1Arg && right->nodetype == ETYPCON) { + rightTypcon = 1; + rightInvariant = (right->flags & IROLF_LoopInvariant) != 0; + right = right->u.monadic; + } + + if (((left->flags & IROLF_LoopInvariant) || leftInvariant) && IRO_IsVariable(right)) { + if (leftInvariant || ((!(obj = IRO_IsVariable(left)) || !IRO_IsRegable(obj)) && !IRO_IsConstant(left))) { + if ( + left->type == IROLinearOp2Arg && + left->nodetype == EADD && + (obj = IRO_IsVariable(left->u.diadic.left)) && + IRO_IsRegable(obj) && + IRO_IsConstant(left->u.diadic.right) + ) + return 0; + + if (rightTypcon) { + if (!IsSafeTypcon(nd->u.diadic.right)) + return 0; + *resultNd2 = nd->u.diadic.right; + } else { + *resultNd2 = right; + } + + indirect = right; + *resultNd1 = IRO_NewLinear(IROLinearOperand); + + enode = IRO_NewENode(EINTCONST); + enode->data.intval = cint64_one; + enode->rtype = nd->u.diadic.right->rtype; + (*resultNd1)->rtype = nd->u.diadic.right->rtype; + (*resultNd1)->u.node = enode; + } else { + return 0; + } + } else if ( + ((left->flags & IROLF_LoopInvariant) || leftInvariant) && + right->type == IROLinearOp2Arg && + !rightTypcon && + (right->nodetype == EMUL || right->nodetype == ESHL) + ) { + if (IRO_IsConstant(right->u.diadic.right)) { + if (right->nodetype == ESHL) { + right->nodetype = EMUL; + right->u.diadic.right->u.node->data.intval = CInt64_Shl(cint64_one, right->u.diadic.right->u.node->data.intval); + } + if (right->u.diadic.left->type == IROLinearOp1Arg) { + if (IRO_IsVariable(right->u.diadic.left)) { + *resultNd2 = right->u.diadic.left; + indirect = right->u.diadic.left; + *resultNd1 = right->u.diadic.right; + } else if (right->u.diadic.left->nodetype == ETYPCON && IRO_IsVariable(right->u.diadic.left->u.monadic)) { + if (!IsSafeTypcon(right->u.diadic.left)) + return 0; + *resultNd2 = right->u.diadic.left; + indirect = right->u.diadic.left->u.monadic; + *resultNd1 = right->u.diadic.right; + } else { + return 0; + } + } else { + return 0; + } + } else { + return 0; + } + } else if ( + ((right->flags & IROLF_LoopInvariant) || rightInvariant) && + left->type == IROLinearOp2Arg && + !leftTypcon && + (left->nodetype == EMUL || left->nodetype == ESHL) + ) { + if (IRO_IsConstant(left->u.diadic.right)) { + if (left->nodetype == ESHL) { + left->nodetype = EMUL; + left->u.diadic.right->u.node->data.intval = CInt64_Shl(cint64_one, left->u.diadic.right->u.node->data.intval); + } + if (left->u.diadic.left->type == IROLinearOp1Arg) { + if (IRO_IsVariable(left->u.diadic.left)) { + *resultNd2 = left->u.diadic.left; + indirect = left->u.diadic.left; + *resultNd1 = left->u.diadic.right; + } else if (left->u.diadic.left->nodetype == ETYPCON && IRO_IsVariable(left->u.diadic.left->u.monadic)) { + if (!IsSafeTypcon(left->u.diadic.left)) + return 0; + *resultNd2 = left->u.diadic.left; + indirect = left->u.diadic.left->u.monadic; + *resultNd1 = left->u.diadic.right; + } else { + return 0; + } + } else { + return 0; + } + } else { + return 0; + } + } else if ( + ((right->flags & IROLF_LoopInvariant) || rightInvariant) && + IRO_IsVariable(left) + ) { + if (rightInvariant || ((!(obj = IRO_IsVariable(right)) || !IRO_IsRegable(obj)) && !IRO_IsConstant(right))) { + if ( + right->type == IROLinearOp2Arg && + right->nodetype == EADD && + (obj = IRO_IsVariable(right->u.diadic.left)) && + IRO_IsRegable(obj) && + IRO_IsConstant(right->u.diadic.right) + ) + return 0; + + if (leftTypcon) { + if (!IsSafeTypcon(nd->u.diadic.left)) + return 0; + *resultNd2 = nd->u.diadic.left; + } else { + *resultNd2 = left; + } + + indirect = left; + *resultNd1 = IRO_NewLinear(IROLinearOperand); + + enode = IRO_NewENode(EINTCONST); + enode->data.intval = cint64_one; + enode->rtype = nd->u.diadic.left->rtype; + (*resultNd1)->rtype = nd->u.diadic.left->rtype; + (*resultNd1)->u.node = enode; + } else { + return 0; + } + } else { + return 0; + } + } else if (nd->type == IROLinearOp2Arg && (nd->nodetype == EMUL || nd->nodetype == ESHL) && nd->rtype->size <= 4 && (IS_TYPE_INT(nd->rtype) || IS_TYPE_POINTER_ONLY(nd->rtype))) { + left = nd->u.diadic.left; + right = nd->u.diadic.right; + + if (IRO_IsConstant(right) && IRO_IsVariable(left)) { + *resultNd2 = left; + indirect = left; + *resultNd1 = right; + } else if (IRO_IsConstant(nd->u.diadic.right) && left->type == IROLinearOp1Arg && left->nodetype == ETYPCON && + IRO_IsVariable(left->u.monadic)) { + if (!IsSafeTypcon(left)) + return 0; + *resultNd2 = left; + indirect = left->u.monadic; + *resultNd1 = right; + } else { + if (nd->type == IROLinearOp2Arg && nd->nodetype == ESHL) + return 0; + + if (nd->u.diadic.right->flags & IROLF_LoopInvariant) { + if (IRO_IsVariable(left)) { + *resultNd2 = left; + indirect = left; + *resultNd1 = right; + } else if (left->type == IROLinearOp1Arg && left->nodetype == ETYPCON && IRO_IsVariable(left->u.monadic)) { + if (!IsSafeTypcon(left)) + return 0; + *resultNd2 = left; + indirect = left->u.monadic; + *resultNd1 = right; + } else { + return 0; + } + } else if (nd->u.diadic.left->flags & IROLF_LoopInvariant) { + if (IRO_IsVariable(right)) { + *resultNd2 = right; + indirect = right; + *resultNd1 = left; + } else if (right->type == IROLinearOp1Arg && right->nodetype == ETYPCON && IRO_IsVariable(right->u.monadic) && nd->type == IROLinearOp2Arg && nd->nodetype == EMUL) { + if (!IsSafeTypcon(right)) + return 0; + *resultNd2 = right; + indirect = right->u.monadic; + *resultNd1 = left; + } else { + return 0; + } + } else { + return 0; + } + } + } else if (nd->type == IROLinearOp2Arg && (nd->nodetype == EDIV || nd->nodetype == ESHR) && nd->rtype->size <= 4 && IS_TYPE_INT(nd->rtype)) { + if (IRO_IsVariable(nd->u.diadic.left) && IRO_IsConstant(nd->u.diadic.right)) { + val64 = nd->u.diadic.right->u.node->data.intval; + if (nd->type == IROLinearOp2Arg && nd->nodetype == ESHR) { + CInt64_GetULong(&val64); + if (CInt64_GetULong(&val64) > 32 || CTool_EndianReadWord32(&val64.hi)) + return 0; + val64 = CInt64_Shl(cint64_one, val64); + } + *resultNd2 = nd->u.diadic.left; + indirect = nd->u.diadic.left; + } else { + return 0; + } + } else { + return 0; + } + + if ( + nd->type == IROLinearOp2Arg && + nd->nodetype == ESHL && + ( + !IRO_IsConstant(*resultNd1) || + (SInt32) CInt64_GetULong(&(*resultNd1)->u.node->data.intval) < 0 || + (SInt32) CInt64_GetULong(&(*resultNd1)->u.node->data.intval) > 32 || + CTool_EndianReadWord32(&(*resultNd1)->u.node->data.intval.hi) + ) + ) + return 0; + + CError_ASSERT(802, indirect->u.monadic->u.node != NULL); + *resultVar = IRO_FindVar(indirect->u.monadic->u.node->data.objref, 0, 1); + if (!*resultVar || (*resultVar)->xA != 2) + return 0; + + if (copts.ANSIstrict || copts.strengthreductionstrict) { + Type *type = (*resultVar)->object->type; + if (IRO_IsUnsignedType(type) && type->size < stunsignedlong.size) + return 0; + } + + if (nd->type == IROLinearOp2Arg && (nd->nodetype == ESHR || nd->nodetype == EDIV)) { + ind = FirstInd; + while (ind && ind->var != *resultVar) + ind = ind->next; + + CError_ASSERT(845, ind != NULL); + + if (ind->addNode == NULL) { + if (ind->addConst < (val = CInt64_GetULong(&val64))) + return 0; + if ((div = ind->addConst / val) <= 0) + return 0; + + *resultNd1 = IRO_NewLinear(IROLinearOperand); + enode = IRO_NewENode(EINTCONST); + CInt64_SetULong(&enode->data.intval, div); + enode->rtype = nd->u.diadic.left->rtype; + (*resultNd1)->rtype = nd->u.diadic.left->rtype; + (*resultNd1)->u.node = enode; + } else { + return 0; + } + } + + return 1; +} + +static void IRO_RemoveExpr_Action(IROLinear *linear, Boolean isFirst) { + if (isFirst && linear->expr) + IRO_RemoveExpr(linear->expr); +} + +static void IRO_ActUnmarkRISCandidate(IROLinear *linear, Boolean isFirst) { + if (isFirst && linear->expr) + linear->flags &= ~IROLF_Ris; +} + +static IROExpr *CreateRIS(IROExpr *expr, IROLinear *nd1, IROLinear *nd2, IROLoopInd *induction, int unk) { + Object *tempObj; + Type *type; + Boolean flag23; + Object *tempObj2; + IROLinear *firstnode; + IROLinear *fourthnode; + IROLinear *fifthnode; + IROLinear *secondnode; + IROLinear *thirdnode; + IROLinear *tmp; + ENode *enode; + IROList list1; + IROList list2; + + flag23 = 0; + type = expr->linear->rtype; + tempObj = create_temp_object(type); + IRO_FindVar(tempObj, 1, 1); + IRO_InitList(&list1); + + if (IS_LINEAR_DIADIC(expr->linear, EADD)) { + firstnode = IRO_DuplicateExpr(expr->linear, &list1); + } else if (IS_LINEAR_DIADIC_2(expr->linear, EDIV, ESHR)) { + firstnode = IRO_DuplicateExpr(expr->linear, &list1); + } else { + firstnode = IRO_NewLinear(IROLinearOp2Arg); + firstnode->index = ++IRO_NumLinear; + firstnode->rtype = type; + firstnode->nodetype = EMUL; + firstnode->u.diadic.left = IRO_DuplicateExpr(nd1, &list1); + if (unk) + firstnode->u.diadic.right = IRO_DuplicateExpr(nd1, &list1); + else + firstnode->u.diadic.right = IRO_DuplicateExpr(nd2, &list1); + IRO_AddToList(firstnode, &list1); + } + + secondnode = IRO_NewLinear(IROLinearOp2Arg); + secondnode->index = ++IRO_NumLinear; + secondnode->rtype = type; + secondnode->nodetype = EASS; + secondnode->u.diadic.left = IRO_TempReference(tempObj, &list1); + secondnode->u.diadic.left->flags |= IROLF_Ind | IROLF_Assigned; + secondnode->u.diadic.left->u.monadic->flags |= IROLF_Ind | IROLF_Assigned; + secondnode->u.diadic.right = firstnode; + IRO_AddToList(secondnode, &list1); + IRO_Paste(list1.head, list1.tail, PredInt); + if ( + !IS_LINEAR_DIADIC_2(expr->linear, EDIV, ESHR) && + induction->addConst != 1 && + (induction->addNode || !IRO_IsConstant(nd2)) + ) { + flag23 = 1; + IRO_InitList(&list1); + thirdnode = IRO_NewLinear(IROLinearOp2Arg); + thirdnode->index = ++IRO_NumLinear; + thirdnode->rtype = nd2->rtype; + thirdnode->nodetype = EMUL; + + if (!induction->addNode) { + thirdnode->u.diadic.left = IRO_DuplicateExpr(nd2, &list1); + thirdnode->u.diadic.right = IRO_NewLinear(IROLinearOperand); + thirdnode->u.diadic.right->index = ++IRO_NumLinear; + enode = IRO_NewENode(EINTCONST); + enode->rtype = nd2->rtype; + thirdnode->u.diadic.right->rtype = nd2->rtype; + CInt64_SetLong(&enode->data.intval, induction->addConst); + thirdnode->u.diadic.right->u.node = enode; + IRO_AddToList(thirdnode->u.diadic.right, &list1); + } else { + thirdnode->u.diadic.left = IRO_DuplicateExpr(nd2, &list1); + thirdnode->u.diadic.right = IRO_DuplicateExpr(induction->addNode, &list1); + if (nd2->rtype != induction->addNode->rtype) { + tmp = IRO_NewLinear(IROLinearOp1Arg); + tmp->nodetype = ETYPCON; + tmp->index = ++IRO_NumLinear; + tmp->rtype = nd2->rtype; + tmp->u.monadic = thirdnode->u.diadic.right; + IRO_AddToList(tmp, &list1); + thirdnode->u.diadic.right = tmp; + } + } + IRO_AddToList(thirdnode, &list1); + + tempObj2 = create_temp_object(nd2->rtype); + + fourthnode = IRO_NewLinear(IROLinearOp2Arg); + fourthnode->index = ++IRO_NumLinear; + fourthnode->rtype = nd2->rtype; + fourthnode->nodetype = EASS; + fourthnode->u.diadic.left = IRO_TempReference(tempObj2, &list1); + fourthnode->u.diadic.left->flags |= IROLF_Ind | IROLF_Assigned; + fourthnode->u.diadic.left->u.monadic->flags |= IROLF_Ind | IROLF_Assigned; + fourthnode->u.diadic.right = thirdnode; + IRO_AddToList(fourthnode, &list1); + IRO_Paste(list1.head, list1.tail, PredInt); + } + + IRO_InitList(&list2); + fifthnode = IRO_NewLinear(IROLinearOp2Arg); + fifthnode->index = ++IRO_NumLinear; + fifthnode->rtype = type; + if (induction->nd->type == IROLinearOp2Arg) { + if (induction->nd->nodetype == EASS && IS_LINEAR_DIADIC(induction->nd->u.diadic.right, EADD)) + fifthnode->nodetype = EADDASS; + else if (induction->nd->nodetype == EASS && IS_LINEAR_DIADIC(induction->nd->u.diadic.right, ESUB)) + fifthnode->nodetype = ESUBASS; + else + fifthnode->nodetype = induction->nd->nodetype; + } else { + if (induction->nd->nodetype == EPREINC || induction->nd->nodetype == EPOSTINC) + fifthnode->nodetype = EADDASS; + else + fifthnode->nodetype = ESUBASS; + } + + fifthnode->u.diadic.left = IRO_TempReference(tempObj, &list2); + fifthnode->u.diadic.left->flags |= IROLF_Ind | IROLF_Used | IROLF_Assigned; + fifthnode->u.diadic.left->u.monadic->flags |= IROLF_Ind | IROLF_Used | IROLF_Assigned; + if (!unk) { + if (!flag23) { + if (induction->addConst == 1 || IS_LINEAR_DIADIC_2(expr->linear, EDIV, ESHR)) { + fifthnode->u.diadic.right = IRO_DuplicateExpr(nd2, &list2); + } else { + fifthnode->u.diadic.right = IRO_NewLinear(IROLinearOperand); + fifthnode->u.diadic.right->index = ++IRO_NumLinear; + enode = IRO_NewENode(EINTCONST); + enode->rtype = nd2->rtype; + fifthnode->u.diadic.right->rtype = nd2->rtype; + CInt64_SetLong(&enode->data.intval, induction->addConst * CInt64_GetULong(&nd2->u.node->data.intval)); + fifthnode->u.diadic.right->u.node = enode; + IRO_AddToList(fifthnode->u.diadic.right, &list2); + } + } else { + fifthnode->u.diadic.right = IRO_TempReference(tempObj2, &list2); + fifthnode->u.diadic.right->flags |= IROLF_Used; + } + } + + fifthnode->index = ++IRO_NumLinear; + IRO_AddToList(fifthnode, &list2); + IRO_Paste(list2.head, list2.tail, IRO_FindStart(induction->nd)); + IRO_WalkTree(expr->linear, IRO_RemoveExpr_Action); + expr->x8 = tempObj; + expr->next = RisList; + RisList = expr; + return expr; +} + +static IRONode *CreatePreHeader(IRONode *fnode1, IRONode *fnode2) { + IROLinear *labelnode; + IRONode *newfnode; + IRONode *iter; + CLabel *oldlabel; + CLabel *newlabel; + SwitchInfo *swinfo; + SwitchCase *swcase; + + newfnode = oalloc(sizeof(IRONode)); + memset(newfnode, 0, sizeof(IRONode)); + newfnode->index = IRO_NumNodes; + IRO_NumNodes++; + + labelnode = IRO_NewLinear(IROLinearLabel); + labelnode->index = IRO_NumLinear++; + labelnode->next = NULL; + labelnode->u.label.label = IRO_NewLabel(); + labelnode->flags |= IROLF_1; + labelnode->u.label.label->stmt = (Statement *) newfnode; + newfnode->first = labelnode; + newfnode->last = labelnode; + + if (fnode2) { + fnode2->last->next = labelnode; + labelnode->next = IRO_NewLinear(IROLinearNop); + labelnode->next->next = fnode1->first; + fnode2->nextnode = newfnode; + newfnode->nextnode = fnode1; + } else { + CError_ASSERT(1254, fnode1->first->type == IROLinearLabel); + labelnode->next = IRO_NewLinear(IROLinearGoto); + labelnode->next->u.label.label = fnode1->first->u.label.label; + IRO_LastNode->last->next = labelnode; + IRO_LastNode->nextnode = newfnode; + IRO_LastNode = newfnode; + IRO_LastLinear = labelnode->next; + } + + newfnode->last = labelnode->next; + + IRO_NodeTable = oalloc(sizeof(IRONode *) * IRO_NumNodes); + memset(IRO_NodeTable, 0, sizeof(IRONode *) * IRO_NumNodes); + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) + IRO_NodeTable[iter->index] = iter; + + if (fnode1->first->type == IROLinearLabel) { + oldlabel = fnode1->first->u.label.label; + newlabel = newfnode->first->u.label.label; + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) { + if (!Bv_IsBitSet(iter->index, InLoop) && iter != newfnode) { + switch (iter->last->type) { + case IROLinearGoto: + if (iter->last->u.label.label == oldlabel) + iter->last->u.label.label = newlabel; + break; + case IROLinearIf: + case IROLinearIfNot: + if (iter->last->u.label.label == oldlabel) + iter->last->u.label.label = newlabel; + break; + case IROLinearSwitch: + swinfo = iter->last->u.swtch.info; + for (swcase = swinfo->cases; swcase; swcase = swcase->next) { + if (swcase->label == oldlabel) + swcase->label = newlabel; + } + if (swinfo->defaultlabel == oldlabel) + swinfo->defaultlabel = newlabel; + break; + } + } + } + } + + IRO_ComputeSuccPred(); + IRO_ComputeDom(); + return newfnode; +} + +static IRONode *CreateNewLoopExitSuccessor(IRONode *fnode1) { + IROLinear *labelnode; + IRONode *fnode2; + IRONode *newfnode; + Boolean flag; + IRONode *iter; + CLabel *oldlabel; + CLabel *newlabel; + SwitchInfo *swinfo; + SwitchCase *swcase; + UInt16 i; + + CError_ASSERT(1355, fnode1 != NULL && LoopExitNumber == 1); + + fnode2 = NULL; + flag = 0; + + for (i = 0; i < fnode1->numpred; i++) { + iter = IRO_NodeTable[fnode1->pred[i]]; + if (Bv_IsBitSet(iter->index, InLoop_Exits)) { + CError_ASSERT(1366, fnode2 == NULL); + fnode2 = iter; + if (!flag) { + if ( + !iter->last || + !fnode1->first || + fnode1->first->type != IROLinearLabel || + ( + (iter->last->type == IROLinearIf || iter->last->type == IROLinearIfNot) && + iter->last->u.label.label != fnode1->first->u.label.label + )) + flag = 1; + } + } + } + + CError_ASSERT(1382, fnode2 != NULL); + + newfnode = oalloc(sizeof(IRONode)); + memset(newfnode, 0, sizeof(IRONode)); + newfnode->index = IRO_NumNodes; + IRO_NumNodes++; + + labelnode = IRO_NewLinear(IROLinearLabel); + labelnode->index = IRO_NumLinear++; + labelnode->next = NULL; + labelnode->u.label.label = IRO_NewLabel(); + labelnode->flags |= IROLF_1; + labelnode->u.label.label->stmt = (Statement *) newfnode; + newfnode->first = labelnode; + newfnode->last = labelnode; + + if (flag) { + fnode2->last->next = labelnode; + labelnode->next = IRO_NewLinear(IROLinearNop); + labelnode->next->next = fnode1->first; + fnode2->nextnode = newfnode; + newfnode->nextnode = fnode1; + } else { + CError_ASSERT(1422, fnode1->first->type == IROLinearLabel); + labelnode->next = IRO_NewLinear(IROLinearGoto); + labelnode->next->u.label.label = fnode1->first->u.label.label; + IRO_LastNode->last->next = labelnode; + IRO_LastNode->nextnode = newfnode; + IRO_LastNode = newfnode; + IRO_LastLinear = labelnode->next; + } + + newfnode->last = labelnode->next; + + IRO_NodeTable = oalloc(sizeof(IRONode *) * IRO_NumNodes); + memset(IRO_NodeTable, 0, sizeof(IRONode *) * IRO_NumNodes); + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) + IRO_NodeTable[iter->index] = iter; + + if (fnode1->first->type == IROLinearLabel) { + oldlabel = fnode1->first->u.label.label; + newlabel = newfnode->first->u.label.label; + switch (fnode2->last->type) { + case IROLinearGoto: + if (fnode2->last->u.label.label == oldlabel) + fnode2->last->u.label.label = newlabel; + break; + case IROLinearIf: + case IROLinearIfNot: + if (fnode2->last->u.label.label == oldlabel) + fnode2->last->u.label.label = newlabel; + break; + case IROLinearSwitch: + swinfo = fnode2->last->u.swtch.info; + for (swcase = swinfo->cases; swcase; swcase = swcase->next) { + if (swcase->label == oldlabel) + swcase->label = newlabel; + } + if (swinfo->defaultlabel == oldlabel) + swinfo->defaultlabel = newlabel; + break; + } + } + + IRO_ComputeSuccPred(); + IRO_ComputeDom(); + return newfnode; +} + +void AddPreds(IRONode *fnode) { + IRONode *pred; + int i; + + for (i = 0; i < fnode->numpred; i++) { + pred = IRO_NodeTable[fnode->pred[i]]; + if (!Bv_IsBitSet(pred->index, InLoop)) { + Bv_SetBit(pred->index, InLoop); + AddPreds(pred); + } + } +} + +static void RemoveNoopsFromExprList(void) { + IROExpr *expr; + IROExpr *prev; + + expr = IRO_FirstExpr; + prev = NULL; + while (expr) { + if (expr->linear->type == IROLinearNop) { + if (prev) + prev->next = expr->next; + else + IRO_FirstExpr = expr->next; + expr = expr->next; + } else { + prev = expr; + expr = expr->next; + } + } +} + +void IncLoopDepth(void) { + IRONode *fnode; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop)) + fnode->loopdepth++; + } +} + +void IRO_SetLoopDepth(void) { + IRONode *fnode; + IRONode *pred; + UInt16 i; + UInt16 flag; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) + fnode->loopdepth = 0; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + flag = 0; + + for (i = 0; i < fnode->numpred; i++) { + pred = IRO_NodeTable[fnode->pred[i]]; + if (Bv_IsBitSet(fnode->index, pred->dom)) { + if (!flag) { + Bv_AllocVector(&InLoop, IRO_NumNodes + 1); + Bv_Clear(InLoop); + Bv_SetBit(fnode->index, InLoop); + } + flag = 1; + Bv_SetBit(pred->index, InLoop); + if (pred != fnode) + AddPreds(pred); + } + } + + if (flag) + IncLoopDepth(); + } + + IRO_CheckForUserBreak(); +} + +static void InsertBranchAroundLoopPreheaders(void) { + IRONode *fnode; + CLabel *label; + IRONode *iter; + IROLinear *endnode; + IROLinear *labelnode; + + if (IRO_EndNode && IRO_EndNode->last && IRO_EndNode->last->type == IROLinearEnd) { + label = IRO_NewLabel(); + fnode = IRO_NewFlowGraphNode(); + IRO_LastNode->nextnode = fnode; + label->stmt = (Statement *) fnode; + + IRO_NodeTable = oalloc(sizeof(IRONode *) * IRO_NumNodes); + memset(IRO_NodeTable, 0, sizeof(IRONode *) * IRO_NumNodes); + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) + IRO_NodeTable[iter->index] = iter; + + labelnode = IRO_NewLinear(IROLinearLabel); + labelnode->index = ++IRO_NumLinear; + labelnode->u.label.label = label; + labelnode->flags |= IROLF_1; + fnode->first = labelnode; + IRO_LastLinear->next = labelnode; + + endnode = IRO_NewLinear(IROLinearEnd); + memcpy(endnode, IRO_EndNode->last, sizeof(IROLinear)); + endnode->index = ++IRO_NumLinear; + endnode->next = NULL; + fnode->last = endnode; + labelnode->next = endnode; + IRO_LastLinear = endnode; + + IRO_EndNode->last->type = IROLinearGoto; + IRO_EndNode->last->u.label.label = label; + IRO_LastNode = fnode; + IRO_EndNode = fnode; + + IRO_ComputeSuccPred(); + IRO_ComputeDom(); + } +} + +void IRO_FindLoops(void) { + IRONode *fnode; + IRONode *pred; + UInt16 i; + UInt16 flag; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + flag = 0; + + for (i = 0; i < fnode->numpred; i++) { + pred = IRO_NodeTable[fnode->pred[i]]; + if (Bv_IsBitSet(fnode->index, pred->dom)) { + if (!flag) { + Bv_AllocVector(&InLoop, IRO_NumNodes + 1); + Bv_Clear(InLoop); + Bv_SetBit(fnode->index, InLoop); + } + flag = 1; + Bv_SetBit(pred->index, InLoop); + if (pred != fnode) + AddPreds(pred); + } + } + + if (flag) { + IncLoopDepth(); + IRO_Dump("IRO_FindLoops:Found loop with header %d\n", fnode->index); + IRO_DumpBits("Loop includes: ", InLoop); + MyHandleLoop_Motion(fnode); + IRO_UpdateFlagsOnInts(); + MyHandleLoop_Vector(fnode); + RemoveNoopsFromExprList(); + IRO_UpdateFlagsOnInts(); + IRO_UpdateVars(); + } + } + + if (!IRO_FunctionHasReturn && IRO_EndNode != IRO_LastNode) + InsertBranchAroundLoopPreheaders(); +} + +static void CheckSubableSub(IROLinear *linear, Boolean isFirst) { + if (isFirst && IRO_IsSubableExpression(linear)) { + IRO_Dump("Subable Expression is %d\n", linear->index); + NoSubableSubs = 0; + } +} + +static int NoSubableSubExprs(IROLinear *nd) { + NoSubableSubs = 1; + IRO_WalkTree(nd, CheckSubableSub); + return NoSubableSubs; +} + +void ComputeLoopKills(void) { + IRONode *fnode; + IROLinear *nd; + + Bv_AllocVector(&AllKills, IRO_NumVars + 1); + Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1); + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop) && (nd = fnode->first)) { + Bv_AllocVector(&fnode->x16, IRO_NumVars + 1); + Bv_AllocVector(&fnode->x1E, IRO_NumVars + 1); + while (1) { + Bv_Clear(IRO_VarKills); + IRO_GetKills(nd); + Bv_Or(IRO_VarKills, AllKills); + if (nd == fnode->last) + break; + nd = nd->next; + } + } + } +} + +void ComputeLoopInvariance(void) { + IRONode *fnode; + IROLinear *nd; + + IRO_Depends = IRO_VarKills; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop) && (nd = fnode->first)) { + nd->flags &= ~IROLF_LoopInvariant; + while (1) { + if ((nd->flags & IROLF_Reffed) && nd->type != IROLinearNop) { + IRO_FindDepends_NoAlloc(nd); + if (!IRO_IsVolatile && !Bv_BitsInCommon(IRO_Depends, AllKills)) + nd->flags |= IROLF_LoopInvariant; + + if (IRO_CouldError) + nd->flags |= IROLF_CouldError; + else + nd->flags &= ~IROLF_CouldError; + } + + if (nd == fnode->last) + break; + nd = nd->next; + } + } + } +} + +void ComputeLoopInduction(void) { + IRONode *fnode; + IROLinear *nd; + Boolean flag; + Object *obj; + Object *obj2; + Object *obj3; + VarRecord *var; + IROLinear *tmpnd; + IROLoopInd *ind; + Boolean isUnsigned; + + Bv_AllocVector(&AllKills, IRO_NumVars + 1); + Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1); + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop) && (nd = fnode->first)) { + while (1) { + Bv_Clear(IRO_VarKills); + IRO_GetKills(nd); + Bv_Or(IRO_VarKills, AllKills); + flag = 0; + if ( + ( + nd->type == IROLinearOp2Arg && + nd->rtype->size <= 4 && + (nd->nodetype == EADDASS || nd->nodetype == ESUBASS) && + (obj = IRO_IsVariable(nd->u.diadic.left)) && + obj->type->size == nd->rtype->size && + IS_TYPE_INT(obj->type) && + ( + (IRO_IsIntConstant(nd->u.diadic.right) && CInt64_GetULong(&nd->u.diadic.right->u.node->data.intval)) + || + (nd->u.diadic.right->flags & IROLF_LoopInvariant) + ) + ) + || + ( + nd->type == IROLinearOp1Arg && + nd->rtype->size <= 4 && + (nd->nodetype == EPOSTINC || nd->nodetype == EPOSTDEC || nd->nodetype == EPREINC || nd->nodetype == EPREDEC) && + (obj = IRO_IsVariable(nd->u.monadic)) && + obj->type->size == nd->rtype->size && + IS_TYPE_INT(obj->type) + ) + ) + { + flag = 1; + } + else if ( + nd->type == IROLinearOp2Arg && + nd->rtype->size <= 4 && + nd->nodetype == EASS && + (obj = IRO_IsVariable(nd->u.diadic.left)) && + obj->type->size == nd->rtype->size && + IS_TYPE_INT(obj->type) && + nd->u.diadic.right->type == IROLinearOp2Arg && + (nd->u.diadic.right->nodetype == EADD || nd->u.diadic.right->nodetype == ESUB) + ) + { + if (nd->u.diadic.right->nodetype == EADD) { + obj2 = IRO_IsVariable(nd->u.diadic.right->u.diadic.left); + obj3 = IRO_IsVariable(nd->u.diadic.right->u.diadic.right); + if (obj2 == obj && obj3 != obj && (nd->u.diadic.right->u.diadic.right->flags & IROLF_LoopInvariant)) + flag = 1; + + if (obj3 == obj && obj2 != obj && (nd->u.diadic.right->u.diadic.left->flags & IROLF_LoopInvariant)) { + flag = 1; + tmpnd = nd->u.diadic.right->u.diadic.left; + nd->u.diadic.right->u.diadic.left = nd->u.diadic.right->u.diadic.right; + nd->u.diadic.right->u.diadic.right = tmpnd; + } + } else { + obj2 = IRO_IsVariable(nd->u.diadic.right->u.diadic.left); + obj3 = IRO_IsVariable(nd->u.diadic.right->u.diadic.right); + if (obj2 == obj && obj3 != obj && (nd->u.diadic.right->u.diadic.right->flags & IROLF_LoopInvariant)) + flag = 1; + } + } + + if (flag) { + if ((var = IRO_FindAssigned(nd))) { + if (var->xA == 2) + var->xA = 0; + else if (var->xA == 1) + var->xA = 2; + } + } else { + for (var = IRO_FirstVar; var; var = var->next) { + if (Bv_IsBitSet(var->index, IRO_VarKills)) + var->xA = 0; + } + } + + if (nd == fnode->last) + break; + nd = nd->next; + } + } + } + + IRO_DumpBits("Killed in loop: ", AllKills); + + for (fnode = IRO_FirstNode, FirstInd = NULL; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop) && (nd = fnode->first)) { + while (1) { + if ( + ( + nd->type == IROLinearOp2Arg && + (nd->nodetype == EADDASS || nd->nodetype == ESUBASS || nd->nodetype == EASS) + ) + || + ( + nd->type == IROLinearOp1Arg && + (nd->nodetype == EPOSTINC || nd->nodetype == EPOSTDEC || nd->nodetype == EPREINC || nd->nodetype == EPREDEC) + ) + ) { + if ((var = IRO_FindAssigned(nd)) && var->xA == 2 && var->object->type->size <= 4) { + ind = oalloc(sizeof(IROLoopInd)); + ind->fnode = fnode; + ind->var = var; + ind->nd = nd; + ind->next = FirstInd; + ind->addNode = NULL; + ind->addConst = 0; + ind->flags = 0; + + if (nd->type == IROLinearOp2Arg) { + isUnsigned = IRO_IsUnsignedType(nd->rtype); + if (IRO_IsIntConstant(nd->u.diadic.right)) { + CInt64 val = nd->u.diadic.right->u.node->data.intval; + if (IS_LINEAR_DIADIC(nd, EADDASS) && CInt64_Less(val, cint64_zero)) { + nd->nodetype = ESUBASS; + nd->u.diadic.right->u.node->data.intval = CInt64_Neg(val); + } + if (isUnsigned) { + CInt64_ConvertUInt32(&nd->u.diadic.right->u.node->data.intval); + ind->addConst = CInt64_GetULong(&nd->u.diadic.right->u.node->data.intval); + } else { + CInt64_ConvertInt32(&nd->u.diadic.right->u.node->data.intval); + ind->addConst = CInt64_GetULong(&nd->u.diadic.right->u.node->data.intval); + } + ind->addNode = NULL; + } else if (nd->nodetype == EADDASS || nd->nodetype == ESUBASS) { + ind->addNode = nd->u.diadic.right; + } else if (nd->nodetype == EASS) { + ind->addNode = nd->u.diadic.right->u.diadic.right; + } + } else { + if (IS_TYPE_POINTER_ONLY(nd->rtype)) + ind->addConst = TPTR_TARGET(nd->rtype)->size; + else + ind->addConst = 1; + ind->addNode = NULL; + } + + FirstInd = ind; + + if (IS_LINEAR_DIADIC_2(nd, EADDASS, ESUBASS)) { + if (nd->u.diadic.right->flags & IROLF_LoopInvariant) + IRO_Dump("Found induction variable the new way: %s\n", var->object->name->name); + else + IRO_Dump("Found induction variable the old way: %s\n", var->object->name->name); + } else if (nd->type == IROLinearOp2Arg && (nd->u.diadic.right->nodetype == EADD || nd->u.diadic.right->nodetype == ESUB)) { + IRO_Dump("Found induction variable the new way: %s\n", var->object->name->name); + } else { + IRO_Dump("Found induction variable the old way: %s\n", var->object->name->name); + } + } + } + + if (nd == fnode->last) + break; + nd = nd->next; + } + } + } +} + +static void IRO_ActUnmarkLoopInvariance(IROLinear *linear, Boolean isFirst) { + if (isFirst) + linear->flags &= ~IROLF_LoopInvariant; +} + +static void UnmarkSubexpressionsOfInvariantExpressions(void) { + IROExpr *expr; + + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if ( + Bv_IsBitSet(expr->node->index, InLoop) && + !expr->notSubable && + (!expr->couldError || expr->node->mustreach) && + (expr->linear->flags & IROLF_LoopInvariant) + ) { + IRO_WalkTree(expr->linear, IRO_ActUnmarkLoopInvariance); + expr->linear->flags |= IROLF_LoopInvariant; + } + } +} + +static void MyHandleLoop_Vector(IRONode *fnode) { + IRONode *pred; + UInt16 i; + IROExpr *expr; + IROExpr *removedExprs; + IROExpr *exprnext; + IROLoopInd *induction; + IROExpr *exprinner; + Boolean flag24; + IRONode *v2; + IRONode *node22; + int flag21; + IRONode *iter; + IROExpr *searchris; + IROLinear *reduceNd1; + VarRecord *var; + IROLinear *reduceNd2; + + IRO_FirstExpr = NULL; + LoopNode = fnode; + FindMustReach(); + + for (var = IRO_FirstVar; var; var = var->next) + var->xA = 1; + + ComputeLoopKills(); + ComputeLoopInvariance(); + ComputeLoopInduction(); + LoopNode = fnode; + ConditionalHeaderAtBottom = 0; + + v2 = NULL; + flag21 = 0; + node22 = NULL; + for (i = 0; i < LoopNode->numpred; i++) { + pred = IRO_NodeTable[LoopNode->pred[i]]; + if (!Bv_IsBitSet(pred->index, InLoop)) { + if (flag21) + node22 = NULL; + else + node22 = pred; + flag21 = 1; + if (pred->nextnode == fnode) { + CError_ASSERT(2880, v2 == NULL || pred == v2); + v2 = pred; + } + } + } + + if (!flag21) { + IRO_Dump("No predecessor outside the loop\n"); + return; + } + + if (!node22 || node22->last->type != IROLinearGoto) + node22 = CreatePreHeader(fnode, v2); + PredInt = node22->last; + + if (PredInt->type == IROLinearGoto && PredInt->u.label.label != LoopNode->first->u.label.label) { + if (!KnownBounds || !Times) { + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) + iter->mustreach = 0; + } else { + PredInt->u.label.label = LoopNode->first->u.label.label; + IRO_ComputeSuccPred(); + } + } + + if (copts.loopinvariants || copts.strengthreduction) { + MoveInvarianceInAddressExpr(); + IRO_DumpAfterPhase("MoveInvarianceInAddressExpr", 0); + IRO_FindExpressions(InLoop, 1); + IRO_DumpExprs(); + } + + if (copts.loopinvariants) + UnmarkSubexpressionsOfInvariantExpressions(); + + if (!copts.optimizesize && copts.strengthreduction) { + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if ( + !(expr->x0 & 4) && + Bv_IsBitSet(expr->node->index, InLoop) && + !expr->notSubable && + (!expr->couldError || expr->node->mustreach) && + Reducable(expr->linear, &reduceNd1, &reduceNd2, &var) + ) { + IRO_WalkTree(expr->linear, IRO_ActUnmarkRISCandidate); + expr->linear->flags |= IROLF_Ris; + expr->x1A = reduceNd1; + expr->x1E = var; + expr->x22 = reduceNd2; + } + } + } + + if (!copts.optimizesize && copts.strengthreduction) { + RisList = NULL; + for (expr = IRO_FirstExpr; expr; expr = exprnext) { + exprnext = expr->next; + if (!(expr->x0 & 4) && (expr->linear->flags & IROLF_Ris)) { + reduceNd1 = expr->x1A; + var = expr->x1E; + reduceNd2 = expr->x22; + + induction = FirstInd; + while (induction && induction->var != var) + induction = induction->next; + CError_ASSERT(3529, induction != NULL); + + IRO_FindDepends(reduceNd1); + if (!Bv_BitsInCommon(IRO_Depends, AllKills)) { + IRO_Dump("Found reduction in strength: %d\n", expr->linear->index); + if (IS_LINEAR_DIADIC(expr->linear, ESHL)) { + expr->linear->nodetype = EMUL; + CInt64_SetULong(&reduceNd1->u.node->data.intval, 1 << CInt64_GetULong(&reduceNd1->u.node->data.intval)); + reduceNd1->u.node->rtype = expr->linear->rtype; + } + + searchris = RisList; + while (1) { + if (!searchris) + break; + if (IRO_ExprsSame(expr->linear, searchris->linear)) + break; + searchris = searchris->next; + } + + if (searchris) { + IRO_Dump("Using existing RIS: %d\n", searchris->linear->index); + IRO_WalkTree(expr->linear, IRO_RemoveExpr_Action); + } else { + searchris = CreateRIS(expr, reduceNd2, reduceNd1, induction, 0); + } + IRO_ReplaceReference(expr->linear, searchris->x8, expr->linear); + IRO_ClipExpr(expr); + } + } + } + } + + RisList = NULL; + + expr = IRO_FirstExpr; + removedExprs = NULL; + if (copts.loopinvariants) { + while (expr) { + exprnext = expr->next; + flag24 = 0; + + if ( + Bv_IsBitSet(expr->node->index, InLoop) && + !expr->notSubable && + (!expr->couldError || expr->node->mustreach) && + (expr->linear->flags & IROLF_LoopInvariant) && + !(expr->x0 & 4) + ) { + IRO_Dump("Found loop invariant: %d\n", expr->linear->index); + + for (exprinner = removedExprs; exprinner; exprinner = exprinner->next) { + if (IRO_ExprsSame(exprinner->linear, expr->linear)) { + IRO_ReplaceReference(expr->linear, exprinner->x8, expr->linear); + IRO_NopOut(expr->linear); + IRO_Dump("Using already removed expr: %d\n", exprinner->linear->index); + IRO_RemoveExpr(expr); + flag24 = 1; + } + } + + if (!flag24 && !expr->x8) { + IRO_GetTemp(expr); + IRO_ReplaceReference(expr->linear, expr->x8, expr->linear); + IRO_MoveExpression(expr, PredInt); + IRO_AssignToTemp(expr); + IRO_RemoveExpr(expr); + expr->next = removedExprs; + removedExprs = expr; + } + } + + expr = exprnext; + } + } +} + +static void MyHandleLoop_Motion(IRONode *fnode) { + IROLoopMemRef *memref; + IRONode *pred; + UInt16 i; + IRONode *v2; + IRONode *node21; + Object *tempobj; + int flag20; + IRONode *iter; + IROLinear *ass; + VarRecord *var; + Boolean checkflag; + IROLoop *loop; + IROList list; + IROElmList *refiter; + + IRO_FirstExpr = NULL; + LoopNode = fnode; + FindMustReach(); + + for (var = IRO_FirstVar; var; var = var->next) + var->xA = 1; + + ComputeLoopKills(); + ComputeLoopInvariance(); + ComputeLoopInduction(); + LoopNode = fnode; + ConditionalHeaderAtBottom = 0; + + v2 = NULL; + flag20 = 0; + node21 = NULL; + for (i = 0; i < LoopNode->numpred; i++) { + pred = IRO_NodeTable[LoopNode->pred[i]]; + if (!Bv_IsBitSet(pred->index, InLoop)) { + if (flag20) + node21 = NULL; + else + node21 = pred; + flag20 = 1; + if (pred->nextnode == fnode) { + CError_ASSERT(3880, v2 == NULL || pred == v2); + v2 = pred; + } + } + } + + if (!flag20) { + IRO_Dump("No predecessor outside the loop\n"); + return; + } + + if (!node21 || node21->last->type != IROLinearGoto) + node21 = CreatePreHeader(fnode, v2); + PredInt = node21->last; + + if (PredInt->type == IROLinearGoto && PredInt->u.label.label != LoopNode->first->u.label.label) { + if (!KnownBounds || !Times) { + for (iter = IRO_FirstNode; iter; iter = iter->nextnode) + iter->mustreach = 0; + } else { + PredInt->u.label.label = LoopNode->first->u.label.label; + IRO_ComputeSuccPred(); + } + } + + if (copts.loopinvariants || copts.strengthreduction) { + MoveInvarianceInAddressExpr(); + IRO_DumpAfterPhase("MoveInvarianceInAddressExpr", 0); + IRO_FindExpressions(InLoop, 0); + IRO_DumpExprs(); + } + + if (copts.loopinvariants) + UnmarkSubexpressionsOfInvariantExpressions(); + + checkflag = 1; + Bv_AllocVector(&InLoop_Exits, IRO_NumNodes + 1); + Bv_AllocVector(&InLoop_Tails, IRO_NumNodes + 1); + LoopExitNumber = 0; + LoopExitSuccessor = NULL; + LoopTailNum = 0; + LoopTail = NULL; + IRO_FindLoopTailsAndExits(fnode); + FindMustReach1(fnode); + + loop = NULL; + if (LoopTailNum == 1) { + if (fnode->last->type == IROLinearIf || fnode->last->type == IROLinearIfNot) + loop = ExtractLoopInfo(fnode); + else if (LoopTail->last->type == IROLinearIf || LoopTail->last->type == IROLinearIfNot) + loop = ExtractLoopInfo(LoopTail); + } + + if (loop && !(loop->flags & LP_IFEXPR_NON_CANONICAL) && LoopExitNumber == 1) { + IRO_LoopMemRefFirst = NULL; + IRO_LoopMemRefCurrent = NULL; + CheckAllLoopAddresses(IRO_FirstNode, InLoop, &checkflag); + CheckAllLoopAddresses(IRO_FirstNode, InLoop, &checkflag); + if (checkflag) { + for (memref = IRO_LoopMemRefFirst; memref; memref = memref->next) { + if (memref->flags & LoopMemRef_10) + memref->flags |= LoopMemRef_8; + } + + for (memref = IRO_LoopMemRefFirst; memref; memref = memref->next) { + IRO_Dump("Loop Motion Candidate:: Int= %d", memref->nd->index); + if (memref->flags & LoopMemRef_8) + IRO_Dump("<invalid>"); + if (memref->flags & LoopMemRef_1) + IRO_Dump("<load>"); + if (memref->flags & LoopMemRef_2) + IRO_Dump("<store>"); + IRO_Dump("\n"); + + if (!(memref->flags & LoopMemRef_8)) { + tempobj = create_temp_object(memref->nd->rtype); + IRO_FindVar(tempobj, 1, 1); + if (IRO_FindVar(((IROLinear *) memref->rec->objRefs->element)->u.node->data.objref, 0, 1)) { + IRO_InitList(&list); + ass = IRO_NewLinear(IROLinearOp2Arg); + ass->index = ++IRO_NumLinear; + ass->rtype = memref->nd->rtype; + ass->nodetype = EASS; + ass->u.diadic.left = IRO_TempReference(tempobj, &list); + ass->u.diadic.left->flags |= IROLF_Ind | IROLF_Assigned; + ass->u.diadic.left->u.monadic->flags |= IROLF_Ind | IROLF_Assigned; + ass->u.diadic.right = IRO_DuplicateExpr(memref->nd, &list); + IRO_AddToList(ass, &list); + IRO_Paste(list.head, list.tail, PredInt); + } else { + CError_FATAL(4123); + } + + if (LoopExitSuccessor->numpred != 1) + LoopExitSuccessor = CreateNewLoopExitSuccessor(LoopExitSuccessor); + + IRO_InitList(&list); + ass = IRO_NewLinear(IROLinearOp2Arg); + ass->index = ++IRO_NumLinear; + ass->rtype = memref->nd->rtype; + ass->nodetype = EASS; + ass->u.diadic.left = IRO_DuplicateExpr(memref->nd, &list); + ass->u.diadic.left->flags |= IROLF_Ind | IROLF_Assigned; + ass->u.diadic.left->u.monadic->flags |= IROLF_Ind | IROLF_Assigned; + ass->u.diadic.right = IRO_TempReference(tempobj, &list); + IRO_AddToList(ass, &list); + + if (LoopExitSuccessor->first->type == IROLinearLabel) + IRO_PasteAfter(list.head, list.tail, LoopExitSuccessor->first); + else + IRO_Paste(list.head, list.tail, LoopExitSuccessor->first); + + for (refiter = memref->list; refiter; refiter = refiter->next) { + IRO_Dump("Loop Motion Candidate Reference at Int= %d\n", ((IROLinear *) refiter->element)->index); + IRO_InitList(&list); + IRO_TempReference(tempobj, &list); + IRO_Paste(list.head, list.tail, refiter->element); + IRO_LocateFather_Cut_And_Paste(refiter->element, list.tail); + } + } + } + } + } + + IRO_DumpAfterPhase("After Motion", 0); +} + +static Boolean CheckLoopAddress(IROLinear *nd, Boolean mustreach1) { + IROLoopMemRef *memref; + IROAddrRecord *rec; + IROAddrRecord *otherrec; + IROLinear *inner; + IROElmList *list; + Boolean flag; + + inner = nd->u.monadic; + rec = IRO_InitAddrRecordPointer(inner); + if (IS_LINEAR_ENODE(inner, EOBJREF)) { + rec->numObjRefs++; + IRO_AddElmToList(inner, &rec->objRefs); + } else if (IS_LINEAR_DIADIC(inner, EADD)) { + IRO_DecomposeAddressExpression(inner, rec); + } else { + return 0; + } + + if (rec->numObjRefs != 1) + return 0; + + flag = (nd->flags & IROLF_CouldError) || !(nd->flags & IROLF_Reffed); + if (!IRO_LoopMemRefFirst) { + MakeLoopEntry(nd, rec, mustreach1, flag); + } else { + for (memref = IRO_LoopMemRefFirst; memref; memref = memref->next) { + otherrec = memref->rec; + if (((IROLinear *) rec->objRefs->element)->u.node->data.objref == ((IROLinear *) otherrec->objRefs->element)->u.node->data.objref) { + if (IRO_ExprsSame(inner, otherrec->linear)) { + list = oalloc(sizeof(IROElmList)); + list->element = nd; + list->next = NULL; + if (!memref->list) { + memref->list = list; + } else { + list->next = memref->list; + memref->list = list; + } + } else { + memref->flags |= LoopMemRef_8; + } + + if (!mustreach1 && flag) + memref->flags |= LoopMemRef_8; + if (mustreach1 || flag) + memref->flags &= ~LoopMemRef_10; + break; + } + } + + if (!memref) + MakeLoopEntry(nd, rec, mustreach1, flag); + } + + return 1; +} + +static void CheckAllLoopAddresses(IRONode *fnode, BitVector *bv, Boolean *resultFlag) { + IROLinear *nd; + Boolean flag; + + flag = *resultFlag; + while (fnode) { + if (Bv_IsBitSet(fnode->index, bv) && (nd = fnode->first)) { + while (flag) { + if (nd->type == IROLinearOp1Arg && nd->nodetype == EINDIRECT) + flag = CheckLoopAddress(nd, fnode->mustreach1); + else if (nd->type == IROLinearFunccall) + flag = 0; + + if (nd == fnode->last) + break; + nd = nd->next; + } + + if (!flag) + break; + } + fnode = fnode->nextnode; + } + *resultFlag = flag; +} + +static void MakeLoopEntry(IROLinear *nd, IROAddrRecord *rec, Boolean mustreach1, Boolean flag2) { + IROElmList *list; + + if (!IRO_IsRegable(((IROLinear *) rec->objRefs->element)->u.node->data.objref) && + (nd->u.monadic->flags & IROLF_LoopInvariant) && + !IRO_HasSideEffect(nd)) { + if (!IRO_LoopMemRefFirst) { + IRO_LoopMemRefCurrent = IRO_LoopMemRefFirst = oalloc(sizeof(IROLoopMemRef)); + } else { + IRO_LoopMemRefCurrent->next = oalloc(sizeof(IROLoopMemRef)); + IRO_LoopMemRefCurrent = IRO_LoopMemRefCurrent->next; + } + IRO_LoopMemRefCurrent->flags = LoopMemRef_10; + IRO_LoopMemRefCurrent->nd = nd; + IRO_LoopMemRefCurrent->rec = rec; + IRO_LoopMemRefCurrent->next = NULL; + IRO_LoopMemRefCurrent->list = NULL; + + list = oalloc(sizeof(IROElmList)); + list->element = nd; + list->next = NULL; + if (!IRO_LoopMemRefCurrent->list) { + IRO_LoopMemRefCurrent->list = list; + } else { + list->next = IRO_LoopMemRefCurrent->list; + IRO_LoopMemRefCurrent->list = list; + } + + if (((IROLinear *) rec->objRefs->element)->flags & IROLF_Assigned) { + IRO_LoopMemRefCurrent->flags |= LoopMemRef_2; + if (((IROLinear *) rec->objRefs->element)->flags & IROLF_Used) + IRO_LoopMemRefCurrent->flags |= LoopMemRef_1; + } else { + IRO_LoopMemRefCurrent->flags |= LoopMemRef_1; + } + + if (!mustreach1 && flag2) + IRO_LoopMemRefCurrent->flags |= LoopMemRef_8; + + if (mustreach1 || flag2) + IRO_LoopMemRefCurrent->flags &= ~LoopMemRef_10; + } +} + +void FindAssignmenttoInductionVar(IROLoop *loop, IRONode *fnode) { + IROLinear *nd; + UInt32 index; + + if (!loop->induction) { + loop->nd14 = NULL; + } else { + index = loop->induction->var->index; + for (nd = fnode->first; nd; nd = nd->next) { + Bv_Clear(IRO_VarKills); + IRO_GetKills(nd); + if (Bv_IsBitSet(index, IRO_VarKills)) + loop->nd14 = nd; + + if (nd == fnode->last) + break; + } + + if (loop->nd14 && loop->nd14->type != IROLinearOp2Arg) + loop->nd14 = NULL; + } +} + +static void ComputeIntWeight(IROLoop *loop, IROLinear *Int) { + loop->sizeBySomeMeasurement++; +} + +static IROLinear *IsTypconVar(IROLinear *nd) { + if (IS_LINEAR_MONADIC(nd, ETYPCON) && IRO_IsVariable(nd->u.monadic)) + return nd->u.monadic; + else + return NULL; +} + +IROLoop *ExtractLoopInfo(IRONode *fnode) { + Boolean flag30; + Boolean flag29; + Boolean flag28; + UInt32 counter27; + IROLoopInd *ind23; + Object *obj; + IROLinear *nd21; + IRONode *scanfnode; + IROLinear *left19; + IROLinear *right18; + IROLinear *tmp18; + IROLinear *scannd; + IROLinear *tmp; + VarRecord *var; + IROLoopInd *scanind; + IROLinear *left; + IROLinear *right; + UInt32 counter2; + UInt32 i; + IROLoop *loop; + + flag30 = 0; + flag29 = 0; + flag28 = 0; + counter27 = 0; + LoopNode = fnode; + + loop = oalloc(sizeof(IROLoop)); + loop->fnode = fnode; + nd21 = LoopNode->last->u.label.x4; + loop->nd18 = nd21; + loop->flags = 0; + loop->x8 = 0; + loop->nd14 = NULL; + loop->induction = NULL; + loop->index20 = -1; + loop->index24 = -1; + loop->sizeBySomeMeasurement = 0; + + if (nd21->type == IROLinearOp2Arg && IS_TYPE_INT(nd21->rtype)) { + ind23 = NULL; + left19 = nd21->u.diadic.left; + right18 = nd21->u.diadic.right; + if (IRO_IsVariable(left19) || (left19 = IsTypconVar(left19))) { + if ((var = IRO_FindVar(left19->u.monadic->u.node->data.objref, 0, 1))) { + scanind = FirstInd; + while (scanind && scanind->var != var) + scanind = scanind->next; + if (scanind) { + ind23 = scanind; + loop->flags |= LoopFlags_1; + loop->induction = scanind; + } + } + } + + if (IRO_IsVariable(right18) || (right18 = IsTypconVar(right18))) { + if ((var = IRO_FindVar(right18->u.monadic->u.node->data.objref, 0, 1))) { + scanind = FirstInd; + while (scanind && scanind->var != var) + scanind = scanind->next; + if (scanind) { + ind23 = scanind; + loop->flags &= ~LoopFlags_1; + loop->induction = scanind; + } + } + } + + if (ind23 && ind23->addConst > 0) { + if (loop->flags & LoopFlags_1) { + if ( + loop->nd18->type != IROLinearOp2Arg || + !(loop->nd18->nodetype == ELESS || loop->nd18->nodetype == EGREATER || loop->nd18->nodetype == ELESSEQU || loop->nd18->nodetype == EGREATEREQU) || + !loop->nd18->u.diadic.left || + !loop->nd18->u.diadic.left->rtype || + !IS_TYPE_INT(loop->nd18->u.diadic.left->rtype) || + !loop->nd18->u.diadic.right || + !loop->nd18->u.diadic.right->rtype || + !IS_TYPE_INT(loop->nd18->u.diadic.right->rtype) + ) { + loop->flags |= LP_IFEXPR_NON_CANONICAL; + return loop; + } + } else { + if ( + loop->nd18->type == IROLinearOp2Arg && + (loop->nd18->nodetype == EGREATER || loop->nd18->nodetype == EGREATEREQU) && + (left = loop->nd18->u.diadic.left) && + left->rtype && + IS_TYPE_INT(left->rtype) && + (right = loop->nd18->u.diadic.right) && + right->rtype && + IS_TYPE_INT(right->rtype) + ) { + loop->nd18->u.diadic.left = right; + loop->nd18->u.diadic.right = left; + if (loop->nd18->nodetype == EGREATER) + loop->nd18->nodetype = ELESS; + else if (loop->nd18->nodetype == EGREATEREQU) + loop->nd18->nodetype = ELESSEQU; + loop->flags |= LoopFlags_1; + } else if ( + loop->nd18->type == IROLinearOp2Arg && + (loop->nd18->nodetype == ELESS || loop->nd18->nodetype == ELESSEQU) && + (left = loop->nd18->u.diadic.left) && + left->rtype && + IS_TYPE_INT(left->rtype) && + (right = loop->nd18->u.diadic.right) && + right->rtype && + IS_TYPE_INT(right->rtype) + ) { + loop->nd18->u.diadic.left = right; + loop->nd18->u.diadic.right = left; + if (loop->nd18->nodetype == ELESS) + loop->nd18->nodetype = EGREATER; + else if (loop->nd18->nodetype == ELESSEQU) + loop->nd18->nodetype = EGREATEREQU; + loop->flags |= LoopFlags_1; + } else { + loop->flags |= LP_IFEXPR_NON_CANONICAL; + return loop; + } + } + } else { + loop->flags |= LP_INDUCTION_NOT_FOUND; + return loop; + } + } else if (nd21->type == IROLinearOp1Arg && IS_TYPE_INT(nd21->rtype)) { + if (nd21->nodetype == EPREINC || nd21->nodetype == EPOSTINC || nd21->nodetype == EPREDEC || nd21->nodetype == EPOSTDEC) { + if (IRO_IsVariable(nd21->u.monadic)) { + if ((var = IRO_FindVar(nd21->u.monadic->u.monadic->u.node->data.objref, 0, 1))) { + scanind = FirstInd; + while (scanind && scanind->var != var) + scanind = scanind->next; + if (scanind) { + ind23 = scanind; + loop->flags |= LoopFlags_10000; + loop->induction = scanind; + } else { + loop->flags |= LP_INDUCTION_NOT_FOUND; + return loop; + } + } else { + loop->flags |= LP_INDUCTION_NOT_FOUND; + return loop; + } + } else { + loop->flags |= LP_INDUCTION_NOT_FOUND; + return loop; + } + } else { + loop->flags |= LP_INDUCTION_NOT_FOUND; + return loop; + } + } else { + loop->flags |= LP_IFEXPR_NON_CANONICAL; + return loop; + } + + counter2 = 0; + scanind = FirstInd; + while (scanind) { + scanind = scanind->next; + counter2++; + } + + if (counter2 > 1) + loop->flags |= LP_HAS_MULTIPLE_INDUCTIONS; + + if ((scanind = loop->induction)) { + nd21 = scanind->nd; + if (nd21->type == IROLinearOp2Arg) { + if (IS_LINEAR_DIADIC_2(loop->nd18, ELESS, ELESSEQU)) { + if (nd21->nodetype == EADDASS) { + if (scanind->addConst == 1) + loop->flags |= LP_LOOP_STEP_ISADD; + if (scanind->addConst > 0) + loop->flags |= LP_LOOP_STEP_ISPOS; + } else if (nd21->nodetype == EASS && + IS_LINEAR_DIADIC(nd21->u.diadic.right, EADD) && + IRO_IsIntConstant(tmp18 = nd21->u.diadic.right->u.diadic.right) && + CTool_EndianReadWord32(&tmp18->u.node->data.intval.hi) == 0) { + if (CInt64_GetULong(&tmp18->u.node->data.intval) == 1) + loop->flags |= LP_LOOP_STEP_ISADD; + if (CInt64_GetULong(&tmp18->u.node->data.intval) > 0) + loop->flags |= LP_LOOP_STEP_ISPOS; + } + } + } else if (nd21->type == IROLinearOp1Arg) { + if (nd21->nodetype == EPREINC || nd21->nodetype == EPOSTINC) { + if (scanind->addConst == 1) + loop->flags |= LP_LOOP_STEP_ISADD; + if (scanind->addConst > 0) + loop->flags |= LP_LOOP_STEP_ISPOS; + } + if (nd21->nodetype == EPREDEC || nd21->nodetype == EPOSTDEC) { + if (scanind->addConst == 1) + loop->flags |= LoopFlags_2000; + if (scanind->addConst > 0) + loop->flags |= LP_LOOP_STEP_ISNEG; + } + } + loop->index24 = nd21->index; + loop->index20 = IRO_FindStart(nd21)->index; + } + + if (ind23) { + tmp = IRO_FindStart(fnode->last->u.diadic.right); + loop->flags |= LoopFlags_200; + if (loop->flags & LoopFlags_10000) { + for (scannd = loop->fnode->first; scannd && scannd != tmp; scannd = scannd->next) { + if (scannd->type != IROLinearLabel && scannd->type != IROLinearNop) + loop->flags &= ~LoopFlags_200; + } + } else { + for (scannd = ind23->nd->next; scannd && scannd != tmp; scannd = scannd->next){ + if (scannd->type != IROLinearLabel && scannd->type != IROLinearNop) + loop->flags &= ~LoopFlags_200; + } + for (scannd = loop->fnode->first; scannd && scannd != tmp; scannd = scannd->next){ + if ((scannd->index < loop->index20 || scannd->index > loop->index24) && scannd->type != IROLinearLabel && scannd->type != IROLinearNop) + loop->flags &= ~LoopFlags_200; + } + } + } + + for (scanfnode = IRO_FirstNode; scanfnode; scanfnode = scanfnode->nextnode) { + if (Bv_IsBitSet(scanfnode->index, InLoop) && scanfnode != fnode && (scannd = scanfnode->first)) { + while (1) { + if (scannd->type == IROLinearFunccall) + flag30 = 1; + if (scannd->type == IROLinearGoto) + flag28++; + if (flag28 >= 1) + flag29 = 1; + if (scannd->type == IROLinearIf || scannd->type == IROLinearIfNot || scannd->type == IROLinearSwitch || scannd->type == IROLinearReturn) + flag29 = 1; + + if (scannd->type == IROLinearAsm) + loop->flags |= LP_LOOP_HAS_ASM; + + if (!(scannd->flags & IROLF_Reffed) && scannd->type != IROLinearNop && scannd->type != IROLinearLabel) { + if (!IRO_IsAssignOp[scannd->nodetype]) { + loop->flags |= LoopFlags_8; + } else if (scannd->index < loop->index20 || scannd->index > loop->index24) { + counter27++; + if (IsAssignmentReductionCandidate(scannd) && counter27 == 1) + loop->flags |= LoopFlags_40000; + if (counter27 > 1) + loop->flags &= ~LoopFlags_40000; + } + } + + if (scannd->index < loop->index20 || scannd->index > loop->index24) { + if (IS_LINEAR_ENODE(scannd, EOBJREF)) { + obj = scannd->u.node->data.objref; + if ((scannd->flags & IROLF_Ind) && obj && obj == loop->induction->var->object) { + if (!(scannd->flags & IROLF_Assigned) && (scannd->flags & IROLF_Used)) { + IRO_Dump("Induction Used in loop\n"); + loop->flags |= LoopFlags_800; + } + } + } + + if (IS_LINEAR_DIADIC(scannd, ESHR) && + (obj = IRO_IsVariable(scannd->u.diadic.left)) && + IRO_IsIntConstant(scannd->u.diadic.right)) { + for (scanind = FirstInd; scanind; scanind = scanind->next) { + if (scanind->var->object == obj) { + IRO_Dump("Induction has DIV: %s\n", obj->name->name); + scanind->flags |= LoopInd_HasDiv; + } + } + } + + if (IS_LINEAR_DIADIC(scannd, EAND) && + (obj = IRO_IsVariable(scannd->u.diadic.left)) && + IRO_IsIntConstant(scannd->u.diadic.right)) { + for (scanind = FirstInd; scanind && obj; scanind = scanind->next) { + if (scanind->var->object == obj) { + IRO_Dump("Induction has MOD: %s\n", obj->name->name); + scanind->flags |= LoopInd_HasMod; + } + } + } + } + + ComputeIntWeight(loop, scannd); + if (scannd == scanfnode->last) + break; + scannd = scannd->next; + } + } + + if (flag30) + loop->flags |= LP_LOOP_HAS_CALLS; + if (flag29) + loop->flags |= LP_LOOP_HAS_CNTRLFLOW; + + for (i = 0; i < scanfnode->numsucc && scanfnode != fnode; i++) { + if (Bv_IsBitSet(scanfnode->index, InLoop) && !Bv_IsBitSet(scanfnode->succ[i], InLoop)) { + IRO_Dump("Node %d has an out of loop successor %d\n", scanfnode->index, scanfnode->succ[i]); + IRO_DumpBits("Loop includes: ", InLoop); + IRO_Dump("loop has multiple exits\n"); + loop->flags |= LoopFlags_1000; + } + } + } + + return loop; +} + +CLabel *BuildLabel(IROList *list) { + IROLinear *nd; + + nd = IRO_NewLinear(IROLinearLabel); + nd->index = IRO_NumLinear++; + nd->u.label.label = IRO_NewLabel(); + nd->flags |= IROLF_1; + IRO_AddToList(nd, list); + return nd->u.label.label; +} + +static void MoveInvarianceInAddressExpr(void) { + IRONode *fnode; + IROLinear *nd; + IROLinear *start; + IROList list; + + IRO_FirstExpr = IRO_LastExpr = NULL; + IRO_NumExprs = 0; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (Bv_IsBitSet(fnode->index, InLoop)) { + for (nd = fnode->first; nd; nd = nd->next) { + if (nd->type == IROLinearOp1Arg && + (nd->nodetype == EINDIRECT || nd->nodetype == EINDIRECT) && + IS_LINEAR_DIADIC(nd->u.monadic, EADD)) { + RearrangeInvarianceInAddressExpr(nd->u.monadic, &list); + start = IRO_FindStart(nd->u.monadic); + IRO_LocateFather_Cut_And_Paste(nd->u.monadic, list.tail); + IRO_Paste(list.head, list.tail, start); + } + + if (nd == fnode->last) + break; + } + } + } + + IRO_UpdateFlagsOnInts(); +} + +static void AddAddendLinear(IROLinear *nd) { + IROElmList *list; + + if (IS_LINEAR_DIADIC(nd, EADD)) { + AddAddendLinear(nd->u.diadic.left); + AddAddendLinear(nd->u.diadic.right); + } else { + list = oalloc(sizeof(IROElmList)); + list->element = nd; + list->next = NULL; + if (FirstAddendLinear) + LastAddendLinear->next = list; + else + FirstAddendLinear = list; + LastAddendLinear = list; + } +} + +static IROLinear *RearrangeInvarianceInAddressExpr(IROLinear *nd, IROList *list) { + IROLinear *result; + IROElmList *scanlist; + IROElmList *elist; + IROLinear *scannd; + + IRO_InitList(list); + FirstAddendLinear = LastAddendLinear = NULL; + AddAddendLinear(nd->u.diadic.left); + AddAddendLinear(nd->u.diadic.right); + + elist = NULL; + result = NULL; + for (scanlist = FirstAddendLinear; scanlist; scanlist = scanlist->next) { + scannd = scanlist->element; + if (!IRO_IsIntConstant(scannd) && (scannd->flags & IROLF_LoopInvariant)) { + if (result) { + IROLinear *tmp = IRO_NewLinear(IROLinearOp2Arg); + tmp->index = ++IRO_NumLinear; + tmp->nodetype = EADD; + tmp->u.diadic.left = result; + tmp->u.diadic.right = IRO_DuplicateExpr(scannd, list); + IRO_AddToList(tmp, list); + tmp->flags |= IROLF_LoopInvariant; + tmp->flags |= IROLF_Reffed; + tmp->rtype = result->rtype; + result = tmp; + } else { + result = IRO_DuplicateExpr(scannd, list); + } + + if (elist) + elist->next = scanlist->next; + else + FirstAddendLinear = scanlist->next; + } else { + elist = scanlist; + } + } + + for (scanlist = FirstAddendLinear, elist = NULL; scanlist; scanlist = scanlist->next) { + scannd = scanlist->element; + if (!IRO_IsIntConstant(scannd)) { + if (result) { + IROLinear *tmp = IRO_NewLinear(IROLinearOp2Arg); + tmp->index = ++IRO_NumLinear; + tmp->nodetype = EADD; + tmp->u.diadic.left = result; + tmp->u.diadic.right = IRO_DuplicateExpr(scannd, list); + IRO_AddToList(tmp, list); + tmp->flags |= IROLF_Reffed; + tmp->rtype = result->rtype; + result = tmp; + } else { + result = IRO_DuplicateExpr(scannd, list); + } + + if (elist) + elist->next = scanlist->next; + else + FirstAddendLinear = scanlist->next; + } else { + elist = scanlist; + } + } + + for (scanlist = FirstAddendLinear; scanlist; scanlist = scanlist->next) { + scannd = scanlist->element; + if (result) { + IROLinear *tmp = IRO_NewLinear(IROLinearOp2Arg); + tmp->index = ++IRO_NumLinear; + tmp->nodetype = EADD; + tmp->u.diadic.left = result; + tmp->u.diadic.right = scannd; + tmp->u.diadic.right = IRO_DuplicateExpr(scannd, list); + IRO_AddToList(tmp, list); + tmp->flags |= IROLF_Reffed; + tmp->rtype = result->rtype; + result = tmp; + } else { + result = IRO_DuplicateExpr(scannd, list); + } + } + + return result; +} + +static IROLinear *FindAddendForReductionPattern(IROLinear *a, IROLinear *b, Boolean *resultFlag) { + IROLinear *left; + IROLinear *right; + IROLinear *node28; + Boolean subflag; + + left = b->u.diadic.left; + right = b->u.diadic.right; + if (b->nodetype == EADD || b->nodetype == ESUB) { + node28 = left; + while (IS_LINEAR_MONADIC(node28, ETYPCON)) + node28 = node28->u.monadic; + + if (IS_LINEAR_MONADIC(node28, EINDIRECT) && (node28->u.monadic->flags & IROLF_LoopInvariant) && IRO_ExprsSame(a, node28)) { + *resultFlag = 1; + return left; + } + + if (IS_LINEAR_DIADIC_2(node28, EADD, ESUB)) { + if ((node28 = FindAddendForReductionPattern(a, node28, &subflag))) { + *resultFlag = 1; + return node28; + } + } + } + + *resultFlag = 0; + if (b->nodetype == EADD) { + node28 = right; + while (IS_LINEAR_MONADIC(node28, ETYPCON)) + node28 = node28->u.monadic; + + if (IS_LINEAR_MONADIC(node28, EINDIRECT) && (node28->u.monadic->flags & IROLF_LoopInvariant) && IRO_ExprsSame(a, node28)) { + return right; + } + + if (IS_LINEAR_DIADIC_2(node28, EADD, ESUB)) { + if ((node28 = FindAddendForReductionPattern(a, node28, &subflag))) { + return node28; + } + } + } + + return NULL; +} + +static void ReorderOperandsForReductionPattern(IROLinear *a, IROLinear *b) { + IROLinear *left; + IROLinear *right; + IROLinear *addend; + IROLinear *tmp; + Boolean flag; + + left = b->u.diadic.left; + right = b->u.diadic.right; + + if (b->nodetype == EADD && (addend = FindAddendForReductionPattern(a, b, &flag)) && addend != left) { + if (flag && IS_LINEAR_DIADIC_2(left, EADD, ESUB) && addend->rtype == right->rtype) { + tmp = left; + b->u.diadic.left = right; + left = right; + b->u.diadic.right = tmp; + right = tmp; + flag = 0; + } + + if (!flag && IS_LINEAR_DIADIC_2(right, EADD, ESUB) && addend->rtype == left->rtype) { + if (IRO_LocateFather_Cut_And_Paste_Without_Nopping(addend, left)) + b->u.diadic.left = addend; + } + } +} + +static UInt32 IsAssignmentReductionCandidate(IROLinear *nd) { + IROLinear *left; + IROLinear *right; + IROLinear *tmp; + + if (nd->type == IROLinearOp2Arg) { + if (nd->nodetype == EASS) { + left = nd->u.diadic.left; + right = nd->u.diadic.right; + if (IS_LINEAR_MONADIC(left, EINDIRECT) && (left->u.monadic->flags & IROLF_LoopInvariant)) { + if (IS_LINEAR_MONADIC(right, ETYPCON) && + right->rtype->type == right->u.monadic->rtype->type && + IS_TYPE_INT(right->rtype) && + right->rtype->size < right->u.monadic->rtype->size) + right = right->u.monadic; + + if (IS_LINEAR_DIADIC_2(right, EADD, ESUB)) { + ReorderOperandsForReductionPattern(left, right); + tmp = right->u.diadic.left; + if (IS_LINEAR_MONADIC(tmp, ETYPCON)) + tmp = tmp->u.monadic; + if (IS_LINEAR_MONADIC(tmp, EINDIRECT) && + (tmp->u.monadic->flags & IROLF_LoopInvariant) && + IRO_ExprsSame(left, tmp) && + right->u.diadic.right->type == IROLinearOp2Arg) { + if (right->u.diadic.right->nodetype == EADD) + return 1; + if (right->u.diadic.right->nodetype == ESUB) + return 1; + if (right->u.diadic.right->nodetype == EMUL) + return 1; + if (right->u.diadic.right->nodetype == EDIV) + return 1; + } + } + } + } else if (nd->nodetype == EADDASS || nd->nodetype == ESUBASS) { + left = nd->u.diadic.left; + right = nd->u.diadic.right; + + if (IS_LINEAR_MONADIC(right, ETYPCON) && + right->rtype->type == right->u.monadic->rtype->type && + IS_TYPE_INT(right->rtype) && + right->rtype->size < right->u.monadic->rtype->size) + right = right->u.monadic; + + if (IS_LINEAR_MONADIC(left, EINDIRECT) && + (left->u.monadic->flags & IROLF_LoopInvariant) && + right->type == IROLinearOp2Arg) { + if (right->nodetype == EADD) + return 1; + if (right->nodetype == ESUB) + return 1; + if (right->nodetype == EMUL) + return 1; + if (right->nodetype == EDIV) + return 1; + } + } + } + + return 0; +} + |