This is an archive of the discontinued LLVM Phabricator instance.

Differential D72602

[IndVarSimplify][LoopUtils] rewriteLoopExitValues. NFC.
ClosedPublic

Authored by SjoerdMeijer on Jan 13 2020, 5:19 AM.

Details

Reviewers
reames
Meinersbur
nikic
samparker
dmgreen
Commits
rG93175a5caa08: [IndVarSimplify][LoopUtils] rewriteLoopExitValues. NFCI
Summary

This moves rewriteLoopExitValues from IndVarSimplify to LoopUtils thus making it a generic loop utility function, which should be a non-functional change. This allows to rewrite loop exit values by just calling this function without running the whole IndVarSimplify pass.

For context, we would like to (re)use rewriteLoopExitValues to rematerialize the iteration count in loop exit blocks, which allows us to optimise away better induction variable expressions in hardware-loops.

Diff Detail

Event Timeline

SjoerdMeijer created this revision.Jan 13 2020, 5:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 13 2020, 5:19 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
SjoerdMeijer mentioned this in D72714: [ARM][MVE] Tail-Predication: rematerialise iteration count in exit blocks.Jan 14 2020, 9:01 AM
SjoerdMeijer added a child revision: D72714: [ARM][MVE] Tail-Predication: rematerialise iteration count in exit blocks.Jan 14 2020, 9:23 AM
dmgreen added a comment.Jan 17 2020, 1:24 AM

These seems like a sensible thing to go along with D72714.

llvm/include/llvm/Transforms/Utils/LoopUtils.h
370

ReplaceExitValue needn't be a reference.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
2690

Does this need the getValue()?

llvm/lib/Transforms/Utils/LoopUtils.cpp
1138

This was added but not removed anywhere?

dmgreen added inline comments.Jan 17 2020, 1:27 AM
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
718

This statistic has gone missing? (Maybe have rewriteLoopExitValues return the number of replaced values, not a bool?)

SjoerdMeijer updated this revision to Diff 238755.Jan 17 2020, 5:22 AM

Thanks for looking! Comments addressed, the main ones being:

  • restored the statistics, and
  • the code that I forgot to delete.
dmgreen accepted this revision.Jan 17 2020, 6:08 AM

This looks useful as a separate function, the interface looks pretty clean and I think it lives nicely in LoopUtils.

LGTM.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
2692

NumReplaced += Rewrites; maybe?

2693

Changed = true at this point.

This revision is now accepted and ready to land.Jan 17 2020, 6:08 AM
Closed by commit rG93175a5caa08: [IndVarSimplify][LoopUtils] rewriteLoopExitValues. NFCI (authored by SjoerdMeijer). · Explain WhyJan 20 2020, 1:12 AM
This revision was automatically updated to reflect the committed changes.
SjoerdMeijer mentioned this in rG8cba99e2aa93: [ARM][MVE] Tail-Predication: rematerialise iteration count in exit blocks.Jan 20 2020, 2:35 AM

Revision Contents

PathSize
llvm/
include/
llvm/
Transforms/
Utils/
13 lines
lib/
Transforms/
Scalar/
355 lines
Utils/
306 lines

Diff 239034

llvm/include/llvm/Transforms/Utils/LoopUtils.h

Show First 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
class LoopInfo; class LoopInfo;
class MemoryAccess; class MemoryAccess;
class MemorySSAUpdater; class MemorySSAUpdater;
class OptimizationRemarkEmitter; class OptimizationRemarkEmitter;
class PredicatedScalarEvolution; class PredicatedScalarEvolution;
class PredIteratorCache; class PredIteratorCache;
class ScalarEvolution; class ScalarEvolution;
class SCEV; class SCEV;
class SCEVExpander;
class TargetLibraryInfo; class TargetLibraryInfo;
class TargetTransformInfo; class TargetTransformInfo;
BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
MemorySSAUpdater *MSSAU, bool PreserveLCSSA); MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
/// Ensure that all exit blocks of the loop are dedicated exits. /// Ensure that all exit blocks of the loop are dedicated exits.
/// ///
▲ Show 20 Lines • Show All 294 Lines • ▼ Show 20 Lines
/// Returns true if \p S is defined and never is equal to signed/unsigned max. /// Returns true if \p S is defined and never is equal to signed/unsigned max.
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
bool Signed); bool Signed);
/// Returns true if \p S is defined and never is equal to signed/unsigned min. /// Returns true if \p S is defined and never is equal to signed/unsigned min.
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
bool Signed); bool Signed);
enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, NoHardUse, AlwaysRepl };
/// If the final value of any expressions that are recurrent in the loop can
/// be computed, substitute the exit values from the loop into any instructions
/// outside of the loop that use the final values of the current expressions.
/// Return the number of loop exit values that have been replaced, and the
/// corresponding phi node will be added to DeadInsts.
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
ScalarEvolution *SE, SCEVExpander &Rewriter,
DominatorTree *DT, ReplaceExitVal ReplaceExitValue,
dmgreenUnsubmitted
Not Done
ReplyInline Actions

