1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file defines common loop utility functions.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Transforms/Utils/LoopUtils.h"
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/PriorityWorklist.h"
17 #include "llvm/ADT/ScopeExit.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/Analysis/BasicAliasAnalysis.h"
23 #include "llvm/Analysis/DomTreeUpdater.h"
24 #include "llvm/Analysis/GlobalsModRef.h"
25 #include "llvm/Analysis/InstructionSimplify.h"
26 #include "llvm/Analysis/LoopAccessAnalysis.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/LoopPass.h"
29 #include "llvm/Analysis/MemorySSA.h"
30 #include "llvm/Analysis/MemorySSAUpdater.h"
31 #include "llvm/Analysis/MustExecute.h"
32 #include "llvm/Analysis/ScalarEvolution.h"
33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
34 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
35 #include "llvm/Analysis/TargetTransformInfo.h"
36 #include "llvm/Analysis/ValueTracking.h"
37 #include "llvm/IR/DIBuilder.h"
38 #include "llvm/IR/Dominators.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/MDBuilder.h"
42 #include "llvm/IR/Module.h"
43 #include "llvm/IR/Operator.h"
44 #include "llvm/IR/PatternMatch.h"
45 #include "llvm/IR/ValueHandle.h"
46 #include "llvm/InitializePasses.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/KnownBits.h"
50 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
51 #include "llvm/Transforms/Utils/Local.h"
52 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
55 using namespace llvm::PatternMatch
;
57 #define DEBUG_TYPE "loop-utils"
59 static const char *LLVMLoopDisableNonforced
= "llvm.loop.disable_nonforced";
60 static const char *LLVMLoopDisableLICM
= "llvm.licm.disable";
62 bool llvm::formDedicatedExitBlocks(Loop
*L
, DominatorTree
*DT
, LoopInfo
*LI
,
63 MemorySSAUpdater
*MSSAU
,
67 // We re-use a vector for the in-loop predecesosrs.
68 SmallVector
<BasicBlock
*, 4> InLoopPredecessors
;
70 auto RewriteExit
= [&](BasicBlock
*BB
) {
71 assert(InLoopPredecessors
.empty() &&
72 "Must start with an empty predecessors list!");
73 auto Cleanup
= make_scope_exit([&] { InLoopPredecessors
.clear(); });
75 // See if there are any non-loop predecessors of this exit block and
76 // keep track of the in-loop predecessors.
77 bool IsDedicatedExit
= true;
78 for (auto *PredBB
: predecessors(BB
))
79 if (L
->contains(PredBB
)) {
80 if (isa
<IndirectBrInst
>(PredBB
->getTerminator()))
81 // We cannot rewrite exiting edges from an indirectbr.
83 if (isa
<CallBrInst
>(PredBB
->getTerminator()))
84 // We cannot rewrite exiting edges from a callbr.
87 InLoopPredecessors
.push_back(PredBB
);
89 IsDedicatedExit
= false;
92 assert(!InLoopPredecessors
.empty() && "Must have *some* loop predecessor!");
94 // Nothing to do if this is already a dedicated exit.
98 auto *NewExitBB
= SplitBlockPredecessors(
99 BB
, InLoopPredecessors
, ".loopexit", DT
, LI
, MSSAU
, PreserveLCSSA
);
103 dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
106 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
107 << NewExitBB
->getName() << "\n");
111 // Walk the exit blocks directly rather than building up a data structure for
112 // them, but only visit each one once.
113 SmallPtrSet
<BasicBlock
*, 4> Visited
;
114 for (auto *BB
: L
->blocks())
115 for (auto *SuccBB
: successors(BB
)) {
116 // We're looking for exit blocks so skip in-loop successors.
117 if (L
->contains(SuccBB
))
120 // Visit each exit block exactly once.
121 if (!Visited
.insert(SuccBB
).second
)
124 Changed
|= RewriteExit(SuccBB
);
130 /// Returns the instructions that use values defined in the loop.
131 SmallVector
<Instruction
*, 8> llvm::findDefsUsedOutsideOfLoop(Loop
*L
) {
132 SmallVector
<Instruction
*, 8> UsedOutside
;
134 for (auto *Block
: L
->getBlocks())
135 // FIXME: I believe that this could use copy_if if the Inst reference could
136 // be adapted into a pointer.
137 for (auto &Inst
: *Block
) {
138 auto Users
= Inst
.users();
139 if (any_of(Users
, [&](User
*U
) {
140 auto *Use
= cast
<Instruction
>(U
);
141 return !L
->contains(Use
->getParent());
143 UsedOutside
.push_back(&Inst
);
149 void llvm::getLoopAnalysisUsage(AnalysisUsage
&AU
) {
150 // By definition, all loop passes need the LoopInfo analysis and the
151 // Dominator tree it depends on. Because they all participate in the loop
152 // pass manager, they must also preserve these.
153 AU
.addRequired
<DominatorTreeWrapperPass
>();
154 AU
.addPreserved
<DominatorTreeWrapperPass
>();
155 AU
.addRequired
<LoopInfoWrapperPass
>();
156 AU
.addPreserved
<LoopInfoWrapperPass
>();
158 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
159 // here because users shouldn't directly get them from this header.
160 extern char &LoopSimplifyID
;
161 extern char &LCSSAID
;
162 AU
.addRequiredID(LoopSimplifyID
);
163 AU
.addPreservedID(LoopSimplifyID
);
164 AU
.addRequiredID(LCSSAID
);
165 AU
.addPreservedID(LCSSAID
);
166 // This is used in the LPPassManager to perform LCSSA verification on passes
167 // which preserve lcssa form
168 AU
.addRequired
<LCSSAVerificationPass
>();
169 AU
.addPreserved
<LCSSAVerificationPass
>();
171 // Loop passes are designed to run inside of a loop pass manager which means
172 // that any function analyses they require must be required by the first loop
173 // pass in the manager (so that it is computed before the loop pass manager
174 // runs) and preserved by all loop pasess in the manager. To make this
175 // reasonably robust, the set needed for most loop passes is maintained here.
176 // If your loop pass requires an analysis not listed here, you will need to
177 // carefully audit the loop pass manager nesting structure that results.
178 AU
.addRequired
<AAResultsWrapperPass
>();
179 AU
.addPreserved
<AAResultsWrapperPass
>();
180 AU
.addPreserved
<BasicAAWrapperPass
>();
181 AU
.addPreserved
<GlobalsAAWrapperPass
>();
182 AU
.addPreserved
<SCEVAAWrapperPass
>();
183 AU
.addRequired
<ScalarEvolutionWrapperPass
>();
184 AU
.addPreserved
<ScalarEvolutionWrapperPass
>();
185 // FIXME: When all loop passes preserve MemorySSA, it can be required and
186 // preserved here instead of the individual handling in each pass.
189 /// Manually defined generic "LoopPass" dependency initialization. This is used
190 /// to initialize the exact set of passes from above in \c
191 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
194 /// INITIALIZE_PASS_DEPENDENCY(LoopPass)
196 /// As-if "LoopPass" were a pass.
197 void llvm::initializeLoopPassPass(PassRegistry
&Registry
) {
198 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
199 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
)
200 INITIALIZE_PASS_DEPENDENCY(LoopSimplify
)
201 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass
)
202 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
)
203 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass
)
204 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass
)
205 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass
)
206 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
)
207 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass
)
210 /// Create MDNode for input string.
211 static MDNode
*createStringMetadata(Loop
*TheLoop
, StringRef Name
, unsigned V
) {
212 LLVMContext
&Context
= TheLoop
->getHeader()->getContext();
214 MDString::get(Context
, Name
),
215 ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context
), V
))};
216 return MDNode::get(Context
, MDs
);
219 /// Set input string into loop metadata by keeping other values intact.
220 /// If the string is already in loop metadata update value if it is
222 void llvm::addStringMetadataToLoop(Loop
*TheLoop
, const char *StringMD
,
224 SmallVector
<Metadata
*, 4> MDs(1);
225 // If the loop already has metadata, retain it.
226 MDNode
*LoopID
= TheLoop
->getLoopID();
228 for (unsigned i
= 1, ie
= LoopID
->getNumOperands(); i
< ie
; ++i
) {
229 MDNode
*Node
= cast
<MDNode
>(LoopID
->getOperand(i
));
230 // If it is of form key = value, try to parse it.
231 if (Node
->getNumOperands() == 2) {
232 MDString
*S
= dyn_cast
<MDString
>(Node
->getOperand(0));
233 if (S
&& S
->getString().equals(StringMD
)) {
235 mdconst::extract_or_null
<ConstantInt
>(Node
->getOperand(1));
236 if (IntMD
&& IntMD
->getSExtValue() == V
)
237 // It is already in place. Do nothing.
239 // We need to update the value, so just skip it here and it will
240 // be added after copying other existed nodes.
248 MDs
.push_back(createStringMetadata(TheLoop
, StringMD
, V
));
249 // Replace current metadata node with new one.
250 LLVMContext
&Context
= TheLoop
->getHeader()->getContext();
251 MDNode
*NewLoopID
= MDNode::get(Context
, MDs
);
252 // Set operand 0 to refer to the loop id itself.
253 NewLoopID
->replaceOperandWith(0, NewLoopID
);
254 TheLoop
->setLoopID(NewLoopID
);
257 Optional
<ElementCount
>
258 llvm::getOptionalElementCountLoopAttribute(const Loop
*TheLoop
) {
259 Optional
<int> Width
=
260 getOptionalIntLoopAttribute(TheLoop
, "llvm.loop.vectorize.width");
262 if (Width
.hasValue()) {
263 Optional
<int> IsScalable
= getOptionalIntLoopAttribute(
264 TheLoop
, "llvm.loop.vectorize.scalable.enable");
265 return ElementCount::get(*Width
, IsScalable
.getValueOr(false));
271 Optional
<MDNode
*> llvm::makeFollowupLoopID(
272 MDNode
*OrigLoopID
, ArrayRef
<StringRef
> FollowupOptions
,
273 const char *InheritOptionsExceptPrefix
, bool AlwaysNew
) {
280 assert(OrigLoopID
->getOperand(0) == OrigLoopID
);
282 bool InheritAllAttrs
= !InheritOptionsExceptPrefix
;
283 bool InheritSomeAttrs
=
284 InheritOptionsExceptPrefix
&& InheritOptionsExceptPrefix
[0] != '\0';
285 SmallVector
<Metadata
*, 8> MDs
;
286 MDs
.push_back(nullptr);
288 bool Changed
= false;
289 if (InheritAllAttrs
|| InheritSomeAttrs
) {
290 for (const MDOperand
&Existing
: drop_begin(OrigLoopID
->operands())) {
291 MDNode
*Op
= cast
<MDNode
>(Existing
.get());
293 auto InheritThisAttribute
= [InheritSomeAttrs
,
294 InheritOptionsExceptPrefix
](MDNode
*Op
) {
295 if (!InheritSomeAttrs
)
298 // Skip malformatted attribute metadata nodes.
299 if (Op
->getNumOperands() == 0)
301 Metadata
*NameMD
= Op
->getOperand(0).get();
302 if (!isa
<MDString
>(NameMD
))
304 StringRef AttrName
= cast
<MDString
>(NameMD
)->getString();
306 // Do not inherit excluded attributes.
307 return !AttrName
.startswith(InheritOptionsExceptPrefix
);
310 if (InheritThisAttribute(Op
))
316 // Modified if we dropped at least one attribute.
317 Changed
= OrigLoopID
->getNumOperands() > 1;
320 bool HasAnyFollowup
= false;
321 for (StringRef OptionName
: FollowupOptions
) {
322 MDNode
*FollowupNode
= findOptionMDForLoopID(OrigLoopID
, OptionName
);
326 HasAnyFollowup
= true;
327 for (const MDOperand
&Option
: drop_begin(FollowupNode
->operands())) {
328 MDs
.push_back(Option
.get());
333 // Attributes of the followup loop not specified explicity, so signal to the
334 // transformation pass to add suitable attributes.
335 if (!AlwaysNew
&& !HasAnyFollowup
)
338 // If no attributes were added or remove, the previous loop Id can be reused.
339 if (!AlwaysNew
&& !Changed
)
342 // No attributes is equivalent to having no !llvm.loop metadata at all.
346 // Build the new loop ID.
347 MDTuple
*FollowupLoopID
= MDNode::get(OrigLoopID
->getContext(), MDs
);
348 FollowupLoopID
->replaceOperandWith(0, FollowupLoopID
);
349 return FollowupLoopID
;
352 bool llvm::hasDisableAllTransformsHint(const Loop
*L
) {
353 return getBooleanLoopAttribute(L
, LLVMLoopDisableNonforced
);
356 bool llvm::hasDisableLICMTransformsHint(const Loop
*L
) {
357 return getBooleanLoopAttribute(L
, LLVMLoopDisableLICM
);
360 TransformationMode
llvm::hasUnrollTransformation(const Loop
*L
) {
361 if (getBooleanLoopAttribute(L
, "llvm.loop.unroll.disable"))
362 return TM_SuppressedByUser
;
364 Optional
<int> Count
=
365 getOptionalIntLoopAttribute(L
, "llvm.loop.unroll.count");
366 if (Count
.hasValue())
367 return Count
.getValue() == 1 ? TM_SuppressedByUser
: TM_ForcedByUser
;
369 if (getBooleanLoopAttribute(L
, "llvm.loop.unroll.enable"))
370 return TM_ForcedByUser
;
372 if (getBooleanLoopAttribute(L
, "llvm.loop.unroll.full"))
373 return TM_ForcedByUser
;
375 if (hasDisableAllTransformsHint(L
))
378 return TM_Unspecified
;
381 TransformationMode
llvm::hasUnrollAndJamTransformation(const Loop
*L
) {
382 if (getBooleanLoopAttribute(L
, "llvm.loop.unroll_and_jam.disable"))
383 return TM_SuppressedByUser
;
385 Optional
<int> Count
=
386 getOptionalIntLoopAttribute(L
, "llvm.loop.unroll_and_jam.count");
387 if (Count
.hasValue())
388 return Count
.getValue() == 1 ? TM_SuppressedByUser
: TM_ForcedByUser
;
390 if (getBooleanLoopAttribute(L
, "llvm.loop.unroll_and_jam.enable"))
391 return TM_ForcedByUser
;
393 if (hasDisableAllTransformsHint(L
))
396 return TM_Unspecified
;
399 TransformationMode
llvm::hasVectorizeTransformation(const Loop
*L
) {
400 Optional
<bool> Enable
=
401 getOptionalBoolLoopAttribute(L
, "llvm.loop.vectorize.enable");
404 return TM_SuppressedByUser
;
406 Optional
<ElementCount
> VectorizeWidth
=
407 getOptionalElementCountLoopAttribute(L
);
408 Optional
<int> InterleaveCount
=
409 getOptionalIntLoopAttribute(L
, "llvm.loop.interleave.count");
411 // 'Forcing' vector width and interleave count to one effectively disables
412 // this tranformation.
413 if (Enable
== true && VectorizeWidth
&& VectorizeWidth
->isScalar() &&
414 InterleaveCount
== 1)
415 return TM_SuppressedByUser
;
417 if (getBooleanLoopAttribute(L
, "llvm.loop.isvectorized"))
421 return TM_ForcedByUser
;
423 if ((VectorizeWidth
&& VectorizeWidth
->isScalar()) && InterleaveCount
== 1)
426 if ((VectorizeWidth
&& VectorizeWidth
->isVector()) || InterleaveCount
> 1)
429 if (hasDisableAllTransformsHint(L
))
432 return TM_Unspecified
;
435 TransformationMode
llvm::hasDistributeTransformation(const Loop
*L
) {
436 if (getBooleanLoopAttribute(L
, "llvm.loop.distribute.enable"))
437 return TM_ForcedByUser
;
439 if (hasDisableAllTransformsHint(L
))
442 return TM_Unspecified
;
445 TransformationMode
llvm::hasLICMVersioningTransformation(const Loop
*L
) {
446 if (getBooleanLoopAttribute(L
, "llvm.loop.licm_versioning.disable"))
447 return TM_SuppressedByUser
;
449 if (hasDisableAllTransformsHint(L
))
452 return TM_Unspecified
;
455 /// Does a BFS from a given node to all of its children inside a given loop.
456 /// The returned vector of nodes includes the starting point.
457 SmallVector
<DomTreeNode
*, 16>
458 llvm::collectChildrenInLoop(DomTreeNode
*N
, const Loop
*CurLoop
) {
459 SmallVector
<DomTreeNode
*, 16> Worklist
;
460 auto AddRegionToWorklist
= [&](DomTreeNode
*DTN
) {
461 // Only include subregions in the top level loop.
462 BasicBlock
*BB
= DTN
->getBlock();
463 if (CurLoop
->contains(BB
))
464 Worklist
.push_back(DTN
);
467 AddRegionToWorklist(N
);
469 for (size_t I
= 0; I
< Worklist
.size(); I
++) {
470 for (DomTreeNode
*Child
: Worklist
[I
]->children())
471 AddRegionToWorklist(Child
);
477 void llvm::deleteDeadLoop(Loop
*L
, DominatorTree
*DT
, ScalarEvolution
*SE
,
478 LoopInfo
*LI
, MemorySSA
*MSSA
) {
479 assert((!DT
|| L
->isLCSSAForm(*DT
)) && "Expected LCSSA!");
480 auto *Preheader
= L
->getLoopPreheader();
481 assert(Preheader
&& "Preheader should exist!");
483 std::unique_ptr
<MemorySSAUpdater
> MSSAU
;
485 MSSAU
= std::make_unique
<MemorySSAUpdater
>(MSSA
);
487 // Now that we know the removal is safe, remove the loop by changing the
488 // branch from the preheader to go to the single exit block.
490 // Because we're deleting a large chunk of code at once, the sequence in which
491 // we remove things is very important to avoid invalidation issues.
493 // Tell ScalarEvolution that the loop is deleted. Do this before
494 // deleting the loop so that ScalarEvolution can look at the loop
495 // to determine what it needs to clean up.
499 auto *OldBr
= dyn_cast
<BranchInst
>(Preheader
->getTerminator());
500 assert(OldBr
&& "Preheader must end with a branch");
501 assert(OldBr
->isUnconditional() && "Preheader must have a single successor");
502 // Connect the preheader to the exit block. Keep the old edge to the header
503 // around to perform the dominator tree update in two separate steps
504 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
505 // preheader -> header.
508 // 0. Preheader 1. Preheader 2. Preheader
511 // Header <--\ | Header <--\ | Header <--\
512 // | | | | | | | | | | |
513 // | V | | | V | | | V |
514 // | Body --/ | | Body --/ | | Body --/
518 // By doing this is two separate steps we can perform the dominator tree
519 // update without using the batch update API.
521 // Even when the loop is never executed, we cannot remove the edge from the
522 // source block to the exit block. Consider the case where the unexecuted loop
523 // branches back to an outer loop. If we deleted the loop and removed the edge
524 // coming to this inner loop, this will break the outer loop structure (by
525 // deleting the backedge of the outer loop). If the outer loop is indeed a
526 // non-loop, it will be deleted in a future iteration of loop deletion pass.
527 IRBuilder
<> Builder(OldBr
);
529 auto *ExitBlock
= L
->getUniqueExitBlock();
530 DomTreeUpdater
DTU(DT
, DomTreeUpdater::UpdateStrategy::Eager
);
532 assert(ExitBlock
&& "Should have a unique exit block!");
533 assert(L
->hasDedicatedExits() && "Loop should have dedicated exits!");
535 Builder
.CreateCondBr(Builder
.getFalse(), L
->getHeader(), ExitBlock
);
536 // Remove the old branch. The conditional branch becomes a new terminator.
537 OldBr
->eraseFromParent();
539 // Rewrite phis in the exit block to get their inputs from the Preheader
540 // instead of the exiting block.
541 for (PHINode
&P
: ExitBlock
->phis()) {
542 // Set the zero'th element of Phi to be from the preheader and remove all
543 // other incoming values. Given the loop has dedicated exits, all other
544 // incoming values must be from the exiting blocks.
546 P
.setIncomingBlock(PredIndex
, Preheader
);
547 // Removes all incoming values from all other exiting blocks (including
548 // duplicate values from an exiting block).
549 // Nuke all entries except the zero'th entry which is the preheader entry.
550 // NOTE! We need to remove Incoming Values in the reverse order as done
551 // below, to keep the indices valid for deletion (removeIncomingValues
552 // updates getNumIncomingValues and shifts all values down into the
553 // operand being deleted).
554 for (unsigned i
= 0, e
= P
.getNumIncomingValues() - 1; i
!= e
; ++i
)
555 P
.removeIncomingValue(e
- i
, false);
557 assert((P
.getNumIncomingValues() == 1 &&
558 P
.getIncomingBlock(PredIndex
) == Preheader
) &&
559 "Should have exactly one value and that's from the preheader!");
563 DTU
.applyUpdates({{DominatorTree::Insert
, Preheader
, ExitBlock
}});
565 MSSAU
->applyUpdates({{DominatorTree::Insert
, Preheader
, ExitBlock
}},
568 MSSA
->verifyMemorySSA();
572 // Disconnect the loop body by branching directly to its exit.
573 Builder
.SetInsertPoint(Preheader
->getTerminator());
574 Builder
.CreateBr(ExitBlock
);
575 // Remove the old branch.
576 Preheader
->getTerminator()->eraseFromParent();
578 assert(L
->hasNoExitBlocks() &&
579 "Loop should have either zero or one exit blocks.");
581 Builder
.SetInsertPoint(OldBr
);
582 Builder
.CreateUnreachable();
583 Preheader
->getTerminator()->eraseFromParent();
587 DTU
.applyUpdates({{DominatorTree::Delete
, Preheader
, L
->getHeader()}});
589 MSSAU
->applyUpdates({{DominatorTree::Delete
, Preheader
, L
->getHeader()}},
591 SmallSetVector
<BasicBlock
*, 8> DeadBlockSet(L
->block_begin(),
593 MSSAU
->removeBlocks(DeadBlockSet
);
595 MSSA
->verifyMemorySSA();
599 // Use a map to unique and a vector to guarantee deterministic ordering.
600 llvm::SmallDenseSet
<std::pair
<DIVariable
*, DIExpression
*>, 4> DeadDebugSet
;
601 llvm::SmallVector
<DbgVariableIntrinsic
*, 4> DeadDebugInst
;
604 // Given LCSSA form is satisfied, we should not have users of instructions
605 // within the dead loop outside of the loop. However, LCSSA doesn't take
606 // unreachable uses into account. We handle them here.
607 // We could do it after drop all references (in this case all users in the
608 // loop will be already eliminated and we have less work to do but according
609 // to API doc of User::dropAllReferences only valid operation after dropping
610 // references, is deletion. So let's substitute all usages of
611 // instruction from the loop with undef value of corresponding type first.
612 for (auto *Block
: L
->blocks())
613 for (Instruction
&I
: *Block
) {
614 auto *Undef
= UndefValue::get(I
.getType());
615 for (Value::use_iterator UI
= I
.use_begin(), E
= I
.use_end();
619 if (auto *Usr
= dyn_cast
<Instruction
>(U
.getUser()))
620 if (L
->contains(Usr
->getParent()))
622 // If we have a DT then we can check that uses outside a loop only in
623 // unreachable block.
625 assert(!DT
->isReachableFromEntry(U
) &&
626 "Unexpected user in reachable block");
629 auto *DVI
= dyn_cast
<DbgVariableIntrinsic
>(&I
);
633 DeadDebugSet
.find({DVI
->getVariable(), DVI
->getExpression()});
634 if (Key
!= DeadDebugSet
.end())
636 DeadDebugSet
.insert({DVI
->getVariable(), DVI
->getExpression()});
637 DeadDebugInst
.push_back(DVI
);
640 // After the loop has been deleted all the values defined and modified
641 // inside the loop are going to be unavailable.
642 // Since debug values in the loop have been deleted, inserting an undef
643 // dbg.value truncates the range of any dbg.value before the loop where the
644 // loop used to be. This is particularly important for constant values.
645 DIBuilder
DIB(*ExitBlock
->getModule());
646 Instruction
*InsertDbgValueBefore
= ExitBlock
->getFirstNonPHI();
647 assert(InsertDbgValueBefore
&&
648 "There should be a non-PHI instruction in exit block, else these "
649 "instructions will have no parent.");
650 for (auto *DVI
: DeadDebugInst
)
651 DIB
.insertDbgValueIntrinsic(UndefValue::get(Builder
.getInt32Ty()),
652 DVI
->getVariable(), DVI
->getExpression(),
653 DVI
->getDebugLoc(), InsertDbgValueBefore
);
656 // Remove the block from the reference counting scheme, so that we can
657 // delete it freely later.
658 for (auto *Block
: L
->blocks())
659 Block
->dropAllReferences();
661 if (MSSA
&& VerifyMemorySSA
)
662 MSSA
->verifyMemorySSA();
665 // Erase the instructions and the blocks without having to worry
666 // about ordering because we already dropped the references.
667 // NOTE: This iteration is safe because erasing the block does not remove
668 // its entry from the loop's block list. We do that in the next section.
669 for (Loop::block_iterator LpI
= L
->block_begin(), LpE
= L
->block_end();
671 (*LpI
)->eraseFromParent();
673 // Finally, the blocks from loopinfo. This has to happen late because
674 // otherwise our loop iterators won't work.
676 SmallPtrSet
<BasicBlock
*, 8> blocks
;
677 blocks
.insert(L
->block_begin(), L
->block_end());
678 for (BasicBlock
*BB
: blocks
)
681 // The last step is to update LoopInfo now that we've eliminated this loop.
682 // Note: LoopInfo::erase remove the given loop and relink its subloops with
683 // its parent. While removeLoop/removeChildLoop remove the given loop but
684 // not relink its subloops, which is what we want.
685 if (Loop
*ParentLoop
= L
->getParentLoop()) {
686 Loop::iterator I
= find(*ParentLoop
, L
);
687 assert(I
!= ParentLoop
->end() && "Couldn't find loop");
688 ParentLoop
->removeChildLoop(I
);
690 Loop::iterator I
= find(*LI
, L
);
691 assert(I
!= LI
->end() && "Couldn't find loop");
698 static Loop
*getOutermostLoop(Loop
*L
) {
699 while (Loop
*Parent
= L
->getParentLoop())
704 void llvm::breakLoopBackedge(Loop
*L
, DominatorTree
&DT
, ScalarEvolution
&SE
,
705 LoopInfo
&LI
, MemorySSA
*MSSA
) {
706 auto *Latch
= L
->getLoopLatch();
707 assert(Latch
&& "multiple latches not yet supported");
708 auto *Header
= L
->getHeader();
709 Loop
*OutermostLoop
= getOutermostLoop(L
);
713 // Note: By splitting the backedge, and then explicitly making it unreachable
714 // we gracefully handle corner cases such as non-bottom tested loops and the
715 // like. We also have the benefit of being able to reuse existing well tested
716 // code. It might be worth special casing the common bottom tested case at
717 // some point to avoid code churn.
719 std::unique_ptr
<MemorySSAUpdater
> MSSAU
;
721 MSSAU
= std::make_unique
<MemorySSAUpdater
>(MSSA
);
723 auto *BackedgeBB
= SplitEdge(Latch
, Header
, &DT
, &LI
, MSSAU
.get());
725 DomTreeUpdater
DTU(&DT
, DomTreeUpdater::UpdateStrategy::Eager
);
726 (void)changeToUnreachable(BackedgeBB
->getTerminator(),
727 /*PreserveLCSSA*/ true, &DTU
, MSSAU
.get());
729 // Erase (and destroy) this loop instance. Handles relinking sub-loops
730 // and blocks within the loop as needed.
733 // If the loop we broke had a parent, then changeToUnreachable might have
734 // caused a block to be removed from the parent loop (see loop_nest_lcssa
735 // test case in zero-btc.ll for an example), thus changing the parent's
736 // exit blocks. If that happened, we need to rebuild LCSSA on the outermost
737 // loop which might have a had a block removed.
738 if (OutermostLoop
!= L
)
739 formLCSSARecursively(*OutermostLoop
, DT
, &LI
, &SE
);
743 /// Checks if \p L has single exit through latch block except possibly
744 /// "deoptimizing" exits. Returns branch instruction terminating the loop
745 /// latch if above check is successful, nullptr otherwise.
746 static BranchInst
*getExpectedExitLoopLatchBranch(Loop
*L
) {
747 BasicBlock
*Latch
= L
->getLoopLatch();
751 BranchInst
*LatchBR
= dyn_cast
<BranchInst
>(Latch
->getTerminator());
752 if (!LatchBR
|| LatchBR
->getNumSuccessors() != 2 || !L
->isLoopExiting(Latch
))
755 assert((LatchBR
->getSuccessor(0) == L
->getHeader() ||
756 LatchBR
->getSuccessor(1) == L
->getHeader()) &&
757 "At least one edge out of the latch must go to the header");
759 SmallVector
<BasicBlock
*, 4> ExitBlocks
;
760 L
->getUniqueNonLatchExitBlocks(ExitBlocks
);
761 if (any_of(ExitBlocks
, [](const BasicBlock
*EB
) {
762 return !EB
->getTerminatingDeoptimizeCall();
770 llvm::getLoopEstimatedTripCount(Loop
*L
,
771 unsigned *EstimatedLoopInvocationWeight
) {
772 // Support loops with an exiting latch and other existing exists only
774 BranchInst
*LatchBranch
= getExpectedExitLoopLatchBranch(L
);
778 // To estimate the number of times the loop body was executed, we want to
779 // know the number of times the backedge was taken, vs. the number of times
780 // we exited the loop.
781 uint64_t BackedgeTakenWeight
, LatchExitWeight
;
782 if (!LatchBranch
->extractProfMetadata(BackedgeTakenWeight
, LatchExitWeight
))
785 if (LatchBranch
->getSuccessor(0) != L
->getHeader())
786 std::swap(BackedgeTakenWeight
, LatchExitWeight
);
788 if (!LatchExitWeight
)
791 if (EstimatedLoopInvocationWeight
)
792 *EstimatedLoopInvocationWeight
= LatchExitWeight
;
794 // Estimated backedge taken count is a ratio of the backedge taken weight by
795 // the weight of the edge exiting the loop, rounded to nearest.
796 uint64_t BackedgeTakenCount
=
797 llvm::divideNearest(BackedgeTakenWeight
, LatchExitWeight
);
798 // Estimated trip count is one plus estimated backedge taken count.
799 return BackedgeTakenCount
+ 1;
802 bool llvm::setLoopEstimatedTripCount(Loop
*L
, unsigned EstimatedTripCount
,
803 unsigned EstimatedloopInvocationWeight
) {
804 // Support loops with an exiting latch and other existing exists only
806 BranchInst
*LatchBranch
= getExpectedExitLoopLatchBranch(L
);
810 // Calculate taken and exit weights.
811 unsigned LatchExitWeight
= 0;
812 unsigned BackedgeTakenWeight
= 0;
814 if (EstimatedTripCount
> 0) {
815 LatchExitWeight
= EstimatedloopInvocationWeight
;
816 BackedgeTakenWeight
= (EstimatedTripCount
- 1) * LatchExitWeight
;
819 // Make a swap if back edge is taken when condition is "false".
820 if (LatchBranch
->getSuccessor(0) != L
->getHeader())
821 std::swap(BackedgeTakenWeight
, LatchExitWeight
);
823 MDBuilder
MDB(LatchBranch
->getContext());
825 // Set/Update profile metadata.
826 LatchBranch
->setMetadata(
827 LLVMContext::MD_prof
,
828 MDB
.createBranchWeights(BackedgeTakenWeight
, LatchExitWeight
));
833 bool llvm::hasIterationCountInvariantInParent(Loop
*InnerLoop
,
834 ScalarEvolution
&SE
) {
835 Loop
*OuterL
= InnerLoop
->getParentLoop();
839 // Get the backedge taken count for the inner loop
840 BasicBlock
*InnerLoopLatch
= InnerLoop
->getLoopLatch();
841 const SCEV
*InnerLoopBECountSC
= SE
.getExitCount(InnerLoop
, InnerLoopLatch
);
842 if (isa
<SCEVCouldNotCompute
>(InnerLoopBECountSC
) ||
843 !InnerLoopBECountSC
->getType()->isIntegerTy())
846 // Get whether count is invariant to the outer loop
847 ScalarEvolution::LoopDisposition LD
=
848 SE
.getLoopDisposition(InnerLoopBECountSC
, OuterL
);
849 if (LD
!= ScalarEvolution::LoopInvariant
)
855 Value
*llvm::createMinMaxOp(IRBuilderBase
&Builder
, RecurKind RK
, Value
*Left
,
857 CmpInst::Predicate Pred
;
860 llvm_unreachable("Unknown min/max recurrence kind");
861 case RecurKind::UMin
:
862 Pred
= CmpInst::ICMP_ULT
;
864 case RecurKind::UMax
:
865 Pred
= CmpInst::ICMP_UGT
;
867 case RecurKind::SMin
:
868 Pred
= CmpInst::ICMP_SLT
;
870 case RecurKind::SMax
:
871 Pred
= CmpInst::ICMP_SGT
;
873 case RecurKind::FMin
:
874 Pred
= CmpInst::FCMP_OLT
;
876 case RecurKind::FMax
:
877 Pred
= CmpInst::FCMP_OGT
;
881 Value
*Cmp
= Builder
.CreateCmp(Pred
, Left
, Right
, "rdx.minmax.cmp");
882 Value
*Select
= Builder
.CreateSelect(Cmp
, Left
, Right
, "rdx.minmax.select");
886 // Helper to generate an ordered reduction.
887 Value
*llvm::getOrderedReduction(IRBuilderBase
&Builder
, Value
*Acc
, Value
*Src
,
888 unsigned Op
, RecurKind RdxKind
,
889 ArrayRef
<Value
*> RedOps
) {
890 unsigned VF
= cast
<FixedVectorType
>(Src
->getType())->getNumElements();
892 // Extract and apply reduction ops in ascending order:
893 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
895 for (unsigned ExtractIdx
= 0; ExtractIdx
!= VF
; ++ExtractIdx
) {
897 Builder
.CreateExtractElement(Src
, Builder
.getInt32(ExtractIdx
));
899 if (Op
!= Instruction::ICmp
&& Op
!= Instruction::FCmp
) {
900 Result
= Builder
.CreateBinOp((Instruction::BinaryOps
)Op
, Result
, Ext
,
903 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind
) &&
905 Result
= createMinMaxOp(Builder
, RdxKind
, Result
, Ext
);
909 propagateIRFlags(Result
, RedOps
);
915 // Helper to generate a log2 shuffle reduction.
916 Value
*llvm::getShuffleReduction(IRBuilderBase
&Builder
, Value
*Src
,
917 unsigned Op
, RecurKind RdxKind
,
918 ArrayRef
<Value
*> RedOps
) {
919 unsigned VF
= cast
<FixedVectorType
>(Src
->getType())->getNumElements();
920 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
921 // and vector ops, reducing the set of values being computed by half each
923 assert(isPowerOf2_32(VF
) &&
924 "Reduction emission only supported for pow2 vectors!");
926 SmallVector
<int, 32> ShuffleMask(VF
);
927 for (unsigned i
= VF
; i
!= 1; i
>>= 1) {
928 // Move the upper half of the vector to the lower half.
929 for (unsigned j
= 0; j
!= i
/ 2; ++j
)
930 ShuffleMask
[j
] = i
/ 2 + j
;
932 // Fill the rest of the mask with undef.
933 std::fill(&ShuffleMask
[i
/ 2], ShuffleMask
.end(), -1);
935 Value
*Shuf
= Builder
.CreateShuffleVector(TmpVec
, ShuffleMask
, "rdx.shuf");
937 if (Op
!= Instruction::ICmp
&& Op
!= Instruction::FCmp
) {
938 // The builder propagates its fast-math-flags setting.
939 TmpVec
= Builder
.CreateBinOp((Instruction::BinaryOps
)Op
, TmpVec
, Shuf
,
942 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind
) &&
944 TmpVec
= createMinMaxOp(Builder
, RdxKind
, TmpVec
, Shuf
);
947 propagateIRFlags(TmpVec
, RedOps
);
949 // We may compute the reassociated scalar ops in a way that does not
950 // preserve nsw/nuw etc. Conservatively, drop those flags.
951 if (auto *ReductionInst
= dyn_cast
<Instruction
>(TmpVec
))
952 ReductionInst
->dropPoisonGeneratingFlags();
954 // The result is in the first element of the vector.
955 return Builder
.CreateExtractElement(TmpVec
, Builder
.getInt32(0));
958 Value
*llvm::createSimpleTargetReduction(IRBuilderBase
&Builder
,
959 const TargetTransformInfo
*TTI
,
960 Value
*Src
, RecurKind RdxKind
,
961 ArrayRef
<Value
*> RedOps
) {
962 auto *SrcVecEltTy
= cast
<VectorType
>(Src
->getType())->getElementType();
965 return Builder
.CreateAddReduce(Src
);
967 return Builder
.CreateMulReduce(Src
);
969 return Builder
.CreateAndReduce(Src
);
971 return Builder
.CreateOrReduce(Src
);
973 return Builder
.CreateXorReduce(Src
);
974 case RecurKind::FAdd
:
975 return Builder
.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy
),
977 case RecurKind::FMul
:
978 return Builder
.CreateFMulReduce(ConstantFP::get(SrcVecEltTy
, 1.0), Src
);
979 case RecurKind::SMax
:
980 return Builder
.CreateIntMaxReduce(Src
, true);
981 case RecurKind::SMin
:
982 return Builder
.CreateIntMinReduce(Src
, true);
983 case RecurKind::UMax
:
984 return Builder
.CreateIntMaxReduce(Src
, false);
985 case RecurKind::UMin
:
986 return Builder
.CreateIntMinReduce(Src
, false);
987 case RecurKind::FMax
:
988 return Builder
.CreateFPMaxReduce(Src
);
989 case RecurKind::FMin
:
990 return Builder
.CreateFPMinReduce(Src
);
992 llvm_unreachable("Unhandled opcode");
996 Value
*llvm::createTargetReduction(IRBuilderBase
&B
,
997 const TargetTransformInfo
*TTI
,
998 const RecurrenceDescriptor
&Desc
,
1000 // TODO: Support in-order reductions based on the recurrence descriptor.
1001 // All ops in the reduction inherit fast-math-flags from the recurrence
1003 IRBuilderBase::FastMathFlagGuard
FMFGuard(B
);
1004 B
.setFastMathFlags(Desc
.getFastMathFlags());
1005 return createSimpleTargetReduction(B
, TTI
, Src
, Desc
.getRecurrenceKind());
1008 Value
*llvm::createOrderedReduction(IRBuilderBase
&B
,
1009 const RecurrenceDescriptor
&Desc
,
1010 Value
*Src
, Value
*Start
) {
1011 assert(Desc
.getRecurrenceKind() == RecurKind::FAdd
&&
1012 "Unexpected reduction kind");
1013 assert(Src
->getType()->isVectorTy() && "Expected a vector type");
1014 assert(!Start
->getType()->isVectorTy() && "Expected a scalar type");
1016 return B
.CreateFAddReduce(Start
, Src
);
1019 void llvm::propagateIRFlags(Value
*I
, ArrayRef
<Value
*> VL
, Value
*OpValue
) {
1020 auto *VecOp
= dyn_cast
<Instruction
>(I
);
1023 auto *Intersection
= (OpValue
== nullptr) ? dyn_cast
<Instruction
>(VL
[0])
1024 : dyn_cast
<Instruction
>(OpValue
);
1027 const unsigned Opcode
= Intersection
->getOpcode();
1028 VecOp
->copyIRFlags(Intersection
);
1029 for (auto *V
: VL
) {
1030 auto *Instr
= dyn_cast
<Instruction
>(V
);
1033 if (OpValue
== nullptr || Opcode
== Instr
->getOpcode())
1034 VecOp
->andIRFlags(V
);
1038 bool llvm::isKnownNegativeInLoop(const SCEV
*S
, const Loop
*L
,
1039 ScalarEvolution
&SE
) {
1040 const SCEV
*Zero
= SE
.getZero(S
->getType());
1041 return SE
.isAvailableAtLoopEntry(S
, L
) &&
1042 SE
.isLoopEntryGuardedByCond(L
, ICmpInst::ICMP_SLT
, S
, Zero
);
1045 bool llvm::isKnownNonNegativeInLoop(const SCEV
*S
, const Loop
*L
,
1046 ScalarEvolution
&SE
) {
1047 const SCEV
*Zero
= SE
.getZero(S
->getType());
1048 return SE
.isAvailableAtLoopEntry(S
, L
) &&
1049 SE
.isLoopEntryGuardedByCond(L
, ICmpInst::ICMP_SGE
, S
, Zero
);
1052 bool llvm::cannotBeMinInLoop(const SCEV
*S
, const Loop
*L
, ScalarEvolution
&SE
,
1054 unsigned BitWidth
= cast
<IntegerType
>(S
->getType())->getBitWidth();
1055 APInt Min
= Signed
? APInt::getSignedMinValue(BitWidth
) :
1056 APInt::getMinValue(BitWidth
);
1057 auto Predicate
= Signed
? ICmpInst::ICMP_SGT
: ICmpInst::ICMP_UGT
;
1058 return SE
.isAvailableAtLoopEntry(S
, L
) &&
1059 SE
.isLoopEntryGuardedByCond(L
, Predicate
, S
,
1060 SE
.getConstant(Min
));
1063 bool llvm::cannotBeMaxInLoop(const SCEV
*S
, const Loop
*L
, ScalarEvolution
&SE
,
1065 unsigned BitWidth
= cast
<IntegerType
>(S
->getType())->getBitWidth();
1066 APInt Max
= Signed
? APInt::getSignedMaxValue(BitWidth
) :
1067 APInt::getMaxValue(BitWidth
);
1068 auto Predicate
= Signed
? ICmpInst::ICMP_SLT
: ICmpInst::ICMP_ULT
;
1069 return SE
.isAvailableAtLoopEntry(S
, L
) &&
1070 SE
.isLoopEntryGuardedByCond(L
, Predicate
, S
,
1071 SE
.getConstant(Max
));
1074 //===----------------------------------------------------------------------===//
1075 // rewriteLoopExitValues - Optimize IV users outside the loop.
1076 // As a side effect, reduces the amount of IV processing within the loop.
1077 //===----------------------------------------------------------------------===//
1079 // Return true if the SCEV expansion generated by the rewriter can replace the
1080 // original value. SCEV guarantees that it produces the same value, but the way
1081 // it is produced may be illegal IR. Ideally, this function will only be
1082 // called for verification.
1083 static bool isValidRewrite(ScalarEvolution
*SE
, Value
*FromVal
, Value
*ToVal
) {
1084 // If an SCEV expression subsumed multiple pointers, its expansion could
1085 // reassociate the GEP changing the base pointer. This is illegal because the
1086 // final address produced by a GEP chain must be inbounds relative to its
1087 // underlying object. Otherwise basic alias analysis, among other things,
1088 // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
1089 // producing an expression involving multiple pointers. Until then, we must
1092 // Retrieve the pointer operand of the GEP. Don't use getUnderlyingObject
1093 // because it understands lcssa phis while SCEV does not.
1094 Value
*FromPtr
= FromVal
;
1095 Value
*ToPtr
= ToVal
;
1096 if (auto *GEP
= dyn_cast
<GEPOperator
>(FromVal
))
1097 FromPtr
= GEP
->getPointerOperand();
1099 if (auto *GEP
= dyn_cast
<GEPOperator
>(ToVal
))
1100 ToPtr
= GEP
->getPointerOperand();
1102 if (FromPtr
!= FromVal
|| ToPtr
!= ToVal
) {
1103 // Quickly check the common case
1104 if (FromPtr
== ToPtr
)
1107 // SCEV may have rewritten an expression that produces the GEP's pointer
1108 // operand. That's ok as long as the pointer operand has the same base
1109 // pointer. Unlike getUnderlyingObject(), getPointerBase() will find the
1110 // base of a recurrence. This handles the case in which SCEV expansion
1111 // converts a pointer type recurrence into a nonrecurrent pointer base
1112 // indexed by an integer recurrence.
1114 // If the GEP base pointer is a vector of pointers, abort.
1115 if (!FromPtr
->getType()->isPointerTy() || !ToPtr
->getType()->isPointerTy())
1118 const SCEV
*FromBase
= SE
->getPointerBase(SE
->getSCEV(FromPtr
));
1119 const SCEV
*ToBase
= SE
->getPointerBase(SE
->getSCEV(ToPtr
));
1120 if (FromBase
== ToBase
)
1123 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out "
1124 << *FromBase
<< " != " << *ToBase
<< "\n");
1131 static bool hasHardUserWithinLoop(const Loop
*L
, const Instruction
*I
) {
1132 SmallPtrSet
<const Instruction
*, 8> Visited
;
1133 SmallVector
<const Instruction
*, 8> WorkList
;
1135 WorkList
.push_back(I
);
1136 while (!WorkList
.empty()) {
1137 const Instruction
*Curr
= WorkList
.pop_back_val();
1138 // This use is outside the loop, nothing to do.
1139 if (!L
->contains(Curr
))
1141 // Do we assume it is a "hard" use which will not be eliminated easily?
1142 if (Curr
->mayHaveSideEffects())
1144 // Otherwise, add all its users to worklist.
1145 for (auto U
: Curr
->users()) {
1146 auto *UI
= cast
<Instruction
>(U
);
1147 if (Visited
.insert(UI
).second
)
1148 WorkList
.push_back(UI
);
1154 // Collect information about PHI nodes which can be transformed in
1155 // rewriteLoopExitValues.
1157 PHINode
*PN
; // For which PHI node is this replacement?
1158 unsigned Ith
; // For which incoming value?
1159 const SCEV
*ExpansionSCEV
; // The SCEV of the incoming value we are rewriting.
1160 Instruction
*ExpansionPoint
; // Where we'd like to expand that SCEV?
1161 bool HighCost
; // Is this expansion a high-cost?
1163 Value
*Expansion
= nullptr;
1164 bool ValidRewrite
= false;
1166 RewritePhi(PHINode
*P
, unsigned I
, const SCEV
*Val
, Instruction
*ExpansionPt
,
1168 : PN(P
), Ith(I
), ExpansionSCEV(Val
), ExpansionPoint(ExpansionPt
),
1172 // Check whether it is possible to delete the loop after rewriting exit
1173 // value. If it is possible, ignore ReplaceExitValue and do rewriting
1175 static bool canLoopBeDeleted(Loop
*L
, SmallVector
<RewritePhi
, 8> &RewritePhiSet
) {
1176 BasicBlock
*Preheader
= L
->getLoopPreheader();
1177 // If there is no preheader, the loop will not be deleted.
1181 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1182 // We obviate multiple ExitingBlocks case for simplicity.
1183 // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1184 // after exit value rewriting, we can enhance the logic here.
1185 SmallVector
<BasicBlock
*, 4> ExitingBlocks
;
1186 L
->getExitingBlocks(ExitingBlocks
);
1187 SmallVector
<BasicBlock
*, 8> ExitBlocks
;
1188 L
->getUniqueExitBlocks(ExitBlocks
);
1189 if (ExitBlocks
.size() != 1 || ExitingBlocks
.size() != 1)
1192 BasicBlock
*ExitBlock
= ExitBlocks
[0];
1193 BasicBlock::iterator BI
= ExitBlock
->begin();
1194 while (PHINode
*P
= dyn_cast
<PHINode
>(BI
)) {
1195 Value
*Incoming
= P
->getIncomingValueForBlock(ExitingBlocks
[0]);
1197 // If the Incoming value of P is found in RewritePhiSet, we know it
1198 // could be rewritten to use a loop invariant value in transformation
1199 // phase later. Skip it in the loop invariant check below.
1201 for (const RewritePhi
&Phi
: RewritePhiSet
) {
1202 if (!Phi
.ValidRewrite
)
1204 unsigned i
= Phi
.Ith
;
1205 if (Phi
.PN
== P
&& (Phi
.PN
)->getIncomingValue(i
) == Incoming
) {
1212 if (!found
&& (I
= dyn_cast
<Instruction
>(Incoming
)))
1213 if (!L
->hasLoopInvariantOperands(I
))
1219 for (auto *BB
: L
->blocks())
1220 if (llvm::any_of(*BB
, [](Instruction
&I
) {
1221 return I
.mayHaveSideEffects();
1228 int llvm::rewriteLoopExitValues(Loop
*L
, LoopInfo
*LI
, TargetLibraryInfo
*TLI
,
1229 ScalarEvolution
*SE
,
1230 const TargetTransformInfo
*TTI
,
1231 SCEVExpander
&Rewriter
, DominatorTree
*DT
,
1232 ReplaceExitVal ReplaceExitValue
,
1233 SmallVector
<WeakTrackingVH
, 16> &DeadInsts
) {
1234 // Check a pre-condition.
1235 assert(L
->isRecursivelyLCSSAForm(*DT
, *LI
) &&
1236 "Indvars did not preserve LCSSA!");
1238 SmallVector
<BasicBlock
*, 8> ExitBlocks
;
1239 L
->getUniqueExitBlocks(ExitBlocks
);
1241 SmallVector
<RewritePhi
, 8> RewritePhiSet
;
1242 // Find all values that are computed inside the loop, but used outside of it.
1243 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
1244 // the exit blocks of the loop to find them.
1245 for (BasicBlock
*ExitBB
: ExitBlocks
) {
1246 // If there are no PHI nodes in this exit block, then no values defined
1247 // inside the loop are used on this path, skip it.
1248 PHINode
*PN
= dyn_cast
<PHINode
>(ExitBB
->begin());
1251 unsigned NumPreds
= PN
->getNumIncomingValues();
1253 // Iterate over all of the PHI nodes.
1254 BasicBlock::iterator BBI
= ExitBB
->begin();
1255 while ((PN
= dyn_cast
<PHINode
>(BBI
++))) {
1256 if (PN
->use_empty())
1257 continue; // dead use, don't replace it
1259 if (!SE
->isSCEVable(PN
->getType()))
1262 // It's necessary to tell ScalarEvolution about this explicitly so that
1263 // it can walk the def-use list and forget all SCEVs, as it may not be
1264 // watching the PHI itself. Once the new exit value is in place, there
1265 // may not be a def-use connection between the loop and every instruction
1266 // which got a SCEVAddRecExpr for that loop.
1267 SE
->forgetValue(PN
);
1269 // Iterate over all of the values in all the PHI nodes.
1270 for (unsigned i
= 0; i
!= NumPreds
; ++i
) {
1271 // If the value being merged in is not integer or is not defined
1272 // in the loop, skip it.
1273 Value
*InVal
= PN
->getIncomingValue(i
);
1274 if (!isa
<Instruction
>(InVal
))
1277 // If this pred is for a subloop, not L itself, skip it.
1278 if (LI
->getLoopFor(PN
->getIncomingBlock(i
)) != L
)
1279 continue; // The Block is in a subloop, skip it.
1281 // Check that InVal is defined in the loop.
1282 Instruction
*Inst
= cast
<Instruction
>(InVal
);
1283 if (!L
->contains(Inst
))
1286 // Okay, this instruction has a user outside of the current loop
1287 // and varies predictably *inside* the loop. Evaluate the value it
1288 // contains when the loop exits, if possible. We prefer to start with
1289 // expressions which are true for all exits (so as to maximize
1290 // expression reuse by the SCEVExpander), but resort to per-exit
1291 // evaluation if that fails.
1292 const SCEV
*ExitValue
= SE
->getSCEVAtScope(Inst
, L
->getParentLoop());
1293 if (isa
<SCEVCouldNotCompute
>(ExitValue
) ||
1294 !SE
->isLoopInvariant(ExitValue
, L
) ||
1295 !isSafeToExpand(ExitValue
, *SE
)) {
1296 // TODO: This should probably be sunk into SCEV in some way; maybe a
1297 // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
1298 // most SCEV expressions and other recurrence types (e.g. shift
1299 // recurrences). Is there existing code we can reuse?
1300 const SCEV
*ExitCount
= SE
->getExitCount(L
, PN
->getIncomingBlock(i
));
1301 if (isa
<SCEVCouldNotCompute
>(ExitCount
))
1303 if (auto *AddRec
= dyn_cast
<SCEVAddRecExpr
>(SE
->getSCEV(Inst
)))
1304 if (AddRec
->getLoop() == L
)
1305 ExitValue
= AddRec
->evaluateAtIteration(ExitCount
, *SE
);
1306 if (isa
<SCEVCouldNotCompute
>(ExitValue
) ||
1307 !SE
->isLoopInvariant(ExitValue
, L
) ||
1308 !isSafeToExpand(ExitValue
, *SE
))
1312 // Computing the value outside of the loop brings no benefit if it is
1313 // definitely used inside the loop in a way which can not be optimized
1314 // away. Avoid doing so unless we know we have a value which computes
1315 // the ExitValue already. TODO: This should be merged into SCEV
1316 // expander to leverage its knowledge of existing expressions.
1317 if (ReplaceExitValue
!= AlwaysRepl
&& !isa
<SCEVConstant
>(ExitValue
) &&
1318 !isa
<SCEVUnknown
>(ExitValue
) && hasHardUserWithinLoop(L
, Inst
))
1321 // Check if expansions of this SCEV would count as being high cost.
1322 bool HighCost
= Rewriter
.isHighCostExpansion(
1323 ExitValue
, L
, SCEVCheapExpansionBudget
, TTI
, Inst
);
1325 // Note that we must not perform expansions until after
1326 // we query *all* the costs, because if we perform temporary expansion
1327 // inbetween, one that we might not intend to keep, said expansion
1328 // *may* affect cost calculation of the the next SCEV's we'll query,
1329 // and next SCEV may errneously get smaller cost.
1331 // Collect all the candidate PHINodes to be rewritten.
1332 RewritePhiSet
.emplace_back(PN
, i
, ExitValue
, Inst
, HighCost
);
1337 // Now that we've done preliminary filtering and billed all the SCEV's,
1338 // we can perform the last sanity check - the expansion must be valid.
1339 for (RewritePhi
&Phi
: RewritePhiSet
) {
1340 Phi
.Expansion
= Rewriter
.expandCodeFor(Phi
.ExpansionSCEV
, Phi
.PN
->getType(),
1341 Phi
.ExpansionPoint
);
1343 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
1344 << *(Phi
.Expansion
) << '\n'
1345 << " LoopVal = " << *(Phi
.ExpansionPoint
) << "\n");
1347 // FIXME: isValidRewrite() is a hack. it should be an assert, eventually.
1348 Phi
.ValidRewrite
= isValidRewrite(SE
, Phi
.ExpansionPoint
, Phi
.Expansion
);
1349 if (!Phi
.ValidRewrite
) {
1350 DeadInsts
.push_back(Phi
.Expansion
);
1355 // If we reuse an instruction from a loop which is neither L nor one of
1356 // its containing loops, we end up breaking LCSSA form for this loop by
1357 // creating a new use of its instruction.
1358 if (auto *ExitInsn
= dyn_cast
<Instruction
>(Phi
.Expansion
))
1359 if (auto *EVL
= LI
->getLoopFor(ExitInsn
->getParent()))
1361 assert(EVL
->contains(L
) && "LCSSA breach detected!");
1365 // TODO: after isValidRewrite() is an assertion, evaluate whether
1366 // it is beneficial to change how we calculate high-cost:
1367 // if we have SCEV 'A' which we know we will expand, should we calculate
1368 // the cost of other SCEV's after expanding SCEV 'A',
1369 // thus potentially giving cost bonus to those other SCEV's?
1371 bool LoopCanBeDel
= canLoopBeDeleted(L
, RewritePhiSet
);
1372 int NumReplaced
= 0;
1375 for (const RewritePhi
&Phi
: RewritePhiSet
) {
1376 if (!Phi
.ValidRewrite
)
1379 PHINode
*PN
= Phi
.PN
;
1380 Value
*ExitVal
= Phi
.Expansion
;
1382 // Only do the rewrite when the ExitValue can be expanded cheaply.
1383 // If LoopCanBeDel is true, rewrite exit value aggressively.
1384 if (ReplaceExitValue
== OnlyCheapRepl
&& !LoopCanBeDel
&& Phi
.HighCost
) {
1385 DeadInsts
.push_back(ExitVal
);
1390 Instruction
*Inst
= cast
<Instruction
>(PN
->getIncomingValue(Phi
.Ith
));
1391 PN
->setIncomingValue(Phi
.Ith
, ExitVal
);
1393 // If this instruction is dead now, delete it. Don't do it now to avoid
1394 // invalidating iterators.
1395 if (isInstructionTriviallyDead(Inst
, TLI
))
1396 DeadInsts
.push_back(Inst
);
1398 // Replace PN with ExitVal if that is legal and does not break LCSSA.
1399 if (PN
->getNumIncomingValues() == 1 &&
1400 LI
->replacementPreservesLCSSAForm(PN
, ExitVal
)) {
1401 PN
->replaceAllUsesWith(ExitVal
);
1402 PN
->eraseFromParent();
1406 // The insertion point instruction may have been deleted; clear it out
1407 // so that the rewriter doesn't trip over it later.
1408 Rewriter
.clearInsertPoint();
1412 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1414 void llvm::setProfileInfoAfterUnrolling(Loop
*OrigLoop
, Loop
*UnrolledLoop
,
1415 Loop
*RemainderLoop
, uint64_t UF
) {
1416 assert(UF
> 0 && "Zero unrolled factor is not supported");
1417 assert(UnrolledLoop
!= RemainderLoop
&&
1418 "Unrolled and Remainder loops are expected to distinct");
1420 // Get number of iterations in the original scalar loop.
1421 unsigned OrigLoopInvocationWeight
= 0;
1422 Optional
<unsigned> OrigAverageTripCount
=
1423 getLoopEstimatedTripCount(OrigLoop
, &OrigLoopInvocationWeight
);
1424 if (!OrigAverageTripCount
)
1427 // Calculate number of iterations in unrolled loop.
1428 unsigned UnrolledAverageTripCount
= *OrigAverageTripCount
/ UF
;
1429 // Calculate number of iterations for remainder loop.
1430 unsigned RemainderAverageTripCount
= *OrigAverageTripCount
% UF
;
1432 setLoopEstimatedTripCount(UnrolledLoop
, UnrolledAverageTripCount
,
1433 OrigLoopInvocationWeight
);
1434 setLoopEstimatedTripCount(RemainderLoop
, RemainderAverageTripCount
,
1435 OrigLoopInvocationWeight
);
1438 /// Utility that implements appending of loops onto a worklist.
1439 /// Loops are added in preorder (analogous for reverse postorder for trees),
1440 /// and the worklist is processed LIFO.
1441 template <typename RangeT
>
1442 void llvm::appendReversedLoopsToWorklist(
1443 RangeT
&&Loops
, SmallPriorityWorklist
<Loop
*, 4> &Worklist
) {
1444 // We use an internal worklist to build up the preorder traversal without
1446 SmallVector
<Loop
*, 4> PreOrderLoops
, PreOrderWorklist
;
1448 // We walk the initial sequence of loops in reverse because we generally want
1449 // to visit defs before uses and the worklist is LIFO.
1450 for (Loop
*RootL
: Loops
) {
1451 assert(PreOrderLoops
.empty() && "Must start with an empty preorder walk.");
1452 assert(PreOrderWorklist
.empty() &&
1453 "Must start with an empty preorder walk worklist.");
1454 PreOrderWorklist
.push_back(RootL
);
1456 Loop
*L
= PreOrderWorklist
.pop_back_val();
1457 PreOrderWorklist
.append(L
->begin(), L
->end());
1458 PreOrderLoops
.push_back(L
);
1459 } while (!PreOrderWorklist
.empty());
1461 Worklist
.insert(std::move(PreOrderLoops
));
1462 PreOrderLoops
.clear();
1466 template <typename RangeT
>
1467 void llvm::appendLoopsToWorklist(RangeT
&&Loops
,
1468 SmallPriorityWorklist
<Loop
*, 4> &Worklist
) {
1469 appendReversedLoopsToWorklist(reverse(Loops
), Worklist
);
1472 template void llvm::appendLoopsToWorklist
<ArrayRef
<Loop
*> &>(
1473 ArrayRef
<Loop
*> &Loops
, SmallPriorityWorklist
<Loop
*, 4> &Worklist
);
1476 llvm::appendLoopsToWorklist
<Loop
&>(Loop
&L
,
1477 SmallPriorityWorklist
<Loop
*, 4> &Worklist
);
1479 void llvm::appendLoopsToWorklist(LoopInfo
&LI
,
1480 SmallPriorityWorklist
<Loop
*, 4> &Worklist
) {
1481 appendReversedLoopsToWorklist(LI
, Worklist
);
1484 Loop
*llvm::cloneLoop(Loop
*L
, Loop
*PL
, ValueToValueMapTy
&VM
,
1485 LoopInfo
*LI
, LPPassManager
*LPM
) {
1486 Loop
&New
= *LI
->AllocateLoop();
1488 PL
->addChildLoop(&New
);
1490 LI
->addTopLevelLoop(&New
);
1495 // Add all of the blocks in L to the new loop.
1496 for (Loop::block_iterator I
= L
->block_begin(), E
= L
->block_end();
1498 if (LI
->getLoopFor(*I
) == L
)
1499 New
.addBasicBlockToLoop(cast
<BasicBlock
>(VM
[*I
]), *LI
);
1501 // Add all of the subloops to the new loop.
1503 cloneLoop(I
, &New
, VM
, LI
, LPM
);
1508 /// IR Values for the lower and upper bounds of a pointer evolution. We
1509 /// need to use value-handles because SCEV expansion can invalidate previously
1510 /// expanded values. Thus expansion of a pointer can invalidate the bounds for
1512 struct PointerBounds
{
1513 TrackingVH
<Value
> Start
;
1514 TrackingVH
<Value
> End
;
1517 /// Expand code for the lower and upper bound of the pointer group \p CG
1518 /// in \p TheLoop. \return the values for the bounds.
1519 static PointerBounds
expandBounds(const RuntimeCheckingPtrGroup
*CG
,
1520 Loop
*TheLoop
, Instruction
*Loc
,
1521 SCEVExpander
&Exp
) {
1522 LLVMContext
&Ctx
= Loc
->getContext();
1523 Type
*PtrArithTy
= Type::getInt8PtrTy(Ctx
, CG
->AddressSpace
);
1525 Value
*Start
= nullptr, *End
= nullptr;
1526 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1527 Start
= Exp
.expandCodeFor(CG
->Low
, PtrArithTy
, Loc
);
1528 End
= Exp
.expandCodeFor(CG
->High
, PtrArithTy
, Loc
);
1529 LLVM_DEBUG(dbgs() << "Start: " << *CG
->Low
<< " End: " << *CG
->High
<< "\n");
1530 return {Start
, End
};
1533 /// Turns a collection of checks into a collection of expanded upper and
1534 /// lower bounds for both pointers in the check.
1535 static SmallVector
<std::pair
<PointerBounds
, PointerBounds
>, 4>
1536 expandBounds(const SmallVectorImpl
<RuntimePointerCheck
> &PointerChecks
, Loop
*L
,
1537 Instruction
*Loc
, SCEVExpander
&Exp
) {
1538 SmallVector
<std::pair
<PointerBounds
, PointerBounds
>, 4> ChecksWithBounds
;
1540 // Here we're relying on the SCEV Expander's cache to only emit code for the
1541 // same bounds once.
1542 transform(PointerChecks
, std::back_inserter(ChecksWithBounds
),
1543 [&](const RuntimePointerCheck
&Check
) {
1544 PointerBounds First
= expandBounds(Check
.first
, L
, Loc
, Exp
),
1545 Second
= expandBounds(Check
.second
, L
, Loc
, Exp
);
1546 return std::make_pair(First
, Second
);
1549 return ChecksWithBounds
;
1552 std::pair
<Instruction
*, Instruction
*> llvm::addRuntimeChecks(
1553 Instruction
*Loc
, Loop
*TheLoop
,
1554 const SmallVectorImpl
<RuntimePointerCheck
> &PointerChecks
,
1555 SCEVExpander
&Exp
) {
1556 // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1557 // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible
1558 auto ExpandedChecks
= expandBounds(PointerChecks
, TheLoop
, Loc
, Exp
);
1560 LLVMContext
&Ctx
= Loc
->getContext();
1561 Instruction
*FirstInst
= nullptr;
1562 IRBuilder
<> ChkBuilder(Loc
);
1563 // Our instructions might fold to a constant.
1564 Value
*MemoryRuntimeCheck
= nullptr;
1566 // FIXME: this helper is currently a duplicate of the one in
1567 // LoopVectorize.cpp.
1568 auto GetFirstInst
= [](Instruction
*FirstInst
, Value
*V
,
1569 Instruction
*Loc
) -> Instruction
* {
1572 if (Instruction
*I
= dyn_cast
<Instruction
>(V
))
1573 return I
->getParent() == Loc
->getParent() ? I
: nullptr;
1577 for (const auto &Check
: ExpandedChecks
) {
1578 const PointerBounds
&A
= Check
.first
, &B
= Check
.second
;
1579 // Check if two pointers (A and B) conflict where conflict is computed as:
1580 // start(A) <= end(B) && start(B) <= end(A)
1581 unsigned AS0
= A
.Start
->getType()->getPointerAddressSpace();
1582 unsigned AS1
= B
.Start
->getType()->getPointerAddressSpace();
1584 assert((AS0
== B
.End
->getType()->getPointerAddressSpace()) &&
1585 (AS1
== A
.End
->getType()->getPointerAddressSpace()) &&
1586 "Trying to bounds check pointers with different address spaces");
1588 Type
*PtrArithTy0
= Type::getInt8PtrTy(Ctx
, AS0
);
1589 Type
*PtrArithTy1
= Type::getInt8PtrTy(Ctx
, AS1
);
1591 Value
*Start0
= ChkBuilder
.CreateBitCast(A
.Start
, PtrArithTy0
, "bc");
1592 Value
*Start1
= ChkBuilder
.CreateBitCast(B
.Start
, PtrArithTy1
, "bc");
1593 Value
*End0
= ChkBuilder
.CreateBitCast(A
.End
, PtrArithTy1
, "bc");
1594 Value
*End1
= ChkBuilder
.CreateBitCast(B
.End
, PtrArithTy0
, "bc");
1596 // [A|B].Start points to the first accessed byte under base [A|B].
1597 // [A|B].End points to the last accessed byte, plus one.
1598 // There is no conflict when the intervals are disjoint:
1599 // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1601 // bound0 = (B.Start < A.End)
1602 // bound1 = (A.Start < B.End)
1603 // IsConflict = bound0 & bound1
1604 Value
*Cmp0
= ChkBuilder
.CreateICmpULT(Start0
, End1
, "bound0");
1605 FirstInst
= GetFirstInst(FirstInst
, Cmp0
, Loc
);
1606 Value
*Cmp1
= ChkBuilder
.CreateICmpULT(Start1
, End0
, "bound1");
1607 FirstInst
= GetFirstInst(FirstInst
, Cmp1
, Loc
);
1608 Value
*IsConflict
= ChkBuilder
.CreateAnd(Cmp0
, Cmp1
, "found.conflict");
1609 FirstInst
= GetFirstInst(FirstInst
, IsConflict
, Loc
);
1610 if (MemoryRuntimeCheck
) {
1612 ChkBuilder
.CreateOr(MemoryRuntimeCheck
, IsConflict
, "conflict.rdx");
1613 FirstInst
= GetFirstInst(FirstInst
, IsConflict
, Loc
);
1615 MemoryRuntimeCheck
= IsConflict
;
1618 if (!MemoryRuntimeCheck
)
1619 return std::make_pair(nullptr, nullptr);
1621 // We have to do this trickery because the IRBuilder might fold the check to a
1622 // constant expression in which case there is no Instruction anchored in a
1624 Instruction
*Check
=
1625 BinaryOperator::CreateAnd(MemoryRuntimeCheck
, ConstantInt::getTrue(Ctx
));
1626 ChkBuilder
.Insert(Check
, "memcheck.conflict");
1627 FirstInst
= GetFirstInst(FirstInst
, Check
, Loc
);
1628 return std::make_pair(FirstInst
, Check
);
1631 Optional
<IVConditionInfo
> llvm::hasPartialIVCondition(Loop
&L
,
1632 unsigned MSSAThreshold
,
1635 auto *TI
= dyn_cast
<BranchInst
>(L
.getHeader()->getTerminator());
1636 if (!TI
|| !TI
->isConditional())
1639 auto *CondI
= dyn_cast
<CmpInst
>(TI
->getCondition());
1640 // The case with the condition outside the loop should already be handled
1642 if (!CondI
|| !L
.contains(CondI
))
1645 SmallVector
<Instruction
*> InstToDuplicate
;
1646 InstToDuplicate
.push_back(CondI
);
1648 SmallVector
<Value
*, 4> WorkList
;
1649 WorkList
.append(CondI
->op_begin(), CondI
->op_end());
1651 SmallVector
<MemoryAccess
*, 4> AccessesToCheck
;
1652 SmallVector
<MemoryLocation
, 4> AccessedLocs
;
1653 while (!WorkList
.empty()) {
1654 Instruction
*I
= dyn_cast
<Instruction
>(WorkList
.pop_back_val());
1655 if (!I
|| !L
.contains(I
))
1658 // TODO: support additional instructions.
1659 if (!isa
<LoadInst
>(I
) && !isa
<GetElementPtrInst
>(I
))
1662 // Do not duplicate volatile and atomic loads.
1663 if (auto *LI
= dyn_cast
<LoadInst
>(I
))
1664 if (LI
->isVolatile() || LI
->isAtomic())
1667 InstToDuplicate
.push_back(I
);
1668 if (MemoryAccess
*MA
= MSSA
.getMemoryAccess(I
)) {
1669 if (auto *MemUse
= dyn_cast_or_null
<MemoryUse
>(MA
)) {
1670 // Queue the defining access to check for alias checks.
1671 AccessesToCheck
.push_back(MemUse
->getDefiningAccess());
1672 AccessedLocs
.push_back(MemoryLocation::get(I
));
1674 // MemoryDefs may clobber the location or may be atomic memory
1675 // operations. Bail out.
1679 WorkList
.append(I
->op_begin(), I
->op_end());
1682 if (InstToDuplicate
.empty())
1685 SmallVector
<BasicBlock
*, 4> ExitingBlocks
;
1686 L
.getExitingBlocks(ExitingBlocks
);
1687 auto HasNoClobbersOnPath
=
1688 [&L
, &AA
, &AccessedLocs
, &ExitingBlocks
, &InstToDuplicate
,
1689 MSSAThreshold
](BasicBlock
*Succ
, BasicBlock
*Header
,
1690 SmallVector
<MemoryAccess
*, 4> AccessesToCheck
)
1691 -> Optional
<IVConditionInfo
> {
1692 IVConditionInfo Info
;
1693 // First, collect all blocks in the loop that are on a patch from Succ
1695 SmallVector
<BasicBlock
*, 4> WorkList
;
1696 WorkList
.push_back(Succ
);
1697 WorkList
.push_back(Header
);
1698 SmallPtrSet
<BasicBlock
*, 4> Seen
;
1699 Seen
.insert(Header
);
1701 all_of(*Header
, [](Instruction
&I
) { return !I
.mayHaveSideEffects(); });
1703 while (!WorkList
.empty()) {
1704 BasicBlock
*Current
= WorkList
.pop_back_val();
1705 if (!L
.contains(Current
))
1707 const auto &SeenIns
= Seen
.insert(Current
);
1708 if (!SeenIns
.second
)
1711 Info
.PathIsNoop
&= all_of(
1712 *Current
, [](Instruction
&I
) { return !I
.mayHaveSideEffects(); });
1713 WorkList
.append(succ_begin(Current
), succ_end(Current
));
1716 // Require at least 2 blocks on a path through the loop. This skips
1717 // paths that directly exit the loop.
1718 if (Seen
.size() < 2)
1721 // Next, check if there are any MemoryDefs that are on the path through
1722 // the loop (in the Seen set) and they may-alias any of the locations in
1723 // AccessedLocs. If that is the case, they may modify the condition and
1724 // partial unswitching is not possible.
1725 SmallPtrSet
<MemoryAccess
*, 4> SeenAccesses
;
1726 while (!AccessesToCheck
.empty()) {
1727 MemoryAccess
*Current
= AccessesToCheck
.pop_back_val();
1728 auto SeenI
= SeenAccesses
.insert(Current
);
1729 if (!SeenI
.second
|| !Seen
.contains(Current
->getBlock()))
1732 // Bail out if exceeded the threshold.
1733 if (SeenAccesses
.size() >= MSSAThreshold
)
1736 // MemoryUse are read-only accesses.
1737 if (isa
<MemoryUse
>(Current
))
1740 // For a MemoryDef, check if is aliases any of the location feeding
1741 // the original condition.
1742 if (auto *CurrentDef
= dyn_cast
<MemoryDef
>(Current
)) {
1743 if (any_of(AccessedLocs
, [&AA
, CurrentDef
](MemoryLocation
&Loc
) {
1745 AA
.getModRefInfo(CurrentDef
->getMemoryInst(), Loc
));
1750 for (Use
&U
: Current
->uses())
1751 AccessesToCheck
.push_back(cast
<MemoryAccess
>(U
.getUser()));
1754 // We could also allow loops with known trip counts without mustprogress,
1755 // but ScalarEvolution may not be available.
1756 Info
.PathIsNoop
&= isMustProgress(&L
);
1758 // If the path is considered a no-op so far, check if it reaches a
1759 // single exit block without any phis. This ensures no values from the
1760 // loop are used outside of the loop.
1761 if (Info
.PathIsNoop
) {
1762 for (auto *Exiting
: ExitingBlocks
) {
1763 if (!Seen
.contains(Exiting
))
1765 for (auto *Succ
: successors(Exiting
)) {
1766 if (L
.contains(Succ
))
1769 Info
.PathIsNoop
&= llvm::empty(Succ
->phis()) &&
1770 (!Info
.ExitForPath
|| Info
.ExitForPath
== Succ
);
1771 if (!Info
.PathIsNoop
)
1773 assert((!Info
.ExitForPath
|| Info
.ExitForPath
== Succ
) &&
1774 "cannot have multiple exit blocks");
1775 Info
.ExitForPath
= Succ
;
1779 if (!Info
.ExitForPath
)
1780 Info
.PathIsNoop
= false;
1782 Info
.InstToDuplicate
= InstToDuplicate
;
1786 // If we branch to the same successor, partial unswitching will not be
1788 if (TI
->getSuccessor(0) == TI
->getSuccessor(1))
1791 if (auto Info
= HasNoClobbersOnPath(TI
->getSuccessor(0), L
.getHeader(),
1793 Info
->KnownValue
= ConstantInt::getTrue(TI
->getContext());
1796 if (auto Info
= HasNoClobbersOnPath(TI
->getSuccessor(1), L
.getHeader(),
1798 Info
->KnownValue
= ConstantInt::getFalse(TI
->getContext());