#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
-#include "llvm/Intrinsics.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/Dominators.h"
class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
LoopInfo *LI;
- ETForest *EF;
+ DominatorTree *DT;
ScalarEvolution *SE;
const TargetData *TD;
const Type *UIntPtrTy;
public:
static char ID; // Pass ID, replacement for typeid
- LoopStrengthReduce(const TargetLowering *tli = NULL) :
+ explicit LoopStrengthReduce(const TargetLowering *tli = NULL) :
LoopPass((intptr_t)&ID), TLI(tli) {
}
// many analyses if they are around.
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<LoopInfo>();
- AU.addPreserved<ETForest>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<DominatorTree>();
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
- AU.addRequired<ETForest>();
+ AU.addRequired<DominatorTree>();
AU.addRequired<TargetData>();
AU.addRequired<ScalarEvolution>();
}
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
Insts.insert(U);
- SE->deleteInstructionFromRecords(I);
+ SE->deleteValueFromRecords(I);
I->eraseFromParent();
Changed = true;
}
/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
/// should use the post-inc value).
static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
- Loop *L, ETForest *EF, Pass *P) {
+ Loop *L, DominatorTree *DT, Pass *P) {
// If the user is in the loop, use the preinc value.
if (L->contains(User->getParent())) return false;
// Ok, the user is outside of the loop. If it is dominated by the latch
// block, use the post-inc value.
- if (EF->dominates(LatchBlock, User->getParent()))
+ if (DT->dominates(LatchBlock, User->getParent()))
return true;
// There is one case we have to be careful of: PHI nodes. These little guys
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingValue(i) == IV) {
++NumUses;
- if (!EF->dominates(LatchBlock, PN->getIncomingBlock(i)))
+ if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
return false;
}
// Okay, we found a user that we cannot reduce. Analyze the instruction
// and decide what to do with it. If we are a use inside of the loop, use
// the value before incrementation, otherwise use it after incrementation.
- if (IVUseShouldUsePostIncValue(User, I, L, EF, this)) {
+ if (IVUseShouldUsePostIncValue(User, I, L, DT, this)) {
// The value used will be incremented by the stride more than we are
// expecting, so subtract this off.
SCEVHandle NewStart = SCEV::getMinusSCEV(Start, Stride);
// 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);
+
+ // If we are inserting the base and imm values in the same block, make sure to
+ // adjust the IP position if insertion reused a result.
+ if (IP == BaseInsertPt)
+ IP = Rewriter.getInsertionPoint();
// 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);
+
}
while (isa<PHINode>(InsertPt)) ++InsertPt;
}
}
-
Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
+ // Adjust the type back to match the Inst. Note that we can't use InsertPt
+ // here because the SCEVExpander may have inserted the instructions after
+ // that point, in its efforts to avoid inserting redundant expressions.
+ if (isa<PointerType>(OperandValToReplace->getType())) {
+ NewVal = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
+ NewVal,
+ OperandValToReplace->getType());
+ }
// Replace the use of the operand Value with the new Phi we just created.
Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
- DOUT << " CHANGED: IMM =" << *Imm << " Inst = " << *Inst;
+ DOUT << " CHANGED: IMM =" << *Imm;
+ DOUT << " \tNEWBASE =" << *NewBase;
+ DOUT << " \tInst = " << *Inst;
return;
}
// 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. Note that we can't use
+ // InsertPt here because the SCEVExpander may have inserted its
+ // instructions after that point, in its efforts to avoid inserting
+ // redundant expressions.
+ if (isa<PointerType>(PN->getType())) {
+ Code = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
+ Code,
+ PN->getType());
+ }
}
// Replace the use of the operand Value with the new Phi we just created.
return Val.isUseOfPostIncrementedValue;
}
+/// isNonConstantNegative - REturn true if the specified scev is negated, but
+/// not a constant.
+static bool isNonConstantNegative(const SCEVHandle &Expr) {
+ SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr);
+ if (!Mul) return false;
+
+ // If there is a constant factor, it will be first.
+ SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
+ if (!SC) return false;
+
+ // Return true if the value is negative, this matches things like (-42 * V).
+ return SC->getValue()->getValue().isNegative();
+}
+
/// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
/// stride of IV. All of the users may have different starting values, and this
/// may not be the only stride (we know it is if isOnlyStride is true).
if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst)) {
if (SI->getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
- } else if (CallInst *CI = dyn_cast<CallInst>(UsersToProcess[i].Inst)) {
+ } else if (IntrinsicInst *II =
+ dyn_cast<IntrinsicInst>(UsersToProcess[i].Inst)) {
// Addressing modes can also be folded into prefetches.
- Function *CalledFunc = CI->getCalledFunction();
- if (CalledFunc != NULL &&
- CalledFunc->getIntrinsicID() == Intrinsic::prefetch &&
- CI->getOperand(1) == UsersToProcess[i].OperandValToReplace)
+ if (II->getIntrinsicID() == Intrinsic::prefetch &&
+ II->getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
}
// Now that we know what we need to do, insert the PHI node itself.
//
DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE "
- << *Stride << " and BASE " << *CommonExprs << " :\n";
+ << *Stride << " and BASE " << *CommonExprs << ": ";
SCEVExpander Rewriter(*SE, *LI);
SCEVExpander PreheaderRewriter(*SE, *LI);
// 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.
// Add common base to the new Phi node.
NewPHI->addIncoming(CommonBaseV, Preheader);
+ // If the stride is negative, insert a sub instead of an add for the
+ // increment.
+ bool isNegative = isNonConstantNegative(Stride);
+ SCEVHandle IncAmount = Stride;
+ if (isNegative)
+ IncAmount = SCEV::getNegativeSCEV(Stride);
+
// Insert the stride into the preheader.
- Value *StrideV = PreheaderRewriter.expandCodeFor(Stride, 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
// latch block, and add it to the Phi node.
- SCEVHandle IncExp = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
- SCEVUnknown::get(StrideV));
+ SCEVHandle IncExp = SCEVUnknown::get(StrideV);
+ if (isNegative)
+ 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);
// Remember this in case a later stride is multiple of this.
IVsByStride[Stride].addIV(Stride, CommonExprs, NewPHI, IncV);
+
+ DOUT << " IV=%" << NewPHI->getNameStr() << " INC=%" << IncV->getNameStr();
} else {
Constant *C = dyn_cast<Constant>(CommonBaseV);
if (!C ||
CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(),
"commonbase", PreInsertPt);
}
+ DOUT << "\n";
// We want to emit code for users inside the loop first. To do this, we
// rearrange BasedUser so that the entries at the end have
while (!UsersToProcess.empty()) {
SCEVHandle Base = UsersToProcess.back().Base;
- DOUT << " INSERTING code for BASE = " << *Base << ":\n";
-
// 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())
+ DOUT << " Result value name = %" << BaseV->getNameStr();
+ DOUT << "\n";
+
// If BaseV is a constant other than 0, make sure that it gets inserted into
// the preheader, instead of being forward substituted into the uses. We do
// this by forcing a BitCast (noop cast) to be inserted into the preheader
bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
LI = &getAnalysis<LoopInfo>();
- EF = &getAnalysis<ETForest>();
+ DT = &getAnalysis<DominatorTree>();
SE = &getAnalysis<ScalarEvolution>();
TD = &getAnalysis<TargetData>();
UIntPtrTy = TD->getIntPtrType();
DeadInsts.insert(BO);
// Break the cycle, then delete the PHI.
PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
- SE->deleteInstructionFromRecords(PN);
+ SE->deleteValueFromRecords(PN);
PN->eraseFromParent();
}
}
projects / oota-llvm.git / blobdiff