ReplaceExitValue needn't be a reference.

dmgreen: ReplaceExitValue needn't be a reference.
SmallVector<WeakTrackingVH, 16> &DeadInsts);
} // end namespace llvm } // end namespace llvm
#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

Show First 20 Lines • Show All 97 Lines • ▼ Show 20 Lines
// Trip count verification can be enabled by default under NDEBUG if we // Trip count verification can be enabled by default under NDEBUG if we
// implement a strong expression equivalence checker in SCEV. Until then, we // implement a strong expression equivalence checker in SCEV. Until then, we
// use the verify-indvars flag, which may assert in some cases. // use the verify-indvars flag, which may assert in some cases.
static cl::opt<bool> VerifyIndvars( static cl::opt<bool> VerifyIndvars(
"verify-indvars", cl::Hidden, "verify-indvars", cl::Hidden,
cl::desc("Verify the ScalarEvolution result after running indvars")); cl::desc("Verify the ScalarEvolution result after running indvars"));
enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, NoHardUse, AlwaysRepl };
static cl::opt<ReplaceExitVal> ReplaceExitValue( static cl::opt<ReplaceExitVal> ReplaceExitValue(
"replexitval", cl::Hidden, cl::init(OnlyCheapRepl), "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
clEnumValN(OnlyCheapRepl, "cheap", clEnumValN(OnlyCheapRepl, "cheap",
"only replace exit value when the cost is cheap"), "only replace exit value when the cost is cheap"),
clEnumValN(NoHardUse, "noharduse", clEnumValN(NoHardUse, "noharduse",
"only replace exit values when loop def likely dead"), "only replace exit values when loop def likely dead"),
Show All 22 Linesclass IndVarSimplify {
ScalarEvolution *SE; ScalarEvolution *SE;
DominatorTree *DT; DominatorTree *DT;
const DataLayout &DL; const DataLayout &DL;
TargetLibraryInfo *TLI; TargetLibraryInfo *TLI;
const TargetTransformInfo *TTI; const TargetTransformInfo *TTI;
SmallVector<WeakTrackingVH, 16> DeadInsts; SmallVector<WeakTrackingVH, 16> DeadInsts;
bool isValidRewrite(Value *FromVal, Value *ToVal);
bool handleFloatingPointIV(Loop *L, PHINode *PH); bool handleFloatingPointIV(Loop *L, PHINode *PH);
bool rewriteNonIntegerIVs(Loop *L); bool rewriteNonIntegerIVs(Loop *L);
bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI); bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
/// Try to eliminate loop exits based on analyzeable exit counts /// Try to eliminate loop exits based on analyzeable exit counts
bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter); bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter);
/// Try to form loop invariant tests for loop exits by changing how many /// Try to form loop invariant tests for loop exits by changing how many
/// iterations of the loop run when that is unobservable. /// iterations of the loop run when that is unobservable.
bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter); bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
bool rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
bool rewriteFirstIterationLoopExitValues(Loop *L); bool rewriteFirstIterationLoopExitValues(Loop *L);
bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) const;
bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB, bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
const SCEV *ExitCount, const SCEV *ExitCount,
PHINode *IndVar, SCEVExpander &Rewriter); PHINode *IndVar, SCEVExpander &Rewriter);
bool sinkUnusedInvariants(Loop *L); bool sinkUnusedInvariants(Loop *L);
public: public:
IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
const DataLayout &DL, TargetLibraryInfo *TLI, const DataLayout &DL, TargetLibraryInfo *TLI,
TargetTransformInfo *TTI) TargetTransformInfo *TTI)
: LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {} : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}
bool run(Loop *L); bool run(Loop *L);
}; };
} // end anonymous namespace } // end anonymous namespace
/// Return true if the SCEV expansion generated by the rewriter can replace the
/// original value. SCEV guarantees that it produces the same value, but the way
/// it is produced may be illegal IR. Ideally, this function will only be
/// called for verification.
bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
// If an SCEV expression subsumed multiple pointers, its expansion could
// reassociate the GEP changing the base pointer. This is illegal because the
// final address produced by a GEP chain must be inbounds relative to its
// underlying object. Otherwise basic alias analysis, among other things,
// could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
// producing an expression involving multiple pointers. Until then, we must
// bail out here.
//
// Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
// because it understands lcssa phis while SCEV does not.
Value *FromPtr = FromVal;
Value *ToPtr = ToVal;
if (auto *GEP = dyn_cast<GEPOperator>(FromVal)) {
FromPtr = GEP->getPointerOperand();
}
if (auto *GEP = dyn_cast<GEPOperator>(ToVal)) {
ToPtr = GEP->getPointerOperand();
}
if (FromPtr != FromVal || ToPtr != ToVal) {
// Quickly check the common case
if (FromPtr == ToPtr)
return true;
// SCEV may have rewritten an expression that produces the GEP's pointer
// operand. That's ok as long as the pointer operand has the same base
// pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
// base of a recurrence. This handles the case in which SCEV expansion
// converts a pointer type recurrence into a nonrecurrent pointer base
// indexed by an integer recurrence.
// If the GEP base pointer is a vector of pointers, abort.
if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
return false;
const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
if (FromBase == ToBase)
return true;
LLVM_DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " << *FromBase
<< " != " << *ToBase << "\n");
return false;
}
return true;
}
/// Determine the insertion point for this user. By default, insert immediately /// Determine the insertion point for this user. By default, insert immediately
/// before the user. SCEVExpander or LICM will hoist loop invariants out of the /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
/// loop. For PHI nodes, there may be multiple uses, so compute the nearest /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
/// common dominator for the incoming blocks. A nullptr can be returned if no /// common dominator for the incoming blocks. A nullptr can be returned if no
/// viable location is found: it may happen if User is a PHI and Def only comes /// viable location is found: it may happen if User is a PHI and Def only comes
/// to this PHI from unreachable blocks. /// to this PHI from unreachable blocks.
static Instruction *getInsertPointForUses(Instruction *User, Value *Def, static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
DominatorTree *DT, LoopInfo *LI) { DominatorTree *DT, LoopInfo *LI) {
▲ Show 20 Lines • Show All 277 Lines • ▼ Show 20 Linesbool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
// If the loop previously had floating-point IV, ScalarEvolution // 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 // may not have been able to compute a trip count. Now that we've done some
// re-writing, the trip count may be computable. // re-writing, the trip count may be computable.
if (Changed) if (Changed)
SE->forgetLoop(L); SE->forgetLoop(L);
return Changed; return Changed;
} }
namespace {
// Collect information about PHI nodes which can be transformed in
// rewriteLoopExitValues.
struct RewritePhi {
PHINode *PN;
// Ith incoming value.
unsigned Ith;
// Exit value after expansion.
Value *Val;
// High Cost when expansion.
bool HighCost;
RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
: PN(P), Ith(I), Val(V), HighCost(H) {}
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// rewriteLoopExitValues - Optimize IV users outside the loop.
// As a side effect, reduces the amount of IV processing within the loop.
//===----------------------------------------------------------------------===//
bool IndVarSimplify::hasHardUserWithinLoop(const Loop *L, const Instruction *I) const {
SmallPtrSet<const Instruction *, 8> Visited;
SmallVector<const Instruction *, 8> WorkList;
Visited.insert(I);
WorkList.push_back(I);
while (!WorkList.empty()) {
const Instruction *Curr = WorkList.pop_back_val();
// This use is outside the loop, nothing to do.
if (!L->contains(Curr))
continue;
// Do we assume it is a "hard" use which will not be eliminated easily?
if (Curr->mayHaveSideEffects())
return true;
// Otherwise, add all its users to worklist.
for (auto U : Curr->users()) {
auto *UI = cast<Instruction>(U);
if (Visited.insert(UI).second)
WorkList.push_back(UI);
}
}
return false;
}
/// 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
/// 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.
bool IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
// Check a pre-condition.
assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
"Indvars did not preserve LCSSA!");
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
SmallVector<RewritePhi, 8> RewritePhiSet;
// Find all values that are computed inside the loop, but used outside of it.
// Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
// the exit blocks of the loop to find them.
for (BasicBlock *ExitBB : ExitBlocks) {
// If there are no PHI nodes in this exit block, then no values defined
// inside the loop are used on this path, skip it.
PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
if (!PN) continue;
unsigned NumPreds = PN->getNumIncomingValues();
// Iterate over all of the PHI nodes.
BasicBlock::iterator BBI = ExitBB->begin();
while ((PN = dyn_cast<PHINode>(BBI++))) {
if (PN->use_empty())
continue; // dead use, don't replace it
if (!SE->isSCEVable(PN->getType()))
continue;
// It's necessary to tell ScalarEvolution about this explicitly so that
// it can walk the def-use list and forget all SCEVs, as it may not be
// watching the PHI itself. Once the new exit value is in place, there
// may not be a def-use connection between the loop and every instruction
// which got a SCEVAddRecExpr for that loop.
SE->forgetValue(PN);
// Iterate over all of the values in all the PHI nodes.
for (unsigned i = 0; i != NumPreds; ++i) {
// If the value being merged in is not integer or is not defined
// in the loop, skip it.
Value *InVal = PN->getIncomingValue(i);
if (!isa<Instruction>(InVal))
continue;
// If this pred is for a subloop, not L itself, skip it.
if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
continue; // The Block is in a subloop, skip it.
// Check that InVal is defined in the loop.
Instruction *Inst = cast<Instruction>(InVal);
if (!L->contains(Inst))
continue;
// 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. We prefer to start with
// expressions which are true for all exits (so as to maximize
// expression reuse by the SCEVExpander), but resort to per-exit
// evaluation if that fails.
const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
if (isa<SCEVCouldNotCompute>(ExitValue) ||
!SE->isLoopInvariant(ExitValue, L) ||
!isSafeToExpand(ExitValue, *SE)) {
// TODO: This should probably be sunk into SCEV in some way; maybe a
// getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
// most SCEV expressions and other recurrence types (e.g. shift
// recurrences). Is there existing code we can reuse?
const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
if (isa<SCEVCouldNotCompute>(ExitCount))
continue;
if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
if (AddRec->getLoop() == L)
ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
if (isa<SCEVCouldNotCompute>(ExitValue) ||
!SE->isLoopInvariant(ExitValue, L) ||
!isSafeToExpand(ExitValue, *SE))
continue;
}
// Computing the value outside of the loop brings no benefit if it is
// definitely used inside the loop in a way which can not be optimized
// away. Avoid doing so unless we know we have a value which computes
// the ExitValue already. TODO: This should be merged into SCEV
// expander to leverage its knowledge of existing expressions.
if (ReplaceExitValue != AlwaysRepl &&
!isa<SCEVConstant>(ExitValue) && !isa<SCEVUnknown>(ExitValue) &&
hasHardUserWithinLoop(L, Inst))
continue;
bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< '\n'
<< " LoopVal = " << *Inst << "\n");
if (!isValidRewrite(Inst, ExitVal)) {
DeadInsts.push_back(ExitVal);
continue;
}
#ifndef NDEBUG
// If we reuse an instruction from a loop which is neither L nor one of
// its containing loops, we end up breaking LCSSA form for this loop by
// creating a new use of its instruction.
if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
if (EVL != L)
assert(EVL->contains(L) && "LCSSA breach detected!");
#endif
// Collect all the candidate PHINodes to be rewritten.
RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
}
}
}
bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
bool Changed = false;
// Transformation.
for (const RewritePhi &Phi : RewritePhiSet) {
PHINode *PN = Phi.PN;
Value *ExitVal = Phi.Val;
// Only do the rewrite when the ExitValue can be expanded cheaply.
// If LoopCanBeDel is true, rewrite exit value aggressively.
if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
DeadInsts.push_back(ExitVal);
continue;
}
Changed = true;
++NumReplaced;
dmgreenUnsubmitted
Not Done
ReplyInline Actions

