#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.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;
const TargetLowering *TLI;
public:
- LoopStrengthReduce(const TargetLowering *tli = NULL)
- : TLI(tli) {
+ static char ID; // Pass ID, replacement for typeid
+ explicit LoopStrengthReduce(const TargetLowering *tli = NULL) :
+ LoopPass((intptr_t)&ID), TLI(tli) {
}
bool runOnLoop(Loop *L, LPPassManager &LPM);
// many analyses if they are around.
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<LoopInfo>();
- AU.addPreserved<DominatorSet>();
- AU.addPreserved<ETForest>();
- AU.addPreserved<ImmediateDominators>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<DominatorTree>();
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
- AU.addRequired<ETForest>();
+ AU.addRequired<DominatorTree>();
AU.addRequired<TargetData>();
AU.addRequired<ScalarEvolution>();
}
SCEVHandle GetExpressionSCEV(Instruction *E, Loop *L);
void OptimizeIndvars(Loop *L);
+ bool FindIVForUser(ICmpInst *Cond, IVStrideUse *&CondUse,
+ const SCEVHandle *&CondStride);
unsigned CheckForIVReuse(const SCEVHandle&, IVExpr&, const Type*,
const std::vector<BasedUser>& UsersToProcess);
Loop *L, bool isOnlyStride);
void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
};
+ char LoopStrengthReduce::ID = 0;
RegisterPass<LoopStrengthReduce> X("loop-reduce", "Loop Strength Reduction");
}
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;
}
/// GetExpressionSCEV - Compute and return the SCEV for the specified
/// instruction.
SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) {
+ // Pointer to pointer bitcast instructions return the same value as their
+ // operand.
+ if (BitCastInst *BCI = dyn_cast<BitCastInst>(Exp)) {
+ if (SE->hasSCEV(BCI) || !isa<Instruction>(BCI->getOperand(0)))
+ return SE->getSCEV(BCI);
+ SCEVHandle R = GetExpressionSCEV(cast<Instruction>(BCI->getOperand(0)), L);
+ SE->setSCEV(BCI, R);
+ return R;
+ }
+
// Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
// If this is a GEP that SE doesn't know about, compute it now and insert it.
// If this is not a GEP, or if we have already done this computation, just let
/// 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;
}
if (!getSCEVStartAndStride(ISE, L, Start, Stride))
return false; // Non-reducible symbolic expression, bail out.
- for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;) {
- Instruction *User = cast<Instruction>(*UI);
+ std::vector<Instruction *> IUsers;
+ // Collect all I uses now because IVUseShouldUsePostIncValue may
+ // invalidate use_iterator.
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
+ IUsers.push_back(cast<Instruction>(*UI));
+
+ for (unsigned iused_index = 0, iused_size = IUsers.size();
+ iused_index != iused_size; ++iused_index) {
- // Increment iterator now because IVUseShouldUsePostIncValue may remove
- // User from the list of I users.
- ++UI;
+ Instruction *User = IUsers[iused_index];
// Do not infinitely recurse on PHI nodes.
if (isa<PHINode>(User) && Processed.count(User))
// 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);
+
}
SCEVExpander &Rewriter,
Loop *L, Pass *P) {
if (!isa<PHINode>(Inst)) {
- Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, Inst, L);
+ // By default, insert code at the user instruction.
+ BasicBlock::iterator InsertPt = Inst;
+
+ // However, if the Operand is itself an instruction, the (potentially
+ // complex) inserted code may be shared by many users. Because of this, we
+ // want to emit code for the computation of the operand right before its old
+ // computation. This is usually safe, because we obviously used to use the
+ // computation when it was computed in its current block. However, in some
+ // cases (e.g. use of a post-incremented induction variable) the NewBase
+ // value will be pinned to live somewhere after the original computation.
+ // In this case, we have to back off.
+ if (!isUseOfPostIncrementedValue) {
+ if (Instruction *OpInst = dyn_cast<Instruction>(OperandValToReplace)) {
+ InsertPt = OpInst;
+ 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.
const TargetLowering *TLI) {
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
int64_t VC = SC->getValue()->getSExtValue();
- if (TLI)
- return TLI->isLegalAddressImmediate(VC, UseTy);
- else
+ if (TLI) {
+ TargetLowering::AddrMode AM;
+ AM.BaseOffs = VC;
+ return TLI->isLegalAddressingMode(AM, UseTy);
+ } else {
// Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
return (VC > -(1 << 16) && VC < (1 << 16)-1);
+ }
}
if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
- if (CE->getOpcode() == Instruction::PtrToInt) {
+ if (TLI && CE->getOpcode() == Instruction::PtrToInt) {
Constant *Op0 = CE->getOperand(0);
- if (isa<GlobalValue>(Op0) && TLI &&
- TLI->isLegalAddressImmediate(cast<GlobalValue>(Op0)))
- return true;
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(Op0)) {
+ TargetLowering::AddrMode AM;
+ AM.BaseGV = GV;
+ return TLI->isLegalAddressingMode(AM, UseTy);
+ }
}
return false;
}
}
/// ValidStride - Check whether the given Scale is valid for all loads and
-/// stores in UsersToProcess. Pulled into a function to avoid disturbing the
-/// sensibilities of those who dislike goto's.
+/// stores in UsersToProcess.
///
bool LoopStrengthReduce::ValidStride(int64_t Scale,
const std::vector<BasedUser>& UsersToProcess) {
- for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i)
- if (!TLI->isLegalAddressScale(Scale, UsersToProcess[i].Inst->getType()))
+ for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
+ // If this is a load or other access, pass the type of the access in.
+ const Type *AccessTy = Type::VoidTy;
+ if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
+ AccessTy = SI->getOperand(0)->getType();
+ else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
+ AccessTy = LI->getType();
+
+ TargetLowering::AddrMode AM;
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
+ AM.BaseOffs = SC->getValue()->getSExtValue();
+ AM.Scale = Scale;
+
+ // If load[imm+r*scale] is illegal, bail out.
+ if (!TLI->isLegalAddressingMode(AM, AccessTy))
return false;
+ }
return true;
}
for (std::map<SCEVHandle, IVsOfOneStride>::iterator SI= IVsByStride.begin(),
SE = IVsByStride.end(); SI != SE; ++SI) {
int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
- if (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0)
+ if (SInt != -SSInt &&
+ (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
continue;
int64_t Scale = SInt / SSInt;
// Check that this stride is valid for all the types used for loads and
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).
SCEVHandle CommonExprs =
RemoveCommonExpressionsFromUseBases(UsersToProcess);
- // Check if it is possible to reuse a IV with stride that is factor of this
- // stride. And the multiple is a number that can be encoded in the scale
- // field of the target addressing mode.
- PHINode *NewPHI = NULL;
- Value *IncV = NULL;
- IVExpr ReuseIV;
- unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
- CommonExprs->getType(),
- UsersToProcess);
- if (RewriteFactor != 0) {
- DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
- << " and BASE " << *ReuseIV.Base << " :\n";
- NewPHI = ReuseIV.PHI;
- IncV = ReuseIV.IncV;
- }
-
// Next, figure out what we can represent in the immediate fields of
// instructions. If we can represent anything there, move it to the imm
// fields of the BasedUsers. We do this so that it increases the commonality
// Addressing modes can be folded into loads and stores. Be careful that
// the store is through the expression, not of the expression though.
bool isAddress = isa<LoadInst>(UsersToProcess[i].Inst);
- if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
+ if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst)) {
if (SI->getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
+ } else if (IntrinsicInst *II =
+ dyn_cast<IntrinsicInst>(UsersToProcess[i].Inst)) {
+ // Addressing modes can also be folded into prefetches.
+ if (II->getIntrinsicID() == Intrinsic::prefetch &&
+ II->getOperand(1) == UsersToProcess[i].OperandValToReplace)
+ isAddress = true;
+ }
MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
UsersToProcess[i].Imm, isAddress, L);
}
}
+ // Check if it is possible to reuse a IV with stride that is factor of this
+ // stride. And the multiple is a number that can be encoded in the scale
+ // field of the target addressing mode. And we will have a valid
+ // instruction after this substition, including the immediate field, if any.
+ PHINode *NewPHI = NULL;
+ Value *IncV = NULL;
+ IVExpr ReuseIV;
+ unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
+ CommonExprs->getType(),
+ UsersToProcess);
+ if (RewriteFactor != 0) {
+ DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
+ << " and BASE " << *ReuseIV.Base << " :\n";
+ NewPHI = ReuseIV.PHI;
+ IncV = ReuseIV.IncV;
+ }
+
+ const Type *ReplacedTy = CommonExprs->getType();
+
// Now that we know what we need to do, insert the PHI node itself.
//
- DOUT << "INSERTING IV of STRIDE " << *Stride << " and BASE "
- << *CommonExprs << " :\n";
+ DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE "
+ << *Stride << " and BASE " << *CommonExprs << ": ";
SCEVExpander Rewriter(*SE, *LI);
SCEVExpander PreheaderRewriter(*SE, *LI);
BasicBlock *LatchBlock = L->getLoopLatch();
- const Type *ReplacedTy = CommonExprs->getType();
// 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
// different starting values, into different PHIs.
}
+/// FindIVForUser - If Cond has an operand that is an expression of an IV,
+/// set the IV user and stride information and return true, otherwise return
+/// false.
+bool LoopStrengthReduce::FindIVForUser(ICmpInst *Cond, IVStrideUse *&CondUse,
+ const SCEVHandle *&CondStride) {
+ for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e && !CondUse;
+ ++Stride) {
+ std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
+ IVUsesByStride.find(StrideOrder[Stride]);
+ assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
+
+ for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
+ E = SI->second.Users.end(); UI != E; ++UI)
+ if (UI->User == Cond) {
+ // NOTE: we could handle setcc instructions with multiple uses here, but
+ // InstCombine does it as well for simple uses, it's not clear that it
+ // occurs enough in real life to handle.
+ CondUse = &*UI;
+ CondStride = &SI->first;
+ return true;
+ }
+ }
+ return false;
+}
+
// OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar
// uses in the loop, look to see if we can eliminate some, in favor of using
// common indvars for the different uses.
IVStrideUse *CondUse = 0;
const SCEVHandle *CondStride = 0;
- for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e && !CondUse;
- ++Stride) {
- std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
- IVUsesByStride.find(StrideOrder[Stride]);
- assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
-
- for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
- E = SI->second.Users.end(); UI != E; ++UI)
- if (UI->User == Cond) {
- CondUse = &*UI;
- CondStride = &SI->first;
- // NOTE: we could handle setcc instructions with multiple uses here, but
- // InstCombine does it as well for simple uses, it's not clear that it
- // occurs enough in real life to handle.
- break;
- }
- }
- if (!CondUse) return; // setcc doesn't use the IV.
+ if (!FindIVForUser(Cond, CondUse, CondStride))
+ return; // setcc doesn't use the IV.
+
// It's possible for the setcc instruction to be anywhere in the loop, and
// possible for it to have multiple users. If it is not immediately before
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