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