X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionExpander.cpp;h=59f19a002eccc9fc4a51106a1a71afdf8a9eae06;hb=b7e0193c4d7bdc4838eb6587d1dc45c38b4c2a03;hp=b0676a95fe8eea37478cb6872cc6bb6c0ef444b0;hpb=e67254860230c58a5de34578354a4d1d78c87e83;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index b0676a95fe8..59f19a002ec 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -16,6 +16,7 @@ #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/DataLayout.h" @@ -44,12 +45,10 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, // not allowed to move it. BasicBlock::iterator BIP = Builder.GetInsertPoint(); - Instruction *Ret = NULL; + Instruction *Ret = nullptr; // Check to see if there is already a cast! - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); - UI != E; ++UI) { - User *U = *UI; + for (User *U : V->users()) if (U->getType() == Ty) if (CastInst *CI = dyn_cast(U)) if (CI->getOpcode() == Op) { @@ -69,7 +68,6 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, Ret = CI; break; } - } // Create a new cast. if (!Ret) @@ -210,7 +208,7 @@ static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder, const SCEV *Factor, ScalarEvolution &SE, - const DataLayout *TD) { + const DataLayout *DL) { // Everything is divisible by one. if (Factor->isOne()) return true; @@ -250,7 +248,7 @@ static bool FactorOutConstant(const SCEV *&S, // In a Mul, check if there is a constant operand which is a multiple // of the given factor. if (const SCEVMulExpr *M = dyn_cast(S)) { - if (TD) { + if (DL) { // With DataLayout, the size is known. Check if there is a constant // operand which is a multiple of the given factor. If so, we can // factor it. @@ -270,7 +268,7 @@ static bool FactorOutConstant(const SCEV *&S, for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { const SCEV *SOp = M->getOperand(i); const SCEV *Remainder = SE.getConstant(SOp->getType(), 0); - if (FactorOutConstant(SOp, Remainder, Factor, SE, TD) && + if (FactorOutConstant(SOp, Remainder, Factor, SE, DL) && Remainder->isZero()) { SmallVector NewMulOps(M->op_begin(), M->op_end()); NewMulOps[i] = SOp; @@ -285,12 +283,12 @@ static bool FactorOutConstant(const SCEV *&S, if (const SCEVAddRecExpr *A = dyn_cast(S)) { const SCEV *Step = A->getStepRecurrence(SE); const SCEV *StepRem = SE.getConstant(Step->getType(), 0); - if (!FactorOutConstant(Step, StepRem, Factor, SE, TD)) + if (!FactorOutConstant(Step, StepRem, Factor, SE, DL)) return false; if (!StepRem->isZero()) return false; const SCEV *Start = A->getStart(); - if (!FactorOutConstant(Start, Remainder, Factor, SE, TD)) + if (!FactorOutConstant(Start, Remainder, Factor, SE, DL)) return false; S = SE.getAddRecExpr(Start, Step, A->getLoop(), A->getNoWrapFlags(SCEV::FlagNW)); @@ -404,8 +402,8 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, // without the other. SplitAddRecs(Ops, Ty, SE); - Type *IntPtrTy = SE.TD - ? SE.TD->getIntPtrType(PTy) + Type *IntPtrTy = SE.DL + ? SE.DL->getIntPtrType(PTy) : Type::getInt64Ty(PTy->getContext()); // Descend down the pointer's type and attempt to convert the other @@ -424,7 +422,7 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, for (unsigned i = 0, e = Ops.size(); i != e; ++i) { const SCEV *Op = Ops[i]; const SCEV *Remainder = SE.getConstant(Ty, 0); - if (FactorOutConstant(Op, Remainder, ElSize, SE, SE.TD)) { + if (FactorOutConstant(Op, Remainder, ElSize, SE, SE.DL)) { // Op now has ElSize factored out. ScaledOps.push_back(Op); if (!Remainder->isZero()) @@ -458,13 +456,13 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, bool FoundFieldNo = false; // An empty struct has no fields. if (STy->getNumElements() == 0) break; - if (SE.TD) { + if (SE.DL) { // With DataLayout, field offsets are known. See if a constant offset // falls within any of the struct fields. if (Ops.empty()) break; if (const SCEVConstant *C = dyn_cast(Ops[0])) if (SE.getTypeSizeInBits(C->getType()) <= 64) { - const StructLayout &SL = *SE.TD->getStructLayout(STy); + const StructLayout &SL = *SE.DL->getStructLayout(STy); uint64_t FullOffset = C->getValue()->getZExtValue(); if (FullOffset < SL.getSizeInBytes()) { unsigned ElIdx = SL.getElementContainingOffset(FullOffset); @@ -630,21 +628,21 @@ static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B, const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) { // Test whether we've already computed the most relevant loop for this SCEV. std::pair::iterator, bool> Pair = - RelevantLoops.insert(std::make_pair(S, static_cast(0))); + RelevantLoops.insert(std::make_pair(S, nullptr)); if (!Pair.second) return Pair.first->second; if (isa(S)) // A constant has no relevant loops. - return 0; + return nullptr; if (const SCEVUnknown *U = dyn_cast(S)) { if (const Instruction *I = dyn_cast(U->getValue())) return Pair.first->second = SE.LI->getLoopFor(I->getParent()); // A non-instruction has no relevant loops. - return 0; + return nullptr; } if (const SCEVNAryExpr *N = dyn_cast(S)) { - const Loop *L = 0; + const Loop *L = nullptr; if (const SCEVAddRecExpr *AR = dyn_cast(S)) L = AR->getLoop(); for (SCEVNAryExpr::op_iterator I = N->op_begin(), E = N->op_end(); @@ -719,7 +717,7 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { // Emit instructions to add all the operands. Hoist as much as possible // out of loops, and form meaningful getelementptrs where possible. - Value *Sum = 0; + Value *Sum = nullptr; for (SmallVectorImpl >::iterator I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) { const Loop *CurLoop = I->first; @@ -787,7 +785,7 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { // Emit instructions to mul all the operands. Hoist as much as possible // out of loops. - Value *Prod = 0; + Value *Prod = nullptr; for (SmallVectorImpl >::iterator I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) { const SCEV *Op = I->second; @@ -895,18 +893,18 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale) { if (IncV == InsertPos) - return NULL; + return nullptr; switch (IncV->getOpcode()) { default: - return NULL; + return nullptr; // Check for a simple Add/Sub or GEP of a loop invariant step. case Instruction::Add: case Instruction::Sub: { Instruction *OInst = dyn_cast(IncV->getOperand(1)); if (!OInst || SE.DT->dominates(OInst, InsertPos)) return dyn_cast(IncV->getOperand(0)); - return NULL; + return nullptr; } case Instruction::BitCast: return dyn_cast(IncV->getOperand(0)); @@ -917,7 +915,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, continue; if (Instruction *OInst = dyn_cast(*I)) { if (!SE.DT->dominates(OInst, InsertPos)) - return NULL; + return nullptr; } if (allowScale) { // allow any kind of GEP as long as it can be hoisted. @@ -928,11 +926,11 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, // have 2 operands. i1* is used by the expander to represent an // address-size element. if (IncV->getNumOperands() != 2) - return NULL; + return nullptr; unsigned AS = cast(IncV->getType())->getAddressSpace(); if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS) && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS)) - return NULL; + return nullptr; break; } return dyn_cast(IncV->getOperand(0)); @@ -1080,10 +1078,16 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, // Reuse a previously-inserted PHI, if present. BasicBlock *LatchBlock = L->getLoopLatch(); if (LatchBlock) { - PHINode *AddRecPhiMatch = 0; - Instruction *IncV = 0; - TruncTy = 0; + PHINode *AddRecPhiMatch = nullptr; + Instruction *IncV = nullptr; + TruncTy = nullptr; InvertStep = false; + + // Only try partially matching scevs that need truncation and/or + // step-inversion if we know this loop is outside the current loop. + bool TryNonMatchingSCEV = IVIncInsertLoop && + SE.DT->properlyDominates(LatchBlock, IVIncInsertLoop->getHeader()); + for (BasicBlock::iterator I = L->getHeader()->begin(); PHINode *PN = dyn_cast(I); ++I) { if (!SE.isSCEVable(PN->getType())) @@ -1094,18 +1098,15 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, continue; bool IsMatchingSCEV = PhiSCEV == Normalized; - Instruction *TempIncV = - cast(PN->getIncomingValueForBlock(LatchBlock)); - // We only handle truncation and inversion of phi recurrences for the // expanded expression if the expanded expression's loop dominates the // loop we insert to. Check now, so we can bail out early. - if (!IsMatchingSCEV) - if (!IVIncInsertLoop || - !SE.DT->properlyDominates(L->getHeader(), - IVIncInsertLoop->getHeader())) + if (!IsMatchingSCEV && !TryNonMatchingSCEV) continue; + Instruction *TempIncV = + cast(PN->getIncomingValueForBlock(LatchBlock)); + // Check whether we can reuse this PHI node. if (LSRMode) { if (!isExpandedAddRecExprPHI(PN, TempIncV, L)) @@ -1120,7 +1121,7 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, // Stop if we have found an exact match SCEV. if (IsMatchingSCEV) { IncV = TempIncV; - TruncTy = 0; + TruncTy = nullptr; InvertStep = false; AddRecPhiMatch = PN; break; @@ -1243,13 +1244,13 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { PostIncLoopSet Loops; Loops.insert(L); Normalized = - cast(TransformForPostIncUse(Normalize, S, 0, 0, - Loops, SE, *SE.DT)); + cast(TransformForPostIncUse(Normalize, S, nullptr, + nullptr, Loops, SE, *SE.DT)); } // Strip off any non-loop-dominating component from the addrec start. const SCEV *Start = Normalized->getStart(); - const SCEV *PostLoopOffset = 0; + const SCEV *PostLoopOffset = nullptr; if (!SE.properlyDominates(Start, L->getHeader())) { PostLoopOffset = Start; Start = SE.getConstant(Normalized->getType(), 0); @@ -1261,7 +1262,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { // Strip off any non-loop-dominating component from the addrec step. const SCEV *Step = Normalized->getStepRecurrence(SE); - const SCEV *PostLoopScale = 0; + const SCEV *PostLoopScale = nullptr; if (!SE.dominates(Step, L->getHeader())) { PostLoopScale = Step; Step = SE.getConstant(Normalized->getType(), 1); @@ -1276,7 +1277,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { Type *ExpandTy = PostLoopScale ? IntTy : STy; // In some cases, we decide to reuse an existing phi node but need to truncate // it and/or invert the step. - Type *TruncTy = 0; + Type *TruncTy = nullptr; bool InvertStep = false; PHINode *PN = getAddRecExprPHILiterally(Normalized, L, ExpandTy, IntTy, TruncTy, InvertStep); @@ -1323,10 +1324,16 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { // We have decided to reuse an induction variable of a dominating loop. Apply // truncation and/or invertion of the step. if (TruncTy) { - if (Result->getType() != TruncTy) { + Type *ResTy = Result->getType(); + // Normalize the result type. + if (ResTy != SE.getEffectiveSCEVType(ResTy)) + Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy)); + // Truncate the result. + if (TruncTy != Result->getType()) { Result = Builder.CreateTrunc(Result, TruncTy); rememberInstruction(Result); } + // Invert the result. if (InvertStep) { Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy), Result); @@ -1366,7 +1373,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { const Loop *L = S->getLoop(); // First check for an existing canonical IV in a suitable type. - PHINode *CanonicalIV = 0; + PHINode *CanonicalIV = nullptr; if (PHINode *PN = L->getCanonicalInductionVariable()) if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) CanonicalIV = PN; @@ -1382,12 +1389,12 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(), S->getNoWrapFlags(SCEV::FlagNW))); BasicBlock::iterator NewInsertPt = - llvm::next(BasicBlock::iterator(cast(V))); + std::next(BasicBlock::iterator(cast(V))); BuilderType::InsertPointGuard Guard(Builder); while (isa(NewInsertPt) || isa(NewInsertPt) || isa(NewInsertPt)) ++NewInsertPt; - V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, + V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr, NewInsertPt); return V; } @@ -1436,8 +1443,12 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { Constant *One = ConstantInt::get(Ty, 1); for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { BasicBlock *HP = *HPI; - if (!PredSeen.insert(HP)) + if (!PredSeen.insert(HP).second) { + // There must be an incoming value for each predecessor, even the + // duplicates! + CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP); continue; + } if (L->contains(HP)) { // Insert a unit add instruction right before the terminator @@ -1610,7 +1621,7 @@ Value *SCEVExpander::expand(const SCEV *S) { while (InsertPt != Builder.GetInsertPoint() && (isInsertedInstruction(InsertPt) || isa(InsertPt))) { - InsertPt = llvm::next(BasicBlock::iterator(InsertPt)); + InsertPt = std::next(BasicBlock::iterator(InsertPt)); } break; } @@ -1660,20 +1671,12 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, // Emit code for it. BuilderType::InsertPointGuard Guard(Builder); - PHINode *V = cast(expandCodeFor(H, 0, L->getHeader()->begin())); + PHINode *V = cast(expandCodeFor(H, nullptr, + L->getHeader()->begin())); return V; } -/// Sort values by integer width for replaceCongruentIVs. -static bool width_descending(Value *lhs, Value *rhs) { - // Put pointers at the back and make sure pointer < pointer = false. - if (!lhs->getType()->isIntegerTy() || !rhs->getType()->isIntegerTy()) - return rhs->getType()->isIntegerTy() && !lhs->getType()->isIntegerTy(); - return rhs->getType()->getPrimitiveSizeInBits() - < lhs->getType()->getPrimitiveSizeInBits(); -} - /// replaceCongruentIVs - Check for congruent phis in this loop header and /// replace them with their most canonical representative. Return the number of /// phis eliminated. @@ -1690,7 +1693,13 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, Phis.push_back(Phi); } if (TTI) - std::sort(Phis.begin(), Phis.end(), width_descending); + std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) { + // Put pointers at the back and make sure pointer < pointer = false. + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy(); + return RHS->getType()->getPrimitiveSizeInBits() < + LHS->getType()->getPrimitiveSizeInBits(); + }); unsigned NumElim = 0; DenseMap ExprToIVMap; @@ -1702,7 +1711,7 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, // Fold constant phis. They may be congruent to other constant phis and // would confuse the logic below that expects proper IVs. - if (Value *V = Phi->hasConstantValue()) { + if (Value *V = SimplifyInstruction(Phi, SE.DL, SE.TLI, SE.DT, SE.AC)) { Phi->replaceAllUsesWith(V); DeadInsts.push_back(Phi); ++NumElim;