1 //===- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop -------===//
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 pass transforms loops that contain branches on loop-invariant conditions
10 // to multiple loops. For example, it turns the left into the right code:
19 // This can increase the size of the code exponentially (doubling it every time
20 // a loop is unswitched) so we only unswitch if the resultant code will be
21 // smaller than a threshold.
23 // This pass expects LICM to be run before it to hoist invariant conditions out
24 // of the loop, to make the unswitching opportunity obvious.
26 //===----------------------------------------------------------------------===//
28 #include "llvm/ADT/DenseMap.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/AssumptionCache.h"
33 #include "llvm/Analysis/CodeMetrics.h"
34 #include "llvm/Analysis/InstructionSimplify.h"
35 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
36 #include "llvm/Analysis/LoopInfo.h"
37 #include "llvm/Analysis/LoopIterator.h"
38 #include "llvm/Analysis/LoopPass.h"
39 #include "llvm/Analysis/MemorySSA.h"
40 #include "llvm/Analysis/MemorySSAUpdater.h"
41 #include "llvm/Analysis/MustExecute.h"
42 #include "llvm/Analysis/ScalarEvolution.h"
43 #include "llvm/Analysis/TargetTransformInfo.h"
44 #include "llvm/IR/Attributes.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/Constant.h"
47 #include "llvm/IR/Constants.h"
48 #include "llvm/IR/DerivedTypes.h"
49 #include "llvm/IR/Dominators.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/IRBuilder.h"
52 #include "llvm/IR/InstrTypes.h"
53 #include "llvm/IR/Instruction.h"
54 #include "llvm/IR/Instructions.h"
55 #include "llvm/IR/IntrinsicInst.h"
56 #include "llvm/IR/Intrinsics.h"
57 #include "llvm/IR/Module.h"
58 #include "llvm/IR/Type.h"
59 #include "llvm/IR/User.h"
60 #include "llvm/IR/Value.h"
61 #include "llvm/IR/ValueHandle.h"
62 #include "llvm/InitializePasses.h"
63 #include "llvm/Pass.h"
64 #include "llvm/Support/Casting.h"
65 #include "llvm/Support/CommandLine.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Support/raw_ostream.h"
68 #include "llvm/Transforms/Scalar.h"
69 #include "llvm/Transforms/Scalar/LoopPassManager.h"
70 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
71 #include "llvm/Transforms/Utils/Cloning.h"
72 #include "llvm/Transforms/Utils/Local.h"
73 #include "llvm/Transforms/Utils/LoopUtils.h"
74 #include "llvm/Transforms/Utils/ValueMapper.h"
85 #define DEBUG_TYPE "loop-unswitch"
87 STATISTIC(NumBranches, "Number of branches unswitched");
88 STATISTIC(NumSwitches, "Number of switches unswitched");
89 STATISTIC(NumGuards, "Number of guards unswitched");
90 STATISTIC(NumSelects , "Number of selects unswitched");
91 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
92 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
93 STATISTIC(TotalInsts, "Total number of instructions analyzed");
95 // The specific value of 100 here was chosen based only on intuition and a
96 // few specific examples.
97 static cl::opt<unsigned>
98 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
99 cl::init(100), cl::Hidden);
103 class LUAnalysisCache {
104 using UnswitchedValsMap =
105 DenseMap<const SwitchInst *, SmallPtrSet<const Value *, 8>>;
106 using UnswitchedValsIt = UnswitchedValsMap::iterator;
108 struct LoopProperties {
109 unsigned CanBeUnswitchedCount;
110 unsigned WasUnswitchedCount;
111 unsigned SizeEstimation;
112 UnswitchedValsMap UnswitchedVals;
115 // Here we use std::map instead of DenseMap, since we need to keep valid
116 // LoopProperties pointer for current loop for better performance.
117 using LoopPropsMap = std::map<const Loop *, LoopProperties>;
118 using LoopPropsMapIt = LoopPropsMap::iterator;
120 LoopPropsMap LoopsProperties;
121 UnswitchedValsMap *CurLoopInstructions = nullptr;
122 LoopProperties *CurrentLoopProperties = nullptr;
124 // A loop unswitching with an estimated cost above this threshold
125 // is not performed. MaxSize is turned into unswitching quota for
126 // the current loop, and reduced correspondingly, though note that
127 // the quota is returned by releaseMemory() when the loop has been
128 // processed, so that MaxSize will return to its previous
129 // value. So in most cases MaxSize will equal the Threshold flag
130 // when a new loop is processed. An exception to that is that
131 // MaxSize will have a smaller value while processing nested loops
132 // that were introduced due to loop unswitching of an outer loop.
134 // FIXME: The way that MaxSize works is subtle and depends on the
135 // pass manager processing loops and calling releaseMemory() in a
136 // specific order. It would be good to find a more straightforward
137 // way of doing what MaxSize does.
141 LUAnalysisCache() : MaxSize(Threshold) {}
143 // Analyze loop. Check its size, calculate is it possible to unswitch
144 // it. Returns true if we can unswitch this loop.
145 bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
146 AssumptionCache *AC);
148 // Clean all data related to given loop.
149 void forgetLoop(const Loop *L);
151 // Mark case value as unswitched.
152 // Since SI instruction can be partly unswitched, in order to avoid
153 // extra unswitching in cloned loops keep track all unswitched values.
154 void setUnswitched(const SwitchInst *SI, const Value *V);
156 // Check was this case value unswitched before or not.
157 bool isUnswitched(const SwitchInst *SI, const Value *V);
159 // Returns true if another unswitching could be done within the cost
161 bool costAllowsUnswitching();
163 // Clone all loop-unswitch related loop properties.
164 // Redistribute unswitching quotas.
165 // Note, that new loop data is stored inside the VMap.
166 void cloneData(const Loop *NewLoop, const Loop *OldLoop,
167 const ValueToValueMapTy &VMap);
170 class LoopUnswitch : public LoopPass {
171 LoopInfo *LI; // Loop information
175 // Used to check if second loop needs processing after
176 // rewriteLoopBodyWithConditionConstant rewrites first loop.
177 std::vector<Loop*> LoopProcessWorklist;
179 LUAnalysisCache BranchesInfo;
181 bool OptimizeForSize;
182 bool RedoLoop = false;
184 Loop *CurrentLoop = nullptr;
185 DominatorTree *DT = nullptr;
186 MemorySSA *MSSA = nullptr;
187 std::unique_ptr<MemorySSAUpdater> MSSAU;
188 BasicBlock *LoopHeader = nullptr;
189 BasicBlock *LoopPreheader = nullptr;
192 SimpleLoopSafetyInfo SafetyInfo;
194 // LoopBlocks contains all of the basic blocks of the loop, including the
195 // preheader of the loop, the body of the loop, and the exit blocks of the
196 // loop, in that order.
197 std::vector<BasicBlock*> LoopBlocks;
198 // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
199 std::vector<BasicBlock*> NewBlocks;
201 bool HasBranchDivergence;
204 static char ID; // Pass ID, replacement for typeid
206 explicit LoopUnswitch(bool Os = false, bool HasBranchDivergence = false)
207 : LoopPass(ID), OptimizeForSize(Os),
208 HasBranchDivergence(HasBranchDivergence) {
209 initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
212 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
213 bool processCurrentLoop();
214 bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
216 /// This transformation requires natural loop information & requires that
217 /// loop preheaders be inserted into the CFG.
219 void getAnalysisUsage(AnalysisUsage &AU) const override {
220 AU.addRequired<AssumptionCacheTracker>();
221 AU.addRequired<TargetTransformInfoWrapperPass>();
222 if (EnableMSSALoopDependency) {
223 AU.addRequired<MemorySSAWrapperPass>();
224 AU.addPreserved<MemorySSAWrapperPass>();
226 if (HasBranchDivergence)
227 AU.addRequired<LegacyDivergenceAnalysis>();
228 getLoopAnalysisUsage(AU);
232 void releaseMemory() override { BranchesInfo.forgetLoop(CurrentLoop); }
234 void initLoopData() {
235 LoopHeader = CurrentLoop->getHeader();
236 LoopPreheader = CurrentLoop->getLoopPreheader();
239 /// Split all of the edges from inside the loop to their exit blocks.
240 /// Update the appropriate Phi nodes as we do so.
241 void splitExitEdges(Loop *L,
242 const SmallVectorImpl<BasicBlock *> &ExitBlocks);
244 bool tryTrivialLoopUnswitch(bool &Changed);
246 bool unswitchIfProfitable(Value *LoopCond, Constant *Val,
247 Instruction *TI = nullptr);
248 void unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
249 BasicBlock *ExitBlock, Instruction *TI);
250 void unswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
253 void rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
254 Constant *Val, bool IsEqual);
256 void emitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
257 BasicBlock *TrueDest,
258 BasicBlock *FalseDest,
259 BranchInst *OldBranch, Instruction *TI);
261 void simplifyCode(std::vector<Instruction *> &Worklist, Loop *L);
263 /// Given that the Invariant is not equal to Val. Simplify instructions
265 Value *simplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant,
269 } // end anonymous namespace
271 // Analyze loop. Check its size, calculate is it possible to unswitch
272 // it. Returns true if we can unswitch this loop.
273 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
274 AssumptionCache *AC) {
275 LoopPropsMapIt PropsIt;
277 std::tie(PropsIt, Inserted) =
278 LoopsProperties.insert(std::make_pair(L, LoopProperties()));
280 LoopProperties &Props = PropsIt->second;
285 // Limit the number of instructions to avoid causing significant code
286 // expansion, and the number of basic blocks, to avoid loops with
287 // large numbers of branches which cause loop unswitching to go crazy.
288 // This is a very ad-hoc heuristic.
290 SmallPtrSet<const Value *, 32> EphValues;
291 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
293 // FIXME: This is overly conservative because it does not take into
294 // consideration code simplification opportunities and code that can
295 // be shared by the resultant unswitched loops.
297 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
299 Metrics.analyzeBasicBlock(*I, TTI, EphValues);
301 Props.SizeEstimation = Metrics.NumInsts;
302 Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
303 Props.WasUnswitchedCount = 0;
304 MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
306 if (Metrics.notDuplicatable) {
307 LLVM_DEBUG(dbgs() << "NOT unswitching loop %" << L->getHeader()->getName()
308 << ", contents cannot be "
314 // Be careful. This links are good only before new loop addition.
315 CurrentLoopProperties = &Props;
316 CurLoopInstructions = &Props.UnswitchedVals;
321 // Clean all data related to given loop.
322 void LUAnalysisCache::forgetLoop(const Loop *L) {
323 LoopPropsMapIt LIt = LoopsProperties.find(L);
325 if (LIt != LoopsProperties.end()) {
326 LoopProperties &Props = LIt->second;
327 MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
328 Props.SizeEstimation;
329 LoopsProperties.erase(LIt);
332 CurrentLoopProperties = nullptr;
333 CurLoopInstructions = nullptr;
336 // Mark case value as unswitched.
337 // Since SI instruction can be partly unswitched, in order to avoid
338 // extra unswitching in cloned loops keep track all unswitched values.
339 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
340 (*CurLoopInstructions)[SI].insert(V);
343 // Check was this case value unswitched before or not.
344 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
345 return (*CurLoopInstructions)[SI].count(V);
348 bool LUAnalysisCache::costAllowsUnswitching() {
349 return CurrentLoopProperties->CanBeUnswitchedCount > 0;
352 // Clone all loop-unswitch related loop properties.
353 // Redistribute unswitching quotas.
354 // Note, that new loop data is stored inside the VMap.
355 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
356 const ValueToValueMapTy &VMap) {
357 LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
358 LoopProperties &OldLoopProps = *CurrentLoopProperties;
359 UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
361 // Reallocate "can-be-unswitched quota"
363 --OldLoopProps.CanBeUnswitchedCount;
364 ++OldLoopProps.WasUnswitchedCount;
365 NewLoopProps.WasUnswitchedCount = 0;
366 unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
367 NewLoopProps.CanBeUnswitchedCount = Quota / 2;
368 OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
370 NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
372 // Clone unswitched values info:
373 // for new loop switches we clone info about values that was
374 // already unswitched and has redundant successors.
375 for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
376 const SwitchInst *OldInst = I->first;
377 Value *NewI = VMap.lookup(OldInst);
378 const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
379 assert(NewInst && "All instructions that are in SrcBB must be in VMap.");
381 NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
385 char LoopUnswitch::ID = 0;
387 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
389 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
390 INITIALIZE_PASS_DEPENDENCY(LoopPass)
391 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
392 INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
393 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
394 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
397 Pass *llvm::createLoopUnswitchPass(bool Os, bool HasBranchDivergence) {
398 return new LoopUnswitch(Os, HasBranchDivergence);
401 /// Operator chain lattice.
403 OC_OpChainNone, ///< There is no operator.
404 OC_OpChainOr, ///< There are only ORs.
405 OC_OpChainAnd, ///< There are only ANDs.
406 OC_OpChainMixed ///< There are ANDs and ORs.
409 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
410 /// an invariant piece, return the invariant. Otherwise, return null.
412 /// NOTE: findLIVLoopCondition will not return a partial LIV by walking up a
413 /// mixed operator chain, as we can not reliably find a value which will
414 /// simplify the operator chain. If the chain is AND-only or OR-only, we can use
415 /// 0 or ~0 to simplify the chain.
417 /// NOTE: In case a partial LIV and a mixed operator chain, we may be able to
418 /// simplify the condition itself to a loop variant condition, but at the
419 /// cost of creating an entirely new loop.
420 static Value *findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
421 OperatorChain &ParentChain,
422 DenseMap<Value *, Value *> &Cache,
423 MemorySSAUpdater *MSSAU) {
424 auto CacheIt = Cache.find(Cond);
425 if (CacheIt != Cache.end())
426 return CacheIt->second;
428 // We started analyze new instruction, increment scanned instructions counter.
431 // We can never unswitch on vector conditions.
432 if (Cond->getType()->isVectorTy())
435 // Constants should be folded, not unswitched on!
436 if (isa<Constant>(Cond)) return nullptr;
438 // TODO: Handle: br (VARIANT|INVARIANT).
440 // Hoist simple values out.
441 if (L->makeLoopInvariant(Cond, Changed, nullptr, MSSAU)) {
446 // Walk up the operator chain to find partial invariant conditions.
447 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
448 if (BO->getOpcode() == Instruction::And ||
449 BO->getOpcode() == Instruction::Or) {
450 // Given the previous operator, compute the current operator chain status.
451 OperatorChain NewChain;
452 switch (ParentChain) {
454 NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
458 NewChain = BO->getOpcode() == Instruction::Or ? OC_OpChainOr :
462 NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
465 case OC_OpChainMixed:
466 NewChain = OC_OpChainMixed;
470 // If we reach a Mixed state, we do not want to keep walking up as we can not
471 // reliably find a value that will simplify the chain. With this check, we
472 // will return null on the first sight of mixed chain and the caller will
473 // either backtrack to find partial LIV in other operand or return null.
474 if (NewChain != OC_OpChainMixed) {
475 // Update the current operator chain type before we search up the chain.
476 ParentChain = NewChain;
477 // If either the left or right side is invariant, we can unswitch on this,
478 // which will cause the branch to go away in one loop and the condition to
479 // simplify in the other one.
480 if (Value *LHS = findLIVLoopCondition(BO->getOperand(0), L, Changed,
481 ParentChain, Cache, MSSAU)) {
485 // We did not manage to find a partial LIV in operand(0). Backtrack and try
487 ParentChain = NewChain;
488 if (Value *RHS = findLIVLoopCondition(BO->getOperand(1), L, Changed,
489 ParentChain, Cache, MSSAU)) {
496 Cache[Cond] = nullptr;
500 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
501 /// an invariant piece, return the invariant along with the operator chain type.
502 /// Otherwise, return null.
503 static std::pair<Value *, OperatorChain>
504 findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
505 MemorySSAUpdater *MSSAU) {
506 DenseMap<Value *, Value *> Cache;
507 OperatorChain OpChain = OC_OpChainNone;
508 Value *FCond = findLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU);
510 // In case we do find a LIV, it can not be obtained by walking up a mixed
512 assert((!FCond || OpChain != OC_OpChainMixed) &&
513 "Do not expect a partial LIV with mixed operator chain");
514 return {FCond, OpChain};
517 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPMRef) {
521 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
522 *L->getHeader()->getParent());
523 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
525 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
526 if (EnableMSSALoopDependency) {
527 MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
528 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
529 assert(DT && "Cannot update MemorySSA without a valid DomTree.");
532 Function *F = CurrentLoop->getHeader()->getParent();
534 SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
536 SafetyInfo.computeLoopSafetyInfo(L);
538 if (MSSA && VerifyMemorySSA)
539 MSSA->verifyMemorySSA();
541 bool Changed = false;
543 assert(CurrentLoop->isLCSSAForm(*DT));
544 if (MSSA && VerifyMemorySSA)
545 MSSA->verifyMemorySSA();
547 Changed |= processCurrentLoop();
550 if (MSSA && VerifyMemorySSA)
551 MSSA->verifyMemorySSA();
556 // Return true if the BasicBlock BB is unreachable from the loop header.
557 // Return false, otherwise.
558 bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
559 auto *Node = DT->getNode(BB)->getIDom();
560 BasicBlock *DomBB = Node->getBlock();
561 while (CurrentLoop->contains(DomBB)) {
562 BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator());
564 Node = DT->getNode(DomBB)->getIDom();
565 DomBB = Node->getBlock();
567 if (!BInst || !BInst->isConditional())
570 Value *Cond = BInst->getCondition();
571 if (!isa<ConstantInt>(Cond))
574 BasicBlock *UnreachableSucc =
575 Cond == ConstantInt::getTrue(Cond->getContext())
576 ? BInst->getSuccessor(1)
577 : BInst->getSuccessor(0);
579 if (DT->dominates(UnreachableSucc, BB))
585 /// FIXME: Remove this workaround when freeze related patches are done.
586 /// LoopUnswitch and Equality propagation in GVN have discrepancy about
587 /// whether branch on undef/poison has undefine behavior. Here it is to
588 /// rule out some common cases that we found such discrepancy already
589 /// causing problems. Detail could be found in PR31652. Note if the
590 /// func returns true, it is unsafe. But if it is false, it doesn't mean
591 /// it is necessarily safe.
592 static bool equalityPropUnSafe(Value &LoopCond) {
593 ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond);
594 if (!CI || !CI->isEquality())
597 Value *LHS = CI->getOperand(0);
598 Value *RHS = CI->getOperand(1);
599 if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
602 auto HasUndefInPHI = [](PHINode &PN) {
603 for (Value *Opd : PN.incoming_values()) {
604 if (isa<UndefValue>(Opd))
609 PHINode *LPHI = dyn_cast<PHINode>(LHS);
610 PHINode *RPHI = dyn_cast<PHINode>(RHS);
611 if ((LPHI && HasUndefInPHI(*LPHI)) || (RPHI && HasUndefInPHI(*RPHI)))
614 auto HasUndefInSelect = [](SelectInst &SI) {
615 if (isa<UndefValue>(SI.getTrueValue()) ||
616 isa<UndefValue>(SI.getFalseValue()))
620 SelectInst *LSI = dyn_cast<SelectInst>(LHS);
621 SelectInst *RSI = dyn_cast<SelectInst>(RHS);
622 if ((LSI && HasUndefInSelect(*LSI)) || (RSI && HasUndefInSelect(*RSI)))
627 /// Do actual work and unswitch loop if possible and profitable.
628 bool LoopUnswitch::processCurrentLoop() {
629 bool Changed = false;
633 // If LoopSimplify was unable to form a preheader, don't do any unswitching.
637 // Loops with indirectbr cannot be cloned.
638 if (!CurrentLoop->isSafeToClone())
641 // Without dedicated exits, splitting the exit edge may fail.
642 if (!CurrentLoop->hasDedicatedExits())
645 LLVMContext &Context = LoopHeader->getContext();
647 // Analyze loop cost, and stop unswitching if loop content can not be duplicated.
648 if (!BranchesInfo.countLoop(
650 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
651 *CurrentLoop->getHeader()->getParent()),
655 // Try trivial unswitch first before loop over other basic blocks in the loop.
656 if (tryTrivialLoopUnswitch(Changed)) {
660 // Do not do non-trivial unswitch while optimizing for size.
661 // FIXME: Use Function::hasOptSize().
662 if (OptimizeForSize ||
663 LoopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
666 // Run through the instructions in the loop, keeping track of three things:
668 // - That we do not unswitch loops containing convergent operations, as we
669 // might be making them control dependent on the unswitch value when they
671 // FIXME: This could be refined to only bail if the convergent operation is
672 // not already control-dependent on the unswitch value.
674 // - That basic blocks in the loop contain invokes whose predecessor edges we
677 // - The set of guard intrinsics encountered (these are non terminator
678 // instructions that are also profitable to be unswitched).
680 SmallVector<IntrinsicInst *, 4> Guards;
682 for (const auto BB : CurrentLoop->blocks()) {
683 for (auto &I : *BB) {
684 auto *CB = dyn_cast<CallBase>(&I);
687 if (CB->isConvergent())
689 if (auto *II = dyn_cast<InvokeInst>(&I))
690 if (!II->getUnwindDest()->canSplitPredecessors())
692 if (auto *II = dyn_cast<IntrinsicInst>(&I))
693 if (II->getIntrinsicID() == Intrinsic::experimental_guard)
694 Guards.push_back(II);
698 for (IntrinsicInst *Guard : Guards) {
699 Value *LoopCond = findLIVLoopCondition(Guard->getOperand(0), CurrentLoop,
700 Changed, MSSAU.get())
703 unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
704 // NB! Unswitching (if successful) could have erased some of the
705 // instructions in Guards leaving dangling pointers there. This is fine
706 // because we're returning now, and won't look at Guards again.
712 // Loop over all of the basic blocks in the loop. If we find an interior
713 // block that is branching on a loop-invariant condition, we can unswitch this
715 for (Loop::block_iterator I = CurrentLoop->block_begin(),
716 E = CurrentLoop->block_end();
718 Instruction *TI = (*I)->getTerminator();
720 // Unswitching on a potentially uninitialized predicate is not
721 // MSan-friendly. Limit this to the cases when the original predicate is
722 // guaranteed to execute, to avoid creating a use-of-uninitialized-value
723 // in the code that did not have one.
724 // This is a workaround for the discrepancy between LLVM IR and MSan
725 // semantics. See PR28054 for more details.
726 if (SanitizeMemory &&
727 !SafetyInfo.isGuaranteedToExecute(*TI, DT, CurrentLoop))
730 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
731 // Some branches may be rendered unreachable because of previous
733 // Unswitch only those branches that are reachable.
734 if (isUnreachableDueToPreviousUnswitching(*I))
737 // If this isn't branching on an invariant condition, we can't unswitch
739 if (BI->isConditional()) {
740 // See if this, or some part of it, is loop invariant. If so, we can
741 // unswitch on it if we desire.
742 Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop,
743 Changed, MSSAU.get())
745 if (LoopCond && !equalityPropUnSafe(*LoopCond) &&
746 unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
751 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
752 Value *SC = SI->getCondition();
754 OperatorChain OpChain;
755 std::tie(LoopCond, OpChain) =
756 findLIVLoopCondition(SC, CurrentLoop, Changed, MSSAU.get());
758 unsigned NumCases = SI->getNumCases();
759 if (LoopCond && NumCases) {
760 // Find a value to unswitch on:
761 // FIXME: this should chose the most expensive case!
762 // FIXME: scan for a case with a non-critical edge?
763 Constant *UnswitchVal = nullptr;
764 // Find a case value such that at least one case value is unswitched
766 if (OpChain == OC_OpChainAnd) {
767 // If the chain only has ANDs and the switch has a case value of 0.
768 // Dropping in a 0 to the chain will unswitch out the 0-casevalue.
769 auto *AllZero = cast<ConstantInt>(Constant::getNullValue(SC->getType()));
770 if (BranchesInfo.isUnswitched(SI, AllZero))
772 // We are unswitching 0 out.
773 UnswitchVal = AllZero;
774 } else if (OpChain == OC_OpChainOr) {
775 // If the chain only has ORs and the switch has a case value of ~0.
776 // Dropping in a ~0 to the chain will unswitch out the ~0-casevalue.
777 auto *AllOne = cast<ConstantInt>(Constant::getAllOnesValue(SC->getType()));
778 if (BranchesInfo.isUnswitched(SI, AllOne))
780 // We are unswitching ~0 out.
781 UnswitchVal = AllOne;
783 assert(OpChain == OC_OpChainNone &&
784 "Expect to unswitch on trivial chain");
785 // Do not process same value again and again.
786 // At this point we have some cases already unswitched and
787 // some not yet unswitched. Let's find the first not yet unswitched one.
788 for (auto Case : SI->cases()) {
789 Constant *UnswitchValCandidate = Case.getCaseValue();
790 if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
791 UnswitchVal = UnswitchValCandidate;
800 if (unswitchIfProfitable(LoopCond, UnswitchVal)) {
802 // In case of a full LIV, UnswitchVal is the value we unswitched out.
803 // In case of a partial LIV, we only unswitch when its an AND-chain
804 // or OR-chain. In both cases switch input value simplifies to
806 BranchesInfo.setUnswitched(SI, UnswitchVal);
812 // Scan the instructions to check for unswitchable values.
813 for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
815 if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
816 Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop,
817 Changed, MSSAU.get())
820 unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
829 /// Check to see if all paths from BB exit the loop with no side effects
830 /// (including infinite loops).
832 /// If true, we return true and set ExitBB to the block we
835 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
837 std::set<BasicBlock*> &Visited) {
838 if (!Visited.insert(BB).second) {
839 // Already visited. Without more analysis, this could indicate an infinite
843 if (!L->contains(BB)) {
844 // Otherwise, this is a loop exit, this is fine so long as this is the
846 if (ExitBB) return false;
851 // Otherwise, this is an unvisited intra-loop node. Check all successors.
852 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
853 // Check to see if the successor is a trivial loop exit.
854 if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
858 // Okay, everything after this looks good, check to make sure that this block
859 // doesn't include any side effects.
860 for (Instruction &I : *BB)
861 if (I.mayHaveSideEffects())
867 /// Return true if the specified block unconditionally leads to an exit from
868 /// the specified loop, and has no side-effects in the process. If so, return
869 /// the block that is exited to, otherwise return null.
870 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
871 std::set<BasicBlock*> Visited;
872 Visited.insert(L->getHeader()); // Branches to header make infinite loops.
873 BasicBlock *ExitBB = nullptr;
874 if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
879 /// We have found that we can unswitch CurrentLoop when LoopCond == Val to
880 /// simplify the loop. If we decide that this is profitable,
881 /// unswitch the loop, reprocess the pieces, then return true.
882 bool LoopUnswitch::unswitchIfProfitable(Value *LoopCond, Constant *Val,
884 // Check to see if it would be profitable to unswitch current loop.
885 if (!BranchesInfo.costAllowsUnswitching()) {
886 LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
887 << CurrentLoop->getHeader()->getName()
888 << " at non-trivial condition '" << *Val
889 << "' == " << *LoopCond << "\n"
890 << ". Cost too high.\n");
893 if (HasBranchDivergence &&
894 getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
895 LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
896 << CurrentLoop->getHeader()->getName()
897 << " at non-trivial condition '" << *Val
898 << "' == " << *LoopCond << "\n"
899 << ". Condition is divergent.\n");
903 unswitchNontrivialCondition(LoopCond, Val, CurrentLoop, TI);
907 /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst,
908 /// otherwise branch to FalseDest. Insert the code immediately before OldBranch
909 /// and remove (but not erase!) it from the function.
910 void LoopUnswitch::emitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
911 BasicBlock *TrueDest,
912 BasicBlock *FalseDest,
913 BranchInst *OldBranch,
915 assert(OldBranch->isUnconditional() && "Preheader is not split correctly");
916 assert(TrueDest != FalseDest && "Branch targets should be different");
917 // Insert a conditional branch on LIC to the two preheaders. The original
918 // code is the true version and the new code is the false version.
919 Value *BranchVal = LIC;
920 bool Swapped = false;
921 if (!isa<ConstantInt>(Val) ||
922 Val->getType() != Type::getInt1Ty(LIC->getContext()))
923 BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val);
924 else if (Val != ConstantInt::getTrue(Val->getContext())) {
925 // We want to enter the new loop when the condition is true.
926 std::swap(TrueDest, FalseDest);
930 // Old branch will be removed, so save its parent and successor to update the
932 auto *OldBranchSucc = OldBranch->getSuccessor(0);
933 auto *OldBranchParent = OldBranch->getParent();
935 // Insert the new branch.
937 IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI);
939 BI->swapProfMetadata();
941 // Remove the old branch so there is only one branch at the end. This is
942 // needed to perform DomTree's internal DFS walk on the function's CFG.
943 OldBranch->removeFromParent();
945 // Inform the DT about the new branch.
947 // First, add both successors.
948 SmallVector<DominatorTree::UpdateType, 3> Updates;
949 if (TrueDest != OldBranchSucc)
950 Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
951 if (FalseDest != OldBranchSucc)
952 Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
953 // If both of the new successors are different from the old one, inform the
954 // DT that the edge was deleted.
955 if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
956 Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
958 DT->applyUpdates(Updates);
961 MSSAU->applyUpdates(Updates, *DT);
964 // If either edge is critical, split it. This helps preserve LoopSimplify
965 // form for enclosing loops.
967 CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
968 SplitCriticalEdge(BI, 0, Options);
969 SplitCriticalEdge(BI, 1, Options);
972 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
973 /// from its header block to its latch block, where the path through the loop
974 /// that doesn't execute its body has no side-effects), unswitch it. This
975 /// doesn't involve any code duplication, just moving the conditional branch
976 /// outside of the loop and updating loop info.
977 void LoopUnswitch::unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
978 BasicBlock *ExitBlock,
980 LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
981 << LoopHeader->getName() << " [" << L->getBlocks().size()
982 << " blocks] in Function "
983 << L->getHeader()->getParent()->getName()
984 << " on cond: " << *Val << " == " << *Cond << "\n");
985 // We are going to make essential changes to CFG. This may invalidate cached
986 // information for L or one of its parent loops in SCEV.
987 if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
988 SEWP->getSE().forgetTopmostLoop(L);
990 // First step, split the preheader, so that we know that there is a safe place
991 // to insert the conditional branch. We will change LoopPreheader to have a
992 // conditional branch on Cond.
993 BasicBlock *NewPH = SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get());
995 // Now that we have a place to insert the conditional branch, create a place
996 // to branch to: this is the exit block out of the loop that we should
999 // Split this block now, so that the loop maintains its exit block, and so
1000 // that the jump from the preheader can execute the contents of the exit block
1001 // without actually branching to it (the exit block should be dominated by the
1002 // loop header, not the preheader).
1003 assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
1004 BasicBlock *NewExit =
1005 SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get());
1007 // Okay, now we have a position to branch from and a position to branch to,
1008 // insert the new conditional branch.
1009 auto *OldBranch = dyn_cast<BranchInst>(LoopPreheader->getTerminator());
1010 assert(OldBranch && "Failed to split the preheader");
1011 emitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);
1013 // emitPreheaderBranchOnCondition removed the OldBranch from the function.
1014 // Delete it, as it is no longer needed.
1017 // We need to reprocess this loop, it could be unswitched again.
1020 // Now that we know that the loop is never entered when this condition is a
1021 // particular value, rewrite the loop with this info. We know that this will
1022 // at least eliminate the old branch.
1023 rewriteLoopBodyWithConditionConstant(L, Cond, Val, /*IsEqual=*/false);
1028 /// Check if the first non-constant condition starting from the loop header is
1029 /// a trivial unswitch condition: that is, a condition controls whether or not
1030 /// the loop does anything at all. If it is a trivial condition, unswitching
1031 /// produces no code duplications (equivalently, it produces a simpler loop and
1032 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
1034 bool LoopUnswitch::tryTrivialLoopUnswitch(bool &Changed) {
1035 BasicBlock *CurrentBB = CurrentLoop->getHeader();
1036 Instruction *CurrentTerm = CurrentBB->getTerminator();
1037 LLVMContext &Context = CurrentBB->getContext();
1039 // If loop header has only one reachable successor (currently via an
1040 // unconditional branch or constant foldable conditional branch, but
1041 // should also consider adding constant foldable switch instruction in
1042 // future), we should keep looking for trivial condition candidates in
1043 // the successor as well. An alternative is to constant fold conditions
1044 // and merge successors into loop header (then we only need to check header's
1045 // terminator). The reason for not doing this in LoopUnswitch pass is that
1046 // it could potentially break LoopPassManager's invariants. Folding dead
1047 // branches could either eliminate the current loop or make other loops
1048 // unreachable. LCSSA form might also not be preserved after deleting
1049 // branches. The following code keeps traversing loop header's successors
1050 // until it finds the trivial condition candidate (condition that is not a
1051 // constant). Since unswitching generates branches with constant conditions,
1052 // this scenario could be very common in practice.
1053 SmallPtrSet<BasicBlock*, 8> Visited;
1056 // If we exit loop or reach a previous visited block, then
1057 // we can not reach any trivial condition candidates (unfoldable
1058 // branch instructions or switch instructions) and no unswitch
1059 // can happen. Exit and return false.
1060 if (!CurrentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
1063 // Check if this loop will execute any side-effecting instructions (e.g.
1064 // stores, calls, volatile loads) in the part of the loop that the code
1065 // *would* execute. Check the header first.
1066 for (Instruction &I : *CurrentBB)
1067 if (I.mayHaveSideEffects())
1070 if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1071 if (BI->isUnconditional()) {
1072 CurrentBB = BI->getSuccessor(0);
1073 } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
1074 CurrentBB = BI->getSuccessor(0);
1075 } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
1076 CurrentBB = BI->getSuccessor(1);
1078 // Found a trivial condition candidate: non-foldable conditional branch.
1081 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1082 // At this point, any constant-foldable instructions should have probably
1084 ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
1087 // Find the target block we are definitely going to.
1088 CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
1090 // We do not understand these terminator instructions.
1094 CurrentTerm = CurrentBB->getTerminator();
1097 // CondVal is the condition that controls the trivial condition.
1098 // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
1099 Constant *CondVal = nullptr;
1100 BasicBlock *LoopExitBB = nullptr;
1102 if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1103 // If this isn't branching on an invariant condition, we can't unswitch it.
1104 if (!BI->isConditional())
1107 Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop,
1108 Changed, MSSAU.get())
1111 // Unswitch only if the trivial condition itself is an LIV (not
1112 // partial LIV which could occur in and/or)
1113 if (!LoopCond || LoopCond != BI->getCondition())
1116 // Check to see if a successor of the branch is guaranteed to
1117 // exit through a unique exit block without having any
1118 // side-effects. If so, determine the value of Cond that causes
1121 isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(0)))) {
1122 CondVal = ConstantInt::getTrue(Context);
1123 } else if ((LoopExitBB =
1124 isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(1)))) {
1125 CondVal = ConstantInt::getFalse(Context);
1128 // If we didn't find a single unique LoopExit block, or if the loop exit
1129 // block contains phi nodes, this isn't trivial.
1130 if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1131 return false; // Can't handle this.
1133 if (equalityPropUnSafe(*LoopCond))
1136 unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
1140 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1141 // If this isn't switching on an invariant condition, we can't unswitch it.
1142 Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop,
1143 Changed, MSSAU.get())
1146 // Unswitch only if the trivial condition itself is an LIV (not
1147 // partial LIV which could occur in and/or)
1148 if (!LoopCond || LoopCond != SI->getCondition())
1151 // Check to see if a successor of the switch is guaranteed to go to the
1152 // latch block or exit through a one exit block without having any
1153 // side-effects. If so, determine the value of Cond that causes it to do
1155 // Note that we can't trivially unswitch on the default case or
1156 // on already unswitched cases.
1157 for (auto Case : SI->cases()) {
1158 BasicBlock *LoopExitCandidate;
1159 if ((LoopExitCandidate =
1160 isTrivialLoopExitBlock(CurrentLoop, Case.getCaseSuccessor()))) {
1161 // Okay, we found a trivial case, remember the value that is trivial.
1162 ConstantInt *CaseVal = Case.getCaseValue();
1164 // Check that it was not unswitched before, since already unswitched
1165 // trivial vals are looks trivial too.
1166 if (BranchesInfo.isUnswitched(SI, CaseVal))
1168 LoopExitBB = LoopExitCandidate;
1174 // If we didn't find a single unique LoopExit block, or if the loop exit
1175 // block contains phi nodes, this isn't trivial.
1176 if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1177 return false; // Can't handle this.
1179 unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
1182 // We are only unswitching full LIV.
1183 BranchesInfo.setUnswitched(SI, CondVal);
1190 /// Split all of the edges from inside the loop to their exit blocks.
1191 /// Update the appropriate Phi nodes as we do so.
1192 void LoopUnswitch::splitExitEdges(
1193 Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
1195 for (unsigned I = 0, E = ExitBlocks.size(); I != E; ++I) {
1196 BasicBlock *ExitBlock = ExitBlocks[I];
1197 SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
1198 pred_end(ExitBlock));
1200 // Although SplitBlockPredecessors doesn't preserve loop-simplify in
1201 // general, if we call it on all predecessors of all exits then it does.
1202 SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(),
1203 /*PreserveLCSSA*/ true);
1207 /// We determined that the loop is profitable to unswitch when LIC equal Val.
1208 /// Split it into loop versions and test the condition outside of either loop.
1209 /// Return the loops created as Out1/Out2.
1210 void LoopUnswitch::unswitchNontrivialCondition(Value *LIC, Constant *Val,
1211 Loop *L, Instruction *TI) {
1212 Function *F = LoopHeader->getParent();
1213 LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
1214 << LoopHeader->getName() << " [" << L->getBlocks().size()
1215 << " blocks] in Function " << F->getName() << " when '"
1216 << *Val << "' == " << *LIC << "\n");
1218 // We are going to make essential changes to CFG. This may invalidate cached
1219 // information for L or one of its parent loops in SCEV.
1220 if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1221 SEWP->getSE().forgetTopmostLoop(L);
1226 if (MSSAU && VerifyMemorySSA)
1227 MSSA->verifyMemorySSA();
1229 // First step, split the preheader and exit blocks, and add these blocks to
1230 // the LoopBlocks list.
1231 BasicBlock *NewPreheader =
1232 SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get());
1233 LoopBlocks.push_back(NewPreheader);
1235 // We want the loop to come after the preheader, but before the exit blocks.
1236 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
1238 SmallVector<BasicBlock*, 8> ExitBlocks;
1239 L->getUniqueExitBlocks(ExitBlocks);
1241 // Split all of the edges from inside the loop to their exit blocks. Update
1242 // the appropriate Phi nodes as we do so.
1243 splitExitEdges(L, ExitBlocks);
1245 // The exit blocks may have been changed due to edge splitting, recompute.
1247 L->getUniqueExitBlocks(ExitBlocks);
1249 // Add exit blocks to the loop blocks.
1250 LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
1252 // Next step, clone all of the basic blocks that make up the loop (including
1253 // the loop preheader and exit blocks), keeping track of the mapping between
1254 // the instructions and blocks.
1255 NewBlocks.reserve(LoopBlocks.size());
1256 ValueToValueMapTy VMap;
1257 for (unsigned I = 0, E = LoopBlocks.size(); I != E; ++I) {
1258 BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[I], VMap, ".us", F);
1260 NewBlocks.push_back(NewBB);
1261 VMap[LoopBlocks[I]] = NewBB; // Keep the BB mapping.
1264 // Splice the newly inserted blocks into the function right before the
1265 // original preheader.
1266 F->getBasicBlockList().splice(NewPreheader->getIterator(),
1267 F->getBasicBlockList(),
1268 NewBlocks[0]->getIterator(), F->end());
1270 // Now we create the new Loop object for the versioned loop.
1271 Loop *NewLoop = cloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1273 // Recalculate unswitching quota, inherit simplified switches info for NewBB,
1274 // Probably clone more loop-unswitch related loop properties.
1275 BranchesInfo.cloneData(NewLoop, L, VMap);
1277 Loop *ParentLoop = L->getParentLoop();
1279 // Make sure to add the cloned preheader and exit blocks to the parent loop
1281 ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
1284 for (unsigned EBI = 0, EBE = ExitBlocks.size(); EBI != EBE; ++EBI) {
1285 BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[EBI]]);
1286 // The new exit block should be in the same loop as the old one.
1287 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[EBI]))
1288 ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1290 assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
1291 "Exit block should have been split to have one successor!");
1292 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
1294 // If the successor of the exit block had PHI nodes, add an entry for
1296 for (PHINode &PN : ExitSucc->phis()) {
1297 Value *V = PN.getIncomingValueForBlock(ExitBlocks[EBI]);
1298 ValueToValueMapTy::iterator It = VMap.find(V);
1299 if (It != VMap.end()) V = It->second;
1300 PN.addIncoming(V, NewExit);
1303 if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
1304 PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
1305 &*ExitSucc->getFirstInsertionPt());
1307 for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
1309 BasicBlock *BB = *I;
1310 LandingPadInst *LPI = BB->getLandingPadInst();
1311 LPI->replaceAllUsesWith(PN);
1312 PN->addIncoming(LPI, BB);
1317 // Rewrite the code to refer to itself.
1318 for (unsigned NBI = 0, NBE = NewBlocks.size(); NBI != NBE; ++NBI) {
1319 for (Instruction &I : *NewBlocks[NBI]) {
1320 RemapInstruction(&I, VMap,
1321 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1322 if (auto *II = dyn_cast<IntrinsicInst>(&I))
1323 if (II->getIntrinsicID() == Intrinsic::assume)
1324 AC->registerAssumption(II);
1328 // Rewrite the original preheader to select between versions of the loop.
1329 BranchInst *OldBR = cast<BranchInst>(LoopPreheader->getTerminator());
1330 assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
1331 "Preheader splitting did not work correctly!");
1334 // Update MemorySSA after cloning, and before splitting to unreachables,
1335 // since that invalidates the 1:1 mapping of clones in VMap.
1336 LoopBlocksRPO LBRPO(L);
1338 MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
1341 // Emit the new branch that selects between the two versions of this loop.
1342 emitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1345 // Update MemoryPhis in Exit blocks.
1346 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
1347 if (VerifyMemorySSA)
1348 MSSA->verifyMemorySSA();
1351 // The OldBr was replaced by a new one and removed (but not erased) by
1352 // emitPreheaderBranchOnCondition. It is no longer needed, so delete it.
1355 LoopProcessWorklist.push_back(NewLoop);
1358 // Keep a WeakTrackingVH holding onto LIC. If the first call to
1360 // deletes the instruction (for example by simplifying a PHI that feeds into
1361 // the condition that we're unswitching on), we don't rewrite the second
1363 WeakTrackingVH LICHandle(LIC);
1365 // Now we rewrite the original code to know that the condition is true and the
1366 // new code to know that the condition is false.
1367 rewriteLoopBodyWithConditionConstant(L, LIC, Val, /*IsEqual=*/false);
1369 // It's possible that simplifying one loop could cause the other to be
1370 // changed to another value or a constant. If its a constant, don't simplify
1372 if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1373 LICHandle && !isa<Constant>(LICHandle))
1374 rewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val,
1377 if (MSSA && VerifyMemorySSA)
1378 MSSA->verifyMemorySSA();
1381 /// Remove all instances of I from the worklist vector specified.
1382 static void removeFromWorklist(Instruction *I,
1383 std::vector<Instruction *> &Worklist) {
1385 Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
1389 /// When we find that I really equals V, remove I from the
1390 /// program, replacing all uses with V and update the worklist.
1391 static void replaceUsesOfWith(Instruction *I, Value *V,
1392 std::vector<Instruction *> &Worklist, Loop *L,
1393 LPPassManager *LPM, MemorySSAUpdater *MSSAU) {
1394 LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");
1396 // Add uses to the worklist, which may be dead now.
1397 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1398 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1399 Worklist.push_back(Use);
1401 // Add users to the worklist which may be simplified now.
1402 for (User *U : I->users())
1403 Worklist.push_back(cast<Instruction>(U));
1404 removeFromWorklist(I, Worklist);
1405 I->replaceAllUsesWith(V);
1406 if (!I->mayHaveSideEffects()) {
1408 MSSAU->removeMemoryAccess(I);
1409 I->eraseFromParent();
1414 /// We know either that the value LIC has the value specified by Val in the
1415 /// specified loop, or we know it does NOT have that value.
1416 /// Rewrite any uses of LIC or of properties correlated to it.
1417 void LoopUnswitch::rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1420 assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
1422 // FIXME: Support correlated properties, like:
1429 // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,
1430 // selects, switches.
1431 std::vector<Instruction*> Worklist;
1432 LLVMContext &Context = Val->getContext();
1434 // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
1435 // in the loop with the appropriate one directly.
1436 if (IsEqual || (isa<ConstantInt>(Val) &&
1437 Val->getType()->isIntegerTy(1))) {
1442 Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
1443 !cast<ConstantInt>(Val)->getZExtValue());
1445 for (User *U : LIC->users()) {
1446 Instruction *UI = dyn_cast<Instruction>(U);
1447 if (!UI || !L->contains(UI))
1449 Worklist.push_back(UI);
1452 for (Instruction *UI : Worklist)
1453 UI->replaceUsesOfWith(LIC, Replacement);
1455 simplifyCode(Worklist, L);
1459 // Otherwise, we don't know the precise value of LIC, but we do know that it
1460 // is certainly NOT "Val". As such, simplify any uses in the loop that we
1461 // can. This case occurs when we unswitch switch statements.
1462 for (User *U : LIC->users()) {
1463 Instruction *UI = dyn_cast<Instruction>(U);
1464 if (!UI || !L->contains(UI))
1467 // At this point, we know LIC is definitely not Val. Try to use some simple
1468 // logic to simplify the user w.r.t. to the context.
1469 if (Value *Replacement = simplifyInstructionWithNotEqual(UI, LIC, Val)) {
1470 if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
1471 // This in-loop instruction has been simplified w.r.t. its context,
1472 // i.e. LIC != Val, make sure we propagate its replacement value to
1475 // We can not yet delete UI, the LIC user, yet, because that would invalidate
1476 // the LIC->users() iterator !. However, we can make this instruction
1477 // dead by replacing all its users and push it onto the worklist so that
1478 // it can be properly deleted and its operands simplified.
1479 UI->replaceAllUsesWith(Replacement);
1483 // This is a LIC user, push it into the worklist so that simplifyCode can
1484 // attempt to simplify it.
1485 Worklist.push_back(UI);
1487 // If we know that LIC is not Val, use this info to simplify code.
1488 SwitchInst *SI = dyn_cast<SwitchInst>(UI);
1489 if (!SI || !isa<ConstantInt>(Val)) continue;
1491 // NOTE: if a case value for the switch is unswitched out, we record it
1492 // after the unswitch finishes. We can not record it here as the switch
1493 // is not a direct user of the partial LIV.
1494 SwitchInst::CaseHandle DeadCase =
1495 *SI->findCaseValue(cast<ConstantInt>(Val));
1496 // Default case is live for multiple values.
1497 if (DeadCase == *SI->case_default())
1500 // Found a dead case value. Don't remove PHI nodes in the
1501 // successor if they become single-entry, those PHI nodes may
1502 // be in the Users list.
1504 BasicBlock *Switch = SI->getParent();
1505 BasicBlock *SISucc = DeadCase.getCaseSuccessor();
1506 BasicBlock *Latch = L->getLoopLatch();
1508 if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.
1509 // If the DeadCase successor dominates the loop latch, then the
1510 // transformation isn't safe since it will delete the sole predecessor edge
1512 if (Latch && DT->dominates(SISucc, Latch))
1515 // FIXME: This is a hack. We need to keep the successor around
1516 // and hooked up so as to preserve the loop structure, because
1517 // trying to update it is complicated. So instead we preserve the
1518 // loop structure and put the block on a dead code path.
1519 SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
1520 // Compute the successors instead of relying on the return value
1521 // of SplitEdge, since it may have split the switch successor
1523 BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
1524 BasicBlock *OldSISucc = *succ_begin(NewSISucc);
1525 // Create an "unreachable" destination.
1526 BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
1527 Switch->getParent(),
1529 new UnreachableInst(Context, Abort);
1530 // Force the new case destination to branch to the "unreachable"
1531 // block while maintaining a (dead) CFG edge to the old block.
1532 NewSISucc->getTerminator()->eraseFromParent();
1533 BranchInst::Create(Abort, OldSISucc,
1534 ConstantInt::getTrue(Context), NewSISucc);
1535 // Release the PHI operands for this edge.
1536 for (PHINode &PN : NewSISucc->phis())
1537 PN.setIncomingValueForBlock(Switch, UndefValue::get(PN.getType()));
1538 // Tell the domtree about the new block. We don't fully update the
1539 // domtree here -- instead we force it to do a full recomputation
1540 // after the pass is complete -- but we do need to inform it of
1542 DT->addNewBlock(Abort, NewSISucc);
1545 simplifyCode(Worklist, L);
1548 /// Now that we have simplified some instructions in the loop, walk over it and
1549 /// constant prop, dce, and fold control flow where possible. Note that this is
1550 /// effectively a very simple loop-structure-aware optimizer. During processing
1551 /// of this loop, L could very well be deleted, so it must not be used.
1553 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1556 void LoopUnswitch::simplifyCode(std::vector<Instruction *> &Worklist, Loop *L) {
1557 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1558 while (!Worklist.empty()) {
1559 Instruction *I = Worklist.back();
1560 Worklist.pop_back();
1563 if (isInstructionTriviallyDead(I)) {
1564 LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
1566 // Add uses to the worklist, which may be dead now.
1567 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1568 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1569 Worklist.push_back(Use);
1570 removeFromWorklist(I, Worklist);
1572 MSSAU->removeMemoryAccess(I);
1573 I->eraseFromParent();
1578 // See if instruction simplification can hack this up. This is common for
1579 // things like "select false, X, Y" after unswitching made the condition be
1580 // 'false'. TODO: update the domtree properly so we can pass it here.
1581 if (Value *V = SimplifyInstruction(I, DL))
1582 if (LI->replacementPreservesLCSSAForm(I, V)) {
1583 replaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get());
1587 // Special case hacks that appear commonly in unswitched code.
1588 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1589 if (BI->isUnconditional()) {
1590 // If BI's parent is the only pred of the successor, fold the two blocks
1592 BasicBlock *Pred = BI->getParent();
1594 BasicBlock *Succ = BI->getSuccessor(0);
1595 BasicBlock *SinglePred = Succ->getSinglePredecessor();
1596 if (!SinglePred) continue; // Nothing to do.
1597 assert(SinglePred == Pred && "CFG broken");
1599 // Make the LPM and Worklist updates specific to LoopUnswitch.
1600 removeFromWorklist(BI, Worklist);
1601 auto SuccIt = Succ->begin();
1602 while (PHINode *PN = dyn_cast<PHINode>(SuccIt++)) {
1603 for (unsigned It = 0, E = PN->getNumOperands(); It != E; ++It)
1604 if (Instruction *Use = dyn_cast<Instruction>(PN->getOperand(It)))
1605 Worklist.push_back(Use);
1606 for (User *U : PN->users())
1607 Worklist.push_back(cast<Instruction>(U));
1608 removeFromWorklist(PN, Worklist);
1611 // Merge the block and make the remaining analyses updates.
1612 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1613 MergeBlockIntoPredecessor(Succ, &DTU, LI, MSSAU.get());
1623 /// Simple simplifications we can do given the information that Cond is
1624 /// definitely not equal to Val.
1625 Value *LoopUnswitch::simplifyInstructionWithNotEqual(Instruction *Inst,
1628 // icmp eq cond, val -> false
1629 ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1630 if (CI && CI->isEquality()) {
1631 Value *Op0 = CI->getOperand(0);
1632 Value *Op1 = CI->getOperand(1);
1633 if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
1634 LLVMContext &Ctx = Inst->getContext();
1635 if (CI->getPredicate() == CmpInst::ICMP_EQ)
1636 return ConstantInt::getFalse(Ctx);
1638 return ConstantInt::getTrue(Ctx);
1642 // FIXME: there may be other opportunities, e.g. comparison with floating
1643 // point, or Invariant - Val != 0, etc.