46 #define DEBUG_TYPE "loop-rotate" 48 STATISTIC(NumRotated,
"Number of loops rotated");
53 const unsigned MaxHeaderSize;
65 LoopRotate(
unsigned MaxHeaderSize,
LoopInfo *LI,
69 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
70 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
71 IsUtilMode(IsUtilMode) {}
72 bool processLoop(
Loop *L);
75 bool rotateLoop(
Loop *L,
bool SimplifiedLatch);
76 bool simplifyLoopLatch(
Loop *L);
96 for (I = OrigHeader->
begin(); I !=
E; ++
I) {
97 Value *OrigHeaderVal = &*
I;
104 Value *OrigPreHeaderVal = ValueMap.
lookup(OrigHeaderVal);
125 if (!isa<PHINode>(UserInst)) {
130 if (UserBB == OrigHeader)
135 if (UserBB == OrigPreheader) {
136 U = OrigPreHeaderVal;
149 for (
auto &DbgValue : DbgValues) {
153 if (UserBB == OrigHeader)
161 if (UserBB == OrigPreheader)
162 NewVal = OrigPreHeaderVal;
183 for (
auto &Phi : Header->
phis()) {
186 return cast<Instruction>(U)->
getParent() != HeaderExit;
205 bool LoopRotate::rotateLoop(
Loop *L,
bool SimplifiedLatch) {
230 if (L->
isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode ==
false &&
244 dbgs() <<
"LoopRotation: NOT rotating - contains non-duplicatable" 245 <<
" instructions: ";
250 LLVM_DEBUG(
dbgs() <<
"LoopRotation: NOT rotating - contains convergent " 255 if (Metrics.
NumInsts > MaxHeaderSize)
273 SE->forgetTopmostLoop(L);
277 MSSAU->getMemorySSA()->verifyMemorySSA();
286 assert(NewHeader &&
"Unable to determine new loop header");
288 "Unable to determine loop header and exit blocks");
293 "New header doesn't have one pred!");
311 using DbgIntrinsicHash =
312 std::pair<std::pair<Value *, DILocalVariable *>,
DIExpression *>;
314 return {{
D->getVariableLocation(),
D->getVariable()},
D->getExpression()};
317 for (
auto I = std::next(OrigPreheader->
rbegin()),
E = OrigPreheader->
rend();
319 if (
auto *DII = dyn_cast<DbgVariableIntrinsic>(&*I))
320 DbgIntrinsics.
insert(makeHash(DII));
336 !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
349 if (
auto *DII = dyn_cast<DbgVariableIntrinsic>(C))
350 if (DbgIntrinsics.
count(makeHash(DII))) {
359 if (V && LI->replacementPreservesLCSSAForm(C, V)) {
375 if (
auto *II = dyn_cast<IntrinsicInst>(C))
377 AC->registerAssumption(II);
397 ValueMap[OrigHeader] = OrigPreheader;
398 MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader, ValueMap);
410 if (!InsertedPHIs.
empty())
415 assert(L->
getHeader() == NewHeader &&
"Latch block is our new header");
425 DT->applyUpdates(Updates);
428 MSSAU->applyUpdates(Updates, *DT);
430 MSSAU->getMemorySSA()->verifyMemorySSA();
453 OrigPreheader, NewHeader,
462 bool SplitLatchEdge =
false;
465 Loop *PredLoop = LI->getLoopFor(ExitPred);
466 if (!PredLoop || PredLoop->
contains(Exit))
468 if (isa<IndirectBrInst>(ExitPred->getTerminator()))
477 "Despite splitting all preds, failed to split latch exit?");
487 if (DT) DT->deleteEdge(OrigPreheader, Exit);
491 MSSAU->removeEdge(OrigPreheader, Exit);
498 MSSAU->getMemorySSA()->verifyMemorySSA();
508 MSSAU->getMemorySSA()->verifyMemorySSA();
522 bool seenIncrement =
false;
523 bool MultiExitLoop =
false;
526 MultiExitLoop =
true;
533 if (isa<DbgInfoIntrinsic>(
I))
536 switch (
I->getOpcode()) {
539 case Instruction::GetElementPtr:
541 if (!cast<GEPOperator>(
I)->hasAllConstantIndices())
546 case Instruction::Sub:
547 case Instruction::And:
548 case Instruction::Or:
549 case Instruction::Xor:
550 case Instruction::Shl:
551 case Instruction::LShr:
552 case Instruction::AShr: {
554 !isa<Constant>(
I->getOperand(0))
556 : !isa<Constant>(
I->getOperand(1)) ?
I->getOperand(1) :
nullptr;
564 auto *UserInst = cast<Instruction>(UseI);
572 seenIncrement =
true;
575 case Instruction::Trunc:
576 case Instruction::ZExt:
577 case Instruction::SExt:
593 bool LoopRotate::simplifyLoopLatch(
Loop *L) {
614 << LastExit->
getName() <<
"\n");
623 MSSAU->moveAllAfterMergeBlocks(Latch, LastExit, FirstLatchInst);
625 unsigned FallThruPath = BI->
getSuccessor(0) == Latch ? 0 : 1;
635 assert(Latch->
empty() &&
"unable to evacuate Latch");
636 LI->removeBlock(Latch);
638 DT->eraseNode(Latch);
642 MSSAU->getMemorySSA()->verifyMemorySSA();
648 bool LoopRotate::processLoop(
Loop *L) {
652 bool SimplifiedLatch =
false;
658 SimplifiedLatch = simplifyLoopLatch(L);
660 bool MadeChange = rotateLoop(L, SimplifiedLatch);
662 "Loop latch should be exiting after loop-rotate.");
666 if ((MadeChange || SimplifiedLatch) && LoopMD)
669 return MadeChange || SimplifiedLatch;
679 bool IsUtilMode =
true) {
682 LoopRotate LR(
Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
687 return LR.processLoop(L);
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value *> &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop)...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Helper class for SSA formation on a set of values defined in multiple blocks.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool VerifyMemorySSA
Enables verification of MemorySSA.
This class represents lattice values for constants.
This is the interface for a simple mod/ref and alias analysis over globals.
bool convergent
True if this function contains a call to a convergent function.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
void push_back(const T &Elt)
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)
Determine whether the instructions in this range may be safely and cheaply speculated.
A cache of @llvm.assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
bool isTerminator() const
void deleteValue()
Delete a pointer to a generic Value.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
reverse_iterator rbegin()
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool notDuplicatable
True if this function cannot be duplicated.
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
iterator begin()
Instruction iterator methods.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
This is the interface for a SCEV-based alias analysis.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
static constexpr UpdateKind Delete
A Use represents the edge between a Value definition and its users.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void setName(const Twine &Name)
Change the name of the value.
BlockT * getHeader() const
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode *> &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following: ...
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
void findDbgValues(SmallVectorImpl< DbgValueInst *> &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Type * getType() const
All values are typed, get the type of this value.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
This is the common base class for debug info intrinsics for variables.
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
use_iterator_impl< Use > use_iterator
void replaceSuccessorsPhiUsesWith(BasicBlock *New)
Update all phi nodes in this basic block's successors to refer to basic block New instead of to it...
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
static constexpr UpdateKind Insert
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
LLVM Basic Block Representation.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
static bool shouldRotateLoopExitingLatch(Loop *L)
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
std::pair< iterator, bool > insert(const ValueT &V)
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value *> &EphValues)
Add information about a block to the current state.
void splice(iterator where, iplist_impl &L2)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode)
Convert a loop into a loop with bottom test.
Interval::pred_iterator pred_end(Interval *I)
self_iterator getIterator()
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
const InstListType & getInstList() const
Return the underlying instruction list container.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
Utility to calculate the size and a few similar metrics for a set of basic blocks.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
void setOperand(unsigned i, Value *Val)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Implements a dense probed hash-table based set with some number of buckets stored inline...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
iterator_range< user_iterator > users()
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_NODISCARD bool empty() const
Represents a single loop in the control flow graph.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
StringRef getName() const
Return a constant reference to the value's name.
const Function * getParent() const
Return the enclosing method, or null if none.
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, SmallVectorImpl< PHINode *> *InsertedPHIs)
RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the prehea...
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
bool mayReadFromMemory() const
Return true if this instruction may read memory.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
bool isUnconditional() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
succ_range successors(Instruction *I)
static const Function * getParent(const Value *V)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This is the interface for LLVM's primary stateless and local alias analysis.
unsigned NumInsts
Number of instructions in the analyzed blocks.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
const BasicBlock * getParent() const
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.