This statistic has gone missing? (Maybe have rewriteLoopExitValues return the number of replaced values, not a bool?)

dmgreen: This statistic has gone missing? (Maybe have rewriteLoopExitValues return the number of…
Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
PN->setIncomingValue(Phi.Ith, ExitVal);
// If this instruction is dead now, delete it. Don't do it now to avoid
// invalidating iterators.
if (isInstructionTriviallyDead(Inst, TLI))
DeadInsts.push_back(Inst);
// Replace PN with ExitVal if that is legal and does not break LCSSA.
if (PN->getNumIncomingValues() == 1 &&
LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
PN->replaceAllUsesWith(ExitVal);
PN->eraseFromParent();
}
}
// The insertion point instruction may have been deleted; clear it out
// so that the rewriter doesn't trip over it later.
Rewriter.clearInsertPoint();
return Changed;
}
//===---------------------------------------------------------------------===// //===---------------------------------------------------------------------===//
// rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know // rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
// they will exit at the first iteration. // they will exit at the first iteration.
//===---------------------------------------------------------------------===// //===---------------------------------------------------------------------===//
/// Check to see if this loop has loop invariant conditions which lead to loop /// 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 /// 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 iteration. This lets us predict exit values of PHI nodes that live in
▲ Show 20 Lines • Show All 59 Lines • ▼ Show 20 Lines for (PHINode &PN : ExitBB->phis()) {
ExitVal->getIncomingValue(PreheaderIdx)); ExitVal->getIncomingValue(PreheaderIdx));
} }
} }
} }
} }
return MadeAnyChanges; return MadeAnyChanges;
} }
/// Check whether it is possible to delete the loop after rewriting exit
/// value. If it is possible, ignore ReplaceExitValue and do rewriting
/// aggressively.
bool IndVarSimplify::canLoopBeDeleted(
Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
BasicBlock *Preheader = L->getLoopPreheader();
// If there is no preheader, the loop will not be deleted.
if (!Preheader)
return false;
// In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
// We obviate multiple ExitingBlocks case for simplicity.
// TODO: If we see testcase with multiple ExitingBlocks can be deleted
// after exit value rewriting, we can enhance the logic here.
SmallVector<BasicBlock *, 4> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
SmallVector<BasicBlock *, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
return false;
BasicBlock *ExitBlock = ExitBlocks[0];
BasicBlock::iterator BI = ExitBlock->begin();
while (PHINode *P = dyn_cast<PHINode>(BI)) {
Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
// If the Incoming value of P is found in RewritePhiSet, we know it
// could be rewritten to use a loop invariant value in transformation
// phase later. Skip it in the loop invariant check below.
bool found = false;
for (const RewritePhi &Phi : RewritePhiSet) {
unsigned i = Phi.Ith;
if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
found = true;
break;
}
}
Instruction *I;
if (!found && (I = dyn_cast<Instruction>(Incoming)))
if (!L->hasLoopInvariantOperands(I))
return false;
++BI;
}
for (auto *BB : L->blocks())
if (llvm::any_of(*BB, [](Instruction &I) {
return I.mayHaveSideEffects();
}))
return false;
return true;
}
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// IV Widening - Extend the width of an IV to cover its widest uses. // IV Widening - Extend the width of an IV to cover its widest uses.
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
namespace { namespace {
// Collect information about induction variables that are used by sign/zero // Collect information about induction variables that are used by sign/zero
// extend operations. This information is recorded by CollectExtend and provides // extend operations. This information is recorded by CollectExtend and provides
▲ Show 20 Lines • Show All 2,132 Lines • ▼ Show 20 Lines#endif
// set no-wrap flags before normalizing sign/zero extension. // set no-wrap flags before normalizing sign/zero extension.
Rewriter.disableCanonicalMode(); Rewriter.disableCanonicalMode();
Changed |= simplifyAndExtend(L, Rewriter, LI); Changed |= simplifyAndExtend(L, Rewriter, LI);
// Check to see if we can compute the final value of any expressions // Check to see if we can compute the final value of any expressions
// that are recurrent in the loop, and substitute the exit values from the // 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 // loop into any instructions outside of the loop that use the final values
// of the current expressions. // of the current expressions.
if (ReplaceExitValue != NeverRepl) if (ReplaceExitValue != NeverRepl) {
Changed |= rewriteLoopExitValues(L, Rewriter); if (int Rewrites = rewriteLoopExitValues(L, LI, TLI, SE, Rewriter, DT,
dmgreenUnsubmitted
Not Done
ReplyInline Actions

Does this need the getValue()?

dmgreen: Does this need the getValue()?
ReplaceExitValue, DeadInsts)) {
NumReplaced += Rewrites;
dmgreenUnsubmitted
Not Done
ReplyInline Actions

NumReplaced += Rewrites; maybe?

dmgreen: NumReplaced += Rewrites; maybe?
Changed = true;
dmgreenUnsubmitted
Not Done
ReplyInline Actions

Changed = true at this point.

dmgreen: Changed = true at this point.
}
}
// Eliminate redundant IV cycles. // Eliminate redundant IV cycles.
NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts); NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
// Try to eliminate loop exits based on analyzeable exit counts // Try to eliminate loop exits based on analyzeable exit counts
if (optimizeLoopExits(L, Rewriter)) { if (optimizeLoopExits(L, Rewriter)) {
Changed = true; Changed = true;
// Given we've changed exit counts, notify SCEV // Given we've changed exit counts, notify SCEV
SE->forgetLoop(L); SE->forgetLoop(L);
} }
// Try to form loop invariant tests for loop exits by changing how many // Try to form loop invariant tests for loop exits by changing how many
// iterations of the loop run when that is unobservable. // iterations of the loop run when that is unobservable.
if (predicateLoopExits(L, Rewriter)) { if (predicateLoopExits(L, Rewriter)) {
Changed = true; Changed = true;
// Given we've changed exit counts, notify SCEV // Given we've changed exit counts, notify SCEV
SE->forgetLoop(L); SE->forgetLoop(L);
} }
// If we have a trip count expression, rewrite the loop's exit condition // If we have a trip count expression, rewrite the loop's exit condition
// using it. // using it.
if (!DisableLFTR) { if (!DisableLFTR) {
SmallVector<BasicBlock*, 16> ExitingBlocks; SmallVector<BasicBlock*, 16> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks); L->getExitingBlocks(ExitingBlocks);
for (BasicBlock *ExitingBB : ExitingBlocks) { for (BasicBlock *ExitingBB : ExitingBlocks) {
// Can't rewrite non-branch yet. // Can't rewrite non-branch yet.
if (!isa<BranchInst>(ExitingBB->getTerminator())) if (!isa<BranchInst>(ExitingBB->getTerminator()))
continue; continue;
// If our exitting block exits multiple loops, we can only rewrite the // If our exitting block exits multiple loops, we can only rewrite the
// innermost one. Otherwise, we're changing how many times the innermost // innermost one. Otherwise, we're changing how many times the innermost
// loop runs before it exits. // loop runs before it exits.
if (LI->getLoopFor(ExitingBB) != L) if (LI->getLoopFor(ExitingBB) != L)
continue; continue;
if (!needsLFTR(L, ExitingBB)) if (!needsLFTR(L, ExitingBB))
continue; continue;
const SCEV *ExitCount = SE->getExitCount(L, ExitingBB); const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
if (isa<SCEVCouldNotCompute>(ExitCount)) if (isa<SCEVCouldNotCompute>(ExitCount))
continue; continue;
// This was handled above, but as we form SCEVs, we can sometimes refine // This was handled above, but as we form SCEVs, we can sometimes refine
// existing ones; this allows exit counts to be folded to zero which // existing ones; this allows exit counts to be folded to zero which
// weren't when optimizeLoopExits saw them. Arguably, we should iterate // weren't when optimizeLoopExits saw them. Arguably, we should iterate
// until stable to handle cases like this better. // until stable to handle cases like this better.
if (ExitCount->isZero()) if (ExitCount->isZero())
continue; continue;
PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT); PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);
if (!IndVar) if (!IndVar)
continue; continue;
// Avoid high cost expansions. Note: This heuristic is questionable in // Avoid high cost expansions. Note: This heuristic is questionable in
// that our definition of "high cost" is not exactly principled. // that our definition of "high cost" is not exactly principled.
if (Rewriter.isHighCostExpansion(ExitCount, L)) if (Rewriter.isHighCostExpansion(ExitCount, L))
continue; continue;
// Check preconditions for proper SCEVExpander operation. SCEV does not // Check preconditions for proper SCEVExpander operation. SCEV does not
// express SCEVExpander's dependencies, such as LoopSimplify. Instead // express SCEVExpander's dependencies, such as LoopSimplify. Instead
// any pass that uses the SCEVExpander must do it. This does not work // any pass that uses the SCEVExpander must do it. This does not work
// well for loop passes because SCEVExpander makes assumptions about // well for loop passes because SCEVExpander makes assumptions about
// all loops, while LoopPassManager only forces the current loop to be // all loops, while LoopPassManager only forces the current loop to be
// simplified. // simplified.
// //
// FIXME: SCEV expansion has no way to bail out, so the caller must // FIXME: SCEV expansion has no way to bail out, so the caller must
// explicitly check any assumptions made by SCEV. Brittle. // explicitly check any assumptions made by SCEV. Brittle.
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ExitCount); const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ExitCount);
if (!AR || AR->getLoop()->getLoopPreheader()) if (!AR || AR->getLoop()->getLoopPreheader())
Changed |= linearFunctionTestReplace(L, ExitingBB, Changed |= linearFunctionTestReplace(L, ExitingBB,
ExitCount, IndVar, ExitCount, IndVar,
Rewriter); Rewriter);
▲ Show 20 Lines • Show All 114 Lines • Show Last 20 Lines

