diff options
Diffstat (limited to 'compiler_and_linker/unsorted/IroLoop.c')
| -rw-r--r-- | compiler_and_linker/unsorted/IroLoop.c | 2324 |
1 files changed, 0 insertions, 2324 deletions
diff --git a/compiler_and_linker/unsorted/IroLoop.c b/compiler_and_linker/unsorted/IroLoop.c deleted file mode 100644 index d6ec5f0..0000000 --- a/compiler_and_linker/unsorted/IroLoop.c +++ /dev/null @@ -1,2324 +0,0 @@ -#include "compiler/IroLoop.h" -#include "compiler/IroCSE.h" -#include "compiler/IroDump.h" -#include "compiler/IroFlowgraph.h" -#include "compiler/IroLinearForm.h" -#include "compiler/IroPropagate.h" -#include "compiler/IroSubable.h" -#include "compiler/IroUtil.h" -#include "compiler/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; -} - |