1///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
10#include "ScalarOptions.h"
11#include "llvm/ADT/DenseMap.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/Sequence.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/Twine.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/BlockFrequencyInfo.h"
21#include "llvm/Analysis/CFG.h"
22#include "llvm/Analysis/CodeMetrics.h"
23#include "llvm/Analysis/DomTreeUpdater.h"
24#include "llvm/Analysis/GuardUtils.h"
25#include "llvm/Analysis/LoopAnalysisManager.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/LoopIterator.h"
28#include "llvm/Analysis/MemorySSA.h"
29#include "llvm/Analysis/MemorySSAUpdater.h"
30#include "llvm/Analysis/MustExecute.h"
31#include "llvm/Analysis/ScalarEvolution.h"
32#include "llvm/Analysis/TargetTransformInfo.h"
33#include "llvm/Analysis/ValueTracking.h"
34#include "llvm/IR/BasicBlock.h"
35#include "llvm/IR/Constant.h"
36#include "llvm/IR/Constants.h"
37#include "llvm/IR/Dominators.h"
38#include "llvm/IR/Function.h"
39#include "llvm/IR/IRBuilder.h"
40#include "llvm/IR/InstrTypes.h"
41#include "llvm/IR/Instruction.h"
42#include "llvm/IR/Instructions.h"
43#include "llvm/IR/IntrinsicInst.h"
44#include "llvm/IR/MDBuilder.h"
45#include "llvm/IR/Module.h"
46#include "llvm/IR/PatternMatch.h"
47#include "llvm/IR/ProfDataUtils.h"
48#include "llvm/IR/Use.h"
49#include "llvm/IR/Value.h"
50#include "llvm/Support/Casting.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/ErrorHandling.h"
53#include "llvm/Support/GenericDomTree.h"
54#include "llvm/Support/InstructionCost.h"
55#include "llvm/Support/raw_ostream.h"
56#include "llvm/Transforms/Scalar/LoopPassManager.h"
57#include "llvm/Transforms/Utils/BasicBlockUtils.h"
58#include "llvm/Transforms/Utils/Cloning.h"
59#include "llvm/Transforms/Utils/Local.h"
60#include "llvm/Transforms/Utils/LoopUtils.h"
61#include "llvm/Transforms/Utils/ValueMapper.h"
62#include <algorithm>
63#include <cassert>
64#include <iterator>
65#include <numeric>
66#include <optional>
67#include <utility>
68
69#define DEBUG_TYPE "simple-loop-unswitch"
70
71using namespace llvm;
72using namespace llvm::PatternMatch;
73
74STATISTIC(NumBranches, "Number of branches unswitched");
75STATISTIC(NumSwitches, "Number of switches unswitched");
76STATISTIC(NumSelects, "Number of selects turned into branches for unswitching");
77STATISTIC(NumGuards, "Number of guards turned into branches for unswitching");
78STATISTIC(NumTrivial, "Number of unswitches that are trivial");
79STATISTIC(
80 NumCostMultiplierSkipped,
81 "Number of unswitch candidates that had their cost multiplier skipped");
82STATISTIC(NumInvariantConditionsInjected,
83 "Number of invariant conditions injected and unswitched");
84
85AnalysisKey ShouldRunExtraSimpleLoopUnswitch::Key;
86namespace {
87struct CompareDesc {
88 CondBrInst *Term;
89 Value *Invariant;
90 BasicBlock *InLoopSucc;
91
92 CompareDesc(CondBrInst *Term, Value *Invariant, BasicBlock *InLoopSucc)
93 : Term(Term), Invariant(Invariant), InLoopSucc(InLoopSucc) {}
94};
95
96struct InjectedInvariant {
97 ICmpInst::Predicate Pred;
98 Value *LHS;
99 Value *RHS;
100 BasicBlock *InLoopSucc;
101
102 InjectedInvariant(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
103 BasicBlock *InLoopSucc)
104 : Pred(Pred), LHS(LHS), RHS(RHS), InLoopSucc(InLoopSucc) {}
105};
106
107struct NonTrivialUnswitchCandidate {
108 Instruction *TI = nullptr;
109 TinyPtrVector<Value *> Invariants;
110 std::optional<InstructionCost> Cost;
111 std::optional<InjectedInvariant> PendingInjection;
112 NonTrivialUnswitchCandidate(
113 Instruction *TI, ArrayRef<Value *> Invariants,
114 std::optional<InstructionCost> Cost = std::nullopt,
115 std::optional<InjectedInvariant> PendingInjection = std::nullopt)
116 : TI(TI), Invariants(Invariants), Cost(Cost),
117 PendingInjection(PendingInjection) {};
118
119 bool hasPendingInjection() const { return PendingInjection.has_value(); }
120};
121} // end anonymous namespace.
122
123// Helper to skip (select x, true, false), which matches both a logical AND and
124// OR and can confuse code that tries to determine if \p Cond is either a
125// logical AND or OR but not both.
126static Value *skipTrivialSelect(Value *Cond) {
127 Value *CondNext;
128 while (match(V: Cond, P: m_Select(C: m_Value(V&: CondNext), L: m_One(), R: m_Zero())))
129 Cond = CondNext;
130 return Cond;
131}
132
133/// Collect all of the loop invariant input values transitively used by the
134/// homogeneous instruction graph from a given root.
135///
136/// This essentially walks from a root recursively through loop variant operands
137/// which have perform the same logical operation (AND or OR) and finds all
138/// inputs which are loop invariant. For some operations these can be
139/// re-associated and unswitched out of the loop entirely.
140static TinyPtrVector<Value *>
141collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root,
142 const LoopInfo &LI) {
143 assert(!L.isLoopInvariant(&Root) &&
144 "Only need to walk the graph if root itself is not invariant.");
145 TinyPtrVector<Value *> Invariants;
146
147 bool IsRootAnd = match(V: &Root, P: m_LogicalAnd());
148 bool IsRootOr = match(V: &Root, P: m_LogicalOr());
149
150 // Build a worklist and recurse through operators collecting invariants.
151 SmallVector<Instruction *, 4> Worklist;
152 SmallPtrSet<Instruction *, 8> Visited;
153 Worklist.push_back(Elt: &Root);
154 Visited.insert(Ptr: &Root);
155 do {
156 Instruction &I = *Worklist.pop_back_val();
157 for (Value *OpV : I.operand_values()) {
158 // Skip constants as unswitching isn't interesting for them.
159 if (isa<Constant>(Val: OpV))
160 continue;
161
162 // Add it to our result if loop invariant.
163 if (L.isLoopInvariant(V: OpV)) {
164 Invariants.push_back(NewVal: OpV);
165 continue;
166 }
167
168 // If not an instruction with the same opcode, nothing we can do.
169 Instruction *OpI = dyn_cast<Instruction>(Val: skipTrivialSelect(Cond: OpV));
170
171 if (OpI && ((IsRootAnd && match(V: OpI, P: m_LogicalAnd())) ||
172 (IsRootOr && match(V: OpI, P: m_LogicalOr())))) {
173 // Visit this operand.
174 if (Visited.insert(Ptr: OpI).second)
175 Worklist.push_back(Elt: OpI);
176 }
177 }
178 } while (!Worklist.empty());
179
180 return Invariants;
181}
182
183static void replaceLoopInvariantUses(const Loop &L, Value *Invariant,
184 Constant &Replacement) {
185 assert(!isa<Constant>(Invariant) && "Why are we unswitching on a constant?");
186
187 // Replace uses of LIC in the loop with the given constant.
188 // We use make_early_inc_range as set invalidates the iterator.
189 for (Use &U : llvm::make_early_inc_range(Range: Invariant->uses())) {
190 Instruction *UserI = dyn_cast<Instruction>(Val: U.getUser());
191
192 // Replace this use within the loop body.
193 if (UserI && L.contains(Inst: UserI))
194 U.set(&Replacement);
195 }
196}
197
198/// Return true if \p V is a PHI node in the header of \p L.
199static bool isLoopHeaderPHI(const Loop &L, const Value *V) {
200 const auto *PN = dyn_cast<PHINode>(Val: V);
201 return PN && PN->getParent() == L.getHeader();
202}
203
204/// Return the value \p V holds on entry to \p L. For a header PHI that is its
205/// incoming value from the preheader; any other value is returned unchanged.
206static Value *getLoopEntryValue(const Loop &L, Value *V) {
207 if (!isLoopHeaderPHI(L, V))
208 return V;
209 return cast<PHINode>(Val: V)->getIncomingValueForBlock(BB: L.getLoopPreheader());
210}
211
212/// Check that all the LCSSA PHI nodes in \p ExitBB have trivial incoming values
213/// along the edge from \p ExitingBB, i.e. values that are still correct if the
214/// loop is not entered.
215///
216/// Only loop invariant values are trivial by default. If \p AllowHeaderPHIs is
217/// set, a PHI in the loop header counts as trivial too.
218static bool areLoopExitPHIsTrivial(const Loop &L, const BasicBlock &ExitingBB,
219 const BasicBlock &ExitBB,
220 bool AllowHeaderPHIs = false) {
221 for (const Instruction &I : ExitBB) {
222 auto *PN = dyn_cast<PHINode>(Val: &I);
223 if (!PN)
224 // No more PHIs to check.
225 return true;
226
227 const Value *Incoming = PN->getIncomingValueForBlock(BB: &ExitingBB);
228 if (!L.isLoopInvariant(V: Incoming) &&
229 !(AllowHeaderPHIs && isLoopHeaderPHI(L, V: Incoming)))
230 return false;
231 }
232 llvm_unreachable("Basic blocks should never be empty!");
233}
234
235/// Copy a set of loop invariant values \p Invariants and insert them at the
236/// end of \p BB and conditionally branch on the copied condition. We only
237/// branch on a single value.
238/// We attempt to estimate the profile of the resulting conditional branch from
239/// \p ComputeProfFrom, which is the original conditional branch we're
240/// unswitching.
241/// When \p Direction is true, the \p Invariants form a disjunction, and the
242/// branch conditioned on it exits the loop on the "true" case. When \p
243/// Direction is false, the \p Invariants form a conjunction and the branch
244/// exits on the "false" case.
245static void buildPartialUnswitchConditionalBranch(
246 const ScalarOptions &Opts, BasicBlock &BB, ArrayRef<Value *> Invariants,
247 bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc,
248 const Instruction *I, AssumptionCache *AC, const DominatorTree &DT,
249 const CondBrInst &ComputeProfFrom) {
250
251 SmallVector<uint32_t> BranchWeights;
252 bool HasBranchWeights = Opts.simple_loop_unswitch_estimate_profile &&
253 extractBranchWeights(I: ComputeProfFrom, Weights&: BranchWeights);
254 // If Direction is true, that means we had a disjunction and that the "true"
255 // case exits. The probability of the disjunction of the subset of terms is at
256 // most as high as the original one. So, if the probability is higher than the
257 // one we'd assign in absence of a profile (i.e. 0.5), we will use 0.5,
258 // but if it's lower, we will use the original probability.
259 // Conversely, if Direction is false, that means we had a conjunction, and the
260 // probability of exiting is captured in the second branch weight. That
261 // probability is a disjunction (of the negation of the original terms). The
262 // same reasoning applies as above.
263 // Issue #165649: should we expect BFI to conserve, and use that to calculate
264 // the branch weights?
265 if (HasBranchWeights &&
266 static_cast<double>(BranchWeights[Direction ? 0 : 1]) /
267 static_cast<double>(sum_of(Range&: BranchWeights)) >
268 0.5)
269 HasBranchWeights = false;
270
271 IRBuilder<> IRB(&BB);
272 IRB.SetCurrentDebugLocation(DebugLoc::getCompilerGenerated());
273
274 SmallVector<Value *> FrozenInvariants;
275 for (Value *Inv : Invariants) {
276 if (Opts.freeze_loop_unswitch_cond &&
277 !isGuaranteedNotToBeUndefOrPoison(V: Inv, AC, CtxI: I, DT: &DT))
278 Inv = IRB.CreateFreeze(V: Inv, Name: Inv->getName() + ".fr");
279 FrozenInvariants.push_back(Elt: Inv);
280 }
281
282 Value *Cond = Direction ? IRB.CreateOr(Ops: FrozenInvariants)
283 : IRB.CreateAnd(Ops: FrozenInvariants);
284 auto *BR = IRB.CreateCondBr(
285 Cond, True: Direction ? &UnswitchedSucc : &NormalSucc,
286 False: Direction ? &NormalSucc : &UnswitchedSucc,
287 BranchWeights: HasBranchWeights ? ComputeProfFrom.getMetadata(KindID: LLVMContext::MD_prof)
288 : nullptr);
289 if (!HasBranchWeights)
290 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
291}
292
293/// Copy a set of loop invariant values, and conditionally branch on them.
294static void buildPartialInvariantUnswitchConditionalBranch(
295 BasicBlock &BB, ArrayRef<Value *> ToDuplicate, bool Direction,
296 BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L,
297 MemorySSAUpdater *MSSAU, const CondBrInst &OriginalBranch) {
298 ValueToValueMapTy VMap;
299 for (auto *Val : reverse(C&: ToDuplicate)) {
300 Instruction *Inst = cast<Instruction>(Val);
301 Instruction *NewInst = Inst->clone();
302
303 if (const DebugLoc &DL = Inst->getDebugLoc())
304 mapAtomInstance(DL, VMap);
305
306 NewInst->insertInto(ParentBB: &BB, It: BB.end());
307 RemapInstruction(I: NewInst, VM&: VMap,
308 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
309 VMap[Val] = NewInst;
310
311 if (!MSSAU)
312 continue;
313
314 MemorySSA *MSSA = MSSAU->getMemorySSA();
315 if (auto *MemUse =
316 dyn_cast_or_null<MemoryUse>(Val: MSSA->getMemoryAccess(I: Inst))) {
317 auto *DefiningAccess = MemUse->getDefiningAccess();
318 // Get the first defining access before the loop.
319 while (L.contains(BB: DefiningAccess->getBlock())) {
320 // If the defining access is a MemoryPhi, get the incoming
321 // value for the pre-header as defining access.
322 if (auto *MemPhi = dyn_cast<MemoryPhi>(Val: DefiningAccess))
323 DefiningAccess =
324 MemPhi->getIncomingValueForBlock(BB: L.getLoopPreheader());
325 else
326 DefiningAccess = cast<MemoryDef>(Val: DefiningAccess)->getDefiningAccess();
327 }
328 MSSAU->createMemoryAccessInBB(I: NewInst, Definition: DefiningAccess,
329 BB: NewInst->getParent(),
330 Point: MemorySSA::BeforeTerminator);
331 }
332 }
333
334 IRBuilder<> IRB(&BB);
335 IRB.SetCurrentDebugLocation(DebugLoc::getCompilerGenerated());
336 Value *Cond = VMap[ToDuplicate[0]];
337 // The expectation is that ToDuplicate[0] is the condition used by the
338 // OriginalBranch, case in which we can clone the profile metadata from there.
339 auto *ProfData =
340 ToDuplicate[0] == skipTrivialSelect(Cond: OriginalBranch.getCondition())
341 ? OriginalBranch.getMetadata(KindID: LLVMContext::MD_prof)
342 : nullptr;
343 auto *BR =
344 IRB.CreateCondBr(Cond, True: Direction ? &UnswitchedSucc : &NormalSucc,
345 False: Direction ? &NormalSucc : &UnswitchedSucc, BranchWeights: ProfData);
346 if (!ProfData)
347 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
348}
349
350/// Rewrite the PHI nodes in an unswitched loop exit basic block.
351///
352/// Requires that the loop exit and unswitched basic block are the same, and
353/// that the exiting block was a unique predecessor of that block. Rewrites the
354/// PHI nodes in that block such that what were LCSSA PHI nodes become trivial
355/// PHI nodes from the old preheader that now contains the unswitched
356/// terminator.
357static void rewritePHINodesForUnswitchedExitBlock(const Loop &L,
358 BasicBlock &UnswitchedBB,
359 BasicBlock &OldExitingBB,
360 BasicBlock &OldPH) {
361 for (PHINode &PN : UnswitchedBB.phis()) {
362 // When the loop exit is directly unswitched we just need to update the
363 // incoming basic block. We loop to handle weird cases with repeated
364 // incoming blocks, but expect to typically only have one operand here.
365 for (auto i : seq<int>(Begin: 0, End: PN.getNumOperands())) {
366 assert(PN.getIncomingBlock(i) == &OldExitingBB &&
367 "Found incoming block different from unique predecessor!");
368 PN.setIncomingBlock(i, BB: &OldPH);
369 PN.setIncomingValue(i, V: getLoopEntryValue(L, V: PN.getIncomingValue(i)));
370 }
371 }
372}
373
374/// Rewrite the PHI nodes in the loop exit basic block and the split off
375/// unswitched block.
376///
377/// Because the exit block remains an exit from the loop, this rewrites the
378/// LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI
379/// nodes into the unswitched basic block to select between the value in the
380/// old preheader and the loop exit.
381static void rewritePHINodesForExitAndUnswitchedBlocks(
382 const Loop &L, BasicBlock &ExitBB, BasicBlock &UnswitchedBB,
383 BasicBlock &OldExitingBB, BasicBlock &OldPH, bool FullUnswitch) {
384 assert(&ExitBB != &UnswitchedBB &&
385 "Must have different loop exit and unswitched blocks!");
386 BasicBlock::iterator InsertPt = UnswitchedBB.begin();
387 for (PHINode &PN : ExitBB.phis()) {
388 auto *NewPN = PHINode::Create(Ty: PN.getType(), /*NumReservedValues*/ 2,
389 NameStr: PN.getName() + ".split");
390 NewPN->insertBefore(InsertPos: InsertPt);
391
392 // Walk backwards over the old PHI node's inputs to minimize the cost of
393 // removing each one. We have to do this weird loop manually so that we
394 // create the same number of new incoming edges in the new PHI as we expect
395 // each case-based edge to be included in the unswitched switch in some
396 // cases.
397 // FIXME: This is really, really gross. It would be much cleaner if LLVM
398 // allowed us to create a single entry for a predecessor block without
399 // having separate entries for each "edge" even though these edges are
400 // required to produce identical results.
401 for (int i = PN.getNumIncomingValues() - 1; i >= 0; --i) {
402 if (PN.getIncomingBlock(i) != &OldExitingBB)
403 continue;
404
405 Value *Incoming = PN.getIncomingValue(i);
406 if (FullUnswitch)
407 // No more edge from the old exiting block to the exit block.
408 PN.removeIncomingValue(Idx: i);
409
410 NewPN->addIncoming(V: getLoopEntryValue(L, V: Incoming), BB: &OldPH);
411 }
412
413 // Now replace the old PHI with the new one and wire the old one in as an
414 // input to the new one.
415 PN.replaceAllUsesWith(V: NewPN);
416 NewPN->addIncoming(V: &PN, BB: &ExitBB);
417 }
418}
419
420/// Hoist the current loop up to the innermost loop containing a remaining exit.
421///
422/// Because we've removed an exit from the loop, we may have changed the set of
423/// loops reachable and need to move the current loop up the loop nest or even
424/// to an entirely separate nest.
425static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
426 DominatorTree &DT, LoopInfo &LI,
427 MemorySSAUpdater *MSSAU, ScalarEvolution *SE) {
428 // If the loop is already at the top level, we can't hoist it anywhere.
429 Loop *OldParentL = L.getParentLoop();
430 if (!OldParentL)
431 return;
432
433 SmallVector<BasicBlock *, 4> Exits;
434 L.getExitBlocks(ExitBlocks&: Exits);
435 Loop *NewParentL = nullptr;
436 for (auto *ExitBB : Exits)
437 if (Loop *ExitL = LI.getLoopFor(BB: ExitBB))
438 if (!NewParentL || NewParentL->contains(L: ExitL))
439 NewParentL = ExitL;
440
441 if (NewParentL == OldParentL)
442 return;
443
444 // The new parent loop (if different) should always contain the old one.
445 if (NewParentL)
446 assert(NewParentL->contains(OldParentL) &&
447 "Can only hoist this loop up the nest!");
448 // The preheader will need to move with the body of this loop. However,
449 // because it isn't in this loop we also need to update the primary loop map.
450 assert(OldParentL == LI.getLoopFor(&Preheader) &&
451 "Parent loop of this loop should contain this loop's preheader!");
452 LI.changeLoopFor(BB: &Preheader, L: NewParentL);
453
454 // Remove this loop from its old parent.
455 OldParentL->removeChildLoop(Child: &L);
456
457 // Add the loop either to the new parent or as a top-level loop.
458 if (NewParentL)
459 NewParentL->addChildLoop(NewChild: &L);
460 else
461 LI.addTopLevelLoop(New: &L);
462
463 // Remove this loops blocks from the old parent and every other loop up the
464 // nest until reaching the new parent. Also update all of these
465 // no-longer-containing loops to reflect the nesting change.
466 for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
467 OldContainingL = OldContainingL->getParentLoop()) {
468 LI.removeBlocksIf(L&: *OldContainingL, Pred: [&](const BasicBlock *BB) {
469 return BB == &Preheader || L.contains(BB);
470 });
471
472 // Because we just hoisted a loop out of this one, we have essentially
473 // created new exit paths from it. That means we need to form LCSSA PHI
474 // nodes for values used in the no-longer-nested loop.
475 formLCSSA(L&: *OldContainingL, DT, LI: &LI, SE);
476
477 // We shouldn't need to form dedicated exits because the exit introduced
478 // here is the (just split by unswitching) preheader. However, after trivial
479 // unswitching it is possible to get new non-dedicated exits out of parent
480 // loop so let's conservatively form dedicated exit blocks and figure out
481 // if we can optimize later.
482 formDedicatedExitBlocks(L: OldContainingL, DT: &DT, LI: &LI, MSSAU,
483 /*PreserveLCSSA*/ true);
484 }
485}
486
487// Return the top-most loop containing ExitBB and having ExitBB as exiting block
488// or the loop containing ExitBB, if there is no parent loop containing ExitBB
489// as exiting block.
490static Loop *getTopMostExitingLoop(const BasicBlock *ExitBB,
491 const LoopInfo &LI) {
492 Loop *TopMost = LI.getLoopFor(BB: ExitBB);
493 Loop *Current = TopMost;
494 while (Current) {
495 if (Current->isLoopExiting(BB: ExitBB))
496 TopMost = Current;
497 Current = Current->getParentLoop();
498 }
499 return TopMost;
500}
501
502/// Unswitch a trivial branch if the condition is loop invariant.
503///
504/// This routine should only be called when loop code leading to the branch has
505/// been validated as trivial (no side effects). This routine checks if the
506/// condition is invariant and one of the successors is a loop exit or a loop
507/// latch with no side-effects. This allows us to unswitch without duplicating
508/// the loop, making it trivial.
509///
510/// If this routine fails to unswitch the branch it returns false.
511///
512/// If the branch can be unswitched, this routine splits the preheader and
513/// hoists the branch above that split. Preserves loop simplified form
514/// (splitting the exit block as necessary). It simplifies the branch within
515/// the loop to an unconditional branch but doesn't remove it entirely. Further
516/// cleanup can be done with some simplifycfg like pass.
517///
518/// If `SE` is not null, it will be updated based on the potential loop SCEVs
519/// invalidated by this.
520static bool unswitchTrivialBranch(const ScalarOptions &Opts, Loop &L,
521 CondBrInst &BI, DominatorTree &DT,
522 LoopInfo &LI, ScalarEvolution *SE,
523 MemorySSAUpdater *MSSAU) {
524 LLVM_DEBUG(dbgs() << " Trying to unswitch branch: " << BI << "\n");
525
526 // The loop invariant values that we want to unswitch.
527 TinyPtrVector<Value *> Invariants;
528
529 // When true, we're fully unswitching the branch rather than just unswitching
530 // some input conditions to the branch.
531 bool FullUnswitch = false;
532
533 Value *Cond = skipTrivialSelect(Cond: BI.getCondition());
534 if (L.isLoopInvariant(V: Cond)) {
535 Invariants.push_back(NewVal: Cond);
536 FullUnswitch = true;
537 } else {
538 if (auto *CondInst = dyn_cast<Instruction>(Val: Cond))
539 Invariants = collectHomogenousInstGraphLoopInvariants(L, Root&: *CondInst, LI);
540 if (Invariants.empty()) {
541 LLVM_DEBUG(dbgs() << " Couldn't find invariant inputs!\n");
542 return false;
543 }
544 }
545
546 std::optional<int> LatchIdx = std::nullopt;
547 auto *LoopLatch = L.getLoopLatch();
548 auto *ULExit = LI.getUniqueLatchExitBlock(L);
549 if (SE && FullUnswitch && ULExit &&
550 // Make sure we do not unswitch a branch when both of its successors are
551 // the loop latch. The branch is actually unconditional.
552 BI.getSuccessor(i: 0) != BI.getSuccessor(i: 1)) {
553 if (BI.getSuccessor(i: 0) == LoopLatch && L.contains(BB: BI.getSuccessor(i: 1)))
554 LatchIdx = 0;
555 else if (BI.getSuccessor(i: 1) == LoopLatch && L.contains(BB: BI.getSuccessor(i: 0)))
556 LatchIdx = 1;
557 }
558
559 bool ModifiedBranch = false;
560 // Redirecting the latch edge to the exit block will cause us to skip latch
561 // instructions. This can only be done if the latch instructions don't have
562 // side effects and don't have any convergent instructions.
563 if (LatchIdx && areLoopExitPHIsTrivial(L, ExitingBB: *LoopLatch, ExitBB: *ULExit) &&
564 !llvm::any_of(Range&: *LoopLatch, P: [](Instruction &I) {
565 if (const auto *CB = dyn_cast<CallBase>(Val: &I))
566 if (CB->isConvergent())
567 return true;
568 return I.mayHaveSideEffects();
569 })) {
570
571 // We need to prove the loop is finite, otherwise this change will convert
572 // it to a finite loop. This conservative check is good enough as we are
573 // mostly interested in perfect countable loop nests that perform
574 // calculations on arrays.
575 const SCEV *MaxBECount = SE->getConstantMaxBackedgeTakenCount(L: &L);
576 if (!isa<SCEVCouldNotCompute>(Val: MaxBECount)) {
577 SmallVector<cfg::Update<BasicBlock *>, 2> Updates;
578 Updates.push_back(Elt: {cfg::UpdateKind::Delete, BI.getParent(),
579 BI.getSuccessor(i: *LatchIdx)});
580 Updates.push_back(Elt: {cfg::UpdateKind::Insert, BI.getParent(), ULExit});
581 LoopLatch->removePredecessor(Pred: BI.getParent());
582 BI.setSuccessor(idx: *LatchIdx, NewSucc: ULExit);
583 for (PHINode &PN : ULExit->phis()) {
584 Value *V = PN.getIncomingValueForBlock(BB: LoopLatch);
585 PN.addIncoming(V, BB: BI.getParent());
586 }
587 if (MSSAU)
588 MSSAU->applyUpdates(Updates, DT, /*UpdateDTFirst=*/true);
589 else
590 DT.applyUpdates(Updates);
591
592 ModifiedBranch = true;
593 }
594 }
595
596 // Check that one of the branch's successors exits, and which one.
597 bool ExitDirection = true;
598 int LoopExitSuccIdx = 0;
599 auto *LoopExitBB = BI.getSuccessor(i: 0);
600 if (L.contains(BB: LoopExitBB)) {
601 ExitDirection = false;
602 LoopExitSuccIdx = 1;
603 LoopExitBB = BI.getSuccessor(i: 1);
604 if (L.contains(BB: LoopExitBB)) {
605 LLVM_DEBUG(dbgs() << " Branch doesn't exit the loop!\n");
606 assert(!ModifiedBranch && "Modified the branch but didn't unswitch");
607 return false;
608 }
609 }
610 auto *ContinueBB = BI.getSuccessor(i: 1 - LoopExitSuccIdx);
611 auto *ParentBB = BI.getParent();
612
613 // If the exit incomings aren't loop-invariant, the unswitch is still trivial
614 // when branch dominates the latch and every non-invariant incoming is a
615 // header PHI.
616 if (!ModifiedBranch && !areLoopExitPHIsTrivial(L, ExitingBB: *ParentBB, ExitBB: *LoopExitBB,
617 /*AllowHeaderPHIs=*/true)) {
618 LLVM_DEBUG(dbgs() << " Loop exit PHI's aren't loop-invariant!\n");
619 return false;
620 }
621
622 // When unswitching only part of the branch's condition, we need the exit
623 // block to be reached directly from the partially unswitched input. This can
624 // be done when the exit block is along the true edge and the branch condition
625 // is a graph of `or` operations, or the exit block is along the false edge
626 // and the condition is a graph of `and` operations.
627 if (!FullUnswitch) {
628 if (ExitDirection ? !match(V: Cond, P: m_LogicalOr())
629 : !match(V: Cond, P: m_LogicalAnd())) {
630 LLVM_DEBUG(dbgs() << " Branch condition is in improper form for "
631 "non-full unswitch!\n");
632 assert(!ModifiedBranch && "Modified the branch but didn't unswitch");
633 return false;
634 }
635 }
636
637 LLVM_DEBUG({
638 dbgs() << " unswitching trivial invariant conditions for: " << BI
639 << "\n";
640 for (Value *Invariant : Invariants) {
641 dbgs() << " " << *Invariant << " == true";
642 if (Invariant != Invariants.back())
643 dbgs() << " ||";
644 dbgs() << "\n";
645 }
646 });
647
648 // If we have scalar evolutions, we need to invalidate them including this
649 // loop, the loop containing the exit block and the topmost parent loop
650 // exiting via LoopExitBB.
651 if (SE) {
652 if (const Loop *ExitL = getTopMostExitingLoop(ExitBB: LoopExitBB, LI))
653 SE->forgetLoop(L: ExitL);
654 else
655 // Forget the entire nest as this exits the entire nest.
656 SE->forgetTopmostLoop(L: &L);
657 SE->forgetBlockAndLoopDispositions();
658 }
659
660 if (MSSAU && VerifyMemorySSA)
661 MSSAU->getMemorySSA()->verifyMemorySSA();
662
663 // Split the preheader, so that we know that there is a safe place to insert
664 // the conditional branch. We will change the preheader to have a conditional
665 // branch on LoopCond.
666 BasicBlock *OldPH = L.getLoopPreheader();
667 BasicBlock *NewPH = SplitEdge(From: OldPH, To: L.getHeader(), DT: &DT, LI: &LI, MSSAU);
668
669 // Now that we have a place to insert the conditional branch, create a place
670 // to branch to: this is the exit block out of the loop that we are
671 // unswitching. We need to split this if there are other loop predecessors.
672 // Because the loop is in simplified form, *any* other predecessor is enough.
673 BasicBlock *UnswitchedBB;
674 if (FullUnswitch && LoopExitBB->getUniquePredecessor()) {
675 assert(LoopExitBB->getUniquePredecessor() == BI.getParent() &&
676 "A branch's parent isn't a predecessor!");
677 UnswitchedBB = LoopExitBB;
678 } else {
679 UnswitchedBB =
680 SplitBlock(Old: LoopExitBB, SplitPt: LoopExitBB->begin(), DT: &DT, LI: &LI, MSSAU, BBName: "");
681 }
682
683 if (MSSAU && VerifyMemorySSA)
684 MSSAU->getMemorySSA()->verifyMemorySSA();
685
686 // Actually move the invariant uses into the unswitched position. If possible,
687 // we do this by moving the instructions, but when doing partial unswitching
688 // we do it by building a new merge of the values in the unswitched position.
689 OldPH->getTerminator()->eraseFromParent();
690 if (FullUnswitch) {
691 // If fully unswitching, we can use the existing branch instruction.
692 // Splice it into the old PH to gate reaching the new preheader and re-point
693 // its successors.
694 BI.moveBefore(BB&: *OldPH, I: OldPH->end());
695 BI.setCondition(Cond);
696 if (MSSAU) {
697 // Temporarily clone the terminator, to make MSSA update cheaper by
698 // separating "insert edge" updates from "remove edge" ones.
699 BI.clone()->insertInto(ParentBB, It: ParentBB->end());
700 } else {
701 // Create a new unconditional branch that will continue the loop as a new
702 // terminator.
703 Instruction *NewBI = UncondBrInst::Create(Target: ContinueBB, InsertBefore: ParentBB);
704 NewBI->setDebugLoc(BI.getDebugLoc());
705 }
706 BI.setSuccessor(idx: LoopExitSuccIdx, NewSucc: UnswitchedBB);
707 BI.setSuccessor(idx: 1 - LoopExitSuccIdx, NewSucc: NewPH);
708 } else {
709 // Only unswitching a subset of inputs to the condition, so we will need to
710 // build a new branch that merges the invariant inputs.
711 if (ExitDirection)
712 assert(match(skipTrivialSelect(BI.getCondition()), m_LogicalOr()) &&
713 "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the "
714 "condition!");
715 else
716 assert(match(skipTrivialSelect(BI.getCondition()), m_LogicalAnd()) &&
717 "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the"
718 " condition!");
719 buildPartialUnswitchConditionalBranch(
720 Opts, BB&: *OldPH, Invariants, Direction: ExitDirection, UnswitchedSucc&: *UnswitchedBB, NormalSucc&: *NewPH,
721 I: OldPH->getTerminatorOrNull(), AC: nullptr, DT, ComputeProfFrom: BI);
722 }
723
724 // Update the dominator tree with the added edge.
725 DT.insertEdge(From: OldPH, To: UnswitchedBB);
726
727 // After the dominator tree was updated with the added edge, update MemorySSA
728 // if available.
729 if (MSSAU) {
730 SmallVector<CFGUpdate, 1> Updates;
731 Updates.push_back(Elt: {cfg::UpdateKind::Insert, OldPH, UnswitchedBB});
732 MSSAU->applyInsertUpdates(Updates, DT);
733 }
734
735 // Finish updating dominator tree and memory ssa for full unswitch.
736 if (FullUnswitch) {
737 if (MSSAU) {
738 Instruction *Term = ParentBB->getTerminator();
739 // Remove the cloned branch instruction and create unconditional branch
740 // now.
741 Instruction *NewBI = UncondBrInst::Create(Target: ContinueBB, InsertBefore: ParentBB);
742 NewBI->setDebugLoc(Term->getDebugLoc());
743 Term->eraseFromParent();
744 MSSAU->removeEdge(From: ParentBB, To: LoopExitBB);
745 }
746 DT.deleteEdge(From: ParentBB, To: LoopExitBB);
747 }
748
749 if (MSSAU && VerifyMemorySSA)
750 MSSAU->getMemorySSA()->verifyMemorySSA();
751
752 // Rewrite the relevant PHI nodes.
753 if (UnswitchedBB == LoopExitBB)
754 rewritePHINodesForUnswitchedExitBlock(L, UnswitchedBB&: *UnswitchedBB, OldExitingBB&: *ParentBB, OldPH&: *OldPH);
755 else
756 rewritePHINodesForExitAndUnswitchedBlocks(L, ExitBB&: *LoopExitBB, UnswitchedBB&: *UnswitchedBB,
757 OldExitingBB&: *ParentBB, OldPH&: *OldPH, FullUnswitch);
758
759 // The constant we can replace all of our invariants with inside the loop
760 // body. If any of the invariants have a value other than this the loop won't
761 // be entered.
762 ConstantInt *Replacement = ExitDirection
763 ? ConstantInt::getFalse(Context&: BI.getContext())
764 : ConstantInt::getTrue(Context&: BI.getContext());
765
766 // Since this is an i1 condition we can also trivially replace uses of it
767 // within the loop with a constant.
768 for (Value *Invariant : Invariants)
769 replaceLoopInvariantUses(L, Invariant, Replacement&: *Replacement);
770
771 // If this was full unswitching, we may have changed the nesting relationship
772 // for this loop so hoist it to its correct parent if needed.
773 if (FullUnswitch)
774 hoistLoopToNewParent(L, Preheader&: *NewPH, DT, LI, MSSAU, SE);
775
776 // If UnswitchedBB was split off LoopExitBB, it is reached from both the old
777 // preheader and LoopExitBB. For enclosing loops that contain the old
778 // preheader but not UnswitchedBB, it is now a non-dedicated exit.
779 for (Loop *ParentL = LI.getLoopFor(BB: OldPH);
780 ParentL && !ParentL->contains(BB: UnswitchedBB);
781 ParentL = ParentL->getParentLoop())
782 formDedicatedExitBlocks(L: ParentL, DT: &DT, LI: &LI, MSSAU, /*PreserveLCSSA*/ true);
783
784 if (MSSAU && VerifyMemorySSA)
785 MSSAU->getMemorySSA()->verifyMemorySSA();
786
787 LLVM_DEBUG(dbgs() << " done: unswitching trivial branch...\n");
788 ++NumTrivial;
789 ++NumBranches;
790 return true;
791}
792
793/// Unswitch a trivial switch if the condition is loop invariant.
794///
795/// This routine should only be called when loop code leading to the switch has
796/// been validated as trivial (no side effects). This routine checks if the
797/// condition is invariant and that at least one of the successors is a loop
798/// exit. This allows us to unswitch without duplicating the loop, making it
799/// trivial.
800///
801/// If this routine fails to unswitch the switch it returns false.
802///
803/// If the switch can be unswitched, this routine splits the preheader and
804/// copies the switch above that split. If the default case is one of the
805/// exiting cases, it copies the non-exiting cases and points them at the new
806/// preheader. If the default case is not exiting, it copies the exiting cases
807/// and points the default at the preheader. It preserves loop simplified form
808/// (splitting the exit blocks as necessary). It simplifies the switch within
809/// the loop by removing now-dead cases. If the default case is one of those
810/// unswitched, it replaces its destination with a new basic block containing
811/// only unreachable. Such basic blocks, while technically loop exits, are not
812/// considered for unswitching so this is a stable transform and the same
813/// switch will not be revisited. If after unswitching there is only a single
814/// in-loop successor, the switch is further simplified to an unconditional
815/// branch. Still more cleanup can be done with some simplifycfg like pass.
816///
817/// If `SE` is not null, it will be updated based on the potential loop SCEVs
818/// invalidated by this.
819static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
820 LoopInfo &LI, ScalarEvolution *SE,
821 MemorySSAUpdater *MSSAU) {
822 LLVM_DEBUG(dbgs() << " Trying to unswitch switch: " << SI << "\n");
823 Value *LoopCond = SI.getCondition();
824
825 // If this isn't switching on an invariant condition, we can't unswitch it.
826 if (!L.isLoopInvariant(V: LoopCond))
827 return false;
828
829 auto *ParentBB = SI.getParent();
830
831 // The same check must be used both for the default and the exit cases. We
832 // should never leave edges from the switch instruction to a basic block that
833 // we are unswitching, hence the condition used to determine the default case
834 // needs to also be used to populate ExitCaseIndices, which is then used to
835 // remove cases from the switch.
836 auto IsTriviallyUnswitchableExitBlock = [&](BasicBlock &BBToCheck) {
837 // BBToCheck is not an exit block if it is inside loop L.
838 if (L.contains(BB: &BBToCheck))
839 return false;
840 // BBToCheck is not trivial to unswitch if its phis aren't loop invariant.
841 if (!areLoopExitPHIsTrivial(L, ExitingBB: *ParentBB, ExitBB: BBToCheck))
842 return false;
843 // We do not unswitch a block that only has an unreachable statement, as
844 // it's possible this is a previously unswitched block. Only unswitch if
845 // either the terminator is not unreachable, or, if it is, it's not the only
846 // instruction in the block.
847 auto *TI = BBToCheck.getTerminator();
848 bool isUnreachable = isa<UnreachableInst>(Val: TI);
849 return !isUnreachable || &*BBToCheck.getFirstNonPHIIt() != TI;
850 };
851
852 SmallVector<int, 4> ExitCaseIndices;
853 for (auto Case : SI.cases())
854 if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor()))
855 ExitCaseIndices.push_back(Elt: Case.getCaseIndex());
856 BasicBlock *DefaultExitBB = nullptr;
857 SwitchInstProfUpdateWrapper::CaseWeightOpt DefaultCaseWeight =
858 SwitchInstProfUpdateWrapper::getSuccessorWeight(SI, idx: 0);
859 if (IsTriviallyUnswitchableExitBlock(*SI.getDefaultDest())) {
860 DefaultExitBB = SI.getDefaultDest();
861 } else if (ExitCaseIndices.empty())
862 return false;
863
864 LLVM_DEBUG(dbgs() << " unswitching trivial switch...\n");
865
866 if (MSSAU && VerifyMemorySSA)
867 MSSAU->getMemorySSA()->verifyMemorySSA();
868
869 // We may need to invalidate SCEVs for the outermost loop reached by any of
870 // the exits.
871 Loop *OuterL = &L;
872
873 if (DefaultExitBB) {
874 // Check the loop containing this exit.
875 Loop *ExitL = getTopMostExitingLoop(ExitBB: DefaultExitBB, LI);
876 if (!ExitL || ExitL->contains(L: OuterL))
877 OuterL = ExitL;
878 }
879 for (unsigned Index : ExitCaseIndices) {
880 auto CaseI = SI.case_begin() + Index;
881 // Compute the outer loop from this exit.
882 Loop *ExitL = getTopMostExitingLoop(ExitBB: CaseI->getCaseSuccessor(), LI);
883 if (!ExitL || ExitL->contains(L: OuterL))
884 OuterL = ExitL;
885 }
886
887 if (SE) {
888 if (OuterL)
889 SE->forgetLoop(L: OuterL);
890 else
891 SE->forgetTopmostLoop(L: &L);
892 }
893
894 if (DefaultExitBB) {
895 // Clear out the default destination temporarily to allow accurate
896 // predecessor lists to be examined below.
897 SI.setDefaultDest(nullptr);
898 }
899
900 // Store the exit cases into a separate data structure and remove them from
901 // the switch.
902 SmallVector<std::tuple<ConstantInt *, BasicBlock *,
903 SwitchInstProfUpdateWrapper::CaseWeightOpt>,
904 4> ExitCases;
905 ExitCases.reserve(N: ExitCaseIndices.size());
906 SwitchInstProfUpdateWrapper SIW(SI);
907 // We walk the case indices backwards so that we remove the last case first
908 // and don't disrupt the earlier indices.
909 for (unsigned Index : reverse(C&: ExitCaseIndices)) {
910 auto CaseI = SI.case_begin() + Index;
911 // Save the value of this case.
912 auto W = SIW.getSuccessorWeight(idx: CaseI->getSuccessorIndex());
913 ExitCases.emplace_back(Args: CaseI->getCaseValue(), Args: CaseI->getCaseSuccessor(), Args&: W);
914 // Delete the unswitched cases.
915 SIW.removeCase(I: CaseI);
916 }
917
918 // Check if after this all of the remaining cases point at the same
919 // successor.
920 BasicBlock *CommonSuccBB = nullptr;
921 if (SI.getNumCases() > 0 &&
922 all_of(Range: drop_begin(RangeOrContainer: SI.cases()), P: [&SI](const SwitchInst::CaseHandle &Case) {
923 return Case.getCaseSuccessor() == SI.case_begin()->getCaseSuccessor();
924 }))
925 CommonSuccBB = SI.case_begin()->getCaseSuccessor();
926 if (!DefaultExitBB) {
927 // If we're not unswitching the default, we need it to match any cases to
928 // have a common successor or if we have no cases it is the common
929 // successor.
930 if (SI.getNumCases() == 0)
931 CommonSuccBB = SI.getDefaultDest();
932 else if (SI.getDefaultDest() != CommonSuccBB)
933 CommonSuccBB = nullptr;
934 }
935
936 // Split the preheader, so that we know that there is a safe place to insert
937 // the switch.
938 BasicBlock *OldPH = L.getLoopPreheader();
939 BasicBlock *NewPH = SplitEdge(From: OldPH, To: L.getHeader(), DT: &DT, LI: &LI, MSSAU);
940 OldPH->getTerminator()->eraseFromParent();
941
942 // Now add the unswitched switch. This new switch instruction inherits the
943 // debug location of the old switch, because it semantically replace the old
944 // one.
945 auto *NewSI = SwitchInst::Create(Value: LoopCond, Default: NewPH, NumCases: ExitCases.size(), InsertBefore: OldPH);
946 NewSI->setDebugLoc(SIW->getDebugLoc());
947 SwitchInstProfUpdateWrapper NewSIW(*NewSI);
948
949 // Rewrite the IR for the unswitched basic blocks. This requires two steps.
950 // First, we split any exit blocks with remaining in-loop predecessors. Then
951 // we update the PHIs in one of two ways depending on if there was a split.
952 // We walk in reverse so that we split in the same order as the cases
953 // appeared. This is purely for convenience of reading the resulting IR, but
954 // it doesn't cost anything really.
955 SmallPtrSet<BasicBlock *, 2> UnswitchedExitBBs;
956 SmallDenseMap<BasicBlock *, BasicBlock *, 2> SplitExitBBMap;
957 // Handle the default exit if necessary.
958 // FIXME: It'd be great if we could merge this with the loop below but LLVM's
959 // ranges aren't quite powerful enough yet.
960 if (DefaultExitBB) {
961 if (pred_empty(BB: DefaultExitBB)) {
962 UnswitchedExitBBs.insert(Ptr: DefaultExitBB);
963 rewritePHINodesForUnswitchedExitBlock(L, UnswitchedBB&: *DefaultExitBB, OldExitingBB&: *ParentBB,
964 OldPH&: *OldPH);
965 } else {
966 auto *SplitBB =
967 SplitBlock(Old: DefaultExitBB, SplitPt: DefaultExitBB->begin(), DT: &DT, LI: &LI, MSSAU);
968 rewritePHINodesForExitAndUnswitchedBlocks(L, ExitBB&: *DefaultExitBB, UnswitchedBB&: *SplitBB,
969 OldExitingBB&: *ParentBB, OldPH&: *OldPH,
970 /*FullUnswitch*/ true);
971 DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
972 }
973 }
974 // Note that we must use a reference in the for loop so that we update the
975 // container.
976 for (auto &ExitCase : reverse(C&: ExitCases)) {
977 // Grab a reference to the exit block in the pair so that we can update it.
978 BasicBlock *ExitBB = std::get<1>(t&: ExitCase);
979
980 // If this case is the last edge into the exit block, we can simply reuse it
981 // as it will no longer be a loop exit. No mapping necessary.
982 if (pred_empty(BB: ExitBB)) {
983 // Only rewrite once.
984 if (UnswitchedExitBBs.insert(Ptr: ExitBB).second)
985 rewritePHINodesForUnswitchedExitBlock(L, UnswitchedBB&: *ExitBB, OldExitingBB&: *ParentBB, OldPH&: *OldPH);
986 continue;
987 }
988
989 // Otherwise we need to split the exit block so that we retain an exit
990 // block from the loop and a target for the unswitched condition.
991 BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
992 if (!SplitExitBB) {
993 // If this is the first time we see this, do the split and remember it.
994 SplitExitBB = SplitBlock(Old: ExitBB, SplitPt: ExitBB->begin(), DT: &DT, LI: &LI, MSSAU);
995 rewritePHINodesForExitAndUnswitchedBlocks(L, ExitBB&: *ExitBB, UnswitchedBB&: *SplitExitBB,
996 OldExitingBB&: *ParentBB, OldPH&: *OldPH,
997 /*FullUnswitch*/ true);
998 }
999 // Update the case pair to point to the split block.
1000 std::get<1>(t&: ExitCase) = SplitExitBB;
1001 }
1002
1003 // Now add the unswitched cases. We do this in reverse order as we built them
1004 // in reverse order.
1005 for (auto &ExitCase : reverse(C&: ExitCases)) {
1006 ConstantInt *CaseVal = std::get<0>(t&: ExitCase);
1007 BasicBlock *UnswitchedBB = std::get<1>(t&: ExitCase);
1008
1009 NewSIW.addCase(OnVal: CaseVal, Dest: UnswitchedBB, W: std::get<2>(t&: ExitCase));
1010 }
1011
1012 // If the default was unswitched, re-point it and add explicit cases for
1013 // entering the loop.
1014 if (DefaultExitBB) {
1015 NewSIW->setDefaultDest(DefaultExitBB);
1016 NewSIW.setSuccessorWeight(idx: 0, W: DefaultCaseWeight);
1017
1018 // We removed all the exit cases, so we just copy the cases to the
1019 // unswitched switch.
1020 for (const auto &Case : SI.cases())
1021 NewSIW.addCase(OnVal: Case.getCaseValue(), Dest: NewPH,
1022 W: SIW.getSuccessorWeight(idx: Case.getSuccessorIndex()));
1023 } else if (DefaultCaseWeight) {
1024 // We have to set branch weight of the default case.
1025 uint64_t SW = *DefaultCaseWeight;
1026 for (const auto &Case : SI.cases()) {
1027 auto W = SIW.getSuccessorWeight(idx: Case.getSuccessorIndex());
1028 assert(W &&
1029 "case weight must be defined as default case weight is defined");
1030 SW += *W;
1031 }
1032 NewSIW.setSuccessorWeight(idx: 0, W: SW);
1033 }
1034
1035 // If we ended up with a common successor for every path through the switch
1036 // after unswitching, rewrite it to an unconditional branch to make it easy
1037 // to recognize. Otherwise we potentially have to recognize the default case
1038 // pointing at unreachable and other complexity.
1039 if (CommonSuccBB) {
1040 BasicBlock *BB = SI.getParent();
1041 // We may have had multiple edges to this common successor block, so remove
1042 // them as predecessors. We skip the first one, either the default or the
1043 // actual first case.
1044 bool SkippedFirst = DefaultExitBB == nullptr;
1045 for (auto Case : SI.cases()) {
1046 assert(Case.getCaseSuccessor() == CommonSuccBB &&
1047 "Non-common successor!");
1048 (void)Case;
1049 if (!SkippedFirst) {
1050 SkippedFirst = true;
1051 continue;
1052 }
1053 CommonSuccBB->removePredecessor(Pred: BB,
1054 /*KeepOneInputPHIs*/ true);
1055 }
1056 // Now nuke the switch and replace it with a direct branch.
1057 Instruction *NewBI = UncondBrInst::Create(Target: CommonSuccBB, InsertBefore: BB);
1058 NewBI->setDebugLoc(SIW->getDebugLoc());
1059 SIW.eraseFromParent();
1060 } else if (DefaultExitBB) {
1061 assert(SI.getNumCases() > 0 &&
1062 "If we had no cases we'd have a common successor!");
1063 // Move the last case to the default successor. This is valid as if the
1064 // default got unswitched it cannot be reached. This has the advantage of
1065 // being simple and keeping the number of edges from this switch to
1066 // successors the same, and avoiding any PHI update complexity.
1067 auto LastCaseI = std::prev(x: SI.case_end());
1068
1069 SI.setDefaultDest(LastCaseI->getCaseSuccessor());
1070 SIW.setSuccessorWeight(
1071 idx: 0, W: SIW.getSuccessorWeight(idx: LastCaseI->getSuccessorIndex()));
1072 SIW.removeCase(I: LastCaseI);
1073 }
1074
1075 // Walk the unswitched exit blocks and the unswitched split blocks and update
1076 // the dominator tree based on the CFG edits. While we are walking unordered
1077 // containers here, the API for applyUpdates takes an unordered list of
1078 // updates and requires them to not contain duplicates.
1079 SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
1080 for (auto *UnswitchedExitBB : UnswitchedExitBBs) {
1081 DTUpdates.push_back(Elt: {DT.Delete, ParentBB, UnswitchedExitBB});
1082 DTUpdates.push_back(Elt: {DT.Insert, OldPH, UnswitchedExitBB});
1083 }
1084 for (auto SplitUnswitchedPair : SplitExitBBMap) {
1085 DTUpdates.push_back(Elt: {DT.Delete, ParentBB, SplitUnswitchedPair.first});
1086 DTUpdates.push_back(Elt: {DT.Insert, OldPH, SplitUnswitchedPair.second});
1087 }
1088
1089 if (MSSAU) {
1090 MSSAU->applyUpdates(Updates: DTUpdates, DT, /*UpdateDT=*/UpdateDTFirst: true);
1091 if (VerifyMemorySSA)
1092 MSSAU->getMemorySSA()->verifyMemorySSA();
1093 } else {
1094 DT.applyUpdates(Updates: DTUpdates);
1095 }
1096
1097 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1098
1099 // We may have changed the nesting relationship for this loop so hoist it to
1100 // its correct parent if needed.
1101 hoistLoopToNewParent(L, Preheader&: *NewPH, DT, LI, MSSAU, SE);
1102
1103 if (MSSAU && VerifyMemorySSA)
1104 MSSAU->getMemorySSA()->verifyMemorySSA();
1105
1106 ++NumTrivial;
1107 ++NumSwitches;
1108 LLVM_DEBUG(dbgs() << " done: unswitching trivial switch...\n");
1109 return true;
1110}
1111
1112/// This routine scans the loop to find a branch or switch which occurs before
1113/// any side effects occur. These can potentially be unswitched without
1114/// duplicating the loop. If a branch or switch is successfully unswitched the
1115/// scanning continues to see if subsequent branches or switches have become
1116/// trivial. Once all trivial candidates have been unswitched, this routine
1117/// returns.
1118///
1119/// The return value indicates whether anything was unswitched (and therefore
1120/// changed).
1121///
1122/// If `SE` is not null, it will be updated based on the potential loop SCEVs
1123/// invalidated by this.
1124static bool unswitchAllTrivialConditions(const ScalarOptions &Opts, Loop &L,
1125 DominatorTree &DT, LoopInfo &LI,
1126 ScalarEvolution *SE,
1127 MemorySSAUpdater *MSSAU) {
1128 bool Changed = false;
1129
1130 // If loop header has only one reachable successor we should keep looking for
1131 // trivial condition candidates in the successor as well. An alternative is
1132 // to constant fold conditions and merge successors into loop header (then we
1133 // only need to check header's terminator). The reason for not doing this in
1134 // LoopUnswitch pass is that it could potentially break LoopPassManager's
1135 // invariants. Folding dead branches could either eliminate the current loop
1136 // or make other loops unreachable. LCSSA form might also not be preserved
1137 // after deleting branches. The following code keeps traversing loop header's
1138 // successors until it finds the trivial condition candidate (condition that
1139 // is not a constant). Since unswitching generates branches with constant
1140 // conditions, this scenario could be very common in practice.
1141 BasicBlock *CurrentBB = L.getHeader();
1142 SmallPtrSet<BasicBlock *, 8> Visited;
1143 Visited.insert(Ptr: CurrentBB);
1144 do {
1145 // Check if there are any side-effecting instructions (e.g. stores, calls,
1146 // volatile loads) in the part of the loop that the code *would* execute
1147 // without unswitching.
1148 if (MSSAU) // Possible early exit with MSSA
1149 if (auto *Defs = MSSAU->getMemorySSA()->getBlockDefs(BB: CurrentBB))
1150 if (!isa<MemoryPhi>(Val: *Defs->begin()) || (++Defs->begin() != Defs->end()))
1151 return Changed;
1152 if (llvm::any_of(Range&: *CurrentBB, P: [](Instruction &I) {
1153 if (const auto *CB = dyn_cast<CallBase>(Val: &I))
1154 if (CB->isConvergent())
1155 return true;
1156 return I.mayHaveSideEffects() && !I.isDroppable();
1157 }))
1158 return Changed;
1159
1160 Instruction *CurrentTerm = CurrentBB->getTerminator();
1161
1162 if (auto *SI = dyn_cast<SwitchInst>(Val: CurrentTerm)) {
1163 // Don't bother trying to unswitch past a switch with a constant
1164 // condition. This should be removed prior to running this pass by
1165 // simplifycfg.
1166 if (isa<Constant>(Val: SI->getCondition()))
1167 return Changed;
1168
1169 if (!unswitchTrivialSwitch(L, SI&: *SI, DT, LI, SE, MSSAU))
1170 // Couldn't unswitch this one so we're done.
1171 return Changed;
1172
1173 // Mark that we managed to unswitch something.
1174 Changed = true;
1175
1176 // If unswitching turned the terminator into an unconditional branch then
1177 // we can continue. The unswitching logic specifically works to fold any
1178 // cases it can into an unconditional branch to make it easier to
1179 // recognize here.
1180 auto *BI = dyn_cast<UncondBrInst>(Val: CurrentBB->getTerminator());
1181 if (!BI)
1182 return Changed;
1183
1184 CurrentBB = BI->getSuccessor();
1185 continue;
1186 }
1187
1188 auto *BI = dyn_cast<CondBrInst>(Val: CurrentTerm);
1189 if (!BI)
1190 // We do not understand other terminator instructions.
1191 return Changed;
1192
1193 // Don't bother trying to unswitch past an unconditional branch or a branch
1194 // with a constant value. These should be removed by simplifycfg prior to
1195 // running this pass.
1196 if (isa<Constant>(Val: skipTrivialSelect(Cond: BI->getCondition())))
1197 return Changed;
1198
1199 // Found a trivial condition candidate: non-foldable conditional branch. If
1200 // we fail to unswitch this, we can't do anything else that is trivial.
1201 if (!unswitchTrivialBranch(Opts, L, BI&: *BI, DT, LI, SE, MSSAU))
1202 return Changed;
1203
1204 // Mark that we managed to unswitch something.
1205 Changed = true;
1206
1207 // If we only unswitched some of the conditions feeding the branch, we won't
1208 // have collapsed it to a single successor.
1209 if (isa<CondBrInst>(Val: CurrentBB->getTerminator()))
1210 return Changed;
1211
1212 // Follow the newly unconditional branch into its successor.
1213 CurrentBB = cast<UncondBrInst>(Val: CurrentBB->getTerminator())->getSuccessor();
1214
1215 // When continuing, if we exit the loop or reach a previous visited block,
1216 // then we can not reach any trivial condition candidates (unfoldable
1217 // branch instructions or switch instructions) and no unswitch can happen.
1218 } while (L.contains(BB: CurrentBB) && Visited.insert(Ptr: CurrentBB).second);
1219
1220 return Changed;
1221}
1222
1223/// Build the cloned blocks for an unswitched copy of the given loop.
1224///
1225/// The cloned blocks are inserted before the loop preheader (`LoopPH`) and
1226/// after the split block (`SplitBB`) that will be used to select between the
1227/// cloned and original loop.
1228///
1229/// This routine handles cloning all of the necessary loop blocks and exit
1230/// blocks including rewriting their instructions and the relevant PHI nodes.
1231/// Any loop blocks or exit blocks which are dominated by a different successor
1232/// than the one for this clone of the loop blocks can be trivially skipped. We
1233/// use the `DominatingSucc` map to determine whether a block satisfies that
1234/// property with a simple map lookup.
1235///
1236/// It also correctly creates the unconditional branch in the cloned
1237/// unswitched parent block to only point at the unswitched successor.
1238///
1239/// This does not handle most of the necessary updates to `LoopInfo`. Only exit
1240/// block splitting is correctly reflected in `LoopInfo`, essentially all of
1241/// the cloned blocks (and their loops) are left without full `LoopInfo`
1242/// updates. This also doesn't fully update `DominatorTree`. It adds the cloned
1243/// blocks to them but doesn't create the cloned `DominatorTree` structure and
1244/// instead the caller must recompute an accurate DT. It *does* correctly
1245/// update the `AssumptionCache` provided in `AC`.
1246static BasicBlock *buildClonedLoopBlocks(
1247 Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB,
1248 ArrayRef<BasicBlock *> ExitBlocks, BasicBlock *ParentBB,
1249 BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB,
1250 const SmallDenseMap<BasicBlock *, BasicBlock *, 16> &DominatingSucc,
1251 ValueToValueMapTy &VMap,
1252 SmallVectorImpl<DominatorTree::UpdateType> &DTUpdates, AssumptionCache &AC,
1253 DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU,
1254 ScalarEvolution *SE) {
1255 SmallVector<BasicBlock *, 4> NewBlocks;
1256 NewBlocks.reserve(N: L.getNumBlocks() + ExitBlocks.size());
1257
1258 // We will need to clone a bunch of blocks, wrap up the clone operation in
1259 // a helper.
1260 auto CloneBlock = [&](BasicBlock *OldBB) {
1261 // Clone the basic block and insert it before the new preheader.
1262 BasicBlock *NewBB = CloneBasicBlock(BB: OldBB, VMap, NameSuffix: ".us", F: OldBB->getParent());
1263 NewBB->moveBefore(MovePos: LoopPH);
1264
1265 // Record this block and the mapping.
1266 NewBlocks.push_back(Elt: NewBB);
1267 VMap[OldBB] = NewBB;
1268
1269 return NewBB;
1270 };
1271
1272 // We skip cloning blocks when they have a dominating succ that is not the
1273 // succ we are cloning for.
1274 auto SkipBlock = [&](BasicBlock *BB) {
1275 auto It = DominatingSucc.find(Val: BB);
1276 return It != DominatingSucc.end() && It->second != UnswitchedSuccBB;
1277 };
1278
1279 // First, clone the preheader.
1280 auto *ClonedPH = CloneBlock(LoopPH);
1281
1282 // Then clone all the loop blocks, skipping the ones that aren't necessary.
1283 for (auto *LoopBB : L.blocks())
1284 if (!SkipBlock(LoopBB))
1285 CloneBlock(LoopBB);
1286
1287 // Split all the loop exit edges so that when we clone the exit blocks, if
1288 // any of the exit blocks are *also* a preheader for some other loop, we
1289 // don't create multiple predecessors entering the loop header.
1290 for (auto *ExitBB : ExitBlocks) {
1291 if (SkipBlock(ExitBB))
1292 continue;
1293
1294 // When we are going to clone an exit, we don't need to clone all the
1295 // instructions in the exit block and we want to ensure we have an easy
1296 // place to merge the CFG, so split the exit first. This is always safe to
1297 // do because there cannot be any non-loop predecessors of a loop exit in
1298 // loop simplified form.
1299 auto *MergeBB = SplitBlock(Old: ExitBB, SplitPt: ExitBB->begin(), DT: &DT, LI: &LI, MSSAU);
1300
1301 // Rearrange the names to make it easier to write test cases by having the
1302 // exit block carry the suffix rather than the merge block carrying the
1303 // suffix.
1304 MergeBB->takeName(V: ExitBB);
1305 ExitBB->setName(Twine(MergeBB->getName()) + ".split");
1306
1307 // Now clone the original exit block.
1308 auto *ClonedExitBB = CloneBlock(ExitBB);
1309 assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 &&
1310 "Exit block should have been split to have one successor!");
1311 assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB &&
1312 "Cloned exit block has the wrong successor!");
1313
1314 // Remap any cloned instructions and create a merge phi node for them.
1315 for (auto ZippedInsts : llvm::zip_first(
1316 t: llvm::make_range(x: ExitBB->begin(), y: std::prev(x: ExitBB->end())),
1317 u: llvm::make_range(x: ClonedExitBB->begin(),
1318 y: std::prev(x: ClonedExitBB->end())))) {
1319 Instruction &I = std::get<0>(t&: ZippedInsts);
1320 Instruction &ClonedI = std::get<1>(t&: ZippedInsts);
1321
1322 // The only instructions in the exit block should be PHI nodes and
1323 // potentially a landing pad.
1324 assert(
1325 (isa<PHINode>(I) || isa<LandingPadInst>(I) || isa<CatchPadInst>(I)) &&
1326 "Bad instruction in exit block!");
1327 // We should have a value map between the instruction and its clone.
1328 assert(VMap.lookup(&I) == &ClonedI && "Mismatch in the value map!");
1329
1330 // Forget SCEVs based on exit phis in case SCEV looked through the phi.
1331 if (SE)
1332 if (auto *PN = dyn_cast<PHINode>(Val: &I))
1333 SE->forgetLcssaPhiWithNewPredecessor(L: &L, V: PN);
1334
1335 BasicBlock::iterator InsertPt = MergeBB->getFirstInsertionPt();
1336
1337 auto *MergePN =
1338 PHINode::Create(Ty: I.getType(), /*NumReservedValues*/ 2, NameStr: ".us-phi");
1339 MergePN->insertBefore(InsertPos: InsertPt);
1340 MergePN->setDebugLoc(InsertPt->getDebugLoc());
1341 I.replaceAllUsesWith(V: MergePN);
1342 MergePN->addIncoming(V: &I, BB: ExitBB);
1343 MergePN->addIncoming(V: &ClonedI, BB: ClonedExitBB);
1344 }
1345 }
1346
1347 // Rewrite the instructions in the cloned blocks to refer to the instructions
1348 // in the cloned blocks. We have to do this as a second pass so that we have
1349 // everything available. Also, we have inserted new instructions which may
1350 // include assume intrinsics, so we update the assumption cache while
1351 // processing this.
1352 Module *M = ClonedPH->getParent()->getParent();
1353 for (auto *ClonedBB : NewBlocks)
1354 for (Instruction &I : *ClonedBB) {
1355 RemapDbgRecordRange(M, Range: I.getDbgRecordRange(), VM&: VMap,
1356 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1357 RemapInstruction(I: &I, VM&: VMap,
1358 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1359 if (auto *II = dyn_cast<AssumeInst>(Val: &I))
1360 AC.registerAssumption(CI: II);
1361 }
1362
1363 // Update any PHI nodes in the cloned successors of the skipped blocks to not
1364 // have spurious incoming values.
1365 for (auto *LoopBB : L.blocks())
1366 if (SkipBlock(LoopBB))
1367 for (auto *SuccBB : successors(BB: LoopBB))
1368 if (auto *ClonedSuccBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: SuccBB)))
1369 for (PHINode &PN : ClonedSuccBB->phis())
1370 PN.removeIncomingValue(BB: LoopBB, /*DeletePHIIfEmpty*/ false);
1371
1372 // Remove the cloned parent as a predecessor of any successor we ended up
1373 // cloning other than the unswitched one.
1374 auto *ClonedParentBB = cast<BasicBlock>(Val: VMap.lookup(Val: ParentBB));
1375 for (auto *SuccBB : successors(BB: ParentBB)) {
1376 if (SuccBB == UnswitchedSuccBB)
1377 continue;
1378
1379 auto *ClonedSuccBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: SuccBB));
1380 if (!ClonedSuccBB)
1381 continue;
1382
1383 ClonedSuccBB->removePredecessor(Pred: ClonedParentBB,
1384 /*KeepOneInputPHIs*/ true);
1385 }
1386
1387 // Replace the cloned branch with an unconditional branch to the cloned
1388 // unswitched successor.
1389 auto *ClonedSuccBB = cast<BasicBlock>(Val: VMap.lookup(Val: UnswitchedSuccBB));
1390 Instruction *ClonedTerminator = ClonedParentBB->getTerminator();
1391 // Trivial Simplification. If Terminator is a conditional branch and
1392 // condition becomes dead - erase it.
1393 Value *ClonedConditionToErase = nullptr;
1394 if (auto *BI = dyn_cast<CondBrInst>(Val: ClonedTerminator))
1395 ClonedConditionToErase = BI->getCondition();
1396 else if (auto *SI = dyn_cast<SwitchInst>(Val: ClonedTerminator))
1397 ClonedConditionToErase = SI->getCondition();
1398
1399 Instruction *BI = UncondBrInst::Create(Target: ClonedSuccBB, InsertBefore: ClonedParentBB);
1400 BI->setDebugLoc(ClonedTerminator->getDebugLoc());
1401 ClonedTerminator->eraseFromParent();
1402
1403 if (ClonedConditionToErase)
1404 RecursivelyDeleteTriviallyDeadInstructions(V: ClonedConditionToErase, TLI: nullptr,
1405 MSSAU);
1406
1407 // If there are duplicate entries in the PHI nodes because of multiple edges
1408 // to the unswitched successor, we need to nuke all but one as we replaced it
1409 // with a direct branch.
1410 for (PHINode &PN : ClonedSuccBB->phis()) {
1411 bool Found = false;
1412 // Loop over the incoming operands backwards so we can easily delete as we
1413 // go without invalidating the index.
1414 for (int i = PN.getNumOperands() - 1; i >= 0; --i) {
1415 if (PN.getIncomingBlock(i) != ClonedParentBB)
1416 continue;
1417 if (!Found) {
1418 Found = true;
1419 continue;
1420 }
1421 PN.removeIncomingValue(Idx: i, /*DeletePHIIfEmpty*/ false);
1422 }
1423 }
1424
1425 // Record the domtree updates for the new blocks.
1426 SmallPtrSet<BasicBlock *, 4> SuccSet;
1427 for (auto *ClonedBB : NewBlocks) {
1428 for (auto *SuccBB : successors(BB: ClonedBB))
1429 if (SuccSet.insert(Ptr: SuccBB).second)
1430 DTUpdates.push_back(Elt: {DominatorTree::Insert, ClonedBB, SuccBB});
1431 SuccSet.clear();
1432 }
1433
1434 return ClonedPH;
1435}
1436
1437/// Recursively clone the specified loop and all of its children.
1438///
1439/// The target parent loop for the clone should be provided, or can be null if
1440/// the clone is a top-level loop. While cloning, all the blocks are mapped
1441/// with the provided value map. The entire original loop must be present in
1442/// the value map. The cloned loop is returned.
1443static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL,
1444 const ValueToValueMapTy &VMap, LoopInfo &LI) {
1445 auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) {
1446 assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!");
1447 ClonedL.reserveBlocks(Size: OrigL.getNumBlocks());
1448 for (auto *BB : OrigL.blocks()) {
1449 auto *ClonedBB = cast<BasicBlock>(Val: VMap.lookup(Val: BB));
1450 ClonedL.addBlockEntry(BB: ClonedBB);
1451 if (LI.getLoopFor(BB) == &OrigL)
1452 LI.changeLoopFor(BB: ClonedBB, L: &ClonedL);
1453 }
1454 };
1455
1456 // We specially handle the first loop because it may get cloned into
1457 // a different parent and because we most commonly are cloning leaf loops.
1458 Loop *ClonedRootL = LI.AllocateLoop();
1459 if (RootParentL)
1460 RootParentL->addChildLoop(NewChild: ClonedRootL);
1461 else
1462 LI.addTopLevelLoop(New: ClonedRootL);
1463 AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
1464
1465 if (OrigRootL.isInnermost())
1466 return ClonedRootL;
1467
1468 // If we have a nest, we can quickly clone the entire loop nest using an
1469 // iterative approach because it is a tree. We keep the cloned parent in the
1470 // data structure to avoid repeatedly querying through a map to find it.
1471 SmallVector<std::pair<Loop *, Loop *>, 16> LoopsToClone;
1472 // Build up the loops to clone in reverse order as we'll clone them from the
1473 // back.
1474 for (Loop *ChildL : llvm::reverse(C&: OrigRootL))
1475 LoopsToClone.push_back(Elt: {ClonedRootL, ChildL});
1476 do {
1477 Loop *ClonedParentL, *L;
1478 std::tie(args&: ClonedParentL, args&: L) = LoopsToClone.pop_back_val();
1479 Loop *ClonedL = LI.AllocateLoop();
1480 ClonedParentL->addChildLoop(NewChild: ClonedL);
1481 AddClonedBlocksToLoop(*L, *ClonedL);
1482 for (Loop *ChildL : llvm::reverse(C&: *L))
1483 LoopsToClone.push_back(Elt: {ClonedL, ChildL});
1484 } while (!LoopsToClone.empty());
1485
1486 return ClonedRootL;
1487}
1488
1489/// Build the cloned loops of an original loop from unswitching.
1490///
1491/// Because unswitching simplifies the CFG of the loop, this isn't a trivial
1492/// operation. We need to re-verify that there even is a loop (as the backedge
1493/// may not have been cloned), and even if there are remaining backedges the
1494/// backedge set may be different. However, we know that each child loop is
1495/// undisturbed, we only need to find where to place each child loop within
1496/// either any parent loop or within a cloned version of the original loop.
1497///
1498/// Because child loops may end up cloned outside of any cloned version of the
1499/// original loop, multiple cloned sibling loops may be created. All of them
1500/// are returned so that the newly introduced loop nest roots can be
1501/// identified.
1502static void buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks,
1503 const ValueToValueMapTy &VMap, LoopInfo &LI,
1504 SmallVectorImpl<Loop *> &NonChildClonedLoops) {
1505 Loop *ClonedL = nullptr;
1506
1507 auto *OrigPH = OrigL.getLoopPreheader();
1508 auto *OrigHeader = OrigL.getHeader();
1509
1510 auto *ClonedPH = cast<BasicBlock>(Val: VMap.lookup(Val: OrigPH));
1511 auto *ClonedHeader = cast<BasicBlock>(Val: VMap.lookup(Val: OrigHeader));
1512
1513 // We need to know the loops of the cloned exit blocks to even compute the
1514 // accurate parent loop. If we only clone exits to some parent of the
1515 // original parent, we want to clone into that outer loop. We also keep track
1516 // of the loops that our cloned exit blocks participate in.
1517 Loop *ParentL = nullptr;
1518 SmallVector<BasicBlock *, 4> ClonedExitsInLoops;
1519 SmallDenseMap<BasicBlock *, Loop *, 16> ExitLoopMap;
1520 ClonedExitsInLoops.reserve(N: ExitBlocks.size());
1521 for (auto *ExitBB : ExitBlocks)
1522 if (auto *ClonedExitBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: ExitBB)))
1523 if (Loop *ExitL = LI.getLoopFor(BB: ExitBB)) {
1524 ExitLoopMap[ClonedExitBB] = ExitL;
1525 ClonedExitsInLoops.push_back(Elt: ClonedExitBB);
1526 if (!ParentL || (ParentL != ExitL && ParentL->contains(L: ExitL)))
1527 ParentL = ExitL;
1528 }
1529 assert((!ParentL || ParentL == OrigL.getParentLoop() ||
1530 ParentL->contains(OrigL.getParentLoop())) &&
1531 "The computed parent loop should always contain (or be) the parent of "
1532 "the original loop.");
1533
1534 // We build the set of blocks dominated by the cloned header from the set of
1535 // cloned blocks out of the original loop. While not all of these will
1536 // necessarily be in the cloned loop, it is enough to establish that they
1537 // aren't in unreachable cycles, etc.
1538 SmallSetVector<BasicBlock *, 16> ClonedLoopBlocks;
1539 for (auto *BB : OrigL.blocks())
1540 if (auto *ClonedBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: BB)))
1541 ClonedLoopBlocks.insert(X: ClonedBB);
1542
1543 // Rebuild the set of blocks that will end up in the cloned loop. We may have
1544 // skipped cloning some region of this loop which can in turn skip some of
1545 // the backedges so we have to rebuild the blocks in the loop based on the
1546 // backedges that remain after cloning.
1547 SmallVector<BasicBlock *, 16> Worklist;
1548 SmallPtrSet<BasicBlock *, 16> BlocksInClonedLoop;
1549 for (auto *Pred : predecessors(BB: ClonedHeader)) {
1550 // The only possible non-loop header predecessor is the preheader because
1551 // we know we cloned the loop in simplified form.
1552 if (Pred == ClonedPH)
1553 continue;
1554
1555 // Because the loop was in simplified form, the only non-loop predecessor
1556 // should be the preheader.
1557 assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop "
1558 "header other than the preheader "
1559 "that is not part of the loop!");
1560
1561 // Insert this block into the loop set and on the first visit (and if it
1562 // isn't the header we're currently walking) put it into the worklist to
1563 // recurse through.
1564 if (BlocksInClonedLoop.insert(Ptr: Pred).second && Pred != ClonedHeader)
1565 Worklist.push_back(Elt: Pred);
1566 }
1567
1568 // If we had any backedges then there *is* a cloned loop. Put the header into
1569 // the loop set and then walk the worklist backwards to find all the blocks
1570 // that remain within the loop after cloning.
1571 if (!BlocksInClonedLoop.empty()) {
1572 BlocksInClonedLoop.insert(Ptr: ClonedHeader);
1573
1574 while (!Worklist.empty()) {
1575 BasicBlock *BB = Worklist.pop_back_val();
1576 assert(BlocksInClonedLoop.count(BB) &&
1577 "Didn't put block into the loop set!");
1578
1579 // Insert any predecessors that are in the possible set into the cloned
1580 // set, and if the insert is successful, add them to the worklist. Note
1581 // that we filter on the blocks that are definitely reachable via the
1582 // backedge to the loop header so we may prune out dead code within the
1583 // cloned loop.
1584 for (auto *Pred : predecessors(BB))
1585 if (ClonedLoopBlocks.count(key: Pred) &&
1586 BlocksInClonedLoop.insert(Ptr: Pred).second)
1587 Worklist.push_back(Elt: Pred);
1588 }
1589
1590 ClonedL = LI.AllocateLoop();
1591 if (ParentL) {
1592 ParentL->addBasicBlockToLoop(NewBB: ClonedPH, LI);
1593 ParentL->addChildLoop(NewChild: ClonedL);
1594 } else {
1595 LI.addTopLevelLoop(New: ClonedL);
1596 }
1597 NonChildClonedLoops.push_back(Elt: ClonedL);
1598
1599 ClonedL->reserveBlocks(Size: BlocksInClonedLoop.size());
1600 // We don't want to just add the cloned loop blocks based on how we
1601 // discovered them. The original order of blocks was carefully built in
1602 // a way that doesn't rely on predecessor ordering. Rather than re-invent
1603 // that logic, we just re-walk the original blocks (and those of the child
1604 // loops) and filter them as we add them into the cloned loop.
1605 for (auto *BB : OrigL.blocks()) {
1606 auto *ClonedBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: BB));
1607 if (!ClonedBB || !BlocksInClonedLoop.count(Ptr: ClonedBB))
1608 continue;
1609
1610 // Directly add the blocks that are only in this loop.
1611 if (LI.getLoopFor(BB) == &OrigL) {
1612 ClonedL->addBasicBlockToLoop(NewBB: ClonedBB, LI);
1613 continue;
1614 }
1615
1616 // We want to manually add it to this loop and parents.
1617 // Registering it with LoopInfo will happen when we clone the top
1618 // loop for this block.
1619 for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop())
1620 PL->addBlockEntry(BB: ClonedBB);
1621 }
1622
1623 // Now add each child loop whose header remains within the cloned loop. All
1624 // of the blocks within the loop must satisfy the same constraints as the
1625 // header so once we pass the header checks we can just clone the entire
1626 // child loop nest.
1627 for (Loop *ChildL : OrigL) {
1628 auto *ClonedChildHeader =
1629 cast_or_null<BasicBlock>(Val: VMap.lookup(Val: ChildL->getHeader()));
1630 if (!ClonedChildHeader || !BlocksInClonedLoop.count(Ptr: ClonedChildHeader))
1631 continue;
1632
1633#ifndef NDEBUG
1634 // We should never have a cloned child loop header but fail to have
1635 // all of the blocks for that child loop.
1636 for (auto *ChildLoopBB : ChildL->blocks())
1637 assert(BlocksInClonedLoop.count(
1638 cast<BasicBlock>(VMap.lookup(ChildLoopBB))) &&
1639 "Child cloned loop has a header within the cloned outer "
1640 "loop but not all of its blocks!");
1641#endif
1642
1643 cloneLoopNest(OrigRootL&: *ChildL, RootParentL: ClonedL, VMap, LI);
1644 }
1645 }
1646
1647 // Now that we've handled all the components of the original loop that were
1648 // cloned into a new loop, we still need to handle anything from the original
1649 // loop that wasn't in a cloned loop.
1650
1651 // Figure out what blocks are left to place within any loop nest containing
1652 // the unswitched loop. If we never formed a loop, the cloned PH is one of
1653 // them.
1654 SmallPtrSet<BasicBlock *, 16> UnloopedBlockSet;
1655 if (BlocksInClonedLoop.empty())
1656 UnloopedBlockSet.insert(Ptr: ClonedPH);
1657 for (auto *ClonedBB : ClonedLoopBlocks)
1658 if (!BlocksInClonedLoop.count(Ptr: ClonedBB))
1659 UnloopedBlockSet.insert(Ptr: ClonedBB);
1660
1661 // Copy the cloned exits and sort them in ascending loop depth, we'll work
1662 // backwards across these to process them inside out. The order shouldn't
1663 // matter as we're just trying to build up the map from inside-out; we use
1664 // the map in a more stably ordered way below.
1665 auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
1666 llvm::sort(C&: OrderedClonedExitsInLoops, Comp: [&](BasicBlock *LHS, BasicBlock *RHS) {
1667 return ExitLoopMap.lookup(Val: LHS)->getLoopDepth() <
1668 ExitLoopMap.lookup(Val: RHS)->getLoopDepth();
1669 });
1670
1671 // Populate the existing ExitLoopMap with everything reachable from each
1672 // exit, starting from the inner most exit.
1673 while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) {
1674 assert(Worklist.empty() && "Didn't clear worklist!");
1675
1676 BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
1677 Loop *ExitL = ExitLoopMap.lookup(Val: ExitBB);
1678
1679 // Walk the CFG back until we hit the cloned PH adding everything reachable
1680 // and in the unlooped set to this exit block's loop.
1681 Worklist.push_back(Elt: ExitBB);
1682 do {
1683 BasicBlock *BB = Worklist.pop_back_val();
1684 // We can stop recursing at the cloned preheader (if we get there).
1685 if (BB == ClonedPH)
1686 continue;
1687
1688 for (BasicBlock *PredBB : predecessors(BB)) {
1689 // If this pred has already been moved to our set or is part of some
1690 // (inner) loop, no update needed.
1691 if (!UnloopedBlockSet.erase(Ptr: PredBB)) {
1692 assert(
1693 (BlocksInClonedLoop.count(PredBB) || ExitLoopMap.count(PredBB)) &&
1694 "Predecessor not mapped to a loop!");
1695 continue;
1696 }
1697
1698 // We just insert into the loop set here. We'll add these blocks to the
1699 // exit loop after we build up the set in an order that doesn't rely on
1700 // predecessor order (which in turn relies on use list order).
1701 bool Inserted = ExitLoopMap.insert(KV: {PredBB, ExitL}).second;
1702 (void)Inserted;
1703 assert(Inserted && "Should only visit an unlooped block once!");
1704
1705 // And recurse through to its predecessors.
1706 Worklist.push_back(Elt: PredBB);
1707 }
1708 } while (!Worklist.empty());
1709 }
1710
1711 // Now that the ExitLoopMap gives as mapping for all the non-looping cloned
1712 // blocks to their outer loops, walk the cloned blocks and the cloned exits
1713 // in their original order adding them to the correct loop.
1714
1715 // We need a stable insertion order. We use the order of the original loop
1716 // order and map into the correct parent loop.
1717 for (auto *BB : llvm::concat<BasicBlock *const>(
1718 Ranges: ArrayRef(ClonedPH), Ranges&: ClonedLoopBlocks, Ranges&: ClonedExitsInLoops))
1719 if (Loop *OuterL = ExitLoopMap.lookup(Val: BB))
1720 OuterL->addBasicBlockToLoop(NewBB: BB, LI);
1721
1722#ifndef NDEBUG
1723 for (auto &BBAndL : ExitLoopMap) {
1724 auto *BB = BBAndL.first;
1725 auto *OuterL = BBAndL.second;
1726 assert(LI.getLoopFor(BB) == OuterL &&
1727 "Failed to put all blocks into outer loops!");
1728 }
1729#endif
1730
1731 // Now that all the blocks are placed into the correct containing loop in the
1732 // absence of child loops, find all the potentially cloned child loops and
1733 // clone them into whatever outer loop we placed their header into.
1734 for (Loop *ChildL : OrigL) {
1735 auto *ClonedChildHeader =
1736 cast_or_null<BasicBlock>(Val: VMap.lookup(Val: ChildL->getHeader()));
1737 if (!ClonedChildHeader || BlocksInClonedLoop.count(Ptr: ClonedChildHeader))
1738 continue;
1739
1740#ifndef NDEBUG
1741 for (auto *ChildLoopBB : ChildL->blocks())
1742 assert(VMap.count(ChildLoopBB) &&
1743 "Cloned a child loop header but not all of that loops blocks!");
1744#endif
1745
1746 NonChildClonedLoops.push_back(Elt: cloneLoopNest(
1747 OrigRootL&: *ChildL, RootParentL: ExitLoopMap.lookup(Val: ClonedChildHeader), VMap, LI));
1748 }
1749}
1750
1751static void
1752deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks,
1753 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps,
1754 DominatorTree &DT, MemorySSAUpdater *MSSAU) {
1755 // Find all the dead clones, and remove them from their successors.
1756 SmallVector<BasicBlock *, 16> DeadBlocks;
1757 for (BasicBlock *BB : llvm::concat<BasicBlock *const>(Ranges: L.blocks(), Ranges&: ExitBlocks))
1758 for (const auto &VMap : VMaps)
1759 if (BasicBlock *ClonedBB = cast_or_null<BasicBlock>(Val: VMap->lookup(Val: BB)))
1760 if (!DT.isReachableFromEntry(A: ClonedBB)) {
1761 for (BasicBlock *SuccBB : successors(BB: ClonedBB))
1762 SuccBB->removePredecessor(Pred: ClonedBB);
1763 DeadBlocks.push_back(Elt: ClonedBB);
1764 }
1765
1766 // Remove all MemorySSA in the dead blocks
1767 if (MSSAU) {
1768 SmallSetVector<BasicBlock *, 8> DeadBlockSet(DeadBlocks.begin(),
1769 DeadBlocks.end());
1770 MSSAU->removeBlocks(DeadBlocks: DeadBlockSet);
1771 }
1772
1773 // Drop any remaining references to break cycles.
1774 for (BasicBlock *BB : DeadBlocks)
1775 BB->dropAllReferences();
1776 // Erase them from the IR.
1777 for (BasicBlock *BB : DeadBlocks)
1778 BB->eraseFromParent();
1779}
1780
1781static void deleteDeadBlocksFromLoop(Loop &L,
1782 SmallVectorImpl<BasicBlock *> &ExitBlocks,
1783 DominatorTree &DT, LoopInfo &LI,
1784 MemorySSAUpdater *MSSAU,
1785 ScalarEvolution *SE,
1786 LPMUpdater &LoopUpdater) {
1787 // Find all the dead blocks tied to this loop, and remove them from their
1788 // successors.
1789 SmallSetVector<BasicBlock *, 8> DeadBlockSet;
1790
1791 // Start with loop/exit blocks and get a transitive closure of reachable dead
1792 // blocks.
1793 SmallVector<BasicBlock *, 16> DeathCandidates(ExitBlocks.begin(),
1794 ExitBlocks.end());
1795 DeathCandidates.append(in_start: L.blocks().begin(), in_end: L.blocks().end());
1796 while (!DeathCandidates.empty()) {
1797 auto *BB = DeathCandidates.pop_back_val();
1798 if (!DeadBlockSet.count(key: BB) && !DT.isReachableFromEntry(A: BB)) {
1799 for (BasicBlock *SuccBB : successors(BB)) {
1800 SuccBB->removePredecessor(Pred: BB);
1801 DeathCandidates.push_back(Elt: SuccBB);
1802 }
1803 DeadBlockSet.insert(X: BB);
1804 }
1805 }
1806
1807 // Remove all MemorySSA in the dead blocks
1808 if (MSSAU)
1809 MSSAU->removeBlocks(DeadBlocks: DeadBlockSet);
1810
1811 // Filter out the dead blocks from the exit blocks list so that it can be
1812 // used in the caller.
1813 llvm::erase_if(C&: ExitBlocks,
1814 P: [&](BasicBlock *BB) { return DeadBlockSet.count(key: BB); });
1815
1816 // Walk from this loop up through its parents removing all of the dead blocks.
1817 for (Loop *Cur = &L; Cur; Cur = Cur->getParentLoop())
1818 LI.removeBlocksIf(L&: *Cur,
1819 Pred: [&](BasicBlock *BB) { return DeadBlockSet.count(key: BB); });
1820
1821 // Delete the dead child loops here: recompute requires every loop's header
1822 // to still be in the function, and these blocks are about to be erased.
1823 for (Loop *ChildL : L) {
1824 if (!DeadBlockSet.count(key: ChildL->getHeader()))
1825 continue;
1826
1827 assert(llvm::all_of(ChildL->blocks(),
1828 [&](BasicBlock *ChildBB) {
1829 return DeadBlockSet.count(ChildBB);
1830 }) &&
1831 "If the child loop header is dead all blocks in the child loop must "
1832 "be dead as well!");
1833 LoopUpdater.markLoopAsDeleted(L&: *ChildL, Name: ChildL->getName());
1834 if (SE)
1835 SE->forgetBlockAndLoopDispositions();
1836 }
1837 for (Loop *ChildL : LI.takeChildrenIf(Parent: &L, Pred: [&](Loop *ChildL) {
1838 return DeadBlockSet.count(key: ChildL->getHeader());
1839 }))
1840 LI.destroy(L: ChildL);
1841
1842 // Remove the loop mappings for the dead blocks and drop all the references
1843 // from these blocks to others to handle cyclic references as we start
1844 // deleting the blocks themselves.
1845 for (auto *BB : DeadBlockSet) {
1846 // Check that the dominator tree has already been updated.
1847 assert(!DT.getNode(BB) && "Should already have cleared domtree!");
1848 LI.changeLoopFor(BB, L: nullptr);
1849 // Drop all uses of the instructions to make sure we won't have dangling
1850 // uses in other blocks.
1851 for (auto &I : *BB)
1852 if (!I.use_empty())
1853 I.replaceAllUsesWith(V: PoisonValue::get(T: I.getType()));
1854 BB->dropAllReferences();
1855 }
1856
1857 // Actually delete the blocks now that they've been fully unhooked from the
1858 // IR.
1859 for (auto *BB : DeadBlockSet)
1860 BB->eraseFromParent();
1861}
1862
1863/// Rebuild the loop forest after unswitching removes some subset of blocks and
1864/// edges.
1865///
1866/// Child loops of \p L that ended up elsewhere in the nest are returned in
1867/// \p HoistedLoops; ones that are no longer loops at all are reported to
1868/// \p LoopUpdater and destroyed.
1869///
1870/// Returns false if \p L is no longer a loop, in which case it should not
1871/// continue to be referenced.
1872static bool rebuildLoopAfterUnswitch(Loop &L, DominatorTree &DT, LoopInfo &LI,
1873 SmallVectorImpl<Loop *> &HoistedLoops,
1874 ScalarEvolution *SE,
1875 LPMUpdater &LoopUpdater) {
1876 SmallVector<Loop *, 4> Children(L.begin(), L.end());
1877
1878 SmallVector<std::pair<Loop *, BasicBlock *>, 4> Removed = LI.recompute(DomTree: DT);
1879 SmallPtrSet<Loop *, 4> RemovedSet;
1880 for (Loop *RemovedL : make_first_range(c&: Removed))
1881 RemovedSet.insert(Ptr: RemovedL);
1882
1883 for (Loop *ChildL : Children)
1884 if (!RemovedSet.contains(Ptr: ChildL) && ChildL->getParentLoop() != &L)
1885 HoistedLoops.push_back(Elt: ChildL);
1886
1887 if (SE && !Removed.empty())
1888 SE->forgetBlockAndLoopDispositions();
1889
1890 for (auto [RemovedL, Header] : Removed) {
1891 assert((RemovedL == &L || is_contained(Children, RemovedL)) &&
1892 "Unswitching can only remove loops from the current nest!");
1893 // The caller (postUnswitch) marks L itself as deleted; past this destroy
1894 // its pointer serves only as a key.
1895 if (RemovedL != &L)
1896 LoopUpdater.markLoopAsDeleted(L&: *RemovedL, Name: Header->getName());
1897 LI.destroy(L: RemovedL);
1898 }
1899
1900 return !RemovedSet.contains(Ptr: &L);
1901}
1902
1903/// Helper to visit a dominator subtree, invoking a callable on each node.
1904///
1905/// Returning false at any point will stop walking past that node of the tree.
1906template <typename CallableT>
1907void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) {
1908 SmallVector<DomTreeNode *, 4> DomWorklist;
1909 DomWorklist.push_back(Elt: DT[BB]);
1910#ifndef NDEBUG
1911 SmallPtrSet<DomTreeNode *, 4> Visited;
1912 Visited.insert(DT[BB]);
1913#endif
1914 do {
1915 DomTreeNode *N = DomWorklist.pop_back_val();
1916
1917 // Visit this node.
1918 if (!Callable(N->getBlock()))
1919 continue;
1920
1921 // Accumulate the child nodes.
1922 for (DomTreeNode *ChildN : *N) {
1923 assert(Visited.insert(ChildN).second &&
1924 "Cannot visit a node twice when walking a tree!");
1925 DomWorklist.push_back(Elt: ChildN);
1926 }
1927 } while (!DomWorklist.empty());
1928}
1929
1930void postUnswitch(Loop &L, LPMUpdater &U, StringRef LoopName,
1931 bool CurrentLoopValid, bool PartiallyInvariant,
1932 bool InjectedCondition, ArrayRef<Loop *> NewLoops) {
1933 // If we did a non-trivial unswitch, we have added new (cloned) loops.
1934 if (!NewLoops.empty())
1935 U.addSiblingLoops(NewSibLoops: NewLoops);
1936
1937 // If the current loop remains valid, we should revisit it to catch any
1938 // other unswitch opportunities. Otherwise, we need to mark it as deleted.
1939 if (CurrentLoopValid) {
1940 if (PartiallyInvariant) {
1941 // Mark the new loop as partially unswitched, to avoid unswitching on
1942 // the same condition again.
1943 L.addStringLoopAttribute(Name: "llvm.loop.unswitch.partial.disable",
1944 RemovePrefixes: {"llvm.loop.unswitch.partial"});
1945 } else if (InjectedCondition) {
1946 // Do the same for injection of invariant conditions.
1947 L.addStringLoopAttribute(Name: "llvm.loop.unswitch.injection.disable",
1948 RemovePrefixes: {"llvm.loop.unswitch.injection"});
1949 } else
1950 U.revisitCurrentLoop();
1951 } else
1952 U.markLoopAsDeleted(L, Name: LoopName);
1953}
1954
1955static void unswitchNontrivialInvariants(
1956 const ScalarOptions &Opts, Loop &L, Instruction &TI,
1957 ArrayRef<Value *> Invariants, IVConditionInfo &PartialIVInfo,
1958 DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, ScalarEvolution *SE,
1959 MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater, bool InsertFreeze,
1960 bool InjectedCondition) {
1961 auto *ParentBB = TI.getParent();
1962 CondBrInst *BI = dyn_cast<CondBrInst>(Val: &TI);
1963 SwitchInst *SI = BI ? nullptr : cast<SwitchInst>(Val: &TI);
1964
1965 // Save the current loop name in a variable so that we can report it even
1966 // after it has been deleted.
1967 std::string LoopName(L.getName());
1968
1969 // We can only unswitch switches, conditional branches with an invariant
1970 // condition, or combining invariant conditions with an instruction or
1971 // partially invariant instructions.
1972 assert((SI || BI) && "Can only unswitch switches and conditional branch!");
1973 bool PartiallyInvariant = !PartialIVInfo.InstToDuplicate.empty();
1974 bool FullUnswitch =
1975 SI || (skipTrivialSelect(Cond: BI->getCondition()) == Invariants[0] &&
1976 !PartiallyInvariant);
1977 if (FullUnswitch)
1978 assert(Invariants.size() == 1 &&
1979 "Cannot have other invariants with full unswitching!");
1980 else
1981 assert(isa<Instruction>(skipTrivialSelect(BI->getCondition())) &&
1982 "Partial unswitching requires an instruction as the condition!");
1983
1984 if (MSSAU && VerifyMemorySSA)
1985 MSSAU->getMemorySSA()->verifyMemorySSA();
1986
1987 // Constant and BBs tracking the cloned and continuing successor. When we are
1988 // unswitching the entire condition, this can just be trivially chosen to
1989 // unswitch towards `true`. However, when we are unswitching a set of
1990 // invariants combined with `and` or `or` or partially invariant instructions,
1991 // the combining operation determines the best direction to unswitch: we want
1992 // to unswitch the direction that will collapse the branch.
1993 bool Direction = true;
1994 int ClonedSucc = 0;
1995 if (!FullUnswitch) {
1996 Value *Cond = skipTrivialSelect(Cond: BI->getCondition());
1997 (void)Cond;
1998 assert(((match(Cond, m_LogicalAnd()) ^ match(Cond, m_LogicalOr())) ||
1999 PartiallyInvariant) &&
2000 "Only `or`, `and`, an `select`, partially invariant instructions "
2001 "can combine invariants being unswitched.");
2002 if (!match(V: Cond, P: m_LogicalOr())) {
2003 if (match(V: Cond, P: m_LogicalAnd()) ||
2004 (PartiallyInvariant && !PartialIVInfo.KnownValue->isOneValue())) {
2005 Direction = false;
2006 ClonedSucc = 1;
2007 }
2008 }
2009 }
2010
2011 BasicBlock *RetainedSuccBB =
2012 BI ? BI->getSuccessor(i: 1 - ClonedSucc) : SI->getDefaultDest();
2013 SmallSetVector<BasicBlock *, 4> UnswitchedSuccBBs;
2014 if (BI)
2015 UnswitchedSuccBBs.insert(X: BI->getSuccessor(i: ClonedSucc));
2016 else
2017 for (auto Case : SI->cases())
2018 if (Case.getCaseSuccessor() != RetainedSuccBB)
2019 UnswitchedSuccBBs.insert(X: Case.getCaseSuccessor());
2020
2021 assert(!UnswitchedSuccBBs.count(RetainedSuccBB) &&
2022 "Should not unswitch the same successor we are retaining!");
2023
2024 // The branch should be in this exact loop. Any inner loop's invariant branch
2025 // should be handled by unswitching that inner loop. The caller of this
2026 // routine should filter out any candidates that remain (but were skipped for
2027 // whatever reason).
2028 assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!");
2029
2030 // Compute the parent loop now before we start hacking on things.
2031 Loop *ParentL = L.getParentLoop();
2032 // Get blocks in RPO order for MSSA update, before changing the CFG.
2033 LoopBlocksRPO LBRPO(&L);
2034 if (MSSAU)
2035 LBRPO.perform(LI: &LI);
2036
2037 // Compute the outer-most loop containing one of our exit blocks. This is the
2038 // furthest up our loopnest which can be mutated, which we will use below to
2039 // update things.
2040 Loop *OuterExitL = &L;
2041 SmallVector<BasicBlock *, 4> ExitBlocks;
2042 L.getUniqueExitBlocks(ExitBlocks);
2043 for (auto *ExitBB : ExitBlocks) {
2044 // ExitBB can be an exit block for several levels in the loop nest. Make
2045 // sure we find the top most.
2046 Loop *NewOuterExitL = getTopMostExitingLoop(ExitBB, LI);
2047 if (!NewOuterExitL) {
2048 // We exited the entire nest with this block, so we're done.
2049 OuterExitL = nullptr;
2050 break;
2051 }
2052 if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(L: OuterExitL))
2053 OuterExitL = NewOuterExitL;
2054 }
2055
2056 // At this point, we're definitely going to unswitch something so invalidate
2057 // any cached information in ScalarEvolution for the outer most loop
2058 // containing an exit block and all nested loops.
2059 if (SE) {
2060 if (OuterExitL)
2061 SE->forgetLoop(L: OuterExitL);
2062 else
2063 SE->forgetTopmostLoop(L: &L);
2064 SE->forgetBlockAndLoopDispositions();
2065 }
2066
2067 // If the edge from this terminator to a successor dominates that successor,
2068 // store a map from each block in its dominator subtree to it. This lets us
2069 // tell when cloning for a particular successor if a block is dominated by
2070 // some *other* successor with a single data structure. We use this to
2071 // significantly reduce cloning.
2072 SmallDenseMap<BasicBlock *, BasicBlock *, 16> DominatingSucc;
2073 for (auto *SuccBB : llvm::concat<BasicBlock *const>(Ranges: ArrayRef(RetainedSuccBB),
2074 Ranges&: UnswitchedSuccBBs))
2075 if (SuccBB->getUniquePredecessor() ||
2076 llvm::all_of(Range: predecessors(BB: SuccBB), P: [&](BasicBlock *PredBB) {
2077 return PredBB == ParentBB || DT.dominates(A: SuccBB, B: PredBB);
2078 }))
2079 visitDomSubTree(DT, BB: SuccBB, Callable: [&](BasicBlock *BB) {
2080 DominatingSucc[BB] = SuccBB;
2081 return true;
2082 });
2083
2084 // Split the preheader, so that we know that there is a safe place to insert
2085 // the conditional branch. We will change the preheader to have a conditional
2086 // branch on LoopCond. The original preheader will become the split point
2087 // between the unswitched versions, and we will have a new preheader for the
2088 // original loop.
2089 BasicBlock *SplitBB = L.getLoopPreheader();
2090 BasicBlock *LoopPH = SplitEdge(From: SplitBB, To: L.getHeader(), DT: &DT, LI: &LI, MSSAU);
2091
2092 // Keep track of the dominator tree updates needed.
2093 SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
2094
2095 // Clone the loop for each unswitched successor.
2096 SmallVector<std::unique_ptr<ValueToValueMapTy>, 4> VMaps;
2097 VMaps.reserve(N: UnswitchedSuccBBs.size());
2098 SmallDenseMap<BasicBlock *, BasicBlock *, 4> ClonedPHs;
2099 for (auto *SuccBB : UnswitchedSuccBBs) {
2100 VMaps.emplace_back(Args: new ValueToValueMapTy());
2101 ClonedPHs[SuccBB] = buildClonedLoopBlocks(
2102 L, LoopPH, SplitBB, ExitBlocks, ParentBB, UnswitchedSuccBB: SuccBB, ContinueSuccBB: RetainedSuccBB,
2103 DominatingSucc, VMap&: *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU, SE);
2104 }
2105
2106 // Drop metadata if we may break its semantics by moving this instr into the
2107 // split block.
2108 if (TI.getMetadata(KindID: LLVMContext::MD_make_implicit)) {
2109 if (Opts.simple_loop_unswitch_drop_non_trivial_implicit_null_checks)
2110 // Do not spend time trying to understand if we can keep it, just drop it
2111 // to save compile time.
2112 TI.setMetadata(KindID: LLVMContext::MD_make_implicit, Node: nullptr);
2113 else {
2114 // It is only legal to preserve make.implicit metadata if we are
2115 // guaranteed no reach implicit null check after following this branch.
2116 ICFLoopSafetyInfo SafetyInfo(&L);
2117 if (!SafetyInfo.isGuaranteedToExecute(Inst: TI, DT: &DT))
2118 TI.setMetadata(KindID: LLVMContext::MD_make_implicit, Node: nullptr);
2119 }
2120 }
2121
2122 // The stitching of the branched code back together depends on whether we're
2123 // doing full unswitching or not with the exception that we always want to
2124 // nuke the initial terminator placed in the split block.
2125 SplitBB->getTerminator()->eraseFromParent();
2126 if (FullUnswitch) {
2127 // Keep a clone of the terminator for MSSA updates.
2128 Instruction *NewTI = TI.clone();
2129 NewTI->insertInto(ParentBB, It: ParentBB->end());
2130
2131 // Splice the terminator from the original loop and rewrite its
2132 // successors.
2133 TI.moveBefore(BB&: *SplitBB, I: SplitBB->end());
2134 TI.dropLocation();
2135
2136 // First wire up the moved terminator to the preheaders.
2137 if (BI) {
2138 BasicBlock *ClonedPH = ClonedPHs.begin()->second;
2139 BI->setSuccessor(idx: ClonedSucc, NewSucc: ClonedPH);
2140 BI->setSuccessor(idx: 1 - ClonedSucc, NewSucc: LoopPH);
2141 Value *Cond = skipTrivialSelect(Cond: BI->getCondition());
2142 if (InsertFreeze) {
2143 // We don't give any debug location to the new freeze, because the
2144 // BI (`dyn_cast<CondBrInst>(TI)`) is an in-loop instruction hoisted
2145 // out of the loop.
2146 Cond = new FreezeInst(Cond, Cond->getName() + ".fr", BI->getIterator());
2147 cast<Instruction>(Val: Cond)->setDebugLoc(DebugLoc::getDropped());
2148 }
2149 BI->setCondition(Cond);
2150 DTUpdates.push_back(Elt: {DominatorTree::Insert, SplitBB, ClonedPH});
2151 } else {
2152 assert(SI && "Must either be a branch or switch!");
2153
2154 // Walk the cases and directly update their successors.
2155 assert(SI->getDefaultDest() == RetainedSuccBB &&
2156 "Not retaining default successor!");
2157 SI->setDefaultDest(LoopPH);
2158 for (const auto &Case : SI->cases())
2159 if (Case.getCaseSuccessor() == RetainedSuccBB)
2160 Case.setSuccessor(LoopPH);
2161 else
2162 Case.setSuccessor(ClonedPHs.find(Val: Case.getCaseSuccessor())->second);
2163
2164 if (InsertFreeze)
2165 SI->setCondition(new FreezeInst(SI->getCondition(),
2166 SI->getCondition()->getName() + ".fr",
2167 SI->getIterator()));
2168
2169 // We need to use the set to populate domtree updates as even when there
2170 // are multiple cases pointing at the same successor we only want to
2171 // remove and insert one edge in the domtree.
2172 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2173 DTUpdates.push_back(
2174 Elt: {DominatorTree::Insert, SplitBB, ClonedPHs.find(Val: SuccBB)->second});
2175 }
2176
2177 if (MSSAU) {
2178 DT.applyUpdates(Updates: DTUpdates);
2179 DTUpdates.clear();
2180
2181 // Remove all but one edge to the retained block and all unswitched
2182 // blocks. This is to avoid having duplicate entries in the cloned Phis,
2183 // when we know we only keep a single edge for each case.
2184 MSSAU->removeDuplicatePhiEdgesBetween(From: ParentBB, To: RetainedSuccBB);
2185 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2186 MSSAU->removeDuplicatePhiEdgesBetween(From: ParentBB, To: SuccBB);
2187
2188 for (auto &VMap : VMaps)
2189 MSSAU->updateForClonedLoop(LoopBlocks: LBRPO, ExitBlocks, VM: *VMap,
2190 /*IgnoreIncomingWithNoClones=*/true);
2191 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT);
2192
2193 // Remove all edges to unswitched blocks.
2194 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2195 MSSAU->removeEdge(From: ParentBB, To: SuccBB);
2196 }
2197
2198 // Now unhook the successor relationship as we'll be replacing
2199 // the terminator with a direct branch. This is much simpler for branches
2200 // than switches so we handle those first.
2201 if (BI) {
2202 // Remove the parent as a predecessor of the unswitched successor.
2203 assert(UnswitchedSuccBBs.size() == 1 &&
2204 "Only one possible unswitched block for a branch!");
2205 BasicBlock *UnswitchedSuccBB = *UnswitchedSuccBBs.begin();
2206 UnswitchedSuccBB->removePredecessor(Pred: ParentBB,
2207 /*KeepOneInputPHIs*/ true);
2208 DTUpdates.push_back(Elt: {DominatorTree::Delete, ParentBB, UnswitchedSuccBB});
2209 } else {
2210 // Note that we actually want to remove the parent block as a predecessor
2211 // of *every* case successor. The case successor is either unswitched,
2212 // completely eliminating an edge from the parent to that successor, or it
2213 // is a duplicate edge to the retained successor as the retained successor
2214 // is always the default successor and as we'll replace this with a direct
2215 // branch we no longer need the duplicate entries in the PHI nodes.
2216 SwitchInst *NewSI = cast<SwitchInst>(Val: NewTI);
2217 assert(NewSI->getDefaultDest() == RetainedSuccBB &&
2218 "Not retaining default successor!");
2219 for (const auto &Case : NewSI->cases())
2220 Case.getCaseSuccessor()->removePredecessor(
2221 Pred: ParentBB,
2222 /*KeepOneInputPHIs*/ true);
2223
2224 // We need to use the set to populate domtree updates as even when there
2225 // are multiple cases pointing at the same successor we only want to
2226 // remove and insert one edge in the domtree.
2227 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2228 DTUpdates.push_back(Elt: {DominatorTree::Delete, ParentBB, SuccBB});
2229 }
2230
2231 // Create a new unconditional branch to the continuing block (as opposed to
2232 // the one cloned).
2233 Instruction *NewBI = UncondBrInst::Create(Target: RetainedSuccBB, InsertBefore: ParentBB);
2234 NewBI->setDebugLoc(NewTI->getDebugLoc());
2235
2236 // After MSSAU update, remove the cloned terminator instruction NewTI.
2237 NewTI->eraseFromParent();
2238 } else {
2239 assert(BI && "Only branches have partial unswitching.");
2240 assert(UnswitchedSuccBBs.size() == 1 &&
2241 "Only one possible unswitched block for a branch!");
2242 BasicBlock *ClonedPH = ClonedPHs.begin()->second;
2243 // When doing a partial unswitch, we have to do a bit more work to build up
2244 // the branch in the split block.
2245 if (PartiallyInvariant)
2246 buildPartialInvariantUnswitchConditionalBranch(
2247 BB&: *SplitBB, ToDuplicate: Invariants, Direction, UnswitchedSucc&: *ClonedPH, NormalSucc&: *LoopPH, L, MSSAU, OriginalBranch: *BI);
2248 else {
2249 buildPartialUnswitchConditionalBranch(Opts, BB&: *SplitBB, Invariants,
2250 Direction, UnswitchedSucc&: *ClonedPH, NormalSucc&: *LoopPH, I: BI,
2251 AC: &AC, DT, ComputeProfFrom: *BI);
2252 }
2253 DTUpdates.push_back(Elt: {DominatorTree::Insert, SplitBB, ClonedPH});
2254
2255 if (MSSAU) {
2256 DT.applyUpdates(Updates: DTUpdates);
2257 DTUpdates.clear();
2258
2259 // Perform MSSA cloning updates.
2260 for (auto &VMap : VMaps)
2261 MSSAU->updateForClonedLoop(LoopBlocks: LBRPO, ExitBlocks, VM: *VMap,
2262 /*IgnoreIncomingWithNoClones=*/true);
2263 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT);
2264 }
2265 }
2266
2267 // Apply the updates accumulated above to get an up-to-date dominator tree.
2268 DT.applyUpdates(Updates: DTUpdates);
2269
2270 // Now that we have an accurate dominator tree, first delete the dead cloned
2271 // blocks so that we can accurately build any cloned loops. It is important to
2272 // not delete the blocks from the original loop yet because we still want to
2273 // reference the original loop to understand the cloned loop's structure.
2274 deleteDeadClonedBlocks(L, ExitBlocks, VMaps, DT, MSSAU);
2275
2276 // Build the cloned loop structure itself. This may be substantially
2277 // different from the original structure due to the simplified CFG. This also
2278 // handles inserting all the cloned blocks into the correct loops.
2279 SmallVector<Loop *, 4> NonChildClonedLoops;
2280 for (std::unique_ptr<ValueToValueMapTy> &VMap : VMaps)
2281 buildClonedLoops(OrigL&: L, ExitBlocks, VMap: *VMap, LI, NonChildClonedLoops);
2282
2283 // Now that our cloned loops have been built, we can update the original loop.
2284 // First we delete the dead blocks from it and then we rebuild the loop
2285 // structure taking these deletions into account.
2286 deleteDeadBlocksFromLoop(L, ExitBlocks, DT, LI, MSSAU, SE, LoopUpdater);
2287
2288 if (MSSAU && VerifyMemorySSA)
2289 MSSAU->getMemorySSA()->verifyMemorySSA();
2290
2291 SmallVector<Loop *, 4> HoistedLoops;
2292 bool IsStillLoop =
2293 rebuildLoopAfterUnswitch(L, DT, LI, HoistedLoops, SE, LoopUpdater);
2294
2295 if (MSSAU && VerifyMemorySSA)
2296 MSSAU->getMemorySSA()->verifyMemorySSA();
2297
2298#ifdef EXPENSIVE_CHECKS
2299 // This transformation has a high risk of corrupting the dominator tree, and
2300 // the below steps to rebuild loop structures will result in hard to debug
2301 // errors in that case so verify that the dominator tree is sane first.
2302 // FIXME: Remove this when the bugs stop showing up and rely on existing
2303 // verification steps.
2304 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
2305#endif
2306
2307 if (BI && !PartiallyInvariant) {
2308 // If we unswitched a branch which collapses the condition to a known
2309 // constant we want to replace all the uses of the invariants within both
2310 // the original and cloned blocks. We do this here so that we can use the
2311 // now updated dominator tree to identify which side the users are on.
2312 assert(UnswitchedSuccBBs.size() == 1 &&
2313 "Only one possible unswitched block for a branch!");
2314 BasicBlock *ClonedPH = ClonedPHs.begin()->second;
2315
2316 // When considering multiple partially-unswitched invariants
2317 // we cant just go replace them with constants in both branches.
2318 //
2319 // For 'AND' we infer that true branch ("continue") means true
2320 // for each invariant operand.
2321 // For 'OR' we can infer that false branch ("continue") means false
2322 // for each invariant operand.
2323 // So it happens that for multiple-partial case we dont replace
2324 // in the unswitched branch.
2325 bool ReplaceUnswitched =
2326 FullUnswitch || (Invariants.size() == 1) || PartiallyInvariant;
2327
2328 ConstantInt *UnswitchedReplacement =
2329 Direction ? ConstantInt::getTrue(Context&: BI->getContext())
2330 : ConstantInt::getFalse(Context&: BI->getContext());
2331 ConstantInt *ContinueReplacement =
2332 Direction ? ConstantInt::getFalse(Context&: BI->getContext())
2333 : ConstantInt::getTrue(Context&: BI->getContext());
2334 for (Value *Invariant : Invariants) {
2335 assert(!isa<Constant>(Invariant) &&
2336 "Should not be replacing constant values!");
2337 // Use make_early_inc_range here as set invalidates the iterator.
2338 for (Use &U : llvm::make_early_inc_range(Range: Invariant->uses())) {
2339 Instruction *UserI = dyn_cast<Instruction>(Val: U.getUser());
2340 if (!UserI)
2341 continue;
2342
2343 // Replace it with the 'continue' side if in the main loop body, and the
2344 // unswitched if in the cloned blocks.
2345 if (DT.dominates(A: LoopPH, B: UserI->getParent()))
2346 U.set(ContinueReplacement);
2347 else if (ReplaceUnswitched &&
2348 DT.dominates(A: ClonedPH, B: UserI->getParent()))
2349 U.set(UnswitchedReplacement);
2350 }
2351 }
2352 }
2353
2354 // We can change which blocks are exit blocks of all the cloned sibling
2355 // loops, the current loop, and any parent loops which shared exit blocks
2356 // with the current loop. As a consequence, we need to re-form LCSSA for
2357 // them. But we shouldn't need to re-form LCSSA for any child loops.
2358 // FIXME: This could be made more efficient by tracking which exit blocks are
2359 // new, and focusing on them, but that isn't likely to be necessary.
2360 //
2361 // In order to reasonably rebuild LCSSA we need to walk inside-out across the
2362 // loop nest and update every loop that could have had its exits changed. We
2363 // also need to cover any intervening loops. We add all of these loops to
2364 // a list and sort them by loop depth to achieve this without updating
2365 // unnecessary loops.
2366 auto UpdateLoop = [&](Loop &UpdateL) {
2367#ifndef NDEBUG
2368 UpdateL.verifyLoop();
2369 for (Loop *ChildL : UpdateL) {
2370 ChildL->verifyLoop();
2371 assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
2372 "Perturbed a child loop's LCSSA form!");
2373 }
2374#endif
2375 // First build LCSSA for this loop so that we can preserve it when
2376 // forming dedicated exits. We don't want to perturb some other loop's
2377 // LCSSA while doing that CFG edit.
2378 formLCSSA(L&: UpdateL, DT, LI: &LI, SE);
2379
2380 // For loops reached by this loop's original exit blocks we may
2381 // introduced new, non-dedicated exits. At least try to re-form dedicated
2382 // exits for these loops. This may fail if they couldn't have dedicated
2383 // exits to start with.
2384 formDedicatedExitBlocks(L: &UpdateL, DT: &DT, LI: &LI, MSSAU, /*PreserveLCSSA*/ true);
2385 };
2386
2387 // For non-child cloned loops and hoisted loops, we just need to update LCSSA
2388 // and we can do it in any order as they don't nest relative to each other.
2389 //
2390 // Also check if any of the loops we have updated have become top-level loops
2391 // as that will necessitate widening the outer loop scope.
2392 for (Loop *UpdatedL :
2393 llvm::concat<Loop *>(Ranges&: NonChildClonedLoops, Ranges&: HoistedLoops)) {
2394 UpdateLoop(*UpdatedL);
2395 if (UpdatedL->isOutermost())
2396 OuterExitL = nullptr;
2397 }
2398 if (IsStillLoop) {
2399 UpdateLoop(L);
2400 if (L.isOutermost())
2401 OuterExitL = nullptr;
2402 }
2403
2404 // If the original loop had exit blocks, walk up through the outer most loop
2405 // of those exit blocks to update LCSSA and form updated dedicated exits.
2406 if (OuterExitL != &L)
2407 for (Loop *OuterL = ParentL; OuterL != OuterExitL;
2408 OuterL = OuterL->getParentLoop())
2409 UpdateLoop(*OuterL);
2410
2411#ifdef EXPENSIVE_CHECKS
2412 // Verify the entire loop structure to catch any incorrect updates before we
2413 // progress in the pass pipeline.
2414 LI.verify();
2415#endif
2416
2417 // Now that we've unswitched something, make callbacks to report the changes.
2418 // For that we need to merge together the updated loops and the cloned loops
2419 // and check whether the original loop survived.
2420 SmallVector<Loop *, 4> SibLoops;
2421 for (Loop *UpdatedL : llvm::concat<Loop *>(Ranges&: NonChildClonedLoops, Ranges&: HoistedLoops))
2422 if (UpdatedL->getParentLoop() == ParentL)
2423 SibLoops.push_back(Elt: UpdatedL);
2424 postUnswitch(L, U&: LoopUpdater, LoopName, CurrentLoopValid: IsStillLoop, PartiallyInvariant,
2425 InjectedCondition, NewLoops: SibLoops);
2426
2427 if (MSSAU && VerifyMemorySSA)
2428 MSSAU->getMemorySSA()->verifyMemorySSA();
2429
2430 if (BI)
2431 ++NumBranches;
2432 else
2433 ++NumSwitches;
2434}
2435
2436/// Recursively compute the cost of a dominator subtree based on the per-block
2437/// cost map provided.
2438///
2439/// The recursive computation is memozied into the provided DT-indexed cost map
2440/// to allow querying it for most nodes in the domtree without it becoming
2441/// quadratic.
2442static InstructionCost computeDomSubtreeCost(
2443 DomTreeNode &N,
2444 const SmallDenseMap<BasicBlock *, InstructionCost, 4> &BBCostMap,
2445 SmallDenseMap<DomTreeNode *, InstructionCost, 4> &DTCostMap) {
2446 // Don't accumulate cost (or recurse through) blocks not in our block cost
2447 // map and thus not part of the duplication cost being considered.
2448 auto BBCostIt = BBCostMap.find(Val: N.getBlock());
2449 if (BBCostIt == BBCostMap.end())
2450 return 0;
2451
2452 // Lookup this node to see if we already computed its cost.
2453 auto DTCostIt = DTCostMap.find(Val: &N);
2454 if (DTCostIt != DTCostMap.end())
2455 return DTCostIt->second;
2456
2457 // If not, we have to compute it. We can't use insert above and update
2458 // because computing the cost may insert more things into the map.
2459 InstructionCost Cost = std::accumulate(
2460 first: N.begin(), last: N.end(), init: BBCostIt->second,
2461 binary_op: [&](InstructionCost Sum, DomTreeNode *ChildN) -> InstructionCost {
2462 return Sum + computeDomSubtreeCost(N&: *ChildN, BBCostMap, DTCostMap);
2463 });
2464 bool Inserted = DTCostMap.insert(KV: {&N, Cost}).second;
2465 (void)Inserted;
2466 assert(Inserted && "Should not insert a node while visiting children!");
2467 return Cost;
2468}
2469
2470/// Turns a select instruction into implicit control flow branch,
2471/// making the following replacement:
2472///
2473/// head:
2474/// --code before select--
2475/// select %cond, %trueval, %falseval
2476/// --code after select--
2477///
2478/// into
2479///
2480/// head:
2481/// --code before select--
2482/// br i1 %cond, label %then, label %tail
2483///
2484/// then:
2485/// br %tail
2486///
2487/// tail:
2488/// phi [ %trueval, %then ], [ %falseval, %head]
2489/// unreachable
2490///
2491/// It also makes all relevant DT and LI updates, so that all structures are in
2492/// valid state after this transform.
2493static CondBrInst *turnSelectIntoBranch(SelectInst *SI, DominatorTree &DT,
2494 LoopInfo &LI, MemorySSAUpdater *MSSAU,
2495 AssumptionCache *AC) {
2496 LLVM_DEBUG(dbgs() << "Turning " << *SI << " into a branch.\n");
2497 BasicBlock *HeadBB = SI->getParent();
2498
2499 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2500 SplitBlockAndInsertIfThen(Cond: SI->getCondition(), SplitBefore: SI, Unreachable: false,
2501 BranchWeights: SI->getMetadata(KindID: LLVMContext::MD_prof), DTU: &DTU, LI: &LI);
2502 auto *CondBr = cast<CondBrInst>(Val: HeadBB->getTerminator());
2503 BasicBlock *ThenBB = CondBr->getSuccessor(i: 0),
2504 *TailBB = CondBr->getSuccessor(i: 1);
2505 if (MSSAU)
2506 MSSAU->moveAllAfterSpliceBlocks(From: HeadBB, To: TailBB, Start: SI);
2507
2508 PHINode *Phi =
2509 PHINode::Create(Ty: SI->getType(), NumReservedValues: 2, NameStr: "unswitched.select", InsertBefore: SI->getIterator());
2510 Phi->addIncoming(V: SI->getTrueValue(), BB: ThenBB);
2511 Phi->addIncoming(V: SI->getFalseValue(), BB: HeadBB);
2512 Phi->setDebugLoc(SI->getDebugLoc());
2513 SI->replaceAllUsesWith(V: Phi);
2514 SI->eraseFromParent();
2515
2516 if (MSSAU && VerifyMemorySSA)
2517 MSSAU->getMemorySSA()->verifyMemorySSA();
2518
2519 ++NumSelects;
2520 return CondBr;
2521}
2522
2523/// Turns a llvm.experimental.guard intrinsic into implicit control flow branch,
2524/// making the following replacement:
2525///
2526/// --code before guard--
2527/// call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
2528/// --code after guard--
2529///
2530/// into
2531///
2532/// --code before guard--
2533/// br i1 %cond, label %guarded, label %deopt
2534///
2535/// guarded:
2536/// --code after guard--
2537///
2538/// deopt:
2539/// call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
2540/// unreachable
2541///
2542/// It also makes all relevant DT and LI updates, so that all structures are in
2543/// valid state after this transform.
2544static CondBrInst *turnGuardIntoBranch(const ScalarOptions &Opts,
2545 IntrinsicInst *GI, Loop &L,
2546 DominatorTree &DT, LoopInfo &LI,
2547 MemorySSAUpdater *MSSAU) {
2548 LLVM_DEBUG(dbgs() << "Turning " << *GI << " into a branch.\n");
2549 BasicBlock *CheckBB = GI->getParent();
2550
2551 if (MSSAU && VerifyMemorySSA)
2552 MSSAU->getMemorySSA()->verifyMemorySSA();
2553
2554 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2555 // llvm.experimental.guard doesn't have branch weights. We can assume,
2556 // however, that the deopt path is unlikely.
2557 Instruction *DeoptBlockTerm = SplitBlockAndInsertIfThen(
2558 Cond: GI->getArgOperand(i: 0), SplitBefore: GI, Unreachable: true,
2559 BranchWeights: Opts.simple_loop_unswitch_estimate_profile
2560 ? MDBuilder(GI->getContext()).createUnlikelyBranchWeights()
2561 : nullptr,
2562 DTU: &DTU, LI: &LI);
2563 CondBrInst *CheckBI = cast<CondBrInst>(Val: CheckBB->getTerminator());
2564 // SplitBlockAndInsertIfThen inserts control flow that branches to
2565 // DeoptBlockTerm if the condition is true. We want the opposite.
2566 CheckBI->swapSuccessors();
2567
2568 BasicBlock *GuardedBlock = CheckBI->getSuccessor(i: 0);
2569 GuardedBlock->setName("guarded");
2570 CheckBI->getSuccessor(i: 1)->setName("deopt");
2571 BasicBlock *DeoptBlock = CheckBI->getSuccessor(i: 1);
2572
2573 if (MSSAU)
2574 MSSAU->moveAllAfterSpliceBlocks(From: CheckBB, To: GuardedBlock, Start: GI);
2575
2576 GI->moveBefore(InsertPos: DeoptBlockTerm->getIterator());
2577 GI->setArgOperand(i: 0, v: ConstantInt::getFalse(Context&: GI->getContext()));
2578
2579 if (MSSAU) {
2580 MemoryDef *MD = cast<MemoryDef>(Val: MSSAU->getMemorySSA()->getMemoryAccess(I: GI));
2581 MSSAU->moveToPlace(What: MD, BB: DeoptBlock, Where: MemorySSA::BeforeTerminator);
2582 if (VerifyMemorySSA)
2583 MSSAU->getMemorySSA()->verifyMemorySSA();
2584 }
2585
2586 if (VerifyLoopInfo)
2587 LI.verify();
2588 ++NumGuards;
2589 return CheckBI;
2590}
2591
2592/// Cost multiplier is a way to limit potentially exponential behavior
2593/// of loop-unswitch. Cost is multiplied in proportion of 2^number of unswitch
2594/// candidates available. Also consider the number of "sibling" loops with
2595/// the idea of accounting for previous unswitches that already happened on this
2596/// cluster of loops. There was an attempt to keep this formula simple,
2597/// just enough to limit the worst case behavior. Even if it is not that simple
2598/// now it is still not an attempt to provide a detailed heuristic size
2599/// prediction.
2600///
2601/// TODO: Make a proper accounting of "explosion" effect for all kinds of
2602/// unswitch candidates, making adequate predictions instead of wild guesses.
2603/// That requires knowing not just the number of "remaining" candidates but
2604/// also costs of unswitching for each of these candidates.
2605static int calculateUnswitchCostMultiplier(
2606 const ScalarOptions &Opts, const Instruction &TI, const Loop &L,
2607 const LoopInfo &LI, const DominatorTree &DT,
2608 ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates) {
2609
2610 // Guards and other exiting conditions do not contribute to exponential
2611 // explosion as soon as they dominate the latch (otherwise there might be
2612 // another path to the latch remaining that does not allow to eliminate the
2613 // loop copy on unswitch).
2614 const BasicBlock *Latch = L.getLoopLatch();
2615 const BasicBlock *CondBlock = TI.getParent();
2616 if (DT.dominates(A: CondBlock, B: Latch) &&
2617 (isGuard(U: &TI) ||
2618 (TI.isTerminator() &&
2619 llvm::count_if(Range: successors(I: &TI), P: [&L](const BasicBlock *SuccBB) {
2620 return L.contains(BB: SuccBB);
2621 }) <= 1))) {
2622 NumCostMultiplierSkipped++;
2623 return 1;
2624 }
2625
2626 // Each invariant non-trivial condition, after being unswitched, is supposed
2627 // to have its own specialized sibling loop (the invariant condition has been
2628 // hoisted out of the child loop into a newly-cloned loop). When unswitching
2629 // conditions in nested loops, the basic block size of the outer loop should
2630 // not be altered. If such a size significantly increases across unswitching
2631 // invocations, something may be wrong; so adjust the final cost taking this
2632 // into account.
2633 auto *ParentL = L.getParentLoop();
2634 int ParentLoopSizeMultiplier = 1;
2635 if (ParentL)
2636 ParentLoopSizeMultiplier = std::max<int>(
2637 a: ParentL->getNumBlocks() / Opts.unswitch_parent_blocks_div, b: 1);
2638
2639 int SiblingsCount =
2640 (ParentL ? ParentL->getSubLoops().size() : llvm::size(Range: LI));
2641 // Count amount of clones that all the candidates might cause during
2642 // unswitching. Branch/guard/select counts as 1, switch counts as log2 of its
2643 // cases.
2644 int UnswitchedClones = 0;
2645 for (const auto &Candidate : UnswitchCandidates) {
2646 const Instruction *CI = Candidate.TI;
2647 const BasicBlock *CondBlock = CI->getParent();
2648 bool SkipExitingSuccessors = DT.dominates(A: CondBlock, B: Latch);
2649 if (isa<SelectInst>(Val: CI)) {
2650 UnswitchedClones++;
2651 continue;
2652 }
2653 if (isGuard(U: CI)) {
2654 if (!SkipExitingSuccessors)
2655 UnswitchedClones++;
2656 continue;
2657 }
2658 int NonExitingSuccessors =
2659 llvm::count_if(Range: successors(BB: CondBlock),
2660 P: [SkipExitingSuccessors, &L](const BasicBlock *SuccBB) {
2661 return !SkipExitingSuccessors || L.contains(BB: SuccBB);
2662 });
2663 UnswitchedClones += Log2_32(Value: NonExitingSuccessors);
2664 }
2665
2666 // Ignore up to the "unscaled candidates" number of unswitch candidates
2667 // when calculating the power-of-two scaling of the cost. The main idea
2668 // with this control is to allow a small number of unswitches to happen
2669 // and rely more on siblings multiplier (see below) when the number
2670 // of candidates is small.
2671 unsigned ClonesPower = std::max(
2672 a: UnswitchedClones - Opts.unswitch_num_initial_unscaled_candidates, b: 0);
2673
2674 // Allowing top-level loops to spread a bit more than nested ones.
2675 int SiblingsMultiplier =
2676 std::max(a: (ParentL ? SiblingsCount
2677 : SiblingsCount / Opts.unswitch_siblings_toplevel_div),
2678 b: 1);
2679 // Compute the cost multiplier in a way that won't overflow by saturating
2680 // at an upper bound.
2681 int CostMultiplier;
2682 if (ClonesPower > Log2_32(Value: Opts.unswitch_threshold) ||
2683 SiblingsMultiplier > Opts.unswitch_threshold ||
2684 ParentLoopSizeMultiplier > Opts.unswitch_threshold)
2685 CostMultiplier = Opts.unswitch_threshold;
2686 else
2687 CostMultiplier = std::min(a: SiblingsMultiplier * (1 << ClonesPower),
2688 b: Opts.unswitch_threshold);
2689
2690 LLVM_DEBUG(dbgs() << " Computed multiplier " << CostMultiplier
2691 << " (siblings " << SiblingsMultiplier << " * parent size "
2692 << ParentLoopSizeMultiplier << " * clones "
2693 << (1 << ClonesPower) << ")"
2694 << " for unswitch candidate: " << TI << "\n");
2695 return CostMultiplier;
2696}
2697
2698static bool collectUnswitchCandidates(
2699 const ScalarOptions &Opts,
2700 SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates,
2701 IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch,
2702 const Loop &L, const LoopInfo &LI, AAResults &AA,
2703 const MemorySSAUpdater *MSSAU) {
2704 assert(UnswitchCandidates.empty() && "Should be!");
2705
2706 auto AddUnswitchCandidatesForInst = [&](Instruction *I, Value *Cond) {
2707 Cond = skipTrivialSelect(Cond);
2708 if (isa<Constant>(Val: Cond))
2709 return;
2710 if (L.isLoopInvariant(V: Cond)) {
2711 UnswitchCandidates.push_back(Elt: {I, {Cond}});
2712 return;
2713 }
2714 if (match(V: Cond, P: m_CombineOr(Ps: m_LogicalAnd(), Ps: m_LogicalOr()))) {
2715 TinyPtrVector<Value *> Invariants =
2716 collectHomogenousInstGraphLoopInvariants(
2717 L, Root&: *static_cast<Instruction *>(Cond), LI);
2718 if (!Invariants.empty())
2719 UnswitchCandidates.push_back(Elt: {I, std::move(Invariants)});
2720 }
2721 };
2722
2723 // Whether or not we should also collect guards in the loop.
2724 bool CollectGuards = false;
2725 if (Opts.simple_loop_unswitch_guards) {
2726 auto *GuardDecl = Intrinsic::getDeclarationIfExists(
2727 M: L.getHeader()->getParent()->getParent(), id: Intrinsic::experimental_guard);
2728 if (GuardDecl && !GuardDecl->use_empty())
2729 CollectGuards = true;
2730 }
2731
2732 for (auto *BB : L.blocks()) {
2733 if (LI.getLoopFor(BB) != &L)
2734 continue;
2735
2736 for (auto &I : *BB) {
2737 if (auto *SI = dyn_cast<SelectInst>(Val: &I)) {
2738 auto *Cond = SI->getCondition();
2739 // Do not unswitch vector selects and logical and/or selects
2740 if (Cond->getType()->isIntegerTy(BitWidth: 1) && !SI->getType()->isIntegerTy(BitWidth: 1))
2741 AddUnswitchCandidatesForInst(SI, Cond);
2742 } else if (CollectGuards && isGuard(U: &I)) {
2743 auto *Cond =
2744 skipTrivialSelect(Cond: cast<IntrinsicInst>(Val: &I)->getArgOperand(i: 0));
2745 // TODO: Support AND, OR conditions and partial unswitching.
2746 if (!isa<Constant>(Val: Cond) && L.isLoopInvariant(V: Cond))
2747 UnswitchCandidates.push_back(Elt: {&I, {Cond}});
2748 }
2749 }
2750
2751 if (auto *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) {
2752 // We can only consider fully loop-invariant switch conditions as we need
2753 // to completely eliminate the switch after unswitching.
2754 if (!isa<Constant>(Val: SI->getCondition()) &&
2755 L.isLoopInvariant(V: SI->getCondition()) && !BB->getUniqueSuccessor())
2756 UnswitchCandidates.push_back(Elt: {SI, {SI->getCondition()}});
2757 continue;
2758 }
2759
2760 auto *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
2761 if (!BI || BI->getSuccessor(i: 0) == BI->getSuccessor(i: 1))
2762 continue;
2763
2764 AddUnswitchCandidatesForInst(BI, BI->getCondition());
2765 }
2766
2767 BasicBlock *Header = L.getHeader();
2768 // Need to make sure the load instruction to be hoisted is always executed.
2769 bool HeaderCondGuaranteedToExecute =
2770 isGuaranteedToTransferExecutionToSuccessor(
2771 Begin: Header->begin(), End: Header->getTerminator()->getIterator());
2772 if (MSSAU && HeaderCondGuaranteedToExecute &&
2773 !findOptionMDForLoop(TheLoop: &L, Name: "llvm.loop.unswitch.partial.disable") &&
2774 !any_of(Range&: UnswitchCandidates, P: [&L](auto &TerminatorAndInvariants) {
2775 return TerminatorAndInvariants.TI == L.getHeader()->getTerminator();
2776 })) {
2777 MemorySSA *MSSA = MSSAU->getMemorySSA();
2778 if (auto Info = hasPartialIVCondition(
2779 L, MSSAThreshold: Opts.simple_loop_unswitch_memoryssa_threshold, MSSA: *MSSA, AA)) {
2780 LLVM_DEBUG(
2781 dbgs() << "simple-loop-unswitch: Found partially invariant condition "
2782 << *Info->InstToDuplicate[0] << "\n");
2783 PartialIVInfo = *Info;
2784 PartialIVCondBranch = Header->getTerminator();
2785 TinyPtrVector<Value *> ValsToDuplicate;
2786 llvm::append_range(C&: ValsToDuplicate, R&: Info->InstToDuplicate);
2787 UnswitchCandidates.push_back(
2788 Elt: {Header->getTerminator(), std::move(ValsToDuplicate)});
2789 }
2790 }
2791 return !UnswitchCandidates.empty();
2792}
2793
2794/// Tries to canonicalize condition described by:
2795///
2796/// br (LHS pred RHS), label IfTrue, label IfFalse
2797///
2798/// into its equivalent where `Pred` is something that we support for injected
2799/// invariants (so far it is limited to ult), LHS in canonicalized form is
2800/// non-invariant and RHS is an invariant.
2801static void canonicalizeForInvariantConditionInjection(CmpPredicate &Pred,
2802 Value *&LHS, Value *&RHS,
2803 BasicBlock *&IfTrue,
2804 BasicBlock *&IfFalse,
2805 const Loop &L) {
2806 if (!L.contains(BB: IfTrue)) {
2807 Pred = ICmpInst::getInversePredicate(pred: Pred);
2808 std::swap(a&: IfTrue, b&: IfFalse);
2809 }
2810
2811 // Move loop-invariant argument to RHS position.
2812 if (L.isLoopInvariant(V: LHS)) {
2813 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
2814 std::swap(a&: LHS, b&: RHS);
2815 }
2816
2817 if (Pred == ICmpInst::ICMP_SGE && match(V: RHS, P: m_Zero())) {
2818 // Turn "x >=s 0" into "x <u UMIN_INT"
2819 Pred = ICmpInst::ICMP_ULT;
2820 RHS = ConstantInt::get(
2821 Context&: RHS->getContext(),
2822 V: APInt::getSignedMinValue(numBits: RHS->getType()->getIntegerBitWidth()));
2823 }
2824}
2825
2826/// Returns true, if predicate described by ( \p Pred, \p LHS, \p RHS )
2827/// succeeding into blocks ( \p IfTrue, \p IfFalse) can be optimized by
2828/// injecting a loop-invariant condition.
2829static bool shouldTryInjectInvariantCondition(
2830 const ICmpInst::Predicate Pred, const Value *LHS, const Value *RHS,
2831 const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L) {
2832 if (L.isLoopInvariant(V: LHS) || !L.isLoopInvariant(V: RHS))
2833 return false;
2834 // TODO: Support other predicates.
2835 if (Pred != ICmpInst::ICMP_ULT)
2836 return false;
2837 // TODO: Support non-loop-exiting branches?
2838 if (!L.contains(BB: IfTrue) || L.contains(BB: IfFalse))
2839 return false;
2840 // FIXME: For some reason this causes problems with MSSA updates, need to
2841 // investigate why. So far, just don't unswitch latch.
2842 if (L.getHeader() == IfTrue)
2843 return false;
2844 return true;
2845}
2846
2847/// Returns true, if metadata on \p BI allows us to optimize branching into \p
2848/// TakenSucc via injection of invariant conditions. The branch should be not
2849/// enough and not previously unswitched, the information about this comes from
2850/// the metadata.
2851bool shouldTryInjectBasingOnMetadata(const ScalarOptions &Opts,
2852 const CondBrInst *BI,
2853 const BasicBlock *TakenSucc) {
2854 SmallVector<uint32_t> Weights;
2855 if (!extractBranchWeights(I: *BI, Weights))
2856 return false;
2857 unsigned T =
2858 Opts.simple_loop_unswitch_inject_invariant_condition_hotness_threshold;
2859 BranchProbability LikelyTaken(T - 1, T);
2860
2861 assert(Weights.size() == 2 && "Unexpected profile data!");
2862 size_t Idx = BI->getSuccessor(i: 0) == TakenSucc ? 0 : 1;
2863 auto Num = Weights[Idx];
2864 auto Denom = Weights[0] + Weights[1];
2865 // Degenerate or overflowed metadata.
2866 if (Denom == 0 || Num > Denom)
2867 return false;
2868 BranchProbability ActualTaken(Num, Denom);
2869 if (LikelyTaken > ActualTaken)
2870 return false;
2871 return true;
2872}
2873
2874/// Materialize pending invariant condition of the given candidate into IR. The
2875/// injected loop-invariant condition implies the original loop-variant branch
2876/// condition, so the materialization turns
2877///
2878/// loop_block:
2879/// ...
2880/// br i1 %variant_cond, label InLoopSucc, label OutOfLoopSucc
2881///
2882/// into
2883///
2884/// preheader:
2885/// %invariant_cond = LHS pred RHS
2886/// ...
2887/// loop_block:
2888/// br i1 %invariant_cond, label InLoopSucc, label OriginalCheck
2889/// OriginalCheck:
2890/// br i1 %variant_cond, label InLoopSucc, label OutOfLoopSucc
2891/// ...
2892static NonTrivialUnswitchCandidate
2893injectPendingInvariantConditions(NonTrivialUnswitchCandidate Candidate, Loop &L,
2894 DominatorTree &DT, LoopInfo &LI,
2895 AssumptionCache &AC, MemorySSAUpdater *MSSAU) {
2896 assert(Candidate.hasPendingInjection() && "Nothing to inject!");
2897 BasicBlock *Preheader = L.getLoopPreheader();
2898 assert(Preheader && "Loop is not in simplified form?");
2899 assert(LI.getLoopFor(Candidate.TI->getParent()) == &L &&
2900 "Unswitching branch of inner loop!");
2901
2902 auto Pred = Candidate.PendingInjection->Pred;
2903 auto *LHS = Candidate.PendingInjection->LHS;
2904 auto *RHS = Candidate.PendingInjection->RHS;
2905 auto *InLoopSucc = Candidate.PendingInjection->InLoopSucc;
2906 auto *TI = cast<CondBrInst>(Val: Candidate.TI);
2907 auto *BB = Candidate.TI->getParent();
2908 auto *OutOfLoopSucc = InLoopSucc == TI->getSuccessor(i: 0) ? TI->getSuccessor(i: 1)
2909 : TI->getSuccessor(i: 0);
2910 // FIXME: Remove this once limitation on successors is lifted.
2911 assert(L.contains(InLoopSucc) && "Not supported yet!");
2912 assert(!L.contains(OutOfLoopSucc) && "Not supported yet!");
2913 auto &Ctx = BB->getContext();
2914
2915 IRBuilder<> Builder(Preheader->getTerminator());
2916 assert(ICmpInst::isUnsigned(Pred) && "Not supported yet!");
2917 if (LHS->getType() != RHS->getType()) {
2918 if (LHS->getType()->getIntegerBitWidth() <
2919 RHS->getType()->getIntegerBitWidth())
2920 LHS = Builder.CreateZExt(V: LHS, DestTy: RHS->getType(), Name: LHS->getName() + ".wide");
2921 else
2922 RHS = Builder.CreateZExt(V: RHS, DestTy: LHS->getType(), Name: RHS->getName() + ".wide");
2923 }
2924 // Do not use builder here: CreateICmp may simplify this into a constant and
2925 // unswitching will break. Better optimize it away later.
2926 auto *InjectedCond =
2927 ICmpInst::Create(Op: Instruction::ICmp, Pred, S1: LHS, S2: RHS, Name: "injected.cond",
2928 InsertBefore: Preheader->getTerminator()->getIterator());
2929
2930 BasicBlock *CheckBlock = BasicBlock::Create(Context&: Ctx, Name: BB->getName() + ".check",
2931 Parent: BB->getParent(), InsertBefore: InLoopSucc);
2932 Builder.SetInsertPoint(TI);
2933 auto *InvariantBr =
2934 Builder.CreateCondBr(Cond: InjectedCond, True: InLoopSucc, False: CheckBlock);
2935 // We don't know anything about the relation between the limits.
2936 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *InvariantBr, DEBUG_TYPE);
2937
2938 Builder.SetInsertPoint(CheckBlock);
2939 Builder.CreateCondBr(Cond: TI->getCondition(), True: TI->getSuccessor(i: 0),
2940 False: TI->getSuccessor(i: 1),
2941 BranchWeights: TI->getMetadata(KindID: LLVMContext::MD_prof));
2942 TI->eraseFromParent();
2943
2944 // Fixup phis.
2945 for (auto &I : *InLoopSucc) {
2946 auto *PN = dyn_cast<PHINode>(Val: &I);
2947 if (!PN)
2948 break;
2949 auto *Inc = PN->getIncomingValueForBlock(BB);
2950 PN->addIncoming(V: Inc, BB: CheckBlock);
2951 }
2952 OutOfLoopSucc->replacePhiUsesWith(Old: BB, New: CheckBlock);
2953
2954 SmallVector<DominatorTree::UpdateType, 4> DTUpdates = {
2955 { DominatorTree::Insert, BB, CheckBlock },
2956 { DominatorTree::Insert, CheckBlock, InLoopSucc },
2957 { DominatorTree::Insert, CheckBlock, OutOfLoopSucc },
2958 { DominatorTree::Delete, BB, OutOfLoopSucc }
2959 };
2960
2961 DT.applyUpdates(Updates: DTUpdates);
2962 if (MSSAU)
2963 MSSAU->applyUpdates(Updates: DTUpdates, DT);
2964 L.addBasicBlockToLoop(NewBB: CheckBlock, LI);
2965
2966#ifndef NDEBUG
2967 DT.verify();
2968 LI.verify();
2969 if (MSSAU && VerifyMemorySSA)
2970 MSSAU->getMemorySSA()->verifyMemorySSA();
2971#endif
2972
2973 // TODO: In fact, cost of unswitching a new invariant candidate is *slightly*
2974 // higher because we have just inserted a new block. Need to think how to
2975 // adjust the cost of injected candidates when it was first computed.
2976 LLVM_DEBUG(dbgs() << "Injected a new loop-invariant branch " << *InvariantBr
2977 << " and considering it for unswitching.");
2978 ++NumInvariantConditionsInjected;
2979 return NonTrivialUnswitchCandidate(InvariantBr, { InjectedCond },
2980 Candidate.Cost);
2981}
2982
2983/// Given chain of loop branch conditions looking like:
2984/// br (Variant < Invariant1)
2985/// br (Variant < Invariant2)
2986/// br (Variant < Invariant3)
2987/// ...
2988/// collect set of invariant conditions on which we want to unswitch, which
2989/// look like:
2990/// Invariant1 <= Invariant2
2991/// Invariant2 <= Invariant3
2992/// ...
2993/// Though they might not immediately exist in the IR, we can still inject them.
2994static bool insertCandidatesWithPendingInjections(
2995 SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates, Loop &L,
2996 ICmpInst::Predicate Pred, ArrayRef<CompareDesc> Compares,
2997 const DominatorTree &DT) {
2998
2999 assert(ICmpInst::isRelational(Pred));
3000 assert(ICmpInst::isStrictPredicate(Pred));
3001 if (Compares.size() < 2)
3002 return false;
3003 ICmpInst::Predicate NonStrictPred = ICmpInst::getNonStrictPredicate(pred: Pred);
3004 for (auto Prev = Compares.begin(), Next = Compares.begin() + 1;
3005 Next != Compares.end(); ++Prev, ++Next) {
3006 Value *LHS = Next->Invariant;
3007 Value *RHS = Prev->Invariant;
3008 BasicBlock *InLoopSucc = Prev->InLoopSucc;
3009 InjectedInvariant ToInject(NonStrictPred, LHS, RHS, InLoopSucc);
3010 NonTrivialUnswitchCandidate Candidate(Prev->Term, { LHS, RHS },
3011 std::nullopt, std::move(ToInject));
3012 UnswitchCandidates.push_back(Elt: std::move(Candidate));
3013 }
3014 return true;
3015}
3016
3017/// Collect unswitch candidates by invariant conditions that are not immediately
3018/// present in the loop. However, they can be injected into the code if we
3019/// decide it's profitable.
3020/// An example of such conditions is following:
3021///
3022/// for (...) {
3023/// x = load ...
3024/// if (! x <u C1) break;
3025/// if (! x <u C2) break;
3026/// <do something>
3027/// }
3028///
3029/// We can unswitch by condition "C1 <=u C2". If that is true, then "x <u C1 <=
3030/// C2" automatically implies "x <u C2", so we can get rid of one of
3031/// loop-variant checks in unswitched loop version.
3032static bool collectUnswitchCandidatesWithInjections(
3033 const ScalarOptions &Opts,
3034 SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates,
3035 IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L,
3036 const DominatorTree &DT, const LoopInfo &LI, AAResults &AA,
3037 const MemorySSAUpdater *MSSAU) {
3038 if (!Opts.simple_loop_unswitch_inject_invariant_conditions)
3039 return false;
3040
3041 if (!DT.isReachableFromEntry(A: L.getHeader()))
3042 return false;
3043 auto *Latch = L.getLoopLatch();
3044 // Need to have a single latch and a preheader.
3045 if (!Latch)
3046 return false;
3047 assert(L.getLoopPreheader() && "Must have a preheader!");
3048
3049 DenseMap<Value *, SmallVector<CompareDesc, 4> > CandidatesULT;
3050 // Traverse the conditions that dominate latch (and therefore dominate each
3051 // other).
3052 for (auto *DTN = DT.getNode(BB: Latch); L.contains(BB: DTN->getBlock());
3053 DTN = DTN->getIDom()) {
3054 CmpPredicate Pred;
3055 Value *LHS = nullptr, *RHS = nullptr;
3056 BasicBlock *IfTrue = nullptr, *IfFalse = nullptr;
3057 auto *BB = DTN->getBlock();
3058 // Ignore inner loops.
3059 if (LI.getLoopFor(BB) != &L)
3060 continue;
3061 auto *Term = BB->getTerminator();
3062 if (!match(V: Term, P: m_Br(C: m_ICmp(Pred, L: m_Value(V&: LHS), R: m_Value(V&: RHS)),
3063 T: m_BasicBlock(V&: IfTrue), F: m_BasicBlock(V&: IfFalse))))
3064 continue;
3065 if (!LHS->getType()->isIntegerTy())
3066 continue;
3067 canonicalizeForInvariantConditionInjection(Pred, LHS, RHS, IfTrue, IfFalse,
3068 L);
3069 if (!shouldTryInjectInvariantCondition(Pred, LHS, RHS, IfTrue, IfFalse, L))
3070 continue;
3071 if (!shouldTryInjectBasingOnMetadata(Opts, BI: cast<CondBrInst>(Val: Term), TakenSucc: IfTrue))
3072 continue;
3073 // Strip ZEXT for unsigned predicate.
3074 // TODO: once signed predicates are supported, also strip SEXT.
3075 CompareDesc Desc(cast<CondBrInst>(Val: Term), RHS, IfTrue);
3076 while (auto *Zext = dyn_cast<ZExtInst>(Val: LHS))
3077 LHS = Zext->getOperand(i_nocapture: 0);
3078 CandidatesULT[LHS].push_back(Elt: Desc);
3079 }
3080
3081 bool Found = false;
3082 for (auto &It : CandidatesULT)
3083 Found |= insertCandidatesWithPendingInjections(
3084 UnswitchCandidates, L, Pred: ICmpInst::ICMP_ULT, Compares: It.second, DT);
3085 return Found;
3086}
3087
3088static bool isSafeForNoNTrivialUnswitching(const DominatorTree &DT, Loop &L,
3089 LoopInfo &LI) {
3090 if (!L.isSafeToCloneConditionally(DT))
3091 return false;
3092
3093 // Check if there are irreducible CFG cycles in this loop. If so, we cannot
3094 // easily unswitch non-trivial edges out of the loop. Doing so might turn the
3095 // irreducible control flow into reducible control flow and introduce new
3096 // loops "out of thin air". If we ever discover important use cases for doing
3097 // this, we can add support to loop unswitch, but it is a lot of complexity
3098 // for what seems little or no real world benefit.
3099 LoopBlocksRPO RPOT(&L);
3100 RPOT.perform(LI: &LI);
3101 if (containsIrreducibleCFG<const BasicBlock *>(RPOTraversal&: RPOT, LI))
3102 return false;
3103
3104 SmallVector<BasicBlock *, 4> ExitBlocks;
3105 L.getUniqueExitBlocks(ExitBlocks);
3106 // We cannot unswitch if exit blocks contain a cleanuppad/catchswitch
3107 // instruction as we don't know how to split those exit blocks.
3108 // FIXME: We should teach SplitBlock to handle this and remove this
3109 // restriction.
3110 for (auto *ExitBB : ExitBlocks) {
3111 auto It = ExitBB->getFirstNonPHIIt();
3112 if (isa<CleanupPadInst>(Val: It) || isa<CatchSwitchInst>(Val: It)) {
3113 LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch "
3114 "in exit block\n");
3115 return false;
3116 }
3117 }
3118
3119 return true;
3120}
3121
3122static NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate(
3123 const ScalarOptions &Opts,
3124 ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates, const Loop &L,
3125 const DominatorTree &DT, const LoopInfo &LI, AssumptionCache &AC,
3126 const TargetTransformInfo &TTI, const IVConditionInfo &PartialIVInfo) {
3127 // Given that unswitching these terminators will require duplicating parts of
3128 // the loop, so we need to be able to model that cost. Compute the ephemeral
3129 // values and set up a data structure to hold per-BB costs. We cache each
3130 // block's cost so that we don't recompute this when considering different
3131 // subsets of the loop for duplication during unswitching.
3132 SmallPtrSet<const Value *, 4> EphValues;
3133 CodeMetrics::collectEphemeralValues(L: &L, AC: &AC, EphValues);
3134 SmallDenseMap<BasicBlock *, InstructionCost, 4> BBCostMap;
3135
3136 // Compute the cost of each block, as well as the total loop cost. Also, bail
3137 // out if we see instructions which are incompatible with loop unswitching
3138 // (convergent, noduplicate, or cross-basic-block tokens).
3139 // FIXME: We might be able to safely handle some of these in non-duplicated
3140 // regions.
3141 TargetTransformInfo::TargetCostKind CostKind =
3142 L.getHeader()->getParent()->hasMinSize()
3143 ? TargetTransformInfo::TCK_CodeSize
3144 : TargetTransformInfo::TCK_SizeAndLatency;
3145 InstructionCost LoopCost = 0;
3146 for (auto *BB : L.blocks()) {
3147 InstructionCost Cost = 0;
3148 for (auto &I : *BB) {
3149 if (EphValues.count(Ptr: &I))
3150 continue;
3151 Cost += TTI.getInstructionCost(U: &I, CostKind);
3152 }
3153 assert(Cost >= 0 && "Must not have negative costs!");
3154 LoopCost += Cost;
3155 assert(LoopCost >= 0 && "Must not have negative loop costs!");
3156 BBCostMap[BB] = Cost;
3157 }
3158 LLVM_DEBUG(dbgs() << " Total loop cost: " << LoopCost << "\n");
3159
3160 // Now we find the best candidate by searching for the one with the following
3161 // properties in order:
3162 //
3163 // 1) An unswitching cost below the threshold
3164 // 2) The smallest number of duplicated unswitch candidates (to avoid
3165 // creating redundant subsequent unswitching)
3166 // 3) The smallest cost after unswitching.
3167 //
3168 // We prioritize reducing fanout of unswitch candidates provided the cost
3169 // remains below the threshold because this has a multiplicative effect.
3170 //
3171 // This requires memoizing each dominator subtree to avoid redundant work.
3172 //
3173 // FIXME: Need to actually do the number of candidates part above.
3174 SmallDenseMap<DomTreeNode *, InstructionCost, 4> DTCostMap;
3175 // Given a terminator which might be unswitched, computes the non-duplicated
3176 // cost for that terminator.
3177 auto ComputeUnswitchedCost = [&](Instruction &TI,
3178 bool FullUnswitch) -> InstructionCost {
3179 // Unswitching selects unswitches the entire loop.
3180 if (isa<SelectInst>(Val: TI))
3181 return LoopCost;
3182
3183 BasicBlock &BB = *TI.getParent();
3184 SmallPtrSet<BasicBlock *, 4> Visited;
3185
3186 InstructionCost Cost = 0;
3187 for (BasicBlock *SuccBB : successors(BB: &BB)) {
3188 // Don't count successors more than once.
3189 if (!Visited.insert(Ptr: SuccBB).second)
3190 continue;
3191
3192 // If this is a partial unswitch candidate, then it must be a conditional
3193 // branch with a condition of either `or`, `and`, their corresponding
3194 // select forms or partially invariant instructions. In that case, one of
3195 // the successors is necessarily duplicated, so don't even try to remove
3196 // its cost.
3197 if (!FullUnswitch) {
3198 auto &BI = cast<CondBrInst>(Val&: TI);
3199 Value *Cond = skipTrivialSelect(Cond: BI.getCondition());
3200 if (match(V: Cond, P: m_LogicalAnd())) {
3201 if (SuccBB == BI.getSuccessor(i: 1))
3202 continue;
3203 } else if (match(V: Cond, P: m_LogicalOr())) {
3204 if (SuccBB == BI.getSuccessor(i: 0))
3205 continue;
3206 } else if ((PartialIVInfo.KnownValue->isOneValue() &&
3207 SuccBB == BI.getSuccessor(i: 0)) ||
3208 (!PartialIVInfo.KnownValue->isOneValue() &&
3209 SuccBB == BI.getSuccessor(i: 1)))
3210 continue;
3211 }
3212
3213 // This successor's domtree will not need to be duplicated after
3214 // unswitching if the edge to the successor dominates it (and thus the
3215 // entire tree). This essentially means there is no other path into this
3216 // subtree and so it will end up live in only one clone of the loop.
3217 if (SuccBB->getUniquePredecessor() ||
3218 llvm::all_of(Range: predecessors(BB: SuccBB), P: [&](BasicBlock *PredBB) {
3219 return PredBB == &BB || DT.dominates(A: SuccBB, B: PredBB);
3220 })) {
3221 Cost += computeDomSubtreeCost(N&: *DT[SuccBB], BBCostMap, DTCostMap);
3222 assert(Cost <= LoopCost &&
3223 "Non-duplicated cost should never exceed total loop cost!");
3224 }
3225 }
3226
3227 // Now scale the cost by the number of unique successors minus one. We
3228 // subtract one because there is already at least one copy of the entire
3229 // loop. This is computing the new cost of unswitching a condition.
3230 // Note that guards always have 2 unique successors that are implicit and
3231 // will be materialized if we decide to unswitch it.
3232 int SuccessorsCount = isGuard(U: &TI) ? 2 : Visited.size();
3233 assert(SuccessorsCount > 1 &&
3234 "Cannot unswitch a condition without multiple distinct successors!");
3235 return (LoopCost - Cost) * (SuccessorsCount - 1);
3236 };
3237
3238 std::optional<NonTrivialUnswitchCandidate> Best;
3239 for (auto &Candidate : UnswitchCandidates) {
3240 Instruction &TI = *Candidate.TI;
3241 ArrayRef<Value *> Invariants = Candidate.Invariants;
3242 CondBrInst *BI = dyn_cast<CondBrInst>(Val: &TI);
3243 bool FullUnswitch =
3244 !BI || Candidate.hasPendingInjection() ||
3245 (Invariants.size() == 1 &&
3246 Invariants[0] == skipTrivialSelect(Cond: BI->getCondition()));
3247 InstructionCost CandidateCost = ComputeUnswitchedCost(TI, FullUnswitch);
3248 // Calculate cost multiplier which is a tool to limit potentially
3249 // exponential behavior of loop-unswitch.
3250 if (Opts.enable_unswitch_cost_multiplier) {
3251 int CostMultiplier = calculateUnswitchCostMultiplier(Opts, TI, L, LI, DT,
3252 UnswitchCandidates);
3253 assert(
3254 (CostMultiplier > 0 && CostMultiplier <= Opts.unswitch_threshold) &&
3255 "cost multiplier needs to be in the range of 1..UnswitchThreshold");
3256 CandidateCost *= CostMultiplier;
3257 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost
3258 << " (multiplier: " << CostMultiplier << ")"
3259 << " for unswitch candidate: " << TI << "\n");
3260 } else {
3261 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost
3262 << " for unswitch candidate: " << TI << "\n");
3263 }
3264
3265 if (!Best || CandidateCost < Best->Cost) {
3266 Best = Candidate;
3267 Best->Cost = CandidateCost;
3268 }
3269 }
3270 assert(Best && "Must be!");
3271 return *Best;
3272}
3273
3274// Insert a freeze on an unswitched branch if all is true:
3275// 1. freeze-loop-unswitch-cond option is true
3276// 2. The branch may not execute in the loop pre-transformation. If a branch may
3277// not execute and could cause UB, it would always cause UB if it is hoisted outside
3278// of the loop. Insert a freeze to prevent this case.
3279// 3. The branch condition may be poison or undef
3280static bool shouldInsertFreeze(const ScalarOptions &Opts, Loop &L,
3281 Instruction &TI, DominatorTree &DT,
3282 AssumptionCache &AC) {
3283 assert(isa<CondBrInst>(TI) || isa<SwitchInst>(TI));
3284 if (!Opts.freeze_loop_unswitch_cond)
3285 return false;
3286
3287 ICFLoopSafetyInfo SafetyInfo(&L);
3288 if (SafetyInfo.isGuaranteedToExecute(Inst: TI, DT: &DT))
3289 return false;
3290
3291 Value *Cond;
3292 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: &TI))
3293 Cond = skipTrivialSelect(Cond: BI->getCondition());
3294 else
3295 Cond = skipTrivialSelect(Cond: cast<SwitchInst>(Val: &TI)->getCondition());
3296 return !isGuaranteedNotToBeUndefOrPoison(
3297 V: Cond, AC: &AC, CtxI: L.getLoopPreheader()->getTerminator(), DT: &DT);
3298}
3299
3300static bool unswitchBestCondition(const ScalarOptions &Opts, Loop &L,
3301 DominatorTree &DT, LoopInfo &LI,
3302 AssumptionCache &AC, AAResults &AA,
3303 TargetTransformInfo &TTI, ScalarEvolution *SE,
3304 MemorySSAUpdater *MSSAU,
3305 LPMUpdater &LoopUpdater) {
3306 // Collect all invariant conditions within this loop (as opposed to an inner
3307 // loop which would be handled when visiting that inner loop).
3308 SmallVector<NonTrivialUnswitchCandidate, 4> UnswitchCandidates;
3309 IVConditionInfo PartialIVInfo;
3310 Instruction *PartialIVCondBranch = nullptr;
3311 collectUnswitchCandidates(Opts, UnswitchCandidates, PartialIVInfo,
3312 PartialIVCondBranch, L, LI, AA, MSSAU);
3313 if (!findOptionMDForLoop(TheLoop: &L, Name: "llvm.loop.unswitch.injection.disable"))
3314 collectUnswitchCandidatesWithInjections(Opts, UnswitchCandidates,
3315 PartialIVInfo, PartialIVCondBranch,
3316 L, DT, LI, AA, MSSAU);
3317 // If we didn't find any candidates, we're done.
3318 if (UnswitchCandidates.empty())
3319 return false;
3320
3321 LLVM_DEBUG(
3322 dbgs() << "Considering " << UnswitchCandidates.size()
3323 << " non-trivial loop invariant conditions for unswitching.\n");
3324
3325 NonTrivialUnswitchCandidate Best = findBestNonTrivialUnswitchCandidate(
3326 Opts, UnswitchCandidates, L, DT, LI, AC, TTI, PartialIVInfo);
3327
3328 assert(Best.TI && "Failed to find loop unswitch candidate");
3329 assert(Best.Cost && "Failed to compute cost");
3330
3331 if (*Best.Cost >= Opts.unswitch_threshold) {
3332 LLVM_DEBUG(dbgs() << "Cannot unswitch, lowest cost found: " << *Best.Cost
3333 << "\n");
3334 return false;
3335 }
3336
3337 bool InjectedCondition = false;
3338 if (Best.hasPendingInjection()) {
3339 Best = injectPendingInvariantConditions(Candidate: Best, L, DT, LI, AC, MSSAU);
3340 InjectedCondition = true;
3341 }
3342 assert(!Best.hasPendingInjection() &&
3343 "All injections should have been done by now!");
3344
3345 if (Best.TI != PartialIVCondBranch)
3346 PartialIVInfo.InstToDuplicate.clear();
3347
3348 bool InsertFreeze;
3349 if (auto *SI = dyn_cast<SelectInst>(Val: Best.TI)) {
3350 // If the best candidate is a select, turn it into a branch. Select
3351 // instructions with a poison conditional do not propagate poison, but
3352 // branching on poison causes UB. Insert a freeze on the select
3353 // conditional to prevent UB after turning the select into a branch.
3354 InsertFreeze = !isGuaranteedNotToBeUndefOrPoison(
3355 V: SI->getCondition(), AC: &AC, CtxI: L.getLoopPreheader()->getTerminator(), DT: &DT);
3356 Best.TI = turnSelectIntoBranch(SI, DT, LI, MSSAU, AC: &AC);
3357 } else {
3358 // If the best candidate is a guard, turn it into a branch.
3359 if (isGuard(U: Best.TI))
3360 Best.TI = turnGuardIntoBranch(Opts, GI: cast<IntrinsicInst>(Val: Best.TI), L, DT,
3361 LI, MSSAU);
3362 InsertFreeze = shouldInsertFreeze(Opts, L, TI&: *Best.TI, DT, AC);
3363 }
3364
3365 LLVM_DEBUG(dbgs() << " Unswitching non-trivial (cost = " << Best.Cost
3366 << ") terminator: " << *Best.TI << "\n");
3367 unswitchNontrivialInvariants(Opts, L, TI&: *Best.TI, Invariants: Best.Invariants,
3368 PartialIVInfo, DT, LI, AC, SE, MSSAU,
3369 LoopUpdater, InsertFreeze, InjectedCondition);
3370 return true;
3371}
3372
3373/// Unswitch control flow predicated on loop invariant conditions.
3374///
3375/// This first hoists all branches or switches which are trivial (IE, do not
3376/// require duplicating any part of the loop) out of the loop body. It then
3377/// looks at other loop invariant control flows and tries to unswitch those as
3378/// well by cloning the loop if the result is small enough.
3379///
3380/// The `DT`, `LI`, `AC`, `AA`, `TTI` parameters are required analyses that are
3381/// also updated based on the unswitch. The `MSSA` analysis is also updated if
3382/// valid (i.e. its use is enabled).
3383///
3384/// If either `NonTrivial` is true or the flag `EnableNonTrivialUnswitch` is
3385/// true, we will attempt to do non-trivial unswitching as well as trivial
3386/// unswitching.
3387///
3388/// The `postUnswitch` function will be run after unswitching is complete
3389/// with information on whether or not the provided loop remains a loop and
3390/// a list of new sibling loops created.
3391///
3392/// If `SE` is non-null, we will update that analysis based on the unswitching
3393/// done.
3394static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI,
3395 AssumptionCache &AC, AAResults &AA,
3396 TargetTransformInfo &TTI, bool Trivial,
3397 bool NonTrivial, ScalarEvolution *SE,
3398 MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater) {
3399 const ScalarOptions &Opts = getScalarOptions(L);
3400 assert(L.isRecursivelyLCSSAForm(DT, LI) &&
3401 "Loops must be in LCSSA form before unswitching.");
3402
3403 // Must be in loop simplified form: we need a preheader and dedicated exits.
3404 if (!L.isLoopSimplifyForm())
3405 return false;
3406
3407 // Try trivial unswitch first before loop over other basic blocks in the loop.
3408 if (Trivial && unswitchAllTrivialConditions(Opts, L, DT, LI, SE, MSSAU)) {
3409 // If we unswitched successfully we will want to clean up the loop before
3410 // processing it further so just mark it as unswitched and return.
3411 postUnswitch(L, U&: LoopUpdater, LoopName: L.getName(),
3412 /*CurrentLoopValid*/ true, /*PartiallyInvariant*/ false,
3413 /*InjectedCondition*/ false, NewLoops: {});
3414 return true;
3415 }
3416
3417 const Function *F = L.getHeader()->getParent();
3418
3419 // Check whether we should continue with non-trivial conditions.
3420 // EnableNonTrivialUnswitch: Global variable that forces non-trivial
3421 // unswitching for testing and debugging.
3422 // NonTrivial: Parameter that enables non-trivial unswitching for this
3423 // invocation of the transform. But this should be allowed only
3424 // for targets without branch divergence.
3425 //
3426 // FIXME: If divergence analysis becomes available to a loop
3427 // transform, we should allow unswitching for non-trivial uniform
3428 // branches even on targets that have divergence.
3429 // https://bugs.llvm.org/show_bug.cgi?id=48819
3430 bool ContinueWithNonTrivial = Opts.enable_nontrivial_unswitch ||
3431 (NonTrivial && !TTI.hasBranchDivergence(F));
3432 if (!ContinueWithNonTrivial)
3433 return false;
3434
3435 // Skip non-trivial unswitching for optsize functions.
3436 if (F->hasOptSize())
3437 return false;
3438
3439 // Perform legality checks.
3440 if (!isSafeForNoNTrivialUnswitching(DT, L, LI))
3441 return false;
3442
3443 // For non-trivial unswitching, because it often creates new loops, we rely on
3444 // the pass manager to iterate on the loops rather than trying to immediately
3445 // reach a fixed point. There is no substantial advantage to iterating
3446 // internally, and if any of the new loops are simplified enough to contain
3447 // trivial unswitching we want to prefer those.
3448
3449 // Try to unswitch the best invariant condition. We prefer this full unswitch to
3450 // a partial unswitch when possible below the threshold.
3451 if (unswitchBestCondition(Opts, L, DT, LI, AC, AA, TTI, SE, MSSAU,
3452 LoopUpdater))
3453 return true;
3454
3455 // No other opportunities to unswitch.
3456 return false;
3457}
3458
3459PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
3460 LoopStandardAnalysisResults &AR,
3461 LPMUpdater &U) {
3462 Function &F = *L.getHeader()->getParent();
3463 (void)F;
3464 LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L
3465 << "\n");
3466
3467 std::optional<MemorySSAUpdater> MSSAU;
3468 if (AR.MSSA) {
3469 MSSAU = MemorySSAUpdater(AR.MSSA);
3470 if (VerifyMemorySSA)
3471 AR.MSSA->verifyMemorySSA();
3472 }
3473 if (!unswitchLoop(L, DT&: AR.DT, LI&: AR.LI, AC&: AR.AC, AA&: AR.AA, TTI&: AR.TTI, Trivial, NonTrivial,
3474 SE: &AR.SE, MSSAU: MSSAU ? &*MSSAU : nullptr, LoopUpdater&: U))
3475 return PreservedAnalyses::all();
3476
3477 if (AR.MSSA && VerifyMemorySSA)
3478 AR.MSSA->verifyMemorySSA();
3479
3480#ifdef EXPENSIVE_CHECKS
3481 // Historically this pass has had issues with the dominator tree so verify it
3482 // in asserts builds.
3483 assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
3484#endif
3485
3486 auto PA = getLoopPassPreservedAnalyses();
3487 if (AR.MSSA)
3488 PA.preserve<MemorySSAAnalysis>();
3489 return PA;
3490}
3491
3492void SimpleLoopUnswitchPass::printPipeline(
3493 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
3494 static_cast<PassInfoMixin<SimpleLoopUnswitchPass> *>(this)->printPipeline(
3495 OS, MapClassName2PassName);
3496
3497 OS << '<';
3498 OS << (NonTrivial ? "" : "no-") << "nontrivial;";
3499 OS << (Trivial ? "" : "no-") << "trivial";
3500 OS << '>';
3501}
3502