llvm/lib/Transforms/Utils/LoopUtils.cpp

Show All 18 Lines
#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DIBuilder.h" #include "llvm/IR/DIBuilder.h"
#include "llvm/IR/Dominators.h" #include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h" #include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h" #include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h" #include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h" #include "llvm/InitializePasses.h"
#include "llvm/Pass.h" #include "llvm/Pass.h"
#include "llvm/Support/Debug.h" #include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h" #include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm; using namespace llvm;
using namespace llvm::PatternMatch; using namespace llvm::PatternMatch;
#define DEBUG_TYPE "loop-utils" #define DEBUG_TYPE "loop-utils"
static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"; static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
static const char *LLVMLoopDisableLICM = "llvm.licm.disable"; static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
▲ Show 20 Lines • Show All 987 Lines • ▼ Show 20 Linesbool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth(); unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) : APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
APInt::getMaxValue(BitWidth); APInt::getMaxValue(BitWidth);
auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
return SE.isAvailableAtLoopEntry(S, L) && return SE.isAvailableAtLoopEntry(S, L) &&
SE.isLoopEntryGuardedByCond(L, Predicate, S, SE.isLoopEntryGuardedByCond(L, Predicate, S,
SE.getConstant(Max)); SE.getConstant(Max));
} }
//===----------------------------------------------------------------------===//
// rewriteLoopExitValues - Optimize IV users outside the loop.
// As a side effect, reduces the amount of IV processing within the loop.
//===----------------------------------------------------------------------===//
// Return true if the SCEV expansion generated by the rewriter can replace the
// original value. SCEV guarantees that it produces the same value, but the way
// it is produced may be illegal IR. Ideally, this function will only be
// called for verification.
static bool isValidRewrite(ScalarEvolution *SE, Value *FromVal, Value *ToVal) {
// If an SCEV expression subsumed multiple pointers, its expansion could
// reassociate the GEP changing the base pointer. This is illegal because the
// final address produced by a GEP chain must be inbounds relative to its
// underlying object. Otherwise basic alias analysis, among other things,
// could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
// producing an expression involving multiple pointers. Until then, we must
// bail out here.
//
// Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
// because it understands lcssa phis while SCEV does not.
Value *FromPtr = FromVal;
Value *ToPtr = ToVal;
if (auto *GEP = dyn_cast<GEPOperator>(FromVal))
FromPtr = GEP->getPointerOperand();
if (auto *GEP = dyn_cast<GEPOperator>(ToVal))
ToPtr = GEP->getPointerOperand();
if (FromPtr != FromVal || ToPtr != ToVal) {
// Quickly check the common case
if (FromPtr == ToPtr)
return true;
// SCEV may have rewritten an expression that produces the GEP's pointer
// operand. That's ok as long as the pointer operand has the same base
// pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
// base of a recurrence. This handles the case in which SCEV expansion
// converts a pointer type recurrence into a nonrecurrent pointer base
// indexed by an integer recurrence.
// If the GEP base pointer is a vector of pointers, abort.
if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
return false;
const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
if (FromBase == ToBase)
return true;
LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out "
<< *FromBase << " != " << *ToBase << "\n");
return false;
}
return true;
}
static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
SmallPtrSet<const Instruction *, 8> Visited;
SmallVector<const Instruction *, 8> WorkList;
Visited.insert(I);
WorkList.push_back(I);
while (!WorkList.empty()) {
const Instruction *Curr = WorkList.pop_back_val();
// This use is outside the loop, nothing to do.
if (!L->contains(Curr))
continue;
// Do we assume it is a "hard" use which will not be eliminated easily?
if (Curr->mayHaveSideEffects())
return true;
// Otherwise, add all its users to worklist.
for (auto U : Curr->users()) {
auto *UI = cast<Instruction>(U);
if (Visited.insert(UI).second)
WorkList.push_back(UI);
}
}
return false;
}
// Collect information about PHI nodes which can be transformed in
// rewriteLoopExitValues.
struct RewritePhi {
PHINode *PN;
unsigned Ith; // Ith incoming value.
Value *Val; // Exit value after expansion.
bool HighCost; // High Cost when expansion.
RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
: PN(P), Ith(I), Val(V), HighCost(H) {}
};
dmgreenUnsubmitted
Not Done
ReplyInline Actions

