aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Analysis/IVUsers.cpp391
-rw-r--r--lib/Target/README.txt10
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp935
-rw-r--r--lib/Transforms/Scalar/LoopStrengthReduce.cpp569
4 files changed, 975 insertions, 930 deletions
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
new file mode 100644
index 0000000000..9ec9cacbbb
--- /dev/null
+++ b/lib/Analysis/IVUsers.cpp
@@ -0,0 +1,391 @@
+//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements bookkeeping for "interesting" users of expressions
+// computed from induction variables.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "iv-users"
+#include "llvm/Analysis/IVUsers.h"
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+using namespace llvm;
+
+char IVUsers::ID = 0;
+static RegisterPass<IVUsers>
+X("iv-users", "Induction Variable Users", false, true);
+
+Pass *llvm::createIVUsersPass() {
+ return new IVUsers();
+}
+
+/// containsAddRecFromDifferentLoop - Determine whether expression S involves a
+/// subexpression that is an AddRec from a loop other than L. An outer loop
+/// of L is OK, but not an inner loop nor a disjoint loop.
+static bool containsAddRecFromDifferentLoop(SCEVHandle S, Loop *L) {
+ // This is very common, put it first.
+ if (isa<SCEVConstant>(S))
+ return false;
+ if (const SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) {
+ for (unsigned int i=0; i< AE->getNumOperands(); i++)
+ if (containsAddRecFromDifferentLoop(AE->getOperand(i), L))
+ return true;
+ return false;
+ }
+ if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
+ if (const Loop *newLoop = AE->getLoop()) {
+ if (newLoop == L)
+ return false;
+ // if newLoop is an outer loop of L, this is OK.
+ if (!LoopInfoBase<BasicBlock>::isNotAlreadyContainedIn(L, newLoop))
+ return false;
+ }
+ return true;
+ }
+ if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
+ return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
+ containsAddRecFromDifferentLoop(DE->getRHS(), L);
+#if 0
+ // SCEVSDivExpr has been backed out temporarily, but will be back; we'll
+ // need this when it is.
+ if (const SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S))
+ return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
+ containsAddRecFromDifferentLoop(DE->getRHS(), L);
+#endif
+ if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S))
+ return containsAddRecFromDifferentLoop(CE->getOperand(), L);
+ return false;
+}
+
+/// getSCEVStartAndStride - Compute the start and stride of this expression,
+/// returning false if the expression is not a start/stride pair, or true if it
+/// is. The stride must be a loop invariant expression, but the start may be
+/// a mix of loop invariant and loop variant expressions. The start cannot,
+/// however, contain an AddRec from a different loop, unless that loop is an
+/// outer loop of the current loop.
+static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, Loop *UseLoop,
+ SCEVHandle &Start, SCEVHandle &Stride,
+ bool &isSigned,
+ ScalarEvolution *SE, DominatorTree *DT) {
+ SCEVHandle TheAddRec = Start; // Initialize to zero.
+ bool isSExt = false;
+ bool isZExt = false;
+
+ // If the outer level is an AddExpr, the operands are all start values except
+ // for a nested AddRecExpr.
+ if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
+ for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
+ if (const SCEVAddRecExpr *AddRec =
+ dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
+ if (AddRec->getLoop() == L)
+ TheAddRec = SE->getAddExpr(AddRec, TheAddRec);
+ else
+ return false; // Nested IV of some sort?
+ } else {
+ Start = SE->getAddExpr(Start, AE->getOperand(i));
+ }
+
+ } else if (const SCEVZeroExtendExpr *Z = dyn_cast<SCEVZeroExtendExpr>(SH)) {
+ TheAddRec = Z->getOperand();
+ isZExt = true;
+ } else if (const SCEVSignExtendExpr *S = dyn_cast<SCEVSignExtendExpr>(SH)) {
+ TheAddRec = S->getOperand();
+ isSExt = true;
+ } else if (isa<SCEVAddRecExpr>(SH)) {
+ TheAddRec = SH;
+ } else {
+ return false; // not analyzable.
+ }
+
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(TheAddRec);
+ if (!AddRec || AddRec->getLoop() != L) return false;
+
+ // Use getSCEVAtScope to attempt to simplify other loops out of
+ // the picture.
+ SCEVHandle AddRecStart = AddRec->getStart();
+ SCEVHandle BetterAddRecStart = SE->getSCEVAtScope(AddRecStart, UseLoop);
+ if (!isa<SCEVCouldNotCompute>(BetterAddRecStart))
+ AddRecStart = BetterAddRecStart;
+
+ // FIXME: If Start contains an SCEVAddRecExpr from a different loop, other
+ // than an outer loop of the current loop, reject it. LSR has no concept of
+ // operating on more than one loop at a time so don't confuse it with such
+ // expressions.
+ if (containsAddRecFromDifferentLoop(AddRecStart, L))
+ return false;
+
+ if (isSExt || isZExt)
+ Start = SE->getTruncateExpr(Start, AddRec->getType());
+
+ Start = SE->getAddExpr(Start, AddRecStart);
+
+ if (!isa<SCEVConstant>(AddRec->getStepRecurrence(*SE))) {
+ // If stride is an instruction, make sure it dominates the loop preheader.
+ // Otherwise we could end up with a use before def situation.
+ BasicBlock *Preheader = L->getLoopPreheader();
+ if (!AddRec->getStepRecurrence(*SE)->dominates(Preheader, DT))
+ return false;
+
+ DOUT << "[" << L->getHeader()->getName()
+ << "] Variable stride: " << *AddRec << "\n";
+ }
+
+ Stride = AddRec->getStepRecurrence(*SE);
+ isSigned = isSExt;
+ return true;
+}
+
+/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
+/// and now we need to decide whether the user should use the preinc or post-inc
+/// value. If this user should use the post-inc version of the IV, return true.
+///
+/// Choosing wrong here can break dominance properties (if we choose to use the
+/// post-inc value when we cannot) or it can end up adding extra live-ranges to
+/// 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, LoopInfo *LI, DominatorTree *DT,
+ Pass *P) {
+ // If the user is in the loop, use the preinc value.
+ if (L->contains(User->getParent())) return false;
+
+ BasicBlock *LatchBlock = L->getLoopLatch();
+
+ // Ok, the user is outside of the loop. If it is dominated by the latch
+ // block, use the post-inc value.
+ if (DT->dominates(LatchBlock, User->getParent()))
+ return true;
+
+ // There is one case we have to be careful of: PHI nodes. These little guys
+ // can live in blocks that are not dominated by the latch block, but (since
+ // their uses occur in the predecessor block, not the block the PHI lives in)
+ // should still use the post-inc value. Check for this case now.
+ PHINode *PN = dyn_cast<PHINode>(User);
+ if (!PN) return false; // not a phi, not dominated by latch block.
+
+ // Look at all of the uses of IV by the PHI node. If any use corresponds to
+ // a block that is not dominated by the latch block, give up and use the
+ // preincremented value.
+ unsigned NumUses = 0;
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (PN->getIncomingValue(i) == IV) {
+ ++NumUses;
+ if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
+ return false;
+ }
+
+ // Okay, all uses of IV by PN are in predecessor blocks that really are
+ // dominated by the latch block. Use the post-incremented value.
+ return true;
+}
+
+/// AddUsersIfInteresting - Inspect the specified instruction. If it is a
+/// reducible SCEV, recursively add its users to the IVUsesByStride set and
+/// return true. Otherwise, return false.
+bool IVUsers::AddUsersIfInteresting(Instruction *I) {
+ if (!SE->isSCEVable(I->getType()))
+ return false; // Void and FP expressions cannot be reduced.
+
+ // LSR is not APInt clean, do not touch integers bigger than 64-bits.
+ if (SE->getTypeSizeInBits(I->getType()) > 64)
+ return false;
+
+ if (!Processed.insert(I))
+ return true; // Instruction already handled.
+
+ // Get the symbolic expression for this instruction.
+ SCEVHandle ISE = SE->getSCEV(I);
+ if (isa<SCEVCouldNotCompute>(ISE)) return false;
+
+ // Get the start and stride for this expression.
+ Loop *UseLoop = LI->getLoopFor(I->getParent());
+ SCEVHandle Start = SE->getIntegerSCEV(0, ISE->getType());
+ SCEVHandle Stride = Start;
+ bool isSigned;
+
+ if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, isSigned, SE, DT))
+ return false; // Non-reducible symbolic expression, bail out.
+
+ SmallPtrSet<Instruction *, 4> UniqueUsers;
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+ UI != E; ++UI) {
+ Instruction *User = cast<Instruction>(*UI);
+ if (!UniqueUsers.insert(User))
+ continue;
+
+ // Do not infinitely recurse on PHI nodes.
+ if (isa<PHINode>(User) && Processed.count(User))
+ continue;
+
+ // Descend recursively, but not into PHI nodes outside the current loop.
+ // It's important to see the entire expression outside the loop to get
+ // choices that depend on addressing mode use right, although we won't
+ // consider references ouside the loop in all cases.
+ // If User is already in Processed, we don't want to recurse into it again,
+ // but do want to record a second reference in the same instruction.
+ bool AddUserToIVUsers = false;
+ if (LI->getLoopFor(User->getParent()) != L) {
+ if (isa<PHINode>(User) || Processed.count(User) ||
+ !AddUsersIfInteresting(User)) {
+ DOUT << "FOUND USER in other loop: " << *User
+ << " OF SCEV: " << *ISE << "\n";
+ AddUserToIVUsers = true;
+ }
+ } else if (Processed.count(User) ||
+ !AddUsersIfInteresting(User)) {
+ DOUT << "FOUND USER: " << *User
+ << " OF SCEV: " << *ISE << "\n";
+ AddUserToIVUsers = true;
+ }
+
+ if (AddUserToIVUsers) {
+ IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride];
+ if (!StrideUses) { // First occurrence of this stride?
+ StrideOrder.push_back(Stride);
+ StrideUses = new IVUsersOfOneStride(Stride);
+ IVUses.push_back(StrideUses);
+ IVUsesByStride[Stride] = StrideUses;
+ }
+
+ // 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, LI, DT, this)) {
+ // The value used will be incremented by the stride more than we are
+ // expecting, so subtract this off.
+ SCEVHandle NewStart = SE->getMinusSCEV(Start, Stride);
+ StrideUses->addUser(NewStart, User, I, isSigned);
+ StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
+ DOUT << " USING POSTINC SCEV, START=" << *NewStart<< "\n";
+ } else {
+ StrideUses->addUser(Start, User, I, isSigned);
+ }
+ }
+ }
+ return true;
+}
+
+IVUsers::IVUsers()
+ : LoopPass(&ID) {
+}
+
+void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<DominatorTree>();
+ AU.addRequired<ScalarEvolution>();
+ AU.setPreservesAll();
+}
+
+bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
+
+ L = l;
+ LI = &getAnalysis<LoopInfo>();
+ DT = &getAnalysis<DominatorTree>();
+ SE = &getAnalysis<ScalarEvolution>();
+
+ // Find all uses of induction variables in this loop, and categorize
+ // them by stride. Start by finding all of the PHI nodes in the header for
+ // this loop. If they are induction variables, inspect their uses.
+ for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
+ AddUsersIfInteresting(I);
+
+ return false;
+}
+
+/// getReplacementExpr - Return a SCEV expression which computes the
+/// value of the OperandValToReplace of the given IVStrideUse.
+SCEVHandle IVUsers::getReplacementExpr(const IVStrideUse &U) const {
+ const Type *UseTy = U.getOperandValToReplace()->getType();
+ // Start with zero.
+ SCEVHandle RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
+ // Create the basic add recurrence.
+ RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L);
+ // Add the offset in a separate step, because it may be loop-variant.
+ RetVal = SE->getAddExpr(RetVal, U.getOffset());
+ // For uses of post-incremented values, add an extra stride to compute
+ // the actual replacement value.
+ if (U.isUseOfPostIncrementedValue())
+ RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
+ // Evaluate the expression out of the loop, if possible.
+ if (!L->contains(U.getUser()->getParent())) {
+ SCEVHandle ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
+ if (!isa<SCEVCouldNotCompute>(ExitVal) && ExitVal->isLoopInvariant(L))
+ RetVal = ExitVal;
+ }
+ // Promote the result to the type of the use.
+ if (SE->getTypeSizeInBits(RetVal->getType()) !=
+ SE->getTypeSizeInBits(UseTy)) {
+ if (U.isSigned())
+ RetVal = SE->getSignExtendExpr(RetVal, UseTy);
+ else
+ RetVal = SE->getZeroExtendExpr(RetVal, UseTy);
+ }
+ return RetVal;
+}
+
+void IVUsers::print(raw_ostream &OS, const Module *M) const {
+ OS << "IV Users for loop ";
+ WriteAsOperand(OS, L->getHeader(), false);
+ if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
+ OS << " with backedge-taken count "
+ << *SE->getBackedgeTakenCount(L);
+ }
+ OS << ":\n";
+
+ for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) {
+ std::map<SCEVHandle, IVUsersOfOneStride*>::const_iterator SI =
+ IVUsesByStride.find(StrideOrder[Stride]);
+ assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
+ OS << " Stride " << *SI->first->getType() << " " << *SI->first << ":\n";
+
+ for (ilist<IVStrideUse>::const_iterator UI = SI->second->Users.begin(),
+ E = SI->second->Users.end(); UI != E; ++UI) {
+ OS << " ";
+ WriteAsOperand(OS, UI->getOperandValToReplace(), false);
+ OS << " = ";
+ OS << *getReplacementExpr(*UI);
+ if (UI->isUseOfPostIncrementedValue())
+ OS << " (post-inc)";
+ OS << " in ";
+ UI->getUser()->print(OS);
+ }
+ }
+}
+
+void IVUsers::print(std::ostream &o, const Module *M) const {
+ raw_os_ostream OS(o);
+ print(OS, M);
+}
+
+void IVUsers::dump() const {
+ print(errs());
+}
+
+void IVUsers::releaseMemory() {
+ IVUsesByStride.clear();
+ StrideOrder.clear();
+ Processed.clear();
+}
+
+void IVStrideUse::deleted() {
+ // Remove this user from the list.
+ Parent->Users.erase(this);
+ // this now dangles!
+}
diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 538d1371a1..f68cf0e40d 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -749,16 +749,6 @@ be done safely if "b" isn't modified between the strlen and memcpy of course.
//===---------------------------------------------------------------------===//
-We should be able to evaluate this loop:
-
-int test(int x_offs) {
- while (x_offs > 4)
- x_offs -= 4;
- return x_offs;
-}
-
-//===---------------------------------------------------------------------===//
-
Reassociate should turn things like:
int factorial(int X) {
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 3d9017d17e..80d34f6f16 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -43,6 +43,8 @@
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
@@ -51,11 +53,12 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
using namespace llvm;
STATISTIC(NumRemoved , "Number of aux indvars removed");
@@ -65,6 +68,7 @@ STATISTIC(NumLFTR , "Number of loop exit tests replaced");
namespace {
class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
+ IVUsers *IU;
LoopInfo *LI;
ScalarEvolution *SE;
bool Changed;
@@ -76,12 +80,15 @@ namespace {
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<DominatorTree>();
AU.addRequired<ScalarEvolution>();
AU.addRequiredID(LCSSAID);
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
+ AU.addRequired<IVUsers>();
AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(LoopSimplifyID);
+ AU.addPreserved<IVUsers>();
AU.addPreservedID(LCSSAID);
AU.setPreservesCFG();
}
@@ -90,17 +97,21 @@ namespace {
void RewriteNonIntegerIVs(Loop *L);
- void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
+ ICmpInst *LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
BranchInst *BI,
SCEVExpander &Rewriter);
void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount);
- void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts);
+ void RewriteIVExpressions(Loop *L, const Type *LargestType,
+ SCEVExpander &Rewriter);
- void HandleFloatingPointIV(Loop *L, PHINode *PH,
- SmallPtrSet<Instruction*, 16> &DeadInsts);
+ void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter);
+
+ void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter);
+
+ void HandleFloatingPointIV(Loop *L, PHINode *PH);
};
}
@@ -112,31 +123,12 @@ Pass *llvm::createIndVarSimplifyPass() {
return new IndVarSimplify();
}
-/// DeleteTriviallyDeadInstructions - If any of the instructions is the
-/// specified set are trivially dead, delete them and see if this makes any of
-/// their operands subsequently dead.
-void IndVarSimplify::
-DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) {
- while (!Insts.empty()) {
- Instruction *I = *Insts.begin();
- Insts.erase(I);
- if (isInstructionTriviallyDead(I)) {
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
- Insts.insert(U);
- DOUT << "INDVARS: Deleting: " << *I;
- I->eraseFromParent();
- Changed = true;
- }
- }
-}
-
/// LinearFunctionTestReplace - This method rewrites the exit condition of the
/// loop to be a canonical != comparison against the incremented loop induction
/// variable. This pass is able to rewrite the exit tests of any loop where the
/// SCEV analysis can determine a loop-invariant trip count of the loop, which
/// is actually a much broader range than just linear tests.
-void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
+ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
SCEVHandle BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
@@ -196,10 +188,15 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
<< (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
<< " RHS:\t" << *RHS << "\n";
- Value *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
- BI->setCondition(Cond);
+ ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
+
+ Instruction *OrigCond = cast<Instruction>(BI->getCondition());
+ OrigCond->replaceAllUsesWith(Cond);
+ RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
+
++NumLFTR;
Changed = true;
+ return Cond;
}
/// RewriteLoopExitValues - Check to see if this loop has a computable
@@ -207,8 +204,16 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
/// final value of any expressions that are recurrent in the loop, and
/// substitute the exit values from the loop into any instructions outside of
/// the loop that use the final values of the current expressions.
+///
+/// This is mostly redundant with the regular IndVarSimplify activities that
+/// happen later, except that it's more powerful in some cases, because it's
+/// able to brute-force evaluate arbitrary instructions as long as they have
+/// constant operands at the beginning of the loop.
void IndVarSimplify::RewriteLoopExitValues(Loop *L,
const SCEV *BackedgeTakenCount) {
+ // Verify the input to the pass in already in LCSSA form.
+ assert(L->isLCSSAForm());
+
BasicBlock *Preheader = L->getLoopPreheader();
// Scan all of the instructions in the loop, looking at those that have
@@ -226,9 +231,6 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
BlockToInsertInto = Preheader;
BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
- bool HasConstantItCount = isa<SCEVConstant>(BackedgeTakenCount);
-
- SmallPtrSet<Instruction*, 16> InstructionsToDelete;
std::map<Instruction*, Value*> ExitValues;
// Find all values that are computed inside the loop, but used outside of it.
@@ -268,18 +270,11 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
if (!L->contains(Inst->getParent()))
continue;
- // We require that this value either have a computable evolution or that
- // the loop have a constant iteration count. In the case where the loop
- // has a constant iteration count, we can sometimes force evaluation of
- // the exit value through brute force.
- SCEVHandle SH = SE->getSCEV(Inst);
- if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount)
- continue; // Cannot get exit evolution for the loop value.
-
// Okay, this instruction has a user outside of the current loop
// and varies predictably *inside* the loop. Evaluate the value it
// contains when the loop exits, if possible.
- SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+ SCEVHandle SH = SE->getSCEV(Inst);
+ SCEVHandle ExitValue = SE->getSCEVAtScope(SH, L->getParentLoop());
if (isa<SCEVCouldNotCompute>(ExitValue) ||
!ExitValue->isLoopInvariant(L))
continue;
@@ -298,9 +293,8 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
PN->setIncomingValue(i, ExitVal);
- // If this instruction is dead now, schedule it to be removed.
- if (Inst->use_empty())
- InstructionsToDelete.insert(Inst);
+ // If this instruction is dead now, delete it.
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
// See if this is a single-entry LCSSA PHI node. If so, we can (and
// have to) remove
@@ -308,14 +302,12 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
// in the loop, so we don't need an LCSSA phi node anymore.
if (NumPreds == 1) {
PN->replaceAllUsesWith(ExitVal);
- PN->eraseFromParent();
+ RecursivelyDeleteTriviallyDeadInstructions(PN);
break;
}
}
}
}
-
- DeleteTriviallyDeadInstructions(InstructionsToDelete);
}
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
@@ -325,266 +317,24 @@ void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
//
BasicBlock *Header = L->getHeader();
- SmallPtrSet<Instruction*, 16> DeadInsts;
- for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- HandleFloatingPointIV(L, PN, DeadInsts);
- }
+ SmallVector<WeakVH, 8> PHIs;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ PHIs.push_back(PN);
+
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+ if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
+ HandleFloatingPointIV(L, PN);
// If the loop previously had floating-point IV, ScalarEvolution
// may not have been able to compute a trip count. Now that we've done some
// re-writing, the trip count may be computable.
if (Changed)
SE->forgetLoopBackedgeTakenCount(L);
-
- if (!DeadInsts.empty())
- DeleteTriviallyDeadInstructions(DeadInsts);
-}
-
-/// getEffectiveIndvarType - Determine the widest type that the
-/// induction-variable PHINode Phi is cast to.
-///
-static const Type *getEffectiveIndvarType(const PHINode *Phi,
- const ScalarEvolution *SE) {
- const Type *Ty = Phi->getType();
-
- for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end();
- UI != UE; ++UI) {
- const Type *CandidateType = NULL;
- if (const ZExtInst *ZI = dyn_cast<ZExtInst>(UI))
- CandidateType = ZI->getDestTy();
- else if (const SExtInst *SI = dyn_cast<SExtInst>(UI))
- CandidateType = SI->getDestTy();
- else if (const IntToPtrInst *IP = dyn_cast<IntToPtrInst>(UI))
- CandidateType = IP->getDestTy();
- else if (const PtrToIntInst *PI = dyn_cast<PtrToIntInst>(UI))
- CandidateType = PI->getDestTy();
- if (CandidateType &&
- SE->isSCEVable(CandidateType) &&
- SE->getTypeSizeInBits(CandidateType) > SE->getTypeSizeInBits(Ty))
- Ty = CandidateType;
- }
-
- return Ty;
-}
-
-/// TestOrigIVForWrap - Analyze the original induction variable that
-/// controls the loop's iteration to determine whether it would ever
-/// undergo signed or unsigned overflow.
-///
-/// In addition to setting the NoSignedWrap and NoUnsignedWrap
-/// variables to true when appropriate (they are not set to false here),
-/// return the PHI for this induction variable. Also record the initial
-/// and final values and the increment; these are not meaningful unless
-/// either NoSignedWrap or NoUnsignedWrap is true, and are always meaningful
-/// in that case, although the final value may be 0 indicating a nonconstant.
-///
-/// TODO: This duplicates a fair amount of ScalarEvolution logic.
-/// Perhaps this can be merged with
-/// ScalarEvolution::getBackedgeTakenCount
-/// and/or ScalarEvolution::get{Sign,Zero}ExtendExpr.
-///
-static const PHINode *TestOrigIVForWrap(const Loop *L,
- const BranchInst *BI,
- const Instruction *OrigCond,
- const ScalarEvolution &SE,
- bool &NoSignedWrap,
- bool &NoUnsignedWrap,
- const ConstantInt* &InitialVal,
- const ConstantInt* &IncrVal,
- const ConstantInt* &LimitVal) {
- // Verify that the loop is sane and find the exit condition.
- const ICmpInst *Cmp = dyn_cast<ICmpInst>(OrigCond);
- if (!Cmp) return 0;
-
- const Value *CmpLHS = Cmp->getOperand(0);
- const Value *CmpRHS = Cmp->getOperand(1);
- const BasicBlock *TrueBB = BI->getSuccessor(0);
- const BasicBlock *FalseBB = BI->getSuccessor(1);
- ICmpInst::Predicate Pred = Cmp->getPredicate();
-
- // Canonicalize a constant to the RHS.
- if (isa<ConstantInt>(CmpLHS)) {
- Pred = ICmpInst::getSwappedPredicate(Pred);
- std::swap(CmpLHS, CmpRHS);
- }
- // Canonicalize SLE to SLT.
- if (Pred == ICmpInst::ICMP_SLE)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxSignedValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_SLT;
- }
- // Canonicalize SGT to SGE.
- if (Pred == ICmpInst::ICMP_SGT)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxSignedValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_SGE;
- }
- // Canonicalize SGE to SLT.
- if (Pred == ICmpInst::ICMP_SGE) {
- std::swap(TrueBB, FalseBB);
- Pred = ICmpInst::ICMP_SLT;
- }
- // Canonicalize ULE to ULT.
- if (Pred == ICmpInst::ICMP_ULE)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_ULT;
- }
- // Canonicalize UGT to UGE.
- if (Pred == ICmpInst::ICMP_UGT)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_UGE;
- }
- // Canonicalize UGE to ULT.
- if (Pred == ICmpInst::ICMP_UGE) {
- std::swap(TrueBB, FalseBB);
- Pred = ICmpInst::ICMP_ULT;
- }
- // For now, analyze only LT loops for signed overflow.
- if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_ULT)
- return 0;
-
- bool isSigned = Pred == ICmpInst::ICMP_SLT;
-
- // Get the increment instruction. Look past casts if we will
- // be able to prove that the original induction variable doesn't
- // undergo signed or unsigned overflow, respectively.
- const Value *IncrInst = CmpLHS;
- if (isSigned) {
- if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) {
- if (!isa<ConstantInt>(CmpRHS) ||
- !cast<ConstantInt>(CmpRHS)->getValue()
- .isSignedIntN(SE.getTypeSizeInBits(IncrInst->getType())))
- return 0;
- IncrInst = SI->getOperand(0);
- }
- } else {
- if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) {
- if (!isa<ConstantInt>(CmpRHS) ||
- !cast<ConstantInt>(CmpRHS)->getValue()
- .isIntN(SE.getTypeSizeInBits(IncrInst->getType())))
- return 0;
- IncrInst = ZI->getOperand(0);
- }
- }
-
- // For now, only analyze induction variables that have simple increments.
- const BinaryOperator *IncrOp = dyn_cast<BinaryOperator>(IncrInst);
- if (!IncrOp || IncrOp->getOpcode() != Instruction::Add)
- return 0;
- IncrVal = dyn_cast<ConstantInt>(IncrOp->getOperand(1));
- if (!IncrVal)
- return 0;
-
- // Make sure the PHI looks like a normal IV.
- const PHINode *PN = dyn_cast<PHINode>(IncrOp->getOperand(0));
- if (!PN || PN->getNumIncomingValues() != 2)
- return 0;
- unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
- unsigned BackEdge = !IncomingEdge;
- if (!L->contains(PN->getIncomingBlock(BackEdge)) ||
- PN->getIncomingValue(BackEdge) != IncrOp)
- return 0;
- if (!L->contains(TrueBB))
- return 0;
-
- // For now, only analyze loops with a constant start value, so that
- // we can easily determine if the start value is not a maximum value
- // which would wrap on the first iteration.
- InitialVal = dyn_cast<ConstantInt>(PN->getIncomingValue(IncomingEdge));
- if (!InitialVal)
- return 0;
-
- // The upper limit need not be a constant; we'll check later.
- LimitVal = dyn_cast<ConstantInt>(CmpRHS);
-
- // We detect the impossibility of wrapping in two cases, both of
- // which require starting with a non-max value:
- // - The IV counts up by one, and the loop iterates only while it remains
- // less than a limiting value (any) in the same type.
- // - The IV counts up by a positive increment other than 1, and the
- // constant limiting value + the increment is less than the max value
- // (computed as max-increment to avoid overflow)
- if (isSigned && !InitialVal->getValue().isMaxSignedValue()) {
- if (IncrVal->equalsInt(1))
- NoSignedWrap = true; // LimitVal need not be constant
- else if (LimitVal) {
- uint64_t numBits = LimitVal->getValue().getBitWidth();
- if (IncrVal->getValue().sgt(APInt::getNullValue(numBits)) &&
- (APInt::getSignedMaxValue(numBits) - IncrVal->getValue())
- .sgt(LimitVal->getValue()))
- NoSignedWrap = true;
- }
- } else if (!isSigned && !InitialVal->getValue().isMaxValue()) {
- if (IncrVal->equalsInt(1))
- NoUnsignedWrap = true; // LimitVal need not be constant
- else if (LimitVal) {
- uint64_t numBits = LimitVal->getValue().getBitWidth();
- if (IncrVal->getValue().ugt(APInt::getNullValue(numBits)) &&
- (APInt::getMaxValue(numBits) - IncrVal->getValue())
- .ugt(LimitVal->getValue()))
- NoUnsignedWrap = true;
- }
- }
- return PN;
-}
-
-static Value *getSignExtendedTruncVar(const SCEVAddRecExpr *AR,
- ScalarEvolution *SE,
- const Type *LargestType, Loop *L,
- const Type *myType,
- SCEVExpander &Rewriter) {
- SCEVHandle ExtendedStart =
- SE->getSignExtendExpr(AR->getStart(), LargestType);
- SCEVHandle ExtendedStep =
- SE->getSignExtendExpr(AR->getStepRecurrence(*SE), LargestType);
- SCEVHandle ExtendedAddRec =
- SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
- if (LargestType != myType)
- ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, myType);
-}
-
-static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR,
- ScalarEvolution *SE,
- const Type *LargestType, Loop *L,
- const Type *myType,
- SCEVExpander &Rewriter) {
- SCEVHandle ExtendedStart =
- SE->getZeroExtendExpr(AR->getStart(), LargestType);
- SCEVHandle ExtendedStep =
- SE->getZeroExtendExpr(AR->getStepRecurrence(*SE), LargestType);
- SCEVHandle ExtendedAddRec =
- SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
- if (LargestType != myType)
- ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, myType);
-}
-
-/// allUsesAreSameTyped - See whether all Uses of I are instructions
-/// with the same Opcode and the same type.
-static bool allUsesAreSameTyped(unsigned int Opcode, Instruction *I) {
- const Type* firstType = NULL;
- for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
- UI != UE; ++UI) {
- Instruction *II = dyn_cast<Instruction>(*UI);
- if (!II || II->getOpcode() != Opcode)
- return false;
- if (!firstType)
- firstType = II->getType();
- else if (firstType != II->getType())
- return false;
- }
- return true;
}
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
+ IU = &getA