From f6727b01a527369ecdbcf6ea0863dc776091f50c Mon Sep 17 00:00:00 2001 From: Dale Johannesen Date: Tue, 23 Dec 2008 23:21:35 +0000 Subject: [PATCH] Revert 61362 and 61402 until SPEC breakage is fixed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61403 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 178 +++++-------------- 1 file changed, 43 insertions(+), 135 deletions(-) diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index fd4cc056271..fc61b9e9a1e 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -130,12 +130,6 @@ namespace { /// dependent on random ordering of pointers in the process. SmallVector StrideOrder; - /// GEPlist - A list of the GEP's that have been remembered in the SCEV - /// data structures. SCEV does not know to update these when the operands - /// of the GEP are changed, which means we cannot leave them live across - /// loops. - SmallVector GEPlist; - /// CastedValues - As we need to cast values to uintptr_t, this keeps track /// of the casted version of each value. This is accessed by /// getCastedVersionOf. @@ -197,7 +191,7 @@ private: bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse, const SCEVHandle *&CondStride); bool RequiresTypeConversion(const Type *Ty, const Type *NewTy); - SCEVHandle CheckForIVReuse(bool, bool, bool, const SCEVHandle&, + int64_t CheckForIVReuse(bool, bool, bool, const SCEVHandle&, IVExpr&, const Type*, const std::vector& UsersToProcess); bool ValidStride(bool, int64_t, @@ -346,7 +340,6 @@ SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp) { } SE->setSCEV(GEP, GEPVal); - GEPlist.push_back(GEP); return GEPVal; } @@ -515,22 +508,14 @@ bool LoopStrengthReduce::AddUsersIfInteresting(Instruction *I, Loop *L, if (isa(User) && Processed.count(User)) continue; - // Descend recursively, but not into PHI nodes outside the current loop. - // It's important to see the entire expression outside the loop to get - // choices that depend on addressing mode use right, although we won't - // consider references ouside the loop in all cases. - // If User is already in Processed, we don't want to recurse into it again, - // but do want to record a second reference in the same instruction. + // If this is an instruction defined in a nested loop, or outside this loop, + // don't recurse into it. bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { - if (isa(User) || Processed.count(User) || - !AddUsersIfInteresting(User, L, Processed)) { - DOUT << "FOUND USER in other loop: " << *User - << " OF SCEV: " << *ISE << "\n"; - AddUserToIVUsers = true; - } - } else if (Processed.count(User) || - !AddUsersIfInteresting(User, L, Processed)) { + DOUT << "FOUND USER in other loop: " << *User + << " OF SCEV: " << *ISE << "\n"; + AddUserToIVUsers = true; + } else if (!AddUsersIfInteresting(User, L, Processed)) { DOUT << "FOUND USER: " << *User << " OF SCEV: " << *ISE << "\n"; AddUserToIVUsers = true; @@ -719,45 +704,34 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, PHINode *PN = cast(Inst); for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { if (PN->getIncomingValue(i) == OperandValToReplace) { - // If the original expression is outside the loop, put the replacement - // code in the same place as the original expression, - // which need not be an immediate predecessor of this PHI. This way we - // need only one copy of it even if it is referenced multiple times in - // the PHI. We don't do this when the original expression is inside the - // loop because multiple copies sometimes do useful sinking of code in that - // case(?). - Instruction *OldLoc = dyn_cast(OperandValToReplace); - if (L->contains(OldLoc->getParent())) { - // If this is a critical edge, split the edge so that we do not insert the - // code on all predecessor/successor paths. We do this unless this is the - // canonical backedge for this loop, as this can make some inserted code - // be in an illegal position. - BasicBlock *PHIPred = PN->getIncomingBlock(i); - if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 && - (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) { - - // First step, split the critical edge. - SplitCriticalEdge(PHIPred, PN->getParent(), P, false); - - // Next step: move the basic block. In particular, if the PHI node - // is outside of the loop, and PredTI is in the loop, we want to - // move the block to be immediately before the PHI block, not - // immediately after PredTI. - if (L->contains(PHIPred) && !L->contains(PN->getParent())) { - BasicBlock *NewBB = PN->getIncomingBlock(i); - NewBB->moveBefore(PN->getParent()); - } - - // Splitting the edge can reduce the number of PHI entries we have. - e = PN->getNumIncomingValues(); + // If this is a critical edge, split the edge so that we do not insert the + // code on all predecessor/successor paths. We do this unless this is the + // canonical backedge for this loop, as this can make some inserted code + // be in an illegal position. + BasicBlock *PHIPred = PN->getIncomingBlock(i); + if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 && + (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) { + + // First step, split the critical edge. + SplitCriticalEdge(PHIPred, PN->getParent(), P, false); + + // Next step: move the basic block. In particular, if the PHI node + // is outside of the loop, and PredTI is in the loop, we want to + // move the block to be immediately before the PHI block, not + // immediately after PredTI. + if (L->contains(PHIPred) && !L->contains(PN->getParent())) { + BasicBlock *NewBB = PN->getIncomingBlock(i); + NewBB->moveBefore(PN->getParent()); } + + // Splitting the edge can reduce the number of PHI entries we have. + e = PN->getNumIncomingValues(); } + Value *&Code = InsertedCode[PN->getIncomingBlock(i)]; if (!Code) { // Insert the code into the end of the predecessor block. - Instruction *InsertPt = (L->contains(OldLoc->getParent())) ? - PN->getIncomingBlock(i)->getTerminator() : - OldLoc->getParent()->getTerminator(); + Instruction *InsertPt = PN->getIncomingBlock(i)->getTerminator(); Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L); // Adjust the type back to match the PHI. Note that we can't use @@ -1194,11 +1168,7 @@ bool LoopStrengthReduce::RequiresTypeConversion(const Type *Ty1, /// mode scale component and optional base reg. This allows the users of /// this stride to be rewritten as prev iv * factor. It returns 0 if no /// reuse is possible. Factors can be negative on same targets, e.g. ARM. -/// -/// If all uses are outside the loop, we don't require that all multiplies -/// be folded into the addressing mode; a multiply (executed once) outside -/// the loop is better than another IV within. Well, usually. -SCEVHandle LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, +int64_t LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, bool AllUsesAreAddresses, bool AllUsesAreOutsideLoop, const SCEVHandle &Stride, @@ -1210,7 +1180,7 @@ SCEVHandle LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, ++NewStride) { std::map::iterator SI = IVsByStride.find(StrideOrder[NewStride]); - if (SI == IVsByStride.end() || !isa(SI->first)) + if (SI == IVsByStride.end()) continue; int64_t SSInt = cast(SI->first)->getValue()->getSExtValue(); if (SI->first != Stride && @@ -1232,53 +1202,11 @@ SCEVHandle LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, if (II->Base->isZero() && !RequiresTypeConversion(II->Base->getType(), Ty)) { IV = *II; - return SE->getIntegerSCEV(Scale, Stride->getType()); + return Scale; } } - } else if (AllUsesAreOutsideLoop) { - // Accept nonconstant strides here; it is really really right to substitute - // an existing IV if we can. - for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e; - ++NewStride) { - std::map::iterator SI = - IVsByStride.find(StrideOrder[NewStride]); - if (SI == IVsByStride.end() || !isa(SI->first)) - continue; - int64_t SSInt = cast(SI->first)->getValue()->getSExtValue(); - if (SI->first != Stride && SSInt != 1) - continue; - for (std::vector::iterator II = SI->second.IVs.begin(), - IE = SI->second.IVs.end(); II != IE; ++II) - // Accept nonzero base here. - // Only reuse previous IV if it would not require a type conversion. - if (!RequiresTypeConversion(II->Base->getType(), Ty)) { - IV = *II; - return Stride; - } - } - // Special case, old IV is -1*x and this one is x. Can treat this one as - // -1*old. - for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e; - ++NewStride) { - std::map::iterator SI = - IVsByStride.find(StrideOrder[NewStride]); - if (SI == IVsByStride.end()) - continue; - if (SCEVMulExpr *ME = dyn_cast(SI->first)) - if (SCEVConstant *SC = dyn_cast(ME->getOperand(0))) - if (Stride == ME->getOperand(1) && - SC->getValue()->getSExtValue() == -1LL) - for (std::vector::iterator II = SI->second.IVs.begin(), - IE = SI->second.IVs.end(); II != IE; ++II) - // Accept nonzero base here. - // Only reuse previous IV if it would not require type conversion. - if (!RequiresTypeConversion(II->Base->getType(), Ty)) { - IV = *II; - return SE->getIntegerSCEV(-1LL, Stride->getType()); - } - } } - return SE->getIntegerSCEV(0, Stride->getType()); + return 0; } /// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that @@ -1429,13 +1357,12 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, IVExpr ReuseIV(SE->getIntegerSCEV(0, Type::Int32Ty), SE->getIntegerSCEV(0, Type::Int32Ty), 0, 0); - SCEVHandle RewriteFactor = - CheckForIVReuse(HaveCommonExprs, AllUsesAreAddresses, + int64_t RewriteFactor = 0; + RewriteFactor = CheckForIVReuse(HaveCommonExprs, AllUsesAreAddresses, AllUsesAreOutsideLoop, Stride, ReuseIV, CommonExprs->getType(), UsersToProcess); - if (!isa(RewriteFactor) || - !cast(RewriteFactor)->isZero()) { + if (RewriteFactor != 0) { DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride << " and BASE " << *ReuseIV.Base << " :\n"; NewPHI = ReuseIV.PHI; @@ -1463,8 +1390,7 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, Value *CommonBaseV = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt); - if (isa(RewriteFactor) && - cast(RewriteFactor)->isZero()) { + if (RewriteFactor == 0) { // Create a new Phi for this base, and stick it in the loop header. NewPHI = PHINode::Create(ReplacedTy, "iv.", PhiInsertBefore); ++NumInserted; @@ -1611,33 +1537,18 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, // If we are reusing the iv, then it must be multiplied by a constant // factor take advantage of addressing mode scale component. - if (!isa(RewriteFactor) || - !cast(RewriteFactor)->isZero()) { - // If we're reusing an IV with a nonzero base (currently this happens - // only when all reuses are outside the loop) subtract that base here. - // The base has been used to initialize the PHI node but we don't want - // it here. - if (!ReuseIV.Base->isZero()) - RewriteExpr = SE->getMinusSCEV(RewriteExpr, ReuseIV.Base); - - // Multiply old variable, with base removed, by new scale factor. - RewriteExpr = SE->getMulExpr(RewriteFactor, + if (RewriteFactor != 0) { + RewriteExpr = SE->getMulExpr(SE->getIntegerSCEV(RewriteFactor, + RewriteExpr->getType()), RewriteExpr); // The common base is emitted in the loop preheader. But since we // are reusing an IV, it has not been used to initialize the PHI node. // Add it to the expression used to rewrite the uses. - // When this use is outside the loop, we earlier subtracted the - // common base, and are adding it back here. Use the same expression - // as before, rather than CommonBaseV, so DAGCombiner will zap it. if (!isa(CommonBaseV) || - !cast(CommonBaseV)->isZero()) { - if (L->contains(User.Inst->getParent())) - RewriteExpr = SE->getAddExpr(RewriteExpr, + !cast(CommonBaseV)->isZero()) + RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(CommonBaseV)); - else - RewriteExpr = SE->getAddExpr(RewriteExpr, CommonExprs); - } } // Now that we know what we need to do, insert code before User for the @@ -2263,9 +2174,6 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) { IVUsesByStride.clear(); IVsByStride.clear(); StrideOrder.clear(); - for (unsigned i=0; ideleteValueFromRecords(GEPlist[i]); - GEPlist.clear(); // Clean up after ourselves if (!DeadInsts.empty()) { -- 2.34.1