Expand GEPs in ScalarEvolution expressions. SCEV expressions can now
have pointer types, though in contrast to C pointer types, SCEV
addition is never implicitly scaled. This not only eliminates the
need for special code like IndVars' EliminatePointerRecurrence
and LSR's own GEP expansion code, it also does a better job because
it lets the normal optimizations handle pointer expressions just
like integer expressions.
Also, since LLVM IR GEPs can't directly index into multi-dimensional
VLAs, moving the GEP analysis out of client code and into the SCEV
framework makes it easier for clients to handle multi-dimensional
VLAs the same way as other arrays.
Some existing regression tests show improved optimization.
test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to
the point where if-conversion started kicking in; I turned it off
for this test to preserve the intent of the test.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 30df087..d91061b 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -15,12 +15,17 @@
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Target/TargetData.h"
using namespace llvm;
/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
/// we can to share the casts.
Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
const Type *Ty) {
+ // Short-circuit unnecessary bitcasts.
+ if (opcode == Instruction::BitCast && V->getType() == Ty)
+ return V;
+
// FIXME: keep track of the cast instruction.
if (Constant *C = dyn_cast<Constant>(V))
return ConstantExpr::getCast(opcode, C, Ty);
@@ -100,16 +105,23 @@
}
Value *SCEVExpander::visitAddExpr(SCEVAddExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
Value *V = expand(S->getOperand(S->getNumOperands()-1));
+ V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
// Emit a bunch of add instructions
- for (int i = S->getNumOperands()-2; i >= 0; --i)
- V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)),
- InsertPt);
+ for (int i = S->getNumOperands()-2; i >= 0; --i) {
+ Value *W = expand(S->getOperand(i));
+ W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
+ V = InsertBinop(Instruction::Add, V, W, InsertPt);
+ }
return V;
}
Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
int FirstOp = 0; // Set if we should emit a subtract.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
if (SC->getValue()->isAllOnesValue())
@@ -117,29 +129,37 @@
int i = S->getNumOperands()-2;
Value *V = expand(S->getOperand(i+1));
+ V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
// Emit a bunch of multiply instructions
- for (; i >= FirstOp; --i)
- V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)),
- InsertPt);
+ for (; i >= FirstOp; --i) {
+ Value *W = expand(S->getOperand(i));
+ W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
+ V = InsertBinop(Instruction::Mul, V, W, InsertPt);
+ }
+
// -1 * ... ---> 0 - ...
if (FirstOp == 1)
- V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V,
- InsertPt);
+ V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt);
return V;
}
Value *SCEVExpander::visitUDivExpr(SCEVUDivExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
+
Value *LHS = expand(S->getLHS());
+ LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty);
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
const APInt &RHS = SC->getValue()->getValue();
if (RHS.isPowerOf2())
return InsertBinop(Instruction::LShr, LHS,
- ConstantInt::get(S->getType(), RHS.logBase2()),
+ ConstantInt::get(Ty, RHS.logBase2()),
InsertPt);
}
Value *RHS = expand(S->getRHS());
+ RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), RHS, Ty);
return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
}
@@ -147,14 +167,19 @@
const Type *Ty = S->getType();
const Loop *L = S->getLoop();
// We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
- assert(Ty->isInteger() && "Cannot expand fp recurrences yet!");
+ assert((Ty->isInteger() || isa<PointerType>(Ty)) &&
+ "Cannot expand fp recurrences yet!");
// {X,+,F} --> X + {0,+,F}
if (!S->getStart()->isZero()) {
Value *Start = expand(S->getStart());
+ if (isa<PointerType>(Start->getType()))
+ Start = InsertCastOfTo(Instruction::PtrToInt, Start, TD.getIntPtrType());
std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
NewOps[0] = SE.getIntegerSCEV(0, Ty);
Value *Rest = expand(SE.getAddRecExpr(NewOps, L));
+ if (isa<PointerType>(Rest->getType()))
+ Rest = InsertCastOfTo(Instruction::PtrToInt, Rest, TD.getIntPtrType());
// FIXME: look for an existing add to use.
return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
@@ -242,16 +267,22 @@
Value *SCEVExpander::visitTruncateExpr(SCEVTruncateExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateTruncOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
Value *SCEVExpander::visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateZExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
Value *SCEVExpander::visitSignExtendExpr(SCEVSignExtendExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateSExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
@@ -275,10 +306,14 @@
return LHS;
}
-Value *SCEVExpander::expandCodeFor(SCEVHandle SH, Instruction *IP) {
+Value *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty,
+ Instruction *IP) {
// Expand the code for this SCEV.
+ assert(TD.getTypeSizeInBits(Ty) == TD.getTypeSizeInBits(SH->getType()) &&
+ "non-trivial casts should be done with the SCEVs directly!");
this->InsertPt = IP;
- return expand(SH);
+ Value *V = expand(SH);
+ return InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
}
Value *SCEVExpander::expand(SCEV *S) {