This was added but not removed anywhere?

dmgreen: This was added but not removed anywhere?
// Check whether it is possible to delete the loop after rewriting exit
// value. If it is possible, ignore ReplaceExitValue and do rewriting
// aggressively.
static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
BasicBlock *Preheader = L->getLoopPreheader();
// If there is no preheader, the loop will not be deleted.
if (!Preheader)
return false;
// In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
// We obviate multiple ExitingBlocks case for simplicity.
// TODO: If we see testcase with multiple ExitingBlocks can be deleted
// after exit value rewriting, we can enhance the logic here.
SmallVector<BasicBlock *, 4> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
SmallVector<BasicBlock *, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
return false;
BasicBlock *ExitBlock = ExitBlocks[0];
BasicBlock::iterator BI = ExitBlock->begin();
while (PHINode *P = dyn_cast<PHINode>(BI)) {
Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
// If the Incoming value of P is found in RewritePhiSet, we know it
// could be rewritten to use a loop invariant value in transformation
// phase later. Skip it in the loop invariant check below.
bool found = false;
for (const RewritePhi &Phi : RewritePhiSet) {
unsigned i = Phi.Ith;
if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
found = true;
break;
}
}
Instruction *I;
if (!found && (I = dyn_cast<Instruction>(Incoming)))
if (!L->hasLoopInvariantOperands(I))
return false;
++BI;
}
for (auto *BB : L->blocks())
if (llvm::any_of(*BB, [](Instruction &I) {
return I.mayHaveSideEffects();
}))
return false;
return true;
}
int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI,
TargetLibraryInfo *TLI, ScalarEvolution *SE, SCEVExpander &Rewriter,
DominatorTree *DT, ReplaceExitVal ReplaceExitValue,
SmallVector<WeakTrackingVH, 16> &DeadInsts) {
// Check a pre-condition.
assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
"Indvars did not preserve LCSSA!");
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
SmallVector<RewritePhi, 8> RewritePhiSet;
// Find all values that are computed inside the loop, but used outside of it.
// Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
// the exit blocks of the loop to find them.
for (BasicBlock *ExitBB : ExitBlocks) {
// If there are no PHI nodes in this exit block, then no values defined
// inside the loop are used on this path, skip it.
PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
if (!PN) continue;
unsigned NumPreds = PN->getNumIncomingValues();
// Iterate over all of the PHI nodes.
BasicBlock::iterator BBI = ExitBB->begin();
while ((PN = dyn_cast<PHINode>(BBI++))) {
if (PN->use_empty())
continue; // dead use, don't replace it
if (!SE->isSCEVable(PN->getType()))
continue;
// It's necessary to tell ScalarEvolution about this explicitly so that
// it can walk the def-use list and forget all SCEVs, as it may not be
// watching the PHI itself. Once the new exit value is in place, there
// may not be a def-use connection between the loop and every instruction
// which got a SCEVAddRecExpr for that loop.
SE->forgetValue(PN);
// Iterate over all of the values in all the PHI nodes.
for (unsigned i = 0; i != NumPreds; ++i) {
// If the value being merged in is not integer or is not defined
// in the loop, skip it.
Value *InVal = PN->getIncomingValue(i);
if (!isa<Instruction>(InVal))
continue;
// If this pred is for a subloop, not L itself, skip it.
if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
continue; // The Block is in a subloop, skip it.
// Check that InVal is defined in the loop.
Instruction *Inst = cast<Instruction>(InVal);
if (!L->contains(Inst))
continue;
// 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. We prefer to start with
// expressions which are true for all exits (so as to maximize
// expression reuse by the SCEVExpander), but resort to per-exit
// evaluation if that fails.
const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
if (isa<SCEVCouldNotCompute>(ExitValue) ||
!SE->isLoopInvariant(ExitValue, L) ||
!isSafeToExpand(ExitValue, *SE)) {
// TODO: This should probably be sunk into SCEV in some way; maybe a
// getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
// most SCEV expressions and other recurrence types (e.g. shift
// recurrences). Is there existing code we can reuse?
const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
if (isa<SCEVCouldNotCompute>(ExitCount))
continue;
if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
if (AddRec->getLoop() == L)
ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
if (isa<SCEVCouldNotCompute>(ExitValue) ||
!SE->isLoopInvariant(ExitValue, L) ||
!isSafeToExpand(ExitValue, *SE))
continue;
}
// Computing the value outside of the loop brings no benefit if it is
// definitely used inside the loop in a way which can not be optimized
// away. Avoid doing so unless we know we have a value which computes
// the ExitValue already. TODO: This should be merged into SCEV
// expander to leverage its knowledge of existing expressions.
if (ReplaceExitValue != AlwaysRepl &&
!isa<SCEVConstant>(ExitValue) && !isa<SCEVUnknown>(ExitValue) &&
hasHardUserWithinLoop(L, Inst))
continue;
bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
<< *ExitVal << '\n' << " LoopVal = " << *Inst
<< "\n");
if (!isValidRewrite(SE, Inst, ExitVal)) {
DeadInsts.push_back(ExitVal);
continue;
}
#ifndef NDEBUG
// If we reuse an instruction from a loop which is neither L nor one of
// its containing loops, we end up breaking LCSSA form for this loop by
// creating a new use of its instruction.
if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
if (EVL != L)
assert(EVL->contains(L) && "LCSSA breach detected!");
#endif
// Collect all the candidate PHINodes to be rewritten.
RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
}
}
}
bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
int NumReplaced = 0;
// Transformation.
for (const RewritePhi &Phi : RewritePhiSet) {
PHINode *PN = Phi.PN;
Value *ExitVal = Phi.Val;
// Only do the rewrite when the ExitValue can be expanded cheaply.
// If LoopCanBeDel is true, rewrite exit value aggressively.
if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
DeadInsts.push_back(ExitVal);
continue;
}
NumReplaced++;
Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
PN->setIncomingValue(Phi.Ith, ExitVal);
// If this instruction is dead now, delete it. Don't do it now to avoid
// invalidating iterators.
if (isInstructionTriviallyDead(Inst, TLI))
DeadInsts.push_back(Inst);
// Replace PN with ExitVal if that is legal and does not break LCSSA.
if (PN->getNumIncomingValues() == 1 &&
LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
PN->replaceAllUsesWith(ExitVal);
PN->eraseFromParent();
}
}
// The insertion point instruction may have been deleted; clear it out
// so that the rewriter doesn't trip over it later.
Rewriter.clearInsertPoint();
return NumReplaced;
}