#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
using namespace llvm;
void handleFloatingPointIV(Loop *L, PHINode *PH);
void rewriteNonIntegerIVs(Loop *L);
- void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM);
+ void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
- void rewriteFirstIterationLoopExitValues(Loop *L);
Value *linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
PHINode *IndVar, SCEVExpander &Rewriter);
/// loop. For PHI nodes, there may be multiple uses, so compute the nearest
/// common dominator for the incoming blocks.
static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
- DominatorTree *DT) {
+ DominatorTree *DT, LoopInfo *LI) {
PHINode *PHI = dyn_cast<PHINode>(User);
if (!PHI)
return User;
InsertPt = InsertBB->getTerminator();
}
assert(InsertPt && "Missing phi operand");
- assert((!isa<Instruction>(Def) ||
- DT->dominates(cast<Instruction>(Def), InsertPt)) &&
- "def does not dominate all uses");
- return InsertPt;
+
+ auto *DefI = dyn_cast<Instruction>(Def);
+ if (!DefI)
+ return InsertPt;
+
+ assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
+
+ auto *L = LI->getLoopFor(DefI->getParent());
+ assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
+
+ for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
+ if (LI->getLoopFor(DTN->getBlock()) == L)
+ return DTN->getBlock()->getTerminator();
+
+ llvm_unreachable("DefI dominates InsertPt!");
}
//===----------------------------------------------------------------------===//
/// 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, SCEVExpander &Rewriter) {
- // Verify the input to the pass in already in LCSSA form.
- assert(L->isLCSSAForm(*DT));
+ // Check a pre-condition.
+ assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
Rewriter.clearInsertPoint();
}
-//===---------------------------------------------------------------------===//
-// rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
-// they will exit at the first iteration.
-//===---------------------------------------------------------------------===//
-
-/// Check to see if this loop has loop invariant conditions which lead to loop
-/// exits. If so, we know that if the exit path is taken, it is at the first
-/// loop iteration. This lets us predict exit values of PHI nodes that live in
-/// loop header.
-void IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
- // Verify the input to the pass is already in LCSSA form.
- assert(L->isLCSSAForm(*DT));
-
- SmallVector<BasicBlock *, 8> ExitBlocks;
- L->getUniqueExitBlocks(ExitBlocks);
-
- for (auto *ExitBB : ExitBlocks) {
- BasicBlock::iterator begin = ExitBB->begin();
- // If there are no more PHI nodes in this exit block, then no more
- // values defined inside the loop are used on this path.
- while (auto *PN = dyn_cast<PHINode>(begin++)) {
- for (unsigned IncomingValIdx = 0, e = PN->getNumIncomingValues();
- IncomingValIdx != e; ++IncomingValIdx) {
- auto *IncomingBB = PN->getIncomingBlock(IncomingValIdx);
- if (!L->contains(IncomingBB))
- continue;
-
- // Get condition that leads to the exit path.
- auto *TermInst = IncomingBB->getTerminator();
-
- Value *Cond = nullptr;
- if (auto *BI = dyn_cast<BranchInst>(TermInst)) {
- // Must be a conditional branch, otherwise the block
- // should not be in the loop.
- Cond = BI->getCondition();
- } else if (auto *SI = dyn_cast<SwitchInst>(TermInst))
- Cond = SI->getCondition();
- else
- continue;
-
- // All non-instructions are loop-invariant.
- if (isa<Instruction>(Cond) && !L->isLoopInvariant(Cond))
- continue;
-
- auto *ExitVal =
- dyn_cast<PHINode>(PN->getIncomingValue(IncomingValIdx));
-
- // Only deal with PHIs.
- if (!ExitVal)
- continue;
-
- // If ExitVal is a PHI on the loop header, then we know its
- // value along this exit because the exit can only be taken
- // on the first iteration.
- auto *LoopPreheader = L->getLoopPreheader();
- assert(LoopPreheader && "Invalid loop");
- if (ExitVal->getBasicBlockIndex(LoopPreheader) != -1) {
- assert(ExitVal->getParent() == L->getHeader() &&
- "ExitVal must be in loop header");
- PN->setIncomingValue(IncomingValIdx,
- ExitVal->getIncomingValueForBlock(LoopPreheader));
- }
- }
- }
- }
-}
-
/// Check whether it is possible to delete the loop after rewriting exit
/// value. If it is possible, ignore ReplaceExitValue and do rewriting
/// aggressively.
++BI;
}
- for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
- LI != LE; ++LI) {
- for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); BI != BE;
- ++BI) {
- if (BI->mayHaveSideEffects())
- return false;
- }
- }
+ for (auto *BB : L->blocks())
+ if (any_of(*BB, [](Instruction &I) { return I.mayHaveSideEffects(); }))
+ return false;
return true;
}
NarrowBO->getName());
IRBuilder<> Builder(NarrowUse);
Builder.Insert(WideBO);
- if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(NarrowBO)) {
- if (OBO->hasNoUnsignedWrap())
- WideBO->setHasNoUnsignedWrap();
- if (OBO->hasNoSignedWrap())
- WideBO->setHasNoSignedWrap();
- }
+ WideBO->copyIRFlags(NarrowBO);
return WideBO;
}
IRBuilder<> Builder(NarrowUse);
Builder.Insert(WideBO);
- if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(NarrowBO)) {
- if (OBO->hasNoUnsignedWrap())
- WideBO->setHasNoUnsignedWrap();
- if (OBO->hasNoSignedWrap())
- WideBO->setHasNoSignedWrap();
- }
+ WideBO->copyIRFlags(NarrowBO);
return WideBO;
}
/// This IV user cannot be widen. Replace this use of the original narrow IV
/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
-static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT) {
+static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef
<< " for user " << *DU.NarrowUse << "\n");
- IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT));
+ IRBuilder<> Builder(
+ getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
}
assert (CastWidth <= IVWidth && "Unexpected width while widening compare.");
// Widen the compare instruction.
- IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT));
+ IRBuilder<> Builder(
+ getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
// Widen the other operand of the compare, if necessary.
// After SimplifyCFG most loop exit targets have a single predecessor.
// Otherwise fall back to a truncate within the loop.
if (UsePhi->getNumOperands() != 1)
- truncateIVUse(DU, DT);
+ truncateIVUse(DU, DT, LI);
else {
PHINode *WidePhi =
PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
// This user does not evaluate to a recurence after widening, so don't
// follow it. Instead insert a Trunc to kill off the original use,
// eventually isolating the original narrow IV so it can be removed.
- truncateIVUse(DU, DT);
+ truncateIVUse(DU, DT, LI);
return nullptr;
}
// Assume block terminators cannot evaluate to a recurrence. We can't to
///
void IndVarSimplify::simplifyAndExtend(Loop *L,
SCEVExpander &Rewriter,
- LPPassManager &LPM) {
+ LoopInfo *LI) {
SmallVector<WideIVInfo, 8> WideIVs;
SmallVector<PHINode*, 8> LoopPhis;
// Information about sign/zero extensions of CurrIV.
IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
- Changed |= simplifyUsersOfIV(CurrIV, SE, DT, &LPM, DeadInsts, &Visitor);
+ Changed |= simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, &Visitor);
if (Visitor.WI.WidestNativeType) {
WideIVs.push_back(Visitor.WI);
return false;
// Optimistically handle other instructions.
- for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) {
- if (!Visited.insert(*OI).second)
+ for (Value *Op : I->operands()) {
+ if (!Visited.insert(Op).second)
continue;
- if (!hasConcreteDefImpl(*OI, Visited, Depth+1))
+ if (!hasConcreteDefImpl(Op, Visited, Depth+1))
return false;
}
return true;
const SCEV *ARStep = AR->getStepRecurrence(*SE);
// For constant IVCount, avoid truncation.
if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) {
- const APInt &Start = cast<SCEVConstant>(ARStart)->getValue()->getValue();
- APInt Count = cast<SCEVConstant>(IVCount)->getValue()->getValue();
+ const APInt &Start = cast<SCEVConstant>(ARStart)->getAPInt();
+ APInt Count = cast<SCEVConstant>(IVCount)->getAPInt();
// Note that the post-inc value of BackedgeTakenCount may have overflowed
// above such that IVCount is now zero.
if (IVCount != BackedgeTakenCount && Count == 0) {
// other expressions involving loop IVs have been evaluated. This helps SCEV
// set no-wrap flags before normalizing sign/zero extension.
Rewriter.disableCanonicalMode();
- simplifyAndExtend(L, Rewriter, LPM);
+ simplifyAndExtend(L, Rewriter, LI);
// Check to see if this loop has a computable loop-invariant execution count.
// If so, this means that we can compute the final value of any expressions
// loop may be sunk below the loop to reduce register pressure.
sinkUnusedInvariants(L);
- // rewriteFirstIterationLoopExitValues does not rely on the computation of
- // trip count and therefore can further simplify exit values in addition to
- // rewriteLoopExitValues.
- rewriteFirstIterationLoopExitValues(L);
-
// Clean up dead instructions.
Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
+
// Check a post-condition.
- assert(L->isLCSSAForm(*DT) &&
- "Indvars did not leave the loop in lcssa form!");
+ assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
// Verify that LFTR, and any other change have not interfered with SCEV's
// ability to compute trip count.
projects / oota-llvm.git / blobdiff