LLVM 19.0.0git
LoopRotationUtils.cpp
Go to the documentation of this file.
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
14#include "llvm/ADT/Statistic.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/DebugInfo.h"
26#include "llvm/IR/Dominators.h"
28#include "llvm/IR/MDBuilder.h"
31#include "llvm/Support/Debug.h"
38using namespace llvm;
39
40#define DEBUG_TYPE "loop-rotate"
41
42STATISTIC(NumNotRotatedDueToHeaderSize,
43 "Number of loops not rotated due to the header size");
44STATISTIC(NumInstrsHoisted,
45 "Number of instructions hoisted into loop preheader");
46STATISTIC(NumInstrsDuplicated,
47 "Number of instructions cloned into loop preheader");
48STATISTIC(NumRotated, "Number of loops rotated");
49
50static cl::opt<bool>
51 MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden,
52 cl::desc("Allow loop rotation multiple times in order to reach "
53 "a better latch exit"));
54
55// Probability that a rotated loop has zero trip count / is never entered.
56static constexpr uint32_t ZeroTripCountWeights[] = {1, 127};
57
58namespace {
59/// A simple loop rotation transformation.
60class LoopRotate {
61 const unsigned MaxHeaderSize;
62 LoopInfo *LI;
65 DominatorTree *DT;
67 MemorySSAUpdater *MSSAU;
68 const SimplifyQuery &SQ;
69 bool RotationOnly;
70 bool IsUtilMode;
71 bool PrepareForLTO;
72
73public:
74 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
77 const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,
78 bool PrepareForLTO)
79 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
80 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
81 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}
82 bool processLoop(Loop *L);
83
84private:
85 bool rotateLoop(Loop *L, bool SimplifiedLatch);
86 bool simplifyLoopLatch(Loop *L);
87};
88} // end anonymous namespace
89
90/// Insert (K, V) pair into the ValueToValueMap, and verify the key did not
91/// previously exist in the map, and the value was inserted.
93 bool Inserted = VM.insert({K, V}).second;
94 assert(Inserted);
95 (void)Inserted;
96}
97/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
98/// old header into the preheader. If there were uses of the values produced by
99/// these instruction that were outside of the loop, we have to insert PHI nodes
100/// to merge the two values. Do this now.
102 BasicBlock *OrigPreheader,
104 ScalarEvolution *SE,
105 SmallVectorImpl<PHINode*> *InsertedPHIs) {
106 // Remove PHI node entries that are no longer live.
107 BasicBlock::iterator I, E = OrigHeader->end();
108 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
109 PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
110
111 // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
112 // as necessary.
113 SSAUpdater SSA(InsertedPHIs);
114 for (I = OrigHeader->begin(); I != E; ++I) {
115 Value *OrigHeaderVal = &*I;
116
117 // If there are no uses of the value (e.g. because it returns void), there
118 // is nothing to rewrite.
119 if (OrigHeaderVal->use_empty())
120 continue;
121
122 Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
123
124 // The value now exits in two versions: the initial value in the preheader
125 // and the loop "next" value in the original header.
126 SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
127 // Force re-computation of OrigHeaderVal, as some users now need to use the
128 // new PHI node.
129 if (SE)
130 SE->forgetValue(OrigHeaderVal);
131 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
132 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
133
134 // Visit each use of the OrigHeader instruction.
135 for (Use &U : llvm::make_early_inc_range(OrigHeaderVal->uses())) {
136 // SSAUpdater can't handle a non-PHI use in the same block as an
137 // earlier def. We can easily handle those cases manually.
138 Instruction *UserInst = cast<Instruction>(U.getUser());
139 if (!isa<PHINode>(UserInst)) {
140 BasicBlock *UserBB = UserInst->getParent();
141
142 // The original users in the OrigHeader are already using the
143 // original definitions.
144 if (UserBB == OrigHeader)
145 continue;
146
147 // Users in the OrigPreHeader need to use the value to which the
148 // original definitions are mapped.
149 if (UserBB == OrigPreheader) {
150 U = OrigPreHeaderVal;
151 continue;
152 }
153 }
154
155 // Anything else can be handled by SSAUpdater.
156 SSA.RewriteUse(U);
157 }
158
159 // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
160 // intrinsics.
162 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
163 llvm::findDbgValues(DbgValues, OrigHeaderVal, &DbgVariableRecords);
164 for (auto &DbgValue : DbgValues) {
165 // The original users in the OrigHeader are already using the original
166 // definitions.
167 BasicBlock *UserBB = DbgValue->getParent();
168 if (UserBB == OrigHeader)
169 continue;
170
171 // Users in the OrigPreHeader need to use the value to which the
172 // original definitions are mapped and anything else can be handled by
173 // the SSAUpdater. To avoid adding PHINodes, check if the value is
174 // available in UserBB, if not substitute undef.
175 Value *NewVal;
176 if (UserBB == OrigPreheader)
177 NewVal = OrigPreHeaderVal;
178 else if (SSA.HasValueForBlock(UserBB))
179 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
180 else
181 NewVal = UndefValue::get(OrigHeaderVal->getType());
182 DbgValue->replaceVariableLocationOp(OrigHeaderVal, NewVal);
183 }
184
185 // RemoveDIs: duplicate implementation for non-instruction debug-info
186 // storage in DbgVariableRecords.
187 for (DbgVariableRecord *DVR : DbgVariableRecords) {
188 // The original users in the OrigHeader are already using the original
189 // definitions.
190 BasicBlock *UserBB = DVR->getMarker()->getParent();
191 if (UserBB == OrigHeader)
192 continue;
193
194 // Users in the OrigPreHeader need to use the value to which the
195 // original definitions are mapped and anything else can be handled by
196 // the SSAUpdater. To avoid adding PHINodes, check if the value is
197 // available in UserBB, if not substitute undef.
198 Value *NewVal;
199 if (UserBB == OrigPreheader)
200 NewVal = OrigPreHeaderVal;
201 else if (SSA.HasValueForBlock(UserBB))
202 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
203 else
204 NewVal = UndefValue::get(OrigHeaderVal->getType());
205 DVR->replaceVariableLocationOp(OrigHeaderVal, NewVal);
206 }
207 }
208}
209
210// Assuming both header and latch are exiting, look for a phi which is only
211// used outside the loop (via a LCSSA phi) in the exit from the header.
212// This means that rotating the loop can remove the phi.
214 BasicBlock *Header = L->getHeader();
215 BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());
216 assert(BI && BI->isConditional() && "need header with conditional exit");
217 BasicBlock *HeaderExit = BI->getSuccessor(0);
218 if (L->contains(HeaderExit))
219 HeaderExit = BI->getSuccessor(1);
220
221 for (auto &Phi : Header->phis()) {
222 // Look for uses of this phi in the loop/via exits other than the header.
223 if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) {
224 return cast<Instruction>(U)->getParent() != HeaderExit;
225 }))
226 continue;
227 return true;
228 }
229 return false;
230}
231
232// Check that latch exit is deoptimizing (which means - very unlikely to happen)
233// and there is another exit from the loop which is non-deoptimizing.
234// If we rotate latch to that exit our loop has a better chance of being fully
235// canonical.
236//
237// It can give false positives in some rare cases.
239 BasicBlock *Latch = L->getLoopLatch();
240 assert(Latch && "need latch");
241 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
242 // Need normal exiting latch.
243 if (!BI || !BI->isConditional())
244 return false;
245
246 BasicBlock *Exit = BI->getSuccessor(1);
247 if (L->contains(Exit))
248 Exit = BI->getSuccessor(0);
249
250 // Latch exit is non-deoptimizing, no need to rotate.
251 if (!Exit->getPostdominatingDeoptimizeCall())
252 return false;
253
255 L->getUniqueExitBlocks(Exits);
256 if (!Exits.empty()) {
257 // There is at least one non-deoptimizing exit.
258 //
259 // Note, that BasicBlock::getPostdominatingDeoptimizeCall is not exact,
260 // as it can conservatively return false for deoptimizing exits with
261 // complex enough control flow down to deoptimize call.
262 //
263 // That means here we can report success for a case where
264 // all exits are deoptimizing but one of them has complex enough
265 // control flow (e.g. with loops).
266 //
267 // That should be a very rare case and false positives for this function
268 // have compile-time effect only.
269 return any_of(Exits, [](const BasicBlock *BB) {
271 });
272 }
273 return false;
274}
275
276static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI,
277 bool HasConditionalPreHeader,
278 bool SuccsSwapped) {
279 MDNode *WeightMD = getBranchWeightMDNode(PreHeaderBI);
280 if (WeightMD == nullptr)
281 return;
282
283 // LoopBI should currently be a clone of PreHeaderBI with the same
284 // metadata. But we double check to make sure we don't have a degenerate case
285 // where instsimplify changed the instructions.
286 if (WeightMD != getBranchWeightMDNode(LoopBI))
287 return;
288
290 extractFromBranchWeightMD(WeightMD, Weights);
291 if (Weights.size() != 2)
292 return;
293 uint32_t OrigLoopExitWeight = Weights[0];
294 uint32_t OrigLoopBackedgeWeight = Weights[1];
295
296 if (SuccsSwapped)
297 std::swap(OrigLoopExitWeight, OrigLoopBackedgeWeight);
298
299 // Update branch weights. Consider the following edge-counts:
300 //
301 // | |-------- |
302 // V V | V
303 // Br i1 ... | Br i1 ...
304 // | | | | |
305 // x| y| | becomes: | y0| |-----
306 // V V | | V V |
307 // Exit Loop | | Loop |
308 // | | | Br i1 ... |
309 // ----- | | | |
310 // x0| x1| y1 | |
311 // V V ----
312 // Exit
313 //
314 // The following must hold:
315 // - x == x0 + x1 # counts to "exit" must stay the same.
316 // - y0 == x - x0 == x1 # how often loop was entered at all.
317 // - y1 == y - y0 # How often loop was repeated (after first iter.).
318 //
319 // We cannot generally deduce how often we had a zero-trip count loop so we
320 // have to make a guess for how to distribute x among the new x0 and x1.
321
322 uint32_t ExitWeight0; // aka x0
323 uint32_t ExitWeight1; // aka x1
324 uint32_t EnterWeight; // aka y0
325 uint32_t LoopBackWeight; // aka y1
326 if (OrigLoopExitWeight > 0 && OrigLoopBackedgeWeight > 0) {
327 ExitWeight0 = 0;
328 if (HasConditionalPreHeader) {
329 // Here we cannot know how many 0-trip count loops we have, so we guess:
330 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) {
331 // If the loop count is bigger than the exit count then we set
332 // probabilities as if 0-trip count nearly never happens.
333 ExitWeight0 = ZeroTripCountWeights[0];
334 // Scale up counts if necessary so we can match `ZeroTripCountWeights`
335 // for the `ExitWeight0`:`ExitWeight1` (aka `x0`:`x1` ratio`) ratio.
336 while (OrigLoopExitWeight < ZeroTripCountWeights[1] + ExitWeight0) {
337 // ... but don't overflow.
338 uint32_t const HighBit = uint32_t{1} << (sizeof(uint32_t) * 8 - 1);
339 if ((OrigLoopBackedgeWeight & HighBit) != 0 ||
340 (OrigLoopExitWeight & HighBit) != 0)
341 break;
342 OrigLoopBackedgeWeight <<= 1;
343 OrigLoopExitWeight <<= 1;
344 }
345 } else {
346 // If there's a higher exit-count than backedge-count then we set
347 // probabilities as if there are only 0-trip and 1-trip cases.
348 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight;
349 }
350 }
351 ExitWeight1 = OrigLoopExitWeight - ExitWeight0;
352 EnterWeight = ExitWeight1;
353 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight;
354 } else if (OrigLoopExitWeight == 0) {
355 if (OrigLoopBackedgeWeight == 0) {
356 // degenerate case... keep everything zero...
357 ExitWeight0 = 0;
358 ExitWeight1 = 0;
359 EnterWeight = 0;
360 LoopBackWeight = 0;
361 } else {
362 // Special case "LoopExitWeight == 0" weights which behaves like an
363 // endless where we don't want loop-enttry (y0) to be the same as
364 // loop-exit (x1).
365 ExitWeight0 = 0;
366 ExitWeight1 = 0;
367 EnterWeight = 1;
368 LoopBackWeight = OrigLoopBackedgeWeight;
369 }
370 } else {
371 // loop is never entered.
372 assert(OrigLoopBackedgeWeight == 0 && "remaining case is backedge zero");
373 ExitWeight0 = 1;
374 ExitWeight1 = 1;
375 EnterWeight = 0;
376 LoopBackWeight = 0;
377 }
378
379 const uint32_t LoopBIWeights[] = {
380 SuccsSwapped ? LoopBackWeight : ExitWeight1,
381 SuccsSwapped ? ExitWeight1 : LoopBackWeight,
382 };
383 setBranchWeights(LoopBI, LoopBIWeights);
384 if (HasConditionalPreHeader) {
385 const uint32_t PreHeaderBIWeights[] = {
386 SuccsSwapped ? EnterWeight : ExitWeight0,
387 SuccsSwapped ? ExitWeight0 : EnterWeight,
388 };
389 setBranchWeights(PreHeaderBI, PreHeaderBIWeights);
390 }
391}
392
393/// Rotate loop LP. Return true if the loop is rotated.
394///
395/// \param SimplifiedLatch is true if the latch was just folded into the final
396/// loop exit. In this case we may want to rotate even though the new latch is
397/// now an exiting branch. This rotation would have happened had the latch not
398/// been simplified. However, if SimplifiedLatch is false, then we avoid
399/// rotating loops in which the latch exits to avoid excessive or endless
400/// rotation. LoopRotate should be repeatable and converge to a canonical
401/// form. This property is satisfied because simplifying the loop latch can only
402/// happen once across multiple invocations of the LoopRotate pass.
403///
404/// If -loop-rotate-multi is enabled we can do multiple rotations in one go
405/// so to reach a suitable (non-deoptimizing) exit.
406bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
407 // If the loop has only one block then there is not much to rotate.
408 if (L->getBlocks().size() == 1)
409 return false;
410
411 bool Rotated = false;
412 do {
413 BasicBlock *OrigHeader = L->getHeader();
414 BasicBlock *OrigLatch = L->getLoopLatch();
415
416 BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
417 if (!BI || BI->isUnconditional())
418 return Rotated;
419
420 // If the loop header is not one of the loop exiting blocks then
421 // either this loop is already rotated or it is not
422 // suitable for loop rotation transformations.
423 if (!L->isLoopExiting(OrigHeader))
424 return Rotated;
425
426 // If the loop latch already contains a branch that leaves the loop then the
427 // loop is already rotated.
428 if (!OrigLatch)
429 return Rotated;
430
431 // Rotate if either the loop latch does *not* exit the loop, or if the loop
432 // latch was just simplified. Or if we think it will be profitable.
433 if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
436 return Rotated;
437
438 // Check size of original header and reject loop if it is very big or we can't
439 // duplicate blocks inside it.
440 {
442 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
443
445 Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO);
446 if (Metrics.notDuplicatable) {
448 dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
449 << " instructions: ";
450 L->dump());
451 return Rotated;
452 }
453 if (Metrics.convergent) {
454 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
455 "instructions: ";
456 L->dump());
457 return Rotated;
458 }
459 if (!Metrics.NumInsts.isValid()) {
460 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions"
461 " with invalid cost: ";
462 L->dump());
463 return Rotated;
464 }
465 if (Metrics.NumInsts > MaxHeaderSize) {
466 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
467 << Metrics.NumInsts
468 << " instructions, which is more than the threshold ("
469 << MaxHeaderSize << " instructions): ";
470 L->dump());
471 ++NumNotRotatedDueToHeaderSize;
472 return Rotated;
473 }
474
475 // When preparing for LTO, avoid rotating loops with calls that could be
476 // inlined during the LTO stage.
477 if (PrepareForLTO && Metrics.NumInlineCandidates > 0)
478 return Rotated;
479 }
480
481 // Now, this loop is suitable for rotation.
482 BasicBlock *OrigPreheader = L->getLoopPreheader();
483
484 // If the loop could not be converted to canonical form, it must have an
485 // indirectbr in it, just give up.
486 if (!OrigPreheader || !L->hasDedicatedExits())
487 return Rotated;
488
489 // Anything ScalarEvolution may know about this loop or the PHI nodes
490 // in its header will soon be invalidated. We should also invalidate
491 // all outer loops because insertion and deletion of blocks that happens
492 // during the rotation may violate invariants related to backedge taken
493 // infos in them.
494 if (SE) {
495 SE->forgetTopmostLoop(L);
496 // We may hoist some instructions out of loop. In case if they were cached
497 // as "loop variant" or "loop computable", these caches must be dropped.
498 // We also may fold basic blocks, so cached block dispositions also need
499 // to be dropped.
500 SE->forgetBlockAndLoopDispositions();
501 }
502
503 LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
504 if (MSSAU && VerifyMemorySSA)
505 MSSAU->getMemorySSA()->verifyMemorySSA();
506
507 // Find new Loop header. NewHeader is a Header's one and only successor
508 // that is inside loop. Header's other successor is outside the
509 // loop. Otherwise loop is not suitable for rotation.
510 BasicBlock *Exit = BI->getSuccessor(0);
511 BasicBlock *NewHeader = BI->getSuccessor(1);
512 bool BISuccsSwapped = L->contains(Exit);
513 if (BISuccsSwapped)
514 std::swap(Exit, NewHeader);
515 assert(NewHeader && "Unable to determine new loop header");
516 assert(L->contains(NewHeader) && !L->contains(Exit) &&
517 "Unable to determine loop header and exit blocks");
518
519 // This code assumes that the new header has exactly one predecessor.
520 // Remove any single-entry PHI nodes in it.
521 assert(NewHeader->getSinglePredecessor() &&
522 "New header doesn't have one pred!");
523 FoldSingleEntryPHINodes(NewHeader);
524
525 // Begin by walking OrigHeader and populating ValueMap with an entry for
526 // each Instruction.
527 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
528 ValueToValueMapTy ValueMap, ValueMapMSSA;
529
530 // For PHI nodes, the value available in OldPreHeader is just the
531 // incoming value from OldPreHeader.
532 for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
534 PN->getIncomingValueForBlock(OrigPreheader));
535
536 // For the rest of the instructions, either hoist to the OrigPreheader if
537 // possible or create a clone in the OldPreHeader if not.
538 Instruction *LoopEntryBranch = OrigPreheader->getTerminator();
539
540 // Record all debug intrinsics preceding LoopEntryBranch to avoid
541 // duplication.
542 using DbgIntrinsicHash =
543 std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;
544 auto makeHash = [](auto *D) -> DbgIntrinsicHash {
545 auto VarLocOps = D->location_ops();
546 return {{hash_combine_range(VarLocOps.begin(), VarLocOps.end()),
547 D->getVariable()},
548 D->getExpression()};
549 };
550
552 for (Instruction &I : llvm::drop_begin(llvm::reverse(*OrigPreheader))) {
553 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
554 DbgIntrinsics.insert(makeHash(DII));
555 // Until RemoveDIs supports dbg.declares in DbgVariableRecord format,
556 // we'll need to collect DbgVariableRecords attached to any other debug
557 // intrinsics.
558 for (const DbgVariableRecord &DVR :
559 filterDbgVars(DII->getDbgRecordRange()))
560 DbgIntrinsics.insert(makeHash(&DVR));
561 } else {
562 break;
563 }
564 }
565
566 // Build DbgVariableRecord hashes for DbgVariableRecords attached to the
567 // terminator, which isn't considered in the loop above.
568 for (const DbgVariableRecord &DVR :
569 filterDbgVars(OrigPreheader->getTerminator()->getDbgRecordRange()))
570 DbgIntrinsics.insert(makeHash(&DVR));
571
572 // Remember the local noalias scope declarations in the header. After the
573 // rotation, they must be duplicated and the scope must be cloned. This
574 // avoids unwanted interaction across iterations.
575 SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;
576 for (Instruction &I : *OrigHeader)
577 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
578 NoAliasDeclInstructions.push_back(Decl);
579
580 Module *M = OrigHeader->getModule();
581
582 // Track the next DbgRecord to clone. If we have a sequence where an
583 // instruction is hoisted instead of being cloned:
584 // DbgRecord blah
585 // %foo = add i32 0, 0
586 // DbgRecord xyzzy
587 // %bar = call i32 @foobar()
588 // where %foo is hoisted, then the DbgRecord "blah" will be seen twice, once
589 // attached to %foo, then when %foo his hoisted it will "fall down" onto the
590 // function call:
591 // DbgRecord blah
592 // DbgRecord xyzzy
593 // %bar = call i32 @foobar()
594 // causing it to appear attached to the call too.
595 //
596 // To avoid this, cloneDebugInfoFrom takes an optional "start cloning from
597 // here" position to account for this behaviour. We point it at any
598 // DbgRecords on the next instruction, here labelled xyzzy, before we hoist
599 // %foo. Later, we only only clone DbgRecords from that position (xyzzy)
600 // onwards, which avoids cloning DbgRecord "blah" multiple times. (Stored as
601 // a range because it gives us a natural way of testing whether
602 // there were DbgRecords on the next instruction before we hoisted things).
604 (I != E) ? I->getDbgRecordRange() : DbgMarker::getEmptyDbgRecordRange();
605
606 while (I != E) {
607 Instruction *Inst = &*I++;
608
609 // If the instruction's operands are invariant and it doesn't read or write
610 // memory, then it is safe to hoist. Doing this doesn't change the order of
611 // execution in the preheader, but does prevent the instruction from
612 // executing in each iteration of the loop. This means it is safe to hoist
613 // something that might trap, but isn't safe to hoist something that reads
614 // memory (without proving that the loop doesn't write).
615 if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
616 !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
617 !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst) &&
618 // It is not safe to hoist the value of these instructions in
619 // coroutines, as the addresses of otherwise eligible variables (e.g.
620 // thread-local variables and errno) may change if the coroutine is
621 // resumed in a different thread.Therefore, we disable this
622 // optimization for correctness. However, this may block other correct
623 // optimizations.
624 // FIXME: This should be reverted once we have a better model for
625 // memory access in coroutines.
626 !Inst->getFunction()->isPresplitCoroutine()) {
627
628 if (LoopEntryBranch->getParent()->IsNewDbgInfoFormat &&
629 !NextDbgInsts.empty()) {
630 auto DbgValueRange =
631 LoopEntryBranch->cloneDebugInfoFrom(Inst, NextDbgInsts.begin());
632 RemapDbgVariableRecordRange(M, DbgValueRange, ValueMap,
635 // Erase anything we've seen before.
636 for (DbgVariableRecord &DVR :
637 make_early_inc_range(filterDbgVars(DbgValueRange)))
638 if (DbgIntrinsics.count(makeHash(&DVR)))
639 DVR.eraseFromParent();
640 }
641
642 NextDbgInsts = I->getDbgRecordRange();
643
644 Inst->moveBefore(LoopEntryBranch);
645
646 ++NumInstrsHoisted;
647 continue;
648 }
649
650 // Otherwise, create a duplicate of the instruction.
651 Instruction *C = Inst->clone();
652 C->insertBefore(LoopEntryBranch);
653
654 ++NumInstrsDuplicated;
655
656 if (LoopEntryBranch->getParent()->IsNewDbgInfoFormat &&
657 !NextDbgInsts.empty()) {
658 auto Range = C->cloneDebugInfoFrom(Inst, NextDbgInsts.begin());
662 NextDbgInsts = DbgMarker::getEmptyDbgRecordRange();
663 // Erase anything we've seen before.
664 for (DbgVariableRecord &DVR :
666 if (DbgIntrinsics.count(makeHash(&DVR)))
667 DVR.eraseFromParent();
668 }
669
670 // Eagerly remap the operands of the instruction.
673
674 // Avoid inserting the same intrinsic twice.
675 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(C))
676 if (DbgIntrinsics.count(makeHash(DII))) {
677 C->eraseFromParent();
678 continue;
679 }
680
681 // With the operands remapped, see if the instruction constant folds or is
682 // otherwise simplifyable. This commonly occurs because the entry from PHI
683 // nodes allows icmps and other instructions to fold.
685 if (V && LI->replacementPreservesLCSSAForm(C, V)) {
686 // If so, then delete the temporary instruction and stick the folded value
687 // in the map.
689 if (!C->mayHaveSideEffects()) {
690 C->eraseFromParent();
691 C = nullptr;
692 }
693 } else {
695 }
696 if (C) {
697 // Otherwise, stick the new instruction into the new block!
698 C->setName(Inst->getName());
699
700 if (auto *II = dyn_cast<AssumeInst>(C))
701 AC->registerAssumption(II);
702 // MemorySSA cares whether the cloned instruction was inserted or not, and
703 // not whether it can be remapped to a simplified value.
704 if (MSSAU)
705 InsertNewValueIntoMap(ValueMapMSSA, Inst, C);
706 }
707 }
708
709 if (!NoAliasDeclInstructions.empty()) {
710 // There are noalias scope declarations:
711 // (general):
712 // Original: OrigPre { OrigHeader NewHeader ... Latch }
713 // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }
714 //
715 // with D: llvm.experimental.noalias.scope.decl,
716 // U: !noalias or !alias.scope depending on D
717 // ... { D U1 U2 } can transform into:
718 // (0) : ... { D U1 U2 } // no relevant rotation for this part
719 // (1) : ... D' { U1 U2 D } // D is part of OrigHeader
720 // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader
721 //
722 // We now want to transform:
723 // (1) -> : ... D' { D U1 U2 D'' }
724 // (2) -> : ... D' U1' { D U2 D'' U1'' }
725 // D: original llvm.experimental.noalias.scope.decl
726 // D', U1': duplicate with replaced scopes
727 // D'', U1'': different duplicate with replaced scopes
728 // This ensures a safe fallback to 'may_alias' introduced by the rotate,
729 // as U1'' and U1' scopes will not be compatible wrt to the local restrict
730
731 // Clone the llvm.experimental.noalias.decl again for the NewHeader.
732 BasicBlock::iterator NewHeaderInsertionPoint =
733 NewHeader->getFirstNonPHIIt();
734 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {
735 LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"
736 << *NAD << "\n");
737 Instruction *NewNAD = NAD->clone();
738 NewNAD->insertBefore(*NewHeader, NewHeaderInsertionPoint);
739 }
740
741 // Scopes must now be duplicated, once for OrigHeader and once for
742 // OrigPreHeader'.
743 {
744 auto &Context = NewHeader->getContext();
745
746 SmallVector<MDNode *, 8> NoAliasDeclScopes;
747 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)
748 NoAliasDeclScopes.push_back(NAD->getScopeList());
749
750 LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");
751 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context,
752 "h.rot");
753 LLVM_DEBUG(OrigHeader->dump());
754
755 // Keep the compile time impact low by only adapting the inserted block
756 // of instructions in the OrigPreHeader. This might result in slightly
757 // more aliasing between these instructions and those that were already
758 // present, but it will be much faster when the original PreHeader is
759 // large.
760 LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");
761 auto *FirstDecl =
762 cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]);
763 auto *LastInst = &OrigPreheader->back();
764 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst,
765 Context, "pre.rot");
766 LLVM_DEBUG(OrigPreheader->dump());
767
768 LLVM_DEBUG(dbgs() << " Updated NewHeader:\n");
769 LLVM_DEBUG(NewHeader->dump());
770 }
771 }
772
773 // Along with all the other instructions, we just cloned OrigHeader's
774 // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
775 // successors by duplicating their incoming values for OrigHeader.
776 for (BasicBlock *SuccBB : successors(OrigHeader))
777 for (BasicBlock::iterator BI = SuccBB->begin();
778 PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
779 PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
780
781 // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
782 // OrigPreHeader's old terminator (the original branch into the loop), and
783 // remove the corresponding incoming values from the PHI nodes in OrigHeader.
784 LoopEntryBranch->eraseFromParent();
785 OrigPreheader->flushTerminatorDbgRecords();
786
787 // Update MemorySSA before the rewrite call below changes the 1:1
788 // instruction:cloned_instruction_or_value mapping.
789 if (MSSAU) {
790 InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);
791 MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,
792 ValueMapMSSA);
793 }
794
795 SmallVector<PHINode*, 2> InsertedPHIs;
796 // If there were any uses of instructions in the duplicated block outside the
797 // loop, update them, inserting PHI nodes as required
798 RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE,
799 &InsertedPHIs);
800
801 // Attach dbg.value intrinsics to the new phis if that phi uses a value that
802 // previously had debug metadata attached. This keeps the debug info
803 // up-to-date in the loop body.
804 if (!InsertedPHIs.empty())
805 insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);
806
807 // NewHeader is now the header of the loop.
808 L->moveToHeader(NewHeader);
809 assert(L->getHeader() == NewHeader && "Latch block is our new header");
810
811 // Inform DT about changes to the CFG.
812 if (DT) {
813 // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
814 // the DT about the removed edge to the OrigHeader (that got removed).
816 Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
817 Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
818 Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
819
820 if (MSSAU) {
821 MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);
822 if (VerifyMemorySSA)
823 MSSAU->getMemorySSA()->verifyMemorySSA();
824 } else {
825 DT->applyUpdates(Updates);
826 }
827 }
828
829 // At this point, we've finished our major CFG changes. As part of cloning
830 // the loop into the preheader we've simplified instructions and the
831 // duplicated conditional branch may now be branching on a constant. If it is
832 // branching on a constant and if that constant means that we enter the loop,
833 // then we fold away the cond branch to an uncond branch. This simplifies the
834 // loop in cases important for nested loops, and it also means we don't have
835 // to split as many edges.
836 BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
837 assert(PHBI->isConditional() && "Should be clone of BI condbr!");
838 const Value *Cond = PHBI->getCondition();
839 const bool HasConditionalPreHeader =
840 !isa<ConstantInt>(Cond) ||
841 PHBI->getSuccessor(cast<ConstantInt>(Cond)->isZero()) != NewHeader;
842
843 updateBranchWeights(*PHBI, *BI, HasConditionalPreHeader, BISuccsSwapped);
844
845 if (HasConditionalPreHeader) {
846 // The conditional branch can't be folded, handle the general case.
847 // Split edges as necessary to preserve LoopSimplify form.
848
849 // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
850 // thus is not a preheader anymore.
851 // Split the edge to form a real preheader.
853 OrigPreheader, NewHeader,
854 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
855 NewPH->setName(NewHeader->getName() + ".lr.ph");
856
857 // Preserve canonical loop form, which means that 'Exit' should have only
858 // one predecessor. Note that Exit could be an exit block for multiple
859 // nested loops, causing both of the edges to now be critical and need to
860 // be split.
862 bool SplitLatchEdge = false;
863 for (BasicBlock *ExitPred : ExitPreds) {
864 // We only need to split loop exit edges.
865 Loop *PredLoop = LI->getLoopFor(ExitPred);
866 if (!PredLoop || PredLoop->contains(Exit) ||
867 isa<IndirectBrInst>(ExitPred->getTerminator()))
868 continue;
869 SplitLatchEdge |= L->getLoopLatch() == ExitPred;
870 BasicBlock *ExitSplit = SplitCriticalEdge(
871 ExitPred, Exit,
872 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
873 ExitSplit->moveBefore(Exit);
874 }
875 assert(SplitLatchEdge &&
876 "Despite splitting all preds, failed to split latch exit?");
877 (void)SplitLatchEdge;
878 } else {
879 // We can fold the conditional branch in the preheader, this makes things
880 // simpler. The first step is to remove the extra edge to the Exit block.
881 Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
882 BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI->getIterator());
883 NewBI->setDebugLoc(PHBI->getDebugLoc());
884 PHBI->eraseFromParent();
885
886 // With our CFG finalized, update DomTree if it is available.
887 if (DT) DT->deleteEdge(OrigPreheader, Exit);
888
889 // Update MSSA too, if available.
890 if (MSSAU)
891 MSSAU->removeEdge(OrigPreheader, Exit);
892 }
893
894 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
895 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
896
897 if (MSSAU && VerifyMemorySSA)
898 MSSAU->getMemorySSA()->verifyMemorySSA();
899
900 // Now that the CFG and DomTree are in a consistent state again, try to merge
901 // the OrigHeader block into OrigLatch. This will succeed if they are
902 // connected by an unconditional branch. This is just a cleanup so the
903 // emitted code isn't too gross in this common case.
904 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
905 BasicBlock *PredBB = OrigHeader->getUniquePredecessor();
906 bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
907 if (DidMerge)
909
910 if (MSSAU && VerifyMemorySSA)
911 MSSAU->getMemorySSA()->verifyMemorySSA();
912
913 LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
914
915 ++NumRotated;
916
917 Rotated = true;
918 SimplifiedLatch = false;
919
920 // Check that new latch is a deoptimizing exit and then repeat rotation if possible.
921 // Deoptimizing latch exit is not a generally typical case, so we just loop over.
922 // TODO: if it becomes a performance bottleneck extend rotation algorithm
923 // to handle multiple rotations in one go.
925
926
927 return true;
928}
929
930/// Determine whether the instructions in this range may be safely and cheaply
931/// speculated. This is not an important enough situation to develop complex
932/// heuristics. We handle a single arithmetic instruction along with any type
933/// conversions.
936 bool seenIncrement = false;
937 bool MultiExitLoop = false;
938
939 if (!L->getExitingBlock())
940 MultiExitLoop = true;
941
942 for (BasicBlock::iterator I = Begin; I != End; ++I) {
943
945 return false;
946
947 if (isa<DbgInfoIntrinsic>(I))
948 continue;
949
950 switch (I->getOpcode()) {
951 default:
952 return false;
953 case Instruction::GetElementPtr:
954 // GEPs are cheap if all indices are constant.
955 if (!cast<GEPOperator>(I)->hasAllConstantIndices())
956 return false;
957 // fall-thru to increment case
958 [[fallthrough]];
959 case Instruction::Add:
960 case Instruction::Sub:
961 case Instruction::And:
962 case Instruction::Or:
963 case Instruction::Xor:
964 case Instruction::Shl:
965 case Instruction::LShr:
966 case Instruction::AShr: {
967 Value *IVOpnd =
968 !isa<Constant>(I->getOperand(0))
969 ? I->getOperand(0)
970 : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
971 if (!IVOpnd)
972 return false;
973
974 // If increment operand is used outside of the loop, this speculation
975 // could cause extra live range interference.
976 if (MultiExitLoop) {
977 for (User *UseI : IVOpnd->users()) {
978 auto *UserInst = cast<Instruction>(UseI);
979 if (!L->contains(UserInst))
980 return false;
981 }
982 }
983
984 if (seenIncrement)
985 return false;
986 seenIncrement = true;
987 break;
988 }
989 case Instruction::Trunc:
990 case Instruction::ZExt:
991 case Instruction::SExt:
992 // ignore type conversions
993 break;
994 }
995 }
996 return true;
997}
998
999/// Fold the loop tail into the loop exit by speculating the loop tail
1000/// instructions. Typically, this is a single post-increment. In the case of a
1001/// simple 2-block loop, hoisting the increment can be much better than
1002/// duplicating the entire loop header. In the case of loops with early exits,
1003/// rotation will not work anyway, but simplifyLoopLatch will put the loop in
1004/// canonical form so downstream passes can handle it.
1005///
1006/// I don't believe this invalidates SCEV.
1007bool LoopRotate::simplifyLoopLatch(Loop *L) {
1008 BasicBlock *Latch = L->getLoopLatch();
1009 if (!Latch || Latch->hasAddressTaken())
1010 return false;
1011
1012 BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
1013 if (!Jmp || !Jmp->isUnconditional())
1014 return false;
1015
1016 BasicBlock *LastExit = Latch->getSinglePredecessor();
1017 if (!LastExit || !L->isLoopExiting(LastExit))
1018 return false;
1019
1020 BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
1021 if (!BI)
1022 return false;
1023
1024 if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
1025 return false;
1026
1027 LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
1028 << LastExit->getName() << "\n");
1029
1030 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1031 MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr,
1032 /*PredecessorWithTwoSuccessors=*/true);
1033
1034 if (SE) {
1035 // Merging blocks may remove blocks reference in the block disposition cache. Clear the cache.
1036 SE->forgetBlockAndLoopDispositions();
1037 }
1038
1039 if (MSSAU && VerifyMemorySSA)
1040 MSSAU->getMemorySSA()->verifyMemorySSA();
1041
1042 return true;
1043}
1044
1045/// Rotate \c L, and return true if any modification was made.
1046bool LoopRotate::processLoop(Loop *L) {
1047 // Save the loop metadata.
1048 MDNode *LoopMD = L->getLoopID();
1049
1050 bool SimplifiedLatch = false;
1051
1052 // Simplify the loop latch before attempting to rotate the header
1053 // upward. Rotation may not be needed if the loop tail can be folded into the
1054 // loop exit.
1055 if (!RotationOnly)
1056 SimplifiedLatch = simplifyLoopLatch(L);
1057
1058 bool MadeChange = rotateLoop(L, SimplifiedLatch);
1059 assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
1060 "Loop latch should be exiting after loop-rotate.");
1061
1062 // Restore the loop metadata.
1063 // NB! We presume LoopRotation DOESN'T ADD its own metadata.
1064 if ((MadeChange || SimplifiedLatch) && LoopMD)
1065 L->setLoopID(LoopMD);
1066
1067 return MadeChange || SimplifiedLatch;
1068}
1069
1070
1071/// The utility to convert a loop into a loop with bottom test.
1075 const SimplifyQuery &SQ, bool RotationOnly = true,
1076 unsigned Threshold = unsigned(-1),
1077 bool IsUtilMode = true, bool PrepareForLTO) {
1078 LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
1079 IsUtilMode, PrepareForLTO);
1080 return LR.processLoop(L);
1081}
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:531
static constexpr uint32_t ZeroTripCountWeights[]
static bool canRotateDeoptimizingLatchExit(Loop *L)
static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)
Determine whether the instructions in this range may be safely and cheaply speculated.
static cl::opt< bool > MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden, cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit"))
static bool profitableToRotateLoopExitingLatch(Loop *L)
static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI, bool HasConditionalPreHeader, bool SuccsSwapped)
static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V)
Insert (K, V) pair into the ValueToValueMap, and verify the key did not previously exist in the map,...
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *InsertedPHIs)
RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the prehea...
#define I(x, y, z)
Definition: MD5.cpp:58
Machine Trace Metrics
Memory SSA
Definition: MemorySSA.cpp:71
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
LLVMContext & Context
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Class recording the (high level) value of a variable.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:442
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:639
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
Definition: BasicBlock.cpp:356
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:441
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:449
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
Definition: BasicBlock.cpp:701
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:157
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
Definition: BasicBlock.h:65
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
Definition: BasicBlock.h:357
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Definition: BasicBlock.cpp:328
const Instruction & back() const
Definition: BasicBlock.h:454
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
DWARF expression.
static iterator_range< simple_ilist< DbgRecord >::iterator > getEmptyDbgRecordRange()
const BasicBlock * getParent() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Definition: Function.h:516
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
Definition: Instruction.h:84
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:454
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:84
bool isTerminator() const
Definition: Instruction.h:255
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:451
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Metadata node.
Definition: Metadata.h:1067
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
The main scalar evolution driver.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1808
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:164
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:172
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
iterator_range< user_iterator > users()
Definition: Value.h:421
bool use_empty() const
Definition: Value.h:344
iterator_range< use_iterator > uses()
Definition: Value.h:376
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:5219
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
self_iterator getIterator()
Definition: ilist_node.h:109
A range adaptor for a pair of iterators.
IteratorT begin() const
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
auto successors(const MachineBasicBlock *BB)
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:141
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:2061
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
void RemapDbgVariableRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
Definition: ValueMapper.h:285
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1738
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:94
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:76
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
Definition: ValueMapper.h:264
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto predecessors(const MachineBasicBlock *BB)
void extractFromBranchWeightMD(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode, bool PrepareForLTO=false)
Convert a loop into a loop with bottom test.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:31
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:70
Option class for critical edge splitting.