1//===----------------- LoopRotationUtils.cpp -----------------------------===//
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// This file provides utilities to convert a loop into a loop with bottom test.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/LoopRotationUtils.h"
14#include "llvm/ADT/Statistic.h"
15#include "llvm/Analysis/AssumptionCache.h"
16#include "llvm/Analysis/CodeMetrics.h"
17#include "llvm/Analysis/DomTreeUpdater.h"
18#include "llvm/Analysis/InstructionSimplify.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/Analysis/MemorySSA.h"
21#include "llvm/Analysis/MemorySSAUpdater.h"
22#include "llvm/Analysis/ScalarEvolution.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/DebugInfo.h"
26#include "llvm/IR/Dominators.h"
27#include "llvm/IR/IntrinsicInst.h"
28#include "llvm/IR/MDBuilder.h"
29#include "llvm/IR/ProfDataUtils.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32#include "llvm/Transforms/Utils/BasicBlockUtils.h"
33#include "llvm/Transforms/Utils/Cloning.h"
34#include "llvm/Transforms/Utils/Local.h"
35#include "llvm/Transforms/Utils/SSAUpdater.h"
36#include "llvm/Transforms/Utils/ValueMapper.h"
37using namespace llvm;
38
39#define DEBUG_TYPE "loop-rotate"
40
41STATISTIC(NumNotRotatedDueToHeaderSize,
42 "Number of loops not rotated due to the header size");
43STATISTIC(NumInstrsHoisted,
44 "Number of instructions hoisted into loop preheader");
45STATISTIC(NumInstrsDuplicated,
46 "Number of instructions cloned into loop preheader");
47
48// Probability that a rotated loop has zero trip count / is never entered.
49static constexpr uint32_t ZeroTripCountWeights[] = {1, 127};
50
51namespace {
52/// A simple loop rotation transformation.
53class LoopRotate {
54 const unsigned MaxHeaderSize;
55 LoopInfo *LI;
56 const TargetTransformInfo *TTI;
57 AssumptionCache *AC;
58 DominatorTree *DT;
59 ScalarEvolution *SE;
60 MemorySSAUpdater *MSSAU;
61 const SimplifyQuery &SQ;
62 bool RotationOnly;
63 bool IsUtilMode;
64 bool PrepareForLTO;
65 bool CheckExitCount;
66
67public:
68 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
69 const TargetTransformInfo *TTI, AssumptionCache *AC,
70 DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
71 const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,
72 bool PrepareForLTO, bool CheckExitCount)
73 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
74 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
75 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO),
76 CheckExitCount(CheckExitCount) {}
77 bool processLoop(Loop *L);
78
79private:
80 bool rotateLoop(Loop *L, bool SimplifiedLatch);
81 bool simplifyLoopLatch(Loop *L);
82};
83} // end anonymous namespace
84
85/// Insert (K, V) pair into the ValueToValueMap, and verify the key did not
86/// previously exist in the map, and the value was inserted.
87static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V) {
88 bool Inserted = VM.insert(KV: {K, V}).second;
89 assert(Inserted);
90 (void)Inserted;
91}
92/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
93/// old header into the preheader. If there were uses of the values produced by
94/// these instruction that were outside of the loop, we have to insert PHI nodes
95/// to merge the two values. Do this now.
96static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
97 BasicBlock *OrigPreheader,
98 ValueToValueMapTy &ValueMap,
99 ScalarEvolution *SE,
100 SmallVectorImpl<PHINode*> *InsertedPHIs) {
101 // Remove PHI node entries that are no longer live.
102 BasicBlock::iterator I, E = OrigHeader->end();
103 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(Val&: I); ++I)
104 PN->removeIncomingValue(BB: OrigPreheader);
105
106 // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
107 // as necessary.
108 SSAUpdater SSA(InsertedPHIs);
109 for (I = OrigHeader->begin(); I != E; ++I) {
110 Value *OrigHeaderVal = &*I;
111
112 // If there are no uses of the value (e.g. because it returns void), there
113 // is nothing to rewrite.
114 if (OrigHeaderVal->use_empty())
115 continue;
116
117 Value *OrigPreHeaderVal = ValueMap.lookup(Val: OrigHeaderVal);
118
119 // The value now exits in two versions: the initial value in the preheader
120 // and the loop "next" value in the original header.
121 SSA.Initialize(Ty: OrigHeaderVal->getType(), Name: OrigHeaderVal->getName());
122 // Force re-computation of OrigHeaderVal, as some users now need to use the
123 // new PHI node.
124 if (SE)
125 SE->forgetValue(V: OrigHeaderVal);
126 SSA.AddAvailableValue(BB: OrigHeader, V: OrigHeaderVal);
127 SSA.AddAvailableValue(BB: OrigPreheader, V: OrigPreHeaderVal);
128
129 // Visit each use of the OrigHeader instruction.
130 for (Use &U : llvm::make_early_inc_range(Range: OrigHeaderVal->uses())) {
131 // SSAUpdater can't handle a non-PHI use in the same block as an
132 // earlier def. We can easily handle those cases manually.
133 Instruction *UserInst = cast<Instruction>(Val: U.getUser());
134 if (!isa<PHINode>(Val: UserInst)) {
135 BasicBlock *UserBB = UserInst->getParent();
136
137 // The original users in the OrigHeader are already using the
138 // original definitions.
139 if (UserBB == OrigHeader)
140 continue;
141
142 // Users in the OrigPreHeader need to use the value to which the
143 // original definitions are mapped.
144 if (UserBB == OrigPreheader) {
145 U = OrigPreHeaderVal;
146 continue;
147 }
148 }
149
150 // Anything else can be handled by SSAUpdater.
151 SSA.RewriteUse(U);
152 }
153
154 // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
155 // intrinsics.
156 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
157 llvm::findDbgValues(V: OrigHeaderVal, DbgVariableRecords);
158
159 for (DbgVariableRecord *DVR : DbgVariableRecords) {
160 // The original users in the OrigHeader are already using the original
161 // definitions.
162 BasicBlock *UserBB = DVR->getMarker()->getParent();
163 if (UserBB == OrigHeader)
164 continue;
165
166 // Users in the OrigPreHeader need to use the value to which the
167 // original definitions are mapped and anything else can be handled by
168 // the SSAUpdater. To avoid adding PHINodes, check if the value is
169 // available in UserBB, if not substitute poison.
170 Value *NewVal;
171 if (UserBB == OrigPreheader)
172 NewVal = OrigPreHeaderVal;
173 else if (SSA.HasValueForBlock(BB: UserBB))
174 NewVal = SSA.GetValueInMiddleOfBlock(BB: UserBB);
175 else
176 NewVal = PoisonValue::get(T: OrigHeaderVal->getType());
177 DVR->replaceVariableLocationOp(OldValue: OrigHeaderVal, NewValue: NewVal);
178 }
179 }
180}
181
182// Assuming both header and latch are exiting, check if rotating is profitable:
183// either a header phi becomes dead, or rotating makes the latch exit count
184// computable (enabling downstream optimizations like unrolling/vectorization).
185static bool profitableToRotateLoopExitingLatch(Loop *L, ScalarEvolution *SE) {
186 BasicBlock *Header = L->getHeader();
187 BasicBlock *Latch = L->getLoopLatch();
188 CondBrInst *BI = dyn_cast<CondBrInst>(Val: Header->getTerminator());
189 BasicBlock *HeaderExit = BI->getSuccessor(i: 0);
190 if (L->contains(BB: HeaderExit))
191 HeaderExit = BI->getSuccessor(i: 1);
192
193 for (auto &Phi : Header->phis()) {
194 // Look for uses of this phi in the loop/via exits other than the header.
195 if (llvm::any_of(Range: Phi.users(), P: [HeaderExit](const User *U) {
196 return cast<Instruction>(Val: U)->getParent() != HeaderExit;
197 }))
198 continue;
199 return true;
200 }
201
202 // Check if rotating would make the latch exit count computable, enabling
203 // optimizations like runtime unrolling and vectorization.
204 if (SE && isa<SCEVCouldNotCompute>(Val: SE->getExitCount(L, ExitingBlock: Latch)) &&
205 !isa<SCEVCouldNotCompute>(Val: SE->getExitCount(L, ExitingBlock: Header)))
206 return true;
207
208 return false;
209}
210
211static void updateBranchWeights(CondBrInst &PreHeaderBI, CondBrInst &LoopBI,
212 bool HasConditionalPreHeader,
213 bool SuccsSwapped) {
214 MDNode *WeightMD = getBranchWeightMDNode(I: PreHeaderBI);
215 if (WeightMD == nullptr)
216 return;
217
218 // LoopBI should currently be a clone of PreHeaderBI with the same
219 // metadata. But we double check to make sure we don't have a degenerate case
220 // where instsimplify changed the instructions.
221 if (WeightMD != getBranchWeightMDNode(I: LoopBI))
222 return;
223
224 SmallVector<uint32_t, 2> Weights;
225 extractFromBranchWeightMD32(ProfileData: WeightMD, Weights);
226 if (Weights.size() != 2)
227 return;
228 uint32_t OrigLoopExitWeight = Weights[0];
229 uint32_t OrigLoopBackedgeWeight = Weights[1];
230
231 if (SuccsSwapped)
232 std::swap(a&: OrigLoopExitWeight, b&: OrigLoopBackedgeWeight);
233
234 // Update branch weights. Consider the following edge-counts:
235 //
236 // | |-------- |
237 // V V | V
238 // Br i1 ... | Br i1 ...
239 // | | | | |
240 // x| y| | becomes: | y0| |-----
241 // V V | | V V |
242 // Exit Loop | | Loop |
243 // | | | Br i1 ... |
244 // ----- | | | |
245 // x0| x1| y1 | |
246 // V V ----
247 // Exit
248 //
249 // The following must hold:
250 // - x == x0 + x1 # counts to "exit" must stay the same.
251 // - y0 == x - x0 == x1 # how often loop was entered at all.
252 // - y1 == y - y0 # How often loop was repeated (after first iter.).
253 //
254 // We cannot generally deduce how often we had a zero-trip count loop so we
255 // have to make a guess for how to distribute x among the new x0 and x1.
256
257 uint32_t ExitWeight0; // aka x0
258 uint32_t ExitWeight1; // aka x1
259 uint32_t EnterWeight; // aka y0
260 uint32_t LoopBackWeight; // aka y1
261 if (OrigLoopExitWeight > 0 && OrigLoopBackedgeWeight > 0) {
262 ExitWeight0 = 0;
263 if (HasConditionalPreHeader) {
264 // Here we cannot know how many 0-trip count loops we have, so we guess:
265 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) {
266 // If the loop count is bigger than the exit count then we set
267 // probabilities as if 0-trip count nearly never happens.
268 ExitWeight0 = ZeroTripCountWeights[0];
269 // Scale up counts if necessary so we can match `ZeroTripCountWeights`
270 // for the `ExitWeight0`:`ExitWeight1` (aka `x0`:`x1` ratio`) ratio.
271 while (OrigLoopExitWeight < ZeroTripCountWeights[1] + ExitWeight0) {
272 // ... but don't overflow.
273 uint32_t const HighBit = uint32_t{1} << (sizeof(uint32_t) * 8 - 1);
274 if ((OrigLoopBackedgeWeight & HighBit) != 0 ||
275 (OrigLoopExitWeight & HighBit) != 0)
276 break;
277 OrigLoopBackedgeWeight <<= 1;
278 OrigLoopExitWeight <<= 1;
279 }
280 } else {
281 // If there's a higher exit-count than backedge-count then we set
282 // probabilities as if there are only 0-trip and 1-trip cases.
283 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight;
284 }
285 } else {
286 // Theoretically, if the loop body must be executed at least once, the
287 // backedge count must be not less than exit count. However the branch
288 // weight collected by sampling-based PGO may be not very accurate due to
289 // sampling. Therefore this workaround is required here to avoid underflow
290 // of unsigned in following update of branch weight.
291 if (OrigLoopExitWeight > OrigLoopBackedgeWeight)
292 OrigLoopBackedgeWeight = OrigLoopExitWeight;
293 }
294 assert(OrigLoopExitWeight >= ExitWeight0 && "Bad branch weight");
295 ExitWeight1 = OrigLoopExitWeight - ExitWeight0;
296 EnterWeight = ExitWeight1;
297 assert(OrigLoopBackedgeWeight >= EnterWeight && "Bad branch weight");
298 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight;
299 } else if (OrigLoopExitWeight == 0) {
300 if (OrigLoopBackedgeWeight == 0) {
301 // degenerate case... keep everything zero...
302 ExitWeight0 = 0;
303 ExitWeight1 = 0;
304 EnterWeight = 0;
305 LoopBackWeight = 0;
306 } else {
307 // Special case "LoopExitWeight == 0" weights which behaves like an
308 // endless where we don't want loop-enttry (y0) to be the same as
309 // loop-exit (x1).
310 ExitWeight0 = 0;
311 ExitWeight1 = 0;
312 EnterWeight = 1;
313 LoopBackWeight = OrigLoopBackedgeWeight;
314 }
315 } else {
316 // loop is never entered.
317 assert(OrigLoopBackedgeWeight == 0 && "remaining case is backedge zero");
318 ExitWeight0 = 1;
319 ExitWeight1 = 1;
320 EnterWeight = 0;
321 LoopBackWeight = 0;
322 }
323
324 const uint32_t LoopBIWeights[] = {
325 SuccsSwapped ? LoopBackWeight : ExitWeight1,
326 SuccsSwapped ? ExitWeight1 : LoopBackWeight,
327 };
328 setBranchWeights(I&: LoopBI, Weights: LoopBIWeights, /*IsExpected=*/false);
329 if (HasConditionalPreHeader) {
330 const uint32_t PreHeaderBIWeights[] = {
331 SuccsSwapped ? EnterWeight : ExitWeight0,
332 SuccsSwapped ? ExitWeight0 : EnterWeight,
333 };
334 setBranchWeights(I&: PreHeaderBI, Weights: PreHeaderBIWeights, /*IsExpected=*/false);
335 }
336}
337
338/// Rotate loop LP. Return true if the loop is rotated.
339///
340/// \param SimplifiedLatch is true if the latch was just folded into the final
341/// loop exit. In this case we may want to rotate even though the new latch is
342/// now an exiting branch. This rotation would have happened had the latch not
343/// been simplified. However, if SimplifiedLatch is false, then we avoid
344/// rotating loops in which the latch exits to avoid excessive or endless
345/// rotation. LoopRotate should be repeatable and converge to a canonical
346/// form. This property is satisfied because simplifying the loop latch can only
347/// happen once across multiple invocations of the LoopRotate pass.
348bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
349 // If the loop has only one block then there is not much to rotate.
350 if (L->getBlocks().size() == 1)
351 return false;
352
353 bool Rotated = false;
354 BasicBlock *OrigHeader = L->getHeader();
355 BasicBlock *OrigLatch = L->getLoopLatch();
356
357 CondBrInst *BI = dyn_cast<CondBrInst>(Val: OrigHeader->getTerminator());
358 if (!BI)
359 return Rotated;
360
361 // If the loop header is not one of the loop exiting blocks then
362 // either this loop is already rotated or it is not
363 // suitable for loop rotation transformations.
364 if (!L->isLoopExiting(BB: OrigHeader))
365 return Rotated;
366
367 // If the loop latch already contains a branch that leaves the loop then the
368 // loop is already rotated.
369 if (!OrigLatch)
370 return Rotated;
371
372 // Rotate if the loop latch was just simplified. Or if it makes the loop exit
373 // count computable. Or if we think it will be profitable.
374 if (L->isLoopExiting(BB: OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
375 !profitableToRotateLoopExitingLatch(L, SE: CheckExitCount ? SE : nullptr))
376 return Rotated;
377
378 // Check size of original header and reject loop if it is very big or we can't
379 // duplicate blocks inside it.
380 {
381 SmallPtrSet<const Value *, 32> EphValues;
382 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
383
384 CodeMetrics Metrics;
385 Metrics.analyzeBasicBlock(BB: OrigHeader, TTI: *TTI, EphValues, PrepareForLTO);
386 if (Metrics.notDuplicatable) {
387 LLVM_DEBUG(
388 dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
389 << " instructions: ";
390 L->dump());
391 return Rotated;
392 }
393 if (Metrics.Convergence != ConvergenceKind::None) {
394 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
395 "instructions: ";
396 L->dump());
397 return Rotated;
398 }
399 if (!Metrics.NumInsts.isValid()) {
400 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions"
401 " with invalid cost: ";
402 L->dump());
403 return Rotated;
404 }
405 if (Metrics.NumInsts > MaxHeaderSize) {
406 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
407 << Metrics.NumInsts
408 << " instructions, which is more than the threshold ("
409 << MaxHeaderSize << " instructions): ";
410 L->dump());
411 ++NumNotRotatedDueToHeaderSize;
412 return Rotated;
413 }
414
415 // When preparing for LTO, avoid rotating loops with calls that could be
416 // inlined during the LTO stage.
417 if (PrepareForLTO && Metrics.NumInlineCandidates > 0)
418 return Rotated;
419 }
420
421 // Now, this loop is suitable for rotation.
422 BasicBlock *OrigPreheader = L->getLoopPreheader();
423
424 // If the loop could not be converted to canonical form, it must have an
425 // indirectbr in it, just give up.
426 if (!OrigPreheader || !L->hasDedicatedExits())
427 return Rotated;
428
429 // Anything ScalarEvolution may know about this loop or the PHI nodes
430 // in its header will soon be invalidated. We should also invalidate
431 // all outer loops because insertion and deletion of blocks that happens
432 // during the rotation may violate invariants related to backedge taken
433 // infos in them.
434 if (SE) {
435 SE->forgetTopmostLoop(L);
436 // We may hoist some instructions out of loop. In case if they were cached
437 // as "loop variant" or "loop computable", these caches must be dropped.
438 // We also may fold basic blocks, so cached block dispositions also need
439 // to be dropped.
440 SE->forgetBlockAndLoopDispositions();
441 }
442
443 LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
444 if (MSSAU && VerifyMemorySSA)
445 MSSAU->getMemorySSA()->verifyMemorySSA();
446
447 // Find new Loop header. NewHeader is a Header's one and only successor
448 // that is inside loop. Header's other successor is outside the
449 // loop. Otherwise loop is not suitable for rotation.
450 BasicBlock *Exit = BI->getSuccessor(i: 0);
451 BasicBlock *NewHeader = BI->getSuccessor(i: 1);
452 bool BISuccsSwapped = L->contains(BB: Exit);
453 if (BISuccsSwapped)
454 std::swap(a&: Exit, b&: NewHeader);
455 assert(NewHeader && "Unable to determine new loop header");
456 assert(L->contains(NewHeader) && !L->contains(Exit) &&
457 "Unable to determine loop header and exit blocks");
458
459 // This code assumes that the new header has exactly one predecessor.
460 // Remove any single-entry PHI nodes in it.
461 assert(NewHeader->getSinglePredecessor() &&
462 "New header doesn't have one pred!");
463 FoldSingleEntryPHINodes(BB: NewHeader);
464
465 // Begin by walking OrigHeader and populating ValueMap with an entry for
466 // each Instruction.
467 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
468 ValueToValueMapTy ValueMap, ValueMapMSSA;
469
470 // For PHI nodes, the value available in OldPreHeader is just the
471 // incoming value from OldPreHeader.
472 for (; PHINode *PN = dyn_cast<PHINode>(Val&: I); ++I)
473 InsertNewValueIntoMap(VM&: ValueMap, K: PN,
474 V: PN->getIncomingValueForBlock(BB: OrigPreheader));
475
476 // For the rest of the instructions, either hoist to the OrigPreheader if
477 // possible or create a clone in the OldPreHeader if not.
478 Instruction *LoopEntryBranch = OrigPreheader->getTerminator();
479
480 // Record all debug records preceding LoopEntryBranch to avoid
481 // duplication.
482 using DbgHash =
483 std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;
484 auto makeHash = [](const DbgVariableRecord *D) -> DbgHash {
485 auto VarLocOps = D->location_ops();
486 return {{hash_combine_range(R&: VarLocOps), D->getVariable()},
487 D->getExpression()};
488 };
489
490 SmallDenseSet<DbgHash, 8> DbgRecords;
491 // Build DbgVariableRecord hashes for DbgVariableRecords attached to the
492 // terminator.
493 for (const DbgVariableRecord &DVR :
494 filterDbgVars(R: OrigPreheader->getTerminator()->getDbgRecordRange()))
495 DbgRecords.insert(V: makeHash(&DVR));
496
497 // Remember the local noalias scope declarations in the header. After the
498 // rotation, they must be duplicated and the scope must be cloned. This
499 // avoids unwanted interaction across iterations.
500 SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;
501 for (Instruction &I : *OrigHeader)
502 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(Val: &I))
503 NoAliasDeclInstructions.push_back(Elt: Decl);
504
505 Module *M = OrigHeader->getModule();
506
507 // Track the next DbgRecord to clone. If we have a sequence where an
508 // instruction is hoisted instead of being cloned:
509 // DbgRecord blah
510 // %foo = add i32 0, 0
511 // DbgRecord xyzzy
512 // %bar = call i32 @foobar()
513 // where %foo is hoisted, then the DbgRecord "blah" will be seen twice, once
514 // attached to %foo, then when %foo his hoisted it will "fall down" onto the
515 // function call:
516 // DbgRecord blah
517 // DbgRecord xyzzy
518 // %bar = call i32 @foobar()
519 // causing it to appear attached to the call too.
520 //
521 // To avoid this, cloneDebugInfoFrom takes an optional "start cloning from
522 // here" position to account for this behaviour. We point it at any
523 // DbgRecords on the next instruction, here labelled xyzzy, before we hoist
524 // %foo. Later, we only only clone DbgRecords from that position (xyzzy)
525 // onwards, which avoids cloning DbgRecord "blah" multiple times. (Stored as
526 // a range because it gives us a natural way of testing whether
527 // there were DbgRecords on the next instruction before we hoisted things).
528 iterator_range<DbgRecord::self_iterator> NextDbgInsts =
529 (I != E) ? I->getDbgRecordRange() : DbgMarker::getEmptyDbgRecordRange();
530
531 while (I != E) {
532 Instruction *Inst = &*I++;
533
534 // If the instruction's operands are invariant and it doesn't read or write
535 // memory, then it is safe to hoist. Doing this doesn't change the order of
536 // execution in the preheader, but does prevent the instruction from
537 // executing in each iteration of the loop. This means it is safe to hoist
538 // something that might trap, but isn't safe to hoist something that reads
539 // memory (without proving that the loop doesn't write).
540 if (L->hasLoopInvariantOperands(I: Inst) && !Inst->mayReadFromMemory() &&
541 !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
542 !isa<AllocaInst>(Val: Inst) &&
543 // It is not safe to hoist the value of these instructions in
544 // coroutines, as the addresses of otherwise eligible variables (e.g.
545 // thread-local variables and errno) may change if the coroutine is
546 // resumed in a different thread.Therefore, we disable this
547 // optimization for correctness. However, this may block other correct
548 // optimizations.
549 // FIXME: This should be reverted once we have a better model for
550 // memory access in coroutines.
551 !Inst->getFunction()->isPresplitCoroutine()) {
552
553 if (!NextDbgInsts.empty()) {
554 auto DbgValueRange =
555 LoopEntryBranch->cloneDebugInfoFrom(From: Inst, FromHere: NextDbgInsts.begin());
556 RemapDbgRecordRange(M, Range: DbgValueRange, VM&: ValueMap,
557 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
558 // Erase anything we've seen before.
559 for (DbgVariableRecord &DVR :
560 make_early_inc_range(Range: filterDbgVars(R: DbgValueRange)))
561 if (DbgRecords.count(V: makeHash(&DVR)))
562 DVR.eraseFromParent();
563 }
564
565 NextDbgInsts = I->getDbgRecordRange();
566
567 Inst->moveBefore(InsertPos: LoopEntryBranch->getIterator());
568
569 ++NumInstrsHoisted;
570 continue;
571 }
572
573 // Otherwise, create a duplicate of the instruction.
574 Instruction *C = Inst->clone();
575 if (const DebugLoc &DL = C->getDebugLoc())
576 mapAtomInstance(DL, VMap&: ValueMap);
577
578 C->insertBefore(InsertPos: LoopEntryBranch->getIterator());
579
580 ++NumInstrsDuplicated;
581
582 if (!NextDbgInsts.empty()) {
583 auto Range = C->cloneDebugInfoFrom(From: Inst, FromHere: NextDbgInsts.begin());
584 RemapDbgRecordRange(M, Range, VM&: ValueMap,
585 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
586 NextDbgInsts = DbgMarker::getEmptyDbgRecordRange();
587 // Erase anything we've seen before.
588 for (DbgVariableRecord &DVR : make_early_inc_range(Range: filterDbgVars(R: Range)))
589 if (DbgRecords.count(V: makeHash(&DVR)))
590 DVR.eraseFromParent();
591 }
592
593 // Eagerly remap the operands of the instruction.
594 RemapInstruction(I: C, VM&: ValueMap,
595 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
596
597 // With the operands remapped, see if the instruction constant folds or is
598 // otherwise simplifyable. This commonly occurs because the entry from PHI
599 // nodes allows icmps and other instructions to fold.
600 Value *V = simplifyInstruction(I: C, Q: SQ);
601 if (V && LI->replacementPreservesLCSSAForm(From: C, To: V)) {
602 // If so, then delete the temporary instruction and stick the folded value
603 // in the map.
604 InsertNewValueIntoMap(VM&: ValueMap, K: Inst, V);
605 if (!C->mayHaveSideEffects()) {
606 C->eraseFromParent();
607 C = nullptr;
608 }
609 } else {
610 InsertNewValueIntoMap(VM&: ValueMap, K: Inst, V: C);
611 }
612 if (C) {
613 // Otherwise, stick the new instruction into the new block!
614 C->setName(Inst->getName());
615
616 if (auto *II = dyn_cast<AssumeInst>(Val: C))
617 AC->registerAssumption(CI: II);
618 // MemorySSA cares whether the cloned instruction was inserted or not, and
619 // not whether it can be remapped to a simplified value.
620 if (MSSAU)
621 InsertNewValueIntoMap(VM&: ValueMapMSSA, K: Inst, V: C);
622 }
623 }
624
625 if (!NoAliasDeclInstructions.empty()) {
626 // There are noalias scope declarations:
627 // (general):
628 // Original: OrigPre { OrigHeader NewHeader ... Latch }
629 // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }
630 //
631 // with D: llvm.experimental.noalias.scope.decl,
632 // U: !noalias or !alias.scope depending on D
633 // ... { D U1 U2 } can transform into:
634 // (0) : ... { D U1 U2 } // no relevant rotation for this part
635 // (1) : ... D' { U1 U2 D } // D is part of OrigHeader
636 // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader
637 //
638 // We now want to transform:
639 // (1) -> : ... D' { D U1 U2 D'' }
640 // (2) -> : ... D' U1' { D U2 D'' U1'' }
641 // D: original llvm.experimental.noalias.scope.decl
642 // D', U1': duplicate with replaced scopes
643 // D'', U1'': different duplicate with replaced scopes
644 // This ensures a safe fallback to 'may_alias' introduced by the rotate,
645 // as U1'' and U1' scopes will not be compatible wrt to the local restrict
646
647 // Clone the llvm.experimental.noalias.decl again for the NewHeader.
648 BasicBlock::iterator NewHeaderInsertionPoint =
649 NewHeader->getFirstNonPHIIt();
650 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {
651 LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"
652 << *NAD << "\n");
653 Instruction *NewNAD = NAD->clone();
654 NewNAD->insertBefore(BB&: *NewHeader, InsertPos: NewHeaderInsertionPoint);
655 }
656
657 // Scopes must now be duplicated, once for OrigHeader and once for
658 // OrigPreHeader'.
659 {
660 auto &Context = NewHeader->getContext();
661
662 SmallVector<MDNode *, 8> NoAliasDeclScopes;
663 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)
664 NoAliasDeclScopes.push_back(Elt: NAD->getScopeList());
665
666 LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");
667 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, NewBlocks: {OrigHeader}, Context,
668 Ext: "h.rot");
669 LLVM_DEBUG(OrigHeader->dump());
670
671 // Keep the compile time impact low by only adapting the inserted block
672 // of instructions in the OrigPreHeader. This might result in slightly
673 // more aliasing between these instructions and those that were already
674 // present, but it will be much faster when the original PreHeader is
675 // large.
676 LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");
677 auto *FirstDecl =
678 cast<Instruction>(Val&: ValueMap[*NoAliasDeclInstructions.begin()]);
679 auto *LastInst = &OrigPreheader->back();
680 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, IStart: FirstDecl, IEnd: LastInst,
681 Context, Ext: "pre.rot");
682 LLVM_DEBUG(OrigPreheader->dump());
683
684 LLVM_DEBUG(dbgs() << " Updated NewHeader:\n");
685 LLVM_DEBUG(NewHeader->dump());
686 }
687 }
688
689 // Along with all the other instructions, we just cloned OrigHeader's
690 // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
691 // successors by duplicating their incoming values for OrigHeader.
692 for (BasicBlock *SuccBB : successors(BB: OrigHeader))
693 for (BasicBlock::iterator BI = SuccBB->begin();
694 PHINode *PN = dyn_cast<PHINode>(Val&: BI); ++BI)
695 PN->addIncoming(V: PN->getIncomingValueForBlock(BB: OrigHeader), BB: OrigPreheader);
696
697 // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
698 // OrigPreHeader's old terminator (the original branch into the loop), and
699 // remove the corresponding incoming values from the PHI nodes in OrigHeader.
700 LoopEntryBranch->eraseFromParent();
701 OrigPreheader->flushTerminatorDbgRecords();
702
703 // Update MemorySSA before the rewrite call below changes the 1:1
704 // instruction:cloned_instruction_or_value mapping.
705 if (MSSAU) {
706 InsertNewValueIntoMap(VM&: ValueMapMSSA, K: OrigHeader, V: OrigPreheader);
707 MSSAU->updateForClonedBlockIntoPred(BB: OrigHeader, P1: OrigPreheader,
708 VM: ValueMapMSSA);
709 }
710
711 SmallVector<PHINode *, 2> InsertedPHIs;
712 // If there were any uses of instructions in the duplicated block outside the
713 // loop, update them, inserting PHI nodes as required
714 RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE,
715 InsertedPHIs: &InsertedPHIs);
716
717 // Attach debug records to the new phis if that phi uses a value that
718 // previously had debug metadata attached. This keeps the debug info
719 // up-to-date in the loop body.
720 if (!InsertedPHIs.empty())
721 insertDebugValuesForPHIs(BB: OrigHeader, InsertedPHIs);
722
723 // NewHeader is now the header of the loop.
724 L->moveToHeader(BB: NewHeader);
725 assert(L->getHeader() == NewHeader && "Latch block is our new header");
726
727 // Inform DT about changes to the CFG.
728 if (DT) {
729 // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
730 // the DT about the removed edge to the OrigHeader (that got removed).
731 SmallVector<DominatorTree::UpdateType, 3> Updates = {
732 {DominatorTree::Insert, OrigPreheader, Exit},
733 {DominatorTree::Insert, OrigPreheader, NewHeader},
734 {DominatorTree::Delete, OrigPreheader, OrigHeader}};
735
736 if (MSSAU) {
737 MSSAU->applyUpdates(Updates, DT&: *DT, /*UpdateDT=*/UpdateDTFirst: true);
738 if (VerifyMemorySSA)
739 MSSAU->getMemorySSA()->verifyMemorySSA();
740 } else {
741 DT->applyUpdates(Updates);
742 }
743 }
744
745 // At this point, we've finished our major CFG changes. As part of cloning
746 // the loop into the preheader we've simplified instructions and the
747 // duplicated conditional branch may now be branching on a constant. If it is
748 // branching on a constant and if that constant means that we enter the loop,
749 // then we fold away the cond branch to an uncond branch. This simplifies the
750 // loop in cases important for nested loops, and it also means we don't have
751 // to split as many edges.
752 CondBrInst *PHBI = cast<CondBrInst>(Val: OrigPreheader->getTerminator());
753 const Value *Cond = PHBI->getCondition();
754 const bool HasConditionalPreHeader =
755 !isa<ConstantInt>(Val: Cond) ||
756 PHBI->getSuccessor(i: cast<ConstantInt>(Val: Cond)->isZero()) != NewHeader;
757
758 updateBranchWeights(PreHeaderBI&: *PHBI, LoopBI&: *BI, HasConditionalPreHeader, SuccsSwapped: BISuccsSwapped);
759
760 if (HasConditionalPreHeader) {
761 // The conditional branch can't be folded, handle the general case.
762 // Split edges as necessary to preserve LoopSimplify form.
763
764 // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
765 // thus is not a preheader anymore.
766 // Split the edge to form a real preheader.
767 BasicBlock *NewPH = SplitCriticalEdge(
768 Src: OrigPreheader, Dst: NewHeader,
769 Options: CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
770 NewPH->setName(NewHeader->getName() + ".lr.ph");
771
772 // Preserve canonical loop form, which means that 'Exit' should have only
773 // one predecessor. Note that Exit could be an exit block for multiple
774 // nested loops, causing both of the edges to now be critical and need to
775 // be split.
776 SmallVector<BasicBlock *, 4> ExitPreds(predecessors(BB: Exit));
777 bool SplitLatchEdge = false;
778 for (BasicBlock *ExitPred : ExitPreds) {
779 // We only need to split loop exit edges.
780 Loop *PredLoop = LI->getLoopFor(BB: ExitPred);
781 if (!PredLoop || PredLoop->contains(BB: Exit) ||
782 isa<IndirectBrInst>(Val: ExitPred->getTerminator()))
783 continue;
784 SplitLatchEdge |= L->getLoopLatch() == ExitPred;
785 BasicBlock *ExitSplit = SplitCriticalEdge(
786 Src: ExitPred, Dst: Exit,
787 Options: CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
788 ExitSplit->moveBefore(MovePos: Exit);
789 }
790 assert(SplitLatchEdge &&
791 "Despite splitting all preds, failed to split latch exit?");
792 (void)SplitLatchEdge;
793 } else {
794 // We can fold the conditional branch in the preheader, this makes things
795 // simpler. The first step is to remove the extra edge to the Exit block.
796 Exit->removePredecessor(Pred: OrigPreheader, KeepOneInputPHIs: true /*preserve LCSSA*/);
797 UncondBrInst *NewBI = UncondBrInst::Create(Target: NewHeader, InsertBefore: PHBI->getIterator());
798 NewBI->setDebugLoc(PHBI->getDebugLoc());
799 PHBI->eraseFromParent();
800
801 // With our CFG finalized, update DomTree if it is available.
802 if (DT)
803 DT->deleteEdge(From: OrigPreheader, To: Exit);
804
805 // Update MSSA too, if available.
806 if (MSSAU)
807 MSSAU->removeEdge(From: OrigPreheader, To: Exit);
808 }
809
810 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
811 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
812
813 if (MSSAU && VerifyMemorySSA)
814 MSSAU->getMemorySSA()->verifyMemorySSA();
815
816 // Now that the CFG and DomTree are in a consistent state again, try to merge
817 // the OrigHeader block into OrigLatch. This will succeed if they are
818 // connected by an unconditional branch. This is just a cleanup so the
819 // emitted code isn't too gross in this common case.
820 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
821 BasicBlock *PredBB = OrigHeader->getUniquePredecessor();
822 bool DidMerge = MergeBlockIntoPredecessor(BB: OrigHeader, DTU: &DTU, LI, MSSAU);
823 if (DidMerge)
824 RemoveRedundantDbgInstrs(BB: PredBB);
825
826 if (MSSAU && VerifyMemorySSA)
827 MSSAU->getMemorySSA()->verifyMemorySSA();
828
829 LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
830
831 return true;
832}
833
834/// Determine whether the instructions in this range may be safely and cheaply
835/// speculated. This is not an important enough situation to develop complex
836/// heuristics. We handle a single arithmetic instruction along with any type
837/// conversions.
838static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
839 BasicBlock::iterator End, Loop *L) {
840 bool seenIncrement = false;
841 bool MultiExitLoop = false;
842
843 if (!L->getExitingBlock())
844 MultiExitLoop = true;
845
846 for (BasicBlock::iterator I = Begin; I != End; ++I) {
847
848 if (!isSafeToSpeculativelyExecute(I: &*I))
849 return false;
850
851 switch (I->getOpcode()) {
852 default:
853 return false;
854 case Instruction::GetElementPtr:
855 // GEPs are cheap if all indices are constant.
856 if (!cast<GEPOperator>(Val&: I)->hasAllConstantIndices())
857 return false;
858 // fall-thru to increment case
859 [[fallthrough]];
860 case Instruction::Add:
861 case Instruction::Sub:
862 case Instruction::And:
863 case Instruction::Or:
864 case Instruction::Xor:
865 case Instruction::Shl:
866 case Instruction::LShr:
867 case Instruction::AShr: {
868 Value *IVOpnd =
869 !isa<Constant>(Val: I->getOperand(i: 0))
870 ? I->getOperand(i: 0)
871 : !isa<Constant>(Val: I->getOperand(i: 1)) ? I->getOperand(i: 1) : nullptr;
872 if (!IVOpnd)
873 return false;
874
875 // If increment operand is used outside of the loop, this speculation
876 // could cause extra live range interference.
877 if (MultiExitLoop) {
878 for (User *UseI : IVOpnd->users()) {
879 auto *UserInst = cast<Instruction>(Val: UseI);
880 if (!L->contains(Inst: UserInst))
881 return false;
882 }
883 }
884
885 if (seenIncrement)
886 return false;
887 seenIncrement = true;
888 break;
889 }
890 case Instruction::Trunc:
891 case Instruction::ZExt:
892 case Instruction::SExt:
893 // ignore type conversions
894 break;
895 }
896 }
897 return true;
898}
899
900/// Fold the loop tail into the loop exit by speculating the loop tail
901/// instructions. Typically, this is a single post-increment. In the case of a
902/// simple 2-block loop, hoisting the increment can be much better than
903/// duplicating the entire loop header. In the case of loops with early exits,
904/// rotation will not work anyway, but simplifyLoopLatch will put the loop in
905/// canonical form so downstream passes can handle it.
906///
907/// I don't believe this invalidates SCEV.
908bool LoopRotate::simplifyLoopLatch(Loop *L) {
909 BasicBlock *Latch = L->getLoopLatch();
910 if (!Latch || Latch->hasAddressTaken())
911 return false;
912
913 UncondBrInst *Jmp = dyn_cast<UncondBrInst>(Val: Latch->getTerminator());
914 if (!Jmp)
915 return false;
916
917 BasicBlock *LastExit = Latch->getSinglePredecessor();
918 if (!LastExit || !L->isLoopExiting(BB: LastExit))
919 return false;
920
921 if (!isa<UncondBrInst, CondBrInst>(Val: LastExit->getTerminator()))
922 return false;
923
924 if (!shouldSpeculateInstrs(Begin: Latch->begin(), End: Jmp->getIterator(), L))
925 return false;
926
927 LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
928 << LastExit->getName() << "\n");
929
930 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
931 MergeBlockIntoPredecessor(BB: Latch, DTU: &DTU, LI, MSSAU, MemDep: nullptr,
932 /*PredecessorWithTwoSuccessors=*/true);
933
934 if (SE) {
935 // Merging blocks may remove blocks reference in the block disposition cache. Clear the cache.
936 SE->forgetBlockAndLoopDispositions();
937 }
938
939 if (MSSAU && VerifyMemorySSA)
940 MSSAU->getMemorySSA()->verifyMemorySSA();
941
942 return true;
943}
944
945/// Rotate \c L, and return true if any modification was made.
946bool LoopRotate::processLoop(Loop *L) {
947 // Save the loop metadata.
948 MDNode *LoopMD = L->getLoopID();
949
950 bool SimplifiedLatch = false;
951
952 // Simplify the loop latch before attempting to rotate the header
953 // upward. Rotation may not be needed if the loop tail can be folded into the
954 // loop exit.
955 if (!RotationOnly)
956 SimplifiedLatch = simplifyLoopLatch(L);
957
958 bool MadeChange = rotateLoop(L, SimplifiedLatch);
959 assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
960 "Loop latch should be exiting after loop-rotate.");
961
962 // Restore the loop metadata.
963 // NB! We presume LoopRotation DOESN'T ADD its own metadata.
964 if ((MadeChange || SimplifiedLatch) && LoopMD)
965 L->setLoopID(LoopMD);
966
967 return MadeChange || SimplifiedLatch;
968}
969
970
971/// The utility to convert a loop into a loop with bottom test.
972bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
973 AssumptionCache *AC, DominatorTree *DT,
974 ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
975 const SimplifyQuery &SQ, bool RotationOnly = true,
976 unsigned Threshold = unsigned(-1),
977 bool IsUtilMode = true, bool PrepareForLTO,
978 bool CheckExitCount) {
979 LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
980 IsUtilMode, PrepareForLTO, CheckExitCount);
981 return LR.processLoop(L);
982}
983