//===----------------------------------------------------------------------===//
#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/IntrinsicInst.h"
-#include "llvm/LLVMContext.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/Debug.h"
-#include "llvm/DataLayout.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/TargetTransformInfo.h"
using namespace llvm;
}
// Save the original insertion point so we can restore it when we're done.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
+ BuilderType::InsertPointGuard Guard(Builder);
// Move the insertion point out of as many loops as we can.
while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
// If we haven't found this binop, insert it.
Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
- BO->setDebugLoc(SaveInsertPt->getDebugLoc());
+ BO->setDebugLoc(Loc);
rememberInstruction(BO);
- // Restore the original insert point.
- if (SaveInsertBB)
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
-
return BO;
}
const SCEV *Start = A->getStart();
if (!FactorOutConstant(Start, Remainder, Factor, SE, TD))
return false;
- // FIXME: can use A->getNoWrapFlags(FlagNW)
- S = SE.getAddRecExpr(Start, Step, A->getLoop(), SCEV::FlagAnyWrap);
+ S = SE.getAddRecExpr(Start, Step, A->getLoop(),
+ A->getNoWrapFlags(SCEV::FlagNW));
return true;
}
AddRecs.push_back(SE.getAddRecExpr(Zero,
A->getStepRecurrence(SE),
A->getLoop(),
- // FIXME: A->getNoWrapFlags(FlagNW)
- SCEV::FlagAnyWrap));
+ A->getNoWrapFlags(SCEV::FlagNW)));
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
Ops[i] = Zero;
Ops.append(Add->op_begin(), Add->op_end());
// without the other.
SplitAddRecs(Ops, Ty, SE);
+ Type *IntPtrTy = SE.TD
+ ? SE.TD->getIntPtrType(PTy)
+ : Type::getInt64Ty(PTy->getContext());
+
// Descend down the pointer's type and attempt to convert the other
// operands into GEP indices, at each level. The first index in a GEP
// indexes into the array implied by the pointer operand; the rest of
// array indexing.
SmallVector<const SCEV *, 8> ScaledOps;
if (ElTy->isSized()) {
- const SCEV *ElSize = SE.getSizeOfExpr(ElTy);
+ const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy);
if (!ElSize->isZero()) {
SmallVector<const SCEV *, 8> NewOps;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
}
// Save the original insertion point so we can restore it when we're done.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ BuilderType::InsertPointGuard Guard(Builder);
// Move the insertion point out of as many loops as we can.
while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
Value *GEP = Builder.CreateGEP(V, Idx, "uglygep");
rememberInstruction(GEP);
- // Restore the original insert point.
- if (SaveInsertBB)
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
-
return GEP;
}
// Save the original insertion point so we can restore it when we're done.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ BuilderType::InsertPoint SaveInsertPt = Builder.saveIP();
// Move the insertion point out of as many loops as we can.
while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
rememberInstruction(GEP);
// Restore the original insert point.
- if (SaveInsertBB)
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
+ Builder.restoreIP(SaveInsertPt);
return expand(SE.getAddExpr(Ops));
}
SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
A->getStepRecurrence(SE),
A->getLoop(),
- // FIXME: A->getNoWrapFlags(FlagNW)
- SCEV::FlagAnyWrap));
+ A->getNoWrapFlags(SCEV::FlagNW)));
}
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
Base = A->getOperand(A->getNumOperands()-1);
}
// Save the original insertion point so we can restore it when we're done.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ BuilderType::InsertPointGuard Guard(Builder);
// Another AddRec may need to be recursively expanded below. For example, if
// this AddRec is quadratic, the StepV may itself be an AddRec in this
IVIncInsertPos : Pred->getTerminator();
Builder.SetInsertPoint(InsertPos);
Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
-
+ if (isa<OverflowingBinaryOperator>(IncV)) {
+ if (Normalized->getNoWrapFlags(SCEV::FlagNUW))
+ cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
+ if (Normalized->getNoWrapFlags(SCEV::FlagNSW))
+ cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
+ }
PN->addIncoming(IncV, Pred);
}
- // Restore the original insert point.
- if (SaveInsertBB)
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
-
// After expanding subexpressions, restore the PostIncLoops set so the caller
// can ensure that IVIncrement dominates the current uses.
PostIncLoops = SavedPostIncLoops;
Normalized = cast<SCEVAddRecExpr>(
SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
Normalized->getLoop(),
- // FIXME: Normalized->getNoWrapFlags(FlagNW)
- SCEV::FlagAnyWrap));
+ Normalized->getNoWrapFlags(SCEV::FlagNW)));
}
// Strip off any non-loop-dominating component from the addrec step.
PostLoopScale = Step;
Step = SE.getConstant(Normalized->getType(), 1);
Normalized =
- cast<SCEVAddRecExpr>(SE.getAddRecExpr(Start, Step,
- Normalized->getLoop(),
- // FIXME: Normalized
- // ->getNoWrapFlags(FlagNW)
- SCEV::FlagAnyWrap));
+ cast<SCEVAddRecExpr>(SE.getAddRecExpr(
+ Start, Step, Normalized->getLoop(),
+ Normalized->getNoWrapFlags(SCEV::FlagNW)));
}
// Expand the core addrec. If we need post-loop scaling, force it to
!ExpandTy->isPointerTy() && Step->isNonConstantNegative();
if (useSubtract)
Step = SE.getNegativeSCEV(Step);
- // Expand the step somewhere that dominates the loop header.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
- Value *StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin());
- // Restore the insertion point to the place where the caller has
- // determined dominates all uses.
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
+ Value *StepV;
+ {
+ // Expand the step somewhere that dominates the loop header.
+ BuilderType::InsertPointGuard Guard(Builder);
+ StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin());
+ }
Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
}
}
// Re-apply any non-loop-dominating scale.
if (PostLoopScale) {
+ assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
Result = InsertNoopCastOfTo(Result, IntTy);
Result = Builder.CreateMul(Result,
expandCodeFor(PostLoopScale, IntTy));
for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
- // FIXME: S->getNoWrapFlags(FlagNW)
- SCEV::FlagAnyWrap));
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ S->getNoWrapFlags(SCEV::FlagNW)));
BasicBlock::iterator NewInsertPt =
llvm::next(BasicBlock::iterator(cast<Instruction>(V)));
+ BuilderType::InsertPointGuard Guard(Builder);
while (isa<PHINode>(NewInsertPt) || isa<DbgInfoIntrinsic>(NewInsertPt) ||
isa<LandingPadInst>(NewInsertPt))
++NewInsertPt;
V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0,
NewInsertPt);
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
return V;
}
if (!S->getStart()->isZero()) {
SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
NewOps[0] = SE.getConstant(Ty, 0);
- // FIXME: can use S->getNoWrapFlags()
- const SCEV *Rest = SE.getAddRecExpr(NewOps, L, SCEV::FlagAnyWrap);
+ const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
+ S->getNoWrapFlags(SCEV::FlagNW));
// Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
// comments on expandAddToGEP for details.
Header->begin());
rememberInstruction(CanonicalIV);
+ SmallSet<BasicBlock *, 4> PredSeen;
Constant *One = ConstantInt::get(Ty, 1);
for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
BasicBlock *HP = *HPI;
+ if (!PredSeen.insert(HP))
+ continue;
+
if (L->contains(HP)) {
// Insert a unit add instruction right before the terminator
// corresponding to the back-edge.
}
// Check to see if we already expanded this here.
- std::map<std::pair<const SCEV *, Instruction *>,
- AssertingVH<Value> >::iterator I =
- InsertedExpressions.find(std::make_pair(S, InsertPt));
+ std::map<std::pair<const SCEV *, Instruction *>, TrackingVH<Value> >::iterator
+ I = InsertedExpressions.find(std::make_pair(S, InsertPt));
if (I != InsertedExpressions.end())
return I->second;
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ BuilderType::InsertPointGuard Guard(Builder);
Builder.SetInsertPoint(InsertPt->getParent(), InsertPt);
// Expand the expression into instructions.
//
// This is independent of PostIncLoops. The mapped value simply materializes
// the expression at this insertion point. If the mapped value happened to be
- // a postinc expansion, it could be reused by a non postinc user, but only if
+ // a postinc expansion, it could be reused by a non-postinc user, but only if
// its insertion point was already at the head of the loop.
InsertedExpressions[std::make_pair(S, InsertPt)] = V;
-
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
return V;
}
InsertedValues.insert(I);
}
-void SCEVExpander::restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I) {
- Builder.SetInsertPoint(BB, I);
-}
-
/// getOrInsertCanonicalInductionVariable - This method returns the
/// canonical induction variable of the specified type for the specified
/// loop (inserting one if there is none). A canonical induction variable
SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
// Emit code for it.
- BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
- BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+ BuilderType::InsertPointGuard Guard(Builder);
PHINode *V = cast<PHINode>(expandCodeFor(H, 0, L->getHeader()->begin()));
- if (SaveInsertBB)
- restoreInsertPoint(SaveInsertBB, SaveInsertPt);
return V;
}
/// This does not depend on any SCEVExpander state but should be used in
/// the same context that SCEVExpander is used.
unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
- SmallVectorImpl<WeakVH> &DeadInsts,
- const ScalarTargetTransformInfo *STTI) {
+ SmallVectorImpl<WeakVH> &DeadInsts,
+ const TargetTransformInfo *TTI) {
// Find integer phis in order of increasing width.
SmallVector<PHINode*, 8> Phis;
for (BasicBlock::iterator I = L->getHeader()->begin();
PHINode *Phi = dyn_cast<PHINode>(I); ++I) {
Phis.push_back(Phi);
}
- if (STTI)
+ if (TTI)
std::sort(Phis.begin(), Phis.end(), width_descending);
unsigned NumElim = 0;
PEnd = Phis.end(); PIter != PEnd; ++PIter) {
PHINode *Phi = *PIter;
+ // 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()) {
+ Phi->replaceAllUsesWith(V);
+ DeadInsts.push_back(Phi);
+ ++NumElim;
+ DEBUG_WITH_TYPE(DebugType, dbgs()
+ << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
+ continue;
+ }
+
if (!SE.isSCEVable(Phi->getType()))
continue;
PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
if (!OrigPhiRef) {
OrigPhiRef = Phi;
- if (Phi->getType()->isIntegerTy() && STTI &&
- STTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
+ if (Phi->getType()->isIntegerTy() && TTI
+ && TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
// This phi can be freely truncated to the narrowest phi type. Map the
// truncated expression to it so it will be reused for narrow types.
const SCEV *TruncExpr =
// Currently, we only allow division by a nonzero constant here. If this is
// inadequate, we could easily allow division by SCEVUnknown by using
// ValueTracking to check isKnownNonZero().
+//
+// We cannot generally expand recurrences unless the step dominates the loop
+// header. The expander handles the special case of affine recurrences by
+// scaling the recurrence outside the loop, but this technique isn't generally
+// applicable. Expanding a nested recurrence outside a loop requires computing
+// binomial coefficients. This could be done, but the recurrence has to be in a
+// perfectly reduced form, which can't be guaranteed.
struct SCEVFindUnsafe {
+ ScalarEvolution &SE;
bool IsUnsafe;
- SCEVFindUnsafe(): IsUnsafe(false) {}
+ SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
bool follow(const SCEV *S) {
- const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S);
- if (!D)
- return true;
- const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
- if (SC && !SC->getValue()->isZero())
- return true;
- IsUnsafe = true;
- return false;
+ if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
+ const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
+ if (!SC || SC->getValue()->isZero()) {
+ IsUnsafe = true;
+ return false;
+ }
+ }
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
+ const SCEV *Step = AR->getStepRecurrence(SE);
+ if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
+ IsUnsafe = true;
+ return false;
+ }
+ }
+ return true;
}
bool isDone() const { return IsUnsafe; }
};
}
namespace llvm {
-bool isSafeToExpand(const SCEV *S) {
- SCEVFindUnsafe Search;
+bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
+ SCEVFindUnsafe Search(SE);
visitAll(S, Search);
return !Search.IsUnsafe;
}
projects / oota-llvm.git / blobdiff