/// expandCodeFor - Insert code to directly compute the specified SCEV
/// expression into the program. The inserted code is inserted into the
/// specified block.
- ///
- /// If a particular value sign is required, a type may be specified for the
- /// result.
- Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) {
+ Value *expandCodeFor(SCEVHandle SH, Instruction *IP) {
// Expand the code for this SCEV.
this->InsertPt = IP;
- return expandInTy(SH, Ty);
+ return expand(SH);
}
/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
return V;
}
- Value *expandInTy(SCEV *S, const Type *Ty) {
- Value *V = expand(S);
- if (Ty && V->getType() != Ty) {
- if (isa<PointerType>(Ty) && V->getType()->isInteger())
- return InsertCastOfTo(Instruction::IntToPtr, V, Ty);
- else if (Ty->isInteger() && isa<PointerType>(V->getType()))
- return InsertCastOfTo(Instruction::PtrToInt, V, Ty);
- else if (Ty->getPrimitiveSizeInBits() ==
- V->getType()->getPrimitiveSizeInBits())
- return InsertCastOfTo(Instruction::BitCast, V, Ty);
- else if (Ty->getPrimitiveSizeInBits() >
- V->getType()->getPrimitiveSizeInBits())
- return InsertCastOfTo(Instruction::ZExt, V, Ty);
- else
- return InsertCastOfTo(Instruction::Trunc, V, Ty);
- }
- return V;
- }
-
Value *visitConstant(SCEVConstant *S) {
return S->getValue();
}
}
Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
- Value *V = expandInTy(S->getOperand(), S->getType());
+ Value *V = expand(S->getOperand());
return CastInst::createZExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
+ Value *visitSignExtendExpr(SCEVSignExtendExpr *S) {
+ Value *V = expand(S->getOperand());
+ return CastInst::createSExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
+ }
+
Value *visitAddExpr(SCEVAddExpr *S) {
- const Type *Ty = S->getType();
- Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty);
+ Value *V = expand(S->getOperand(S->getNumOperands()-1));
// Emit a bunch of add instructions
for (int i = S->getNumOperands()-2; i >= 0; --i)
- V = InsertBinop(Instruction::Add, V, expandInTy(S->getOperand(i), Ty),
+ V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)),
InsertPt);
return V;
}
Value *visitMulExpr(SCEVMulExpr *S);
Value *visitSDivExpr(SCEVSDivExpr *S) {
- const Type *Ty = S->getType();
- Value *LHS = expandInTy(S->getLHS(), Ty);
- Value *RHS = expandInTy(S->getRHS(), Ty);
+ Value *LHS = expand(S->getLHS());
+ Value *RHS = expand(S->getRHS());
return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
}
enum SCEVTypes {
// These should be ordered in terms of increasing complexity to make the
// folders simpler.
- scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr,
- scAddRecExpr, scUnknown, scCouldNotCompute
+ scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
+ scSDivExpr, scAddRecExpr, scUnknown, scCouldNotCompute
};
//===--------------------------------------------------------------------===//
}
};
+ //===--------------------------------------------------------------------===//
+ /// SCEVSignExtendExpr - This class represents a sign extension of a small
+ /// integer value to a larger integer value.
+ ///
+ class SCEVSignExtendExpr : public SCEV {
+ SCEVHandle Op;
+ const Type *Ty;
+ SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
+ virtual ~SCEVSignExtendExpr();
+ public:
+ /// get method - This just gets and returns a new SCEVSignExtend object
+ ///
+ static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+ const SCEVHandle &getOperand() const { return Op; }
+ virtual const Type *getType() const { return Ty; }
+
+ virtual bool isLoopInvariant(const Loop *L) const {
+ return Op->isLoopInvariant(L);
+ }
+
+ virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ return Op->hasComputableLoopEvolution(L);
+ }
+
+ /// getValueRange - Return the tightest constant bounds that this value is
+ /// known to have. This method is only valid on integer SCEV objects.
+ virtual ConstantRange getValueRange() const;
+
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+ if (H == Op)
+ return this;
+ return get(H, Ty);
+ }
+
+ virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scSignExtend;
+ }
+ };
+
//===--------------------------------------------------------------------===//
/// SCEVCommutativeExpr - This node is the base class for n'ary commutative
return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S);
case scZeroExtend:
return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S);
+ case scSignExtend:
+ return ((SC*)this)->visitSignExtendExpr((SCEVSignExtendExpr*)S);
case scAddExpr:
return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
case scMulExpr:
OS << "(zeroextend " << *Op << " to " << *Ty << ")";
}
+// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
+// particular input. Don't use a SCEVHandle here, or else the object will never
+// be deleted!
+static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+ SCEVSignExtendExpr*> > SCEVSignExtends;
+
+SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
+ : SCEV(scSignExtend), Op(op), Ty(ty) {
+ assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ "Cannot sign extend non-integer value!");
+ assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
+ && "This is not an extending conversion!");
+}
+
+SCEVSignExtendExpr::~SCEVSignExtendExpr() {
+ SCEVSignExtends->erase(std::make_pair(Op, Ty));
+}
+
+ConstantRange SCEVSignExtendExpr::getValueRange() const {
+ return getOperand()->getValueRange().signExtend(getBitWidth());
+}
+
+void SCEVSignExtendExpr::print(std::ostream &OS) const {
+ OS << "(signextend " << *Op << " to " << *Ty << ")";
+}
+
// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
return Result;
}
+SCEVHandle SCEVSignExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+ return SCEVUnknown::get(
+ ConstantExpr::getSExt(SC->getValue(), Ty));
+
+ // FIXME: If the input value is a chrec scev, and we can prove that the value
+ // did not overflow the old, smaller, value, we can sign extend all of the
+ // operands (often constants). This would allow analysis of something like
+ // this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
+
+ SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
+ if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
+ return Result;
+}
+
// get - Get a canonical add expression, or something simpler if possible.
SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S))
return GetConstantFactor(E->getOperand()).zext(
cast<IntegerType>(E->getType())->getBitWidth());
+ if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S))
+ return GetConstantFactor(E->getOperand()).sext(
+ cast<IntegerType>(E->getType())->getBitWidth());
if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands.
case Instruction::ZExt:
return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), I->getType());
+ case Instruction::SExt:
+ return SCEVSignExtendExpr::get(getSCEV(I->getOperand(0)), I->getType());
+
case Instruction::BitCast:
// BitCasts are no-op casts so we just eliminate the cast.
if (I->getType()->isInteger() &&
}
Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
- const Type *Ty = S->getType();
int FirstOp = 0; // Set if we should emit a subtract.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
if (SC->getValue()->isAllOnesValue())
FirstOp = 1;
int i = S->getNumOperands()-2;
- Value *V = expandInTy(S->getOperand(i+1), Ty);
+ Value *V = expand(S->getOperand(i+1));
// Emit a bunch of multiply instructions
for (; i >= FirstOp; --i)
- V = InsertBinop(Instruction::Mul, V, expandInTy(S->getOperand(i), Ty),
+ V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)),
InsertPt);
// -1 * ... ---> 0 - ...
if (FirstOp == 1)
// {X,+,F} --> X + {0,+,F}
if (!isa<SCEVConstant>(S->getStart()) ||
!cast<SCEVConstant>(S->getStart())->getValue()->isZero()) {
- Value *Start = expandInTy(S->getStart(), Ty);
+ Value *Start = expand(S->getStart());
std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty);
- Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty);
+ Value *Rest = expand(SCEVAddRecExpr::get(NewOps, L));
// FIXME: look for an existing add to use.
return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
// If this is a simple linear addrec, emit it now as a special case.
if (S->getNumOperands() == 2) { // {0,+,F} --> i*F
- Value *F = expandInTy(S->getOperand(1), Ty);
+ Value *F = expand(S->getOperand(1));
// IF the step is by one, just return the inserted IV.
if (ConstantInt *CI = dyn_cast<ConstantInt>(F))
SCEVHandle V = S->evaluateAtIteration(IH);
//cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
- return expandInTy(V, Ty);
+ return expand(V);
}
// Expand the code for the iteration count into the preheader of the loop.
BasicBlock *Preheader = L->getLoopPreheader();
- Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator(),
- IndVar->getType());
+ Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator());
// Insert a new icmp_ne or icmp_eq instruction before the branch.
ICmpInst::Predicate Opcode;
// just reuse it.
Value *&ExitVal = ExitValues[Inst];
if (!ExitVal)
- ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt,Inst->getType());
+ ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt);
DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< " LoopVal = " << *Inst << "\n";
Changed = true;
DOUT << "INDVARS: New CanIV: " << *IndVar;
- if (!isa<SCEVCouldNotCompute>(IterationCount))
+ if (!isa<SCEVCouldNotCompute>(IterationCount)) {
+ if (IterationCount->getType() != LargestType)
+ IterationCount = SCEVZeroExtendExpr::get(IterationCount, LargestType);
if (Instruction *DI = LinearFunctionTestReplace(L, IterationCount,Rewriter))
DeadInsts.insert(DI);
+ }
// Now that we have a canonical induction variable, we can rewrite any
// recurrences in terms of the induction variable. Start with the auxillary
std::map<unsigned, Value*> InsertedSizes;
while (!IndVars.empty()) {
PHINode *PN = IndVars.back().first;
- Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt,
- PN->getType());
+ Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt);
DOUT << "INDVARS: Rewrote IV '" << *IndVars.back().second << "' " << *PN
<< " into = " << *NewVal << "\n";
NewVal->takeName(PN);
// If there is no immediate value, skip the next part.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Imm))
if (SC->getValue()->isZero())
- return Rewriter.expandCodeFor(NewBase, BaseInsertPt,
- OperandValToReplace->getType());
+ return Rewriter.expandCodeFor(NewBase, BaseInsertPt);
Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt);
// Always emit the immediate (if non-zero) into the same block as the user.
SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(Base), Imm);
- return Rewriter.expandCodeFor(NewValSCEV, IP,
- OperandValToReplace->getType());
+ return Rewriter.expandCodeFor(NewValSCEV, IP);
}
}
}
Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
+ // Adjust the type back to match the Inst.
+ if (isa<PointerType>(OperandValToReplace->getType())) {
+ NewVal = new IntToPtrInst(NewVal, OperandValToReplace->getType(), "cast",
+ InsertPt);
+ }
// Replace the use of the operand Value with the new Phi we just created.
Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
DOUT << " CHANGED: IMM =" << *Imm;
// Insert the code into the end of the predecessor block.
Instruction *InsertPt = PN->getIncomingBlock(i)->getTerminator();
Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
+
+ // Adjust the type back to match the PHI.
+ if (isa<PointerType>(PN->getType())) {
+ Code = new IntToPtrInst(Code, PN->getType(), "cast", InsertPt);
+ }
}
// Replace the use of the operand Value with the new Phi we just created.
// Emit the initial base value into the loop preheader.
Value *CommonBaseV
- = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt,
- ReplacedTy);
+ = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt);
if (RewriteFactor == 0) {
// Create a new Phi for this base, and stick it in the loop header.
IncAmount = SCEV::getNegativeSCEV(Stride);
// Insert the stride into the preheader.
- Value *StrideV = PreheaderRewriter.expandCodeFor(IncAmount, PreInsertPt,
- ReplacedTy);
+ Value *StrideV = PreheaderRewriter.expandCodeFor(IncAmount, PreInsertPt);
if (!isa<ConstantInt>(StrideV)) ++NumVariable;
// Emit the increment of the base value before the terminator of the loop
IncExp = SCEV::getNegativeSCEV(IncExp);
IncExp = SCEVAddExpr::get(SCEVUnknown::get(NewPHI), IncExp);
- IncV = Rewriter.expandCodeFor(IncExp, LatchBlock->getTerminator(),
- ReplacedTy);
+ IncV = Rewriter.expandCodeFor(IncExp, LatchBlock->getTerminator());
IncV->setName(NewPHI->getName()+".inc");
NewPHI->addIncoming(IncV, LatchBlock);
SCEVHandle Base = UsersToProcess.back().Base;
// Emit the code for Base into the preheader.
- Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt,
- ReplacedTy);
+ Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt);
DOUT << " INSERTING code for BASE = " << *Base << ":";
if (BaseV->hasName())
projects / oota-llvm.git / commitdiff