LLVM 24.0.0git
EarlyIfConversion.cpp
Go to the documentation of this file.
1//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
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// Early if-conversion is for out-of-order CPUs that don't have a lot of
10// predicable instructions. The goal is to eliminate conditional branches that
11// may mispredict.
12//
13// Instructions from both sides of the branch are executed specutatively, and a
14// cmov instruction selects the result.
15//
16//===----------------------------------------------------------------------===//
17
19#include "CodeGenOptions.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/SparseSet.h"
25#include "llvm/ADT/Statistic.h"
45#include "llvm/Support/Debug.h"
47
48using namespace llvm;
49
50#define DEBUG_TYPE "early-ifcvt"
51
52STATISTIC(NumDiamondsSeen, "Number of diamonds");
53STATISTIC(NumDiamondsConv, "Number of diamonds converted");
54STATISTIC(NumTrianglesSeen, "Number of triangles");
55STATISTIC(NumTrianglesConv, "Number of triangles converted");
56STATISTIC(NumDataDependant,
57 "Number of data dependent conditional branches encountered");
58STATISTIC(NumLikelyBiased, "Number of branches with a hot path encountered");
59STATISTIC(NumStronglyBiased,
60 "Number of branches with reduced critical-path budget");
61
62//===----------------------------------------------------------------------===//
63// SSAIfConv
64//===----------------------------------------------------------------------===//
65//
66// The SSAIfConv class performs if-conversion on SSA form machine code after
67// determining if it is possible. The class contains no heuristics; external
68// code should be used to determine when if-conversion is a good idea.
69//
70// SSAIfConv can convert both triangles and diamonds:
71//
72// Triangle: Head Diamond: Head
73// | \ / \_
74// | \ / |
75// | [TF]BB FBB TBB
76// | / \ /
77// | / \ /
78// Tail Tail
79//
80// Instructions in the conditional blocks TBB and/or FBB are spliced into the
81// Head block, and phis in the Tail block are converted to select instructions.
82//
83namespace {
84class SSAIfConv {
85 const CodeGenOptions *Opts;
86 const TargetInstrInfo *TII;
89
90public:
91 /// The block containing the conditional branch.
93
94 /// The block containing phis after the if-then-else.
96
97 /// The 'true' conditional block as determined by analyzeBranch.
99
100 /// The 'false' conditional block as determined by analyzeBranch.
102
103 /// isTriangle - When there is no 'else' block, either TBB or FBB will be
104 /// equal to Tail.
105 bool isTriangle() const { return TBB == Tail || FBB == Tail; }
106
107 /// Returns the Tail predecessor for the True side.
108 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
109
110 /// Returns the Tail predecessor for the False side.
111 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
112
113 /// Information about each phi in the Tail block.
114 struct PHIInfo {
115 MachineInstr *PHI;
116 Register TReg, FReg;
117 /// Description of the select that will replace this phi.
118 TargetInstrInfo::SelectExpansion Select;
119
120 PHIInfo(MachineInstr *phi) : PHI(phi) {}
121 };
122
124
125 /// The branch condition determined by analyzeBranch.
126 SmallVector<MachineOperand, 4> Cond;
127
128private:
129 /// Instructions in Head that define values used by the conditional blocks.
130 /// The hoisted instructions must be inserted after these instructions.
131 SmallPtrSet<MachineInstr*, 8> InsertAfter;
132
133 /// Register units clobbered by the conditional blocks.
134 BitVector ClobberedRegUnits;
135
136 // Scratch pad for findInsertionPoint.
137 SparseSet<MCRegUnit, MCRegUnit, MCRegUnitToIndex> LiveRegUnits;
138
139 /// Insertion point in Head for speculatively executed instructions form TBB
140 /// and FBB.
141 MachineBasicBlock::iterator InsertionPoint;
142
143 /// Return true if all non-terminator instructions in MBB can be safely
144 /// speculated.
145 bool canSpeculateInstrs(MachineBasicBlock *MBB);
146
147 /// Return true if all non-terminator instructions in MBB can be safely
148 /// predicated.
149 bool canPredicateInstrs(MachineBasicBlock *MBB);
150
151 /// Scan through instruction dependencies and update InsertAfter array.
152 /// Return false if any dependency is incompatible with if conversion.
153 bool InstrDependenciesAllowIfConv(MachineInstr *I);
154
155 /// Predicate all instructions of the basic block with current condition
156 /// except for terminators. Reverse the condition if ReversePredicate is set.
157 void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
158
159 /// Find a valid insertion point in Head.
160 bool findInsertionPoint();
161
162 /// Replace PHI instructions in Tail with selects.
163 void replacePHIInstrs();
164
165 /// Insert selects and rewrite PHI operands to use them.
166 void rewritePHIOperands();
167
168public:
169 /// init - Initialize per-function data structures.
170 void init(MachineFunction &MF) {
171 Opts = &getCodeGenOptions(MF);
172 TII = MF.getSubtarget().getInstrInfo();
173 TRI = MF.getSubtarget().getRegisterInfo();
174 MRI = &MF.getRegInfo();
175 LiveRegUnits.clear();
176 LiveRegUnits.setUniverse(TRI->getNumRegUnits());
177 ClobberedRegUnits.clear();
178 ClobberedRegUnits.resize(TRI->getNumRegUnits());
179 }
180
181 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
182 /// initialize the internal state, and return true.
183 /// If predicate is set try to predicate the block otherwise try to
184 /// speculatively execute it.
185 bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
186
187 /// convertIf - If-convert the last block passed to canConvertIf(), assuming
188 /// it is possible. Add any blocks that are to be erased to RemoveBlocks.
189 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
190 bool Predicate = false);
191};
192} // end anonymous namespace
193
194/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
195/// be speculated. The terminators are not considered.
196///
197/// If instructions use any values that are defined in the head basic block,
198/// the defining instructions are added to InsertAfter.
199///
200/// Any clobbered regunits are added to ClobberedRegUnits.
201///
202bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
203 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
204 // get right.
205 if (!MBB->livein_empty()) {
206 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
207 return false;
208 }
209
210 unsigned InstrCount = 0;
211
212 // Check all instructions, except the terminators. It is assumed that
213 // terminators never have side effects or define any used register values.
214 for (MachineInstr &MI :
216 if (MI.isDebugInstr())
217 continue;
218
219 if (++InstrCount > Opts->early_ifcvt_limit && !Opts->stress_early_ifcvt) {
220 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
221 << Opts->early_ifcvt_limit << " instructions.\n");
222 return false;
223 }
224
225 // There shouldn't normally be any phis in a single-predecessor block.
226 if (MI.isPHI()) {
227 LLVM_DEBUG(dbgs() << "Can't hoist: " << MI);
228 return false;
229 }
230
231 // Don't speculate loads. Note that it may be possible and desirable to
232 // speculate GOT or constant pool loads that are guaranteed not to trap,
233 // but we don't support that for now.
234 if (MI.mayLoad()) {
235 LLVM_DEBUG(dbgs() << "Won't speculate load: " << MI);
236 return false;
237 }
238
239 // We never speculate stores, so an AA pointer isn't necessary.
240 bool DontMoveAcrossStore = true;
241 if (!MI.isSafeToMove(DontMoveAcrossStore)) {
242 LLVM_DEBUG(dbgs() << "Can't speculate: " << MI);
243 return false;
244 }
245
246 // Check for any dependencies on Head instructions.
247 if (!InstrDependenciesAllowIfConv(&MI))
248 return false;
249 }
250 return true;
251}
252
253/// Check that there is no dependencies preventing if conversion.
254///
255/// If instruction uses any values that are defined in the head basic block,
256/// the defining instructions are added to InsertAfter.
257bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
258 for (const MachineOperand &MO : I->operands()) {
259 if (MO.isRegMask()) {
260 LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
261 return false;
262 }
263 if (!MO.isReg())
264 continue;
265 Register Reg = MO.getReg();
266
267 // Remember clobbered regunits.
268 if (MO.isDef() && Reg.isPhysical())
269 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
270 ClobberedRegUnits.set(static_cast<unsigned>(Unit));
271
272 if (!MO.readsReg() || !Reg.isVirtual())
273 continue;
274 MachineInstr *DefMI = MRI->getVRegDef(Reg);
275 if (!DefMI || DefMI->getParent() != Head)
276 continue;
277 if (InsertAfter.insert(DefMI).second)
278 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
279 << *DefMI);
280 if (DefMI->isTerminator()) {
281 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
282 return false;
283 }
284 }
285 return true;
286}
287
288/// canPredicateInstrs - Returns true if all the instructions in MBB can safely
289/// be predicates. The terminators are not considered.
290///
291/// If instructions use any values that are defined in the head basic block,
292/// the defining instructions are added to InsertAfter.
293///
294/// Any clobbered regunits are added to ClobberedRegUnits.
295///
296bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
297 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
298 // get right.
299 if (!MBB->livein_empty()) {
300 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
301 return false;
302 }
303
304 unsigned InstrCount = 0;
305
306 // Check all instructions, except the terminators. It is assumed that
307 // terminators never have side effects or define any used register values.
310 I != E; ++I) {
311 if (I->isDebugInstr())
312 continue;
313
314 if (++InstrCount > Opts->early_ifcvt_limit && !Opts->stress_early_ifcvt) {
315 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
316 << Opts->early_ifcvt_limit << " instructions.\n");
317 return false;
318 }
319
320 // There shouldn't normally be any phis in a single-predecessor block.
321 if (I->isPHI()) {
322 LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
323 return false;
324 }
325
326 // Check that instruction is predicable
327 if (!TII->isPredicable(*I)) {
328 LLVM_DEBUG(dbgs() << "Isn't predicable: " << *I);
329 return false;
330 }
331
332 // Check that instruction is not already predicated.
333 if (TII->isPredicated(*I) && !TII->canPredicatePredicatedInstr(*I)) {
334 LLVM_DEBUG(dbgs() << "Is already predicated: " << *I);
335 return false;
336 }
337
338 // Check for any dependencies on Head instructions.
339 if (!InstrDependenciesAllowIfConv(&(*I)))
340 return false;
341 }
342 return true;
343}
344
345// Apply predicate to all instructions in the machine block.
346void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
347 auto Condition = Cond;
348 if (ReversePredicate) {
349 bool CanRevCond = !TII->reverseBranchCondition(Condition);
350 assert(CanRevCond && "Reversed predicate is not supported");
351 (void)CanRevCond;
352 }
353 // Terminators don't need to be predicated as they will be removed.
356 I != E; ++I) {
357 if (I->isDebugInstr())
358 continue;
359 TII->PredicateInstruction(*I, Condition);
360 }
361}
362
363/// Find an insertion point in Head for the speculated instructions. The
364/// insertion point must be:
365///
366/// 1. Before any terminators.
367/// 2. After any instructions in InsertAfter.
368/// 3. Not have any clobbered regunits live.
369///
370/// This function sets InsertionPoint and returns true when successful, it
371/// returns false if no valid insertion point could be found.
372///
373bool SSAIfConv::findInsertionPoint() {
374 // Keep track of live regunits before the current position.
375 // Only track RegUnits that are also in ClobberedRegUnits.
376 LiveRegUnits.clear();
381 while (I != B) {
382 --I;
383 // Some of the conditional code depends in I.
384 if (InsertAfter.count(&*I)) {
385 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
386 return false;
387 }
388
389 // Update live regunits.
390 for (const MachineOperand &MO : I->operands()) {
391 // We're ignoring regmask operands. That is conservatively correct.
392 if (!MO.isReg())
393 continue;
394 Register Reg = MO.getReg();
395 if (!Reg.isPhysical())
396 continue;
397 // I clobbers Reg, so it isn't live before I.
398 if (MO.isDef())
399 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
400 LiveRegUnits.erase(Unit);
401 // Unless I reads Reg.
402 if (MO.readsReg())
403 Reads.push_back(Reg.asMCReg());
404 }
405 // Anything read by I is live before I.
406 while (!Reads.empty())
407 for (MCRegUnit Unit : TRI->regunits(Reads.pop_back_val()))
408 if (ClobberedRegUnits.test(static_cast<unsigned>(Unit)))
409 LiveRegUnits.insert(Unit);
410
411 // We can't insert before a terminator.
412 if (I != FirstTerm && I->isTerminator())
413 continue;
414
415 // Some of the clobbered registers are live before I, not a valid insertion
416 // point.
417 if (!LiveRegUnits.empty()) {
418 LLVM_DEBUG({
419 dbgs() << "Would clobber";
420 for (MCRegUnit LRU : LiveRegUnits)
421 dbgs() << ' ' << printRegUnit(LRU, TRI);
422 dbgs() << " live before " << *I;
423 });
424 continue;
425 }
426
427 // This is a valid insertion point.
428 InsertionPoint = I;
429 LLVM_DEBUG(dbgs() << "Can insert before " << *I);
430 return true;
431 }
432 LLVM_DEBUG(dbgs() << "No legal insertion point found.\n");
433 return false;
434}
435
436
437
438/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
439/// a potential candidate for if-conversion. Fill out the internal state.
440///
441bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {
442 Head = MBB;
443 TBB = FBB = Tail = nullptr;
444
445 if (Head->succ_size() != 2)
446 return false;
447 MachineBasicBlock *Succ0 = Head->succ_begin()[0];
448 MachineBasicBlock *Succ1 = Head->succ_begin()[1];
449
450 // Canonicalize so Succ0 has MBB as its single predecessor.
451 if (Succ0->pred_size() != 1)
452 std::swap(Succ0, Succ1);
453
454 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
455 return false;
456
457 Tail = Succ0->succ_begin()[0];
458
459 // This is not a triangle.
460 if (Tail != Succ1) {
461 // Check for a diamond. We won't deal with any critical edges.
462 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
463 Succ1->succ_begin()[0] != Tail)
464 return false;
465 LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> "
466 << printMBBReference(*Succ0) << "/"
467 << printMBBReference(*Succ1) << " -> "
468 << printMBBReference(*Tail) << '\n');
469
470 // Live-in physregs are tricky to get right when speculating code.
471 if (!Tail->livein_empty()) {
472 LLVM_DEBUG(dbgs() << "Tail has live-ins.\n");
473 return false;
474 }
475 } else {
476 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
477 << printMBBReference(*Succ0) << " -> "
478 << printMBBReference(*Tail) << '\n');
479 }
480
481 // This is a triangle or a diamond.
482 // Skip if we cannot predicate and there are no phis skip as there must be
483 // side effects that can only be handled with predication.
484 if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) {
485 LLVM_DEBUG(dbgs() << "No phis in tail.\n");
486 return false;
487 }
488
489 // The branch we're looking to eliminate must be analyzable.
490 Cond.clear();
491 if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) {
492 LLVM_DEBUG(dbgs() << "Branch not analyzable.\n");
493 return false;
494 }
495
496 // This is weird, probably some sort of degenerate CFG.
497 if (!TBB) {
498 LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n");
499 return false;
500 }
501
502 // Make sure the analyzed branch is conditional; one of the successors
503 // could be a landing pad. (Empty landing pads can be generated on Windows.)
504 if (Cond.empty()) {
505 LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n");
506 return false;
507 }
508
509 // analyzeBranch doesn't set FBB on a fall-through branch.
510 // Make sure it is always set.
511 FBB = TBB == Succ0 ? Succ1 : Succ0;
512
513 // Any phis in the tail block must be convertible to selects.
514 PHIs.clear();
515 MachineBasicBlock *TPred = getTPred();
516 MachineBasicBlock *FPred = getFPred();
517 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
518 I != E && I->isPHI(); ++I) {
519 PHIs.push_back(&*I);
520 PHIInfo &PI = PHIs.back();
521 // Find PHI operands corresponding to TPred and FPred.
522 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
523 if (PI.PHI->getOperand(i+1).getMBB() == TPred)
524 PI.TReg = PI.PHI->getOperand(i).getReg();
525 if (PI.PHI->getOperand(i+1).getMBB() == FPred)
526 PI.FReg = PI.PHI->getOperand(i).getReg();
527 }
528 assert(PI.TReg.isVirtual() && "Bad PHI");
529 assert(PI.FReg.isVirtual() && "Bad PHI");
530
531 // Get target information.
532 if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(),
533 PI.TReg, PI.FReg, PI.Select)) {
534 LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
535 return false;
536 }
537 }
538
539 // Check that the conditional instructions can be speculated.
540 InsertAfter.clear();
541 ClobberedRegUnits.reset();
542 if (Predicate) {
543 if (TBB != Tail && !canPredicateInstrs(TBB))
544 return false;
545 if (FBB != Tail && !canPredicateInstrs(FBB))
546 return false;
547 } else {
548 if (TBB != Tail && !canSpeculateInstrs(TBB))
549 return false;
550 if (FBB != Tail && !canSpeculateInstrs(FBB))
551 return false;
552 }
553
554 // Try to find a valid insertion point for the speculated instructions in the
555 // head basic block.
556 if (!findInsertionPoint())
557 return false;
558
559 if (isTriangle())
560 ++NumTrianglesSeen;
561 else
562 ++NumDiamondsSeen;
563 return true;
564}
565
566/// \return true iff the two registers are known to have the same value.
568 const TargetInstrInfo *TII, Register TReg,
569 Register FReg) {
570 if (TReg == FReg)
571 return true;
572
573 if (!TReg.isVirtual() || !FReg.isVirtual())
574 return false;
575
576 const MachineInstr *TDef = MRI.getUniqueVRegDef(TReg);
577 const MachineInstr *FDef = MRI.getUniqueVRegDef(FReg);
578 if (!TDef || !FDef)
579 return false;
580
581 // If there are side-effects, all bets are off.
582 if (TDef->hasUnmodeledSideEffects())
583 return false;
584
585 // If the instruction could modify memory, or there may be some intervening
586 // store between the two, we can't consider them to be equal.
587 if (TDef->mayLoadOrStore() && !TDef->isDereferenceableInvariantLoad())
588 return false;
589
590 // We also can't guarantee that they are the same if, for example, the
591 // instructions are both a copy from a physical reg, because some other
592 // instruction may have modified the value in that reg between the two
593 // defining insts.
594 if (any_of(TDef->uses(), [](const MachineOperand &MO) {
595 return MO.isReg() && MO.getReg().isPhysical();
596 }))
597 return false;
598
599 // Check whether the two defining instructions produce the same value(s).
600 if (!TII->produceSameValue(*TDef, *FDef, &MRI))
601 return false;
602
603 // Further, check that the two defs come from corresponding operands.
604 int TIdx = TDef->findRegisterDefOperandIdx(TReg, /*TRI=*/nullptr);
605 int FIdx = FDef->findRegisterDefOperandIdx(FReg, /*TRI=*/nullptr);
606 if (TIdx == -1 || FIdx == -1)
607 return false;
608
609 return TIdx == FIdx;
610}
611
612/// replacePHIInstrs - Completely replace PHI instructions with selects.
613/// This is possible when the only Tail predecessors are the if-converted
614/// blocks.
615void SSAIfConv::replacePHIInstrs() {
616 assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
618 assert(FirstTerm != Head->end() && "No terminators");
619 DebugLoc HeadDL = FirstTerm->getDebugLoc();
620
621 // Convert all PHIs to select instructions inserted before FirstTerm.
622 for (PHIInfo &PI : PHIs) {
623 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
624 Register DstReg = PI.PHI->getOperand(0).getReg();
625 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
626 // We do not need the select instruction if both incoming values are
627 // equal, but we do need a COPY.
628 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)
629 .addReg(PI.TReg);
630 } else {
631 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,
632 PI.FReg);
633 }
634 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
635 PI.PHI->eraseFromParent();
636 PI.PHI = nullptr;
637 }
638}
639
640/// rewritePHIOperands - When there are additional Tail predecessors, insert
641/// select instructions in Head and rewrite PHI operands to use the selects.
642/// Keep the PHI instructions in Tail to handle the other predecessors.
643void SSAIfConv::rewritePHIOperands() {
645 assert(FirstTerm != Head->end() && "No terminators");
646 DebugLoc HeadDL = FirstTerm->getDebugLoc();
647
648 // Convert all PHIs to select instructions inserted before FirstTerm.
649 for (PHIInfo &PI : PHIs) {
650 Register DstReg;
651
652 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
653 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
654 // We do not need the select instruction if both incoming values are
655 // equal.
656 DstReg = PI.TReg;
657 } else {
658 Register PHIDst = PI.PHI->getOperand(0).getReg();
659 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
660 TII->insertSelect(*Head, FirstTerm, HeadDL,
661 DstReg, Cond, PI.TReg, PI.FReg);
662 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
663 }
664
665 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
666 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
667 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
668 if (MBB == getTPred()) {
669 PI.PHI->getOperand(i-1).setMBB(Head);
670 PI.PHI->getOperand(i-2).setReg(DstReg);
671 } else if (MBB == getFPred()) {
672 PI.PHI->removeOperand(i-1);
673 PI.PHI->removeOperand(i-2);
674 }
675 }
676 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
677 }
678}
679
680/// convertIf - Execute the if conversion after canConvertIf has determined the
681/// feasibility.
682///
683/// Any basic blocks that need to be erased will be added to RemoveBlocks.
684///
685void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
686 bool Predicate) {
687 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
688
689 // Update statistics.
690 if (isTriangle())
691 ++NumTrianglesConv;
692 else
693 ++NumDiamondsConv;
694
695 // Move all instructions into Head, except for the terminators.
696 if (TBB != Tail) {
697 if (Predicate)
698 PredicateBlock(TBB, /*ReversePredicate=*/false);
699 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
700 }
701 if (FBB != Tail) {
702 if (Predicate)
703 PredicateBlock(FBB, /*ReversePredicate=*/true);
704 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
705 }
706 // Are there extra Tail predecessors?
707 bool ExtraPreds = Tail->pred_size() != 2;
708 if (ExtraPreds)
709 rewritePHIOperands();
710 else
711 replacePHIInstrs();
712
713 // Fix up the CFG, temporarily leave Head without any successors.
714 Head->removeSuccessor(TBB);
715 Head->removeSuccessor(FBB, true);
716 if (TBB != Tail)
717 TBB->removeSuccessor(Tail, true);
718 if (FBB != Tail)
719 FBB->removeSuccessor(Tail, true);
720
721 // Fix up Head's terminators.
722 // It should become a single branch or a fallthrough.
723 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
724 TII->removeBranch(*Head);
725
726 // Mark the now empty conditional blocks for removal and move them to the end.
727 // It is likely that Head can fall
728 // through to Tail, and we can join the two blocks.
729 if (TBB != Tail) {
730 RemoveBlocks.push_back(TBB);
731 if (TBB != &TBB->getParent()->back())
732 TBB->moveAfter(&TBB->getParent()->back());
733 }
734 if (FBB != Tail) {
735 RemoveBlocks.push_back(FBB);
736 if (FBB != &FBB->getParent()->back())
737 FBB->moveAfter(&FBB->getParent()->back());
738 }
739
740 assert(Head->succ_empty() && "Additional head successors?");
741 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
742 // Splice Tail onto the end of Head.
743 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
744 << " into head " << printMBBReference(*Head) << '\n');
745 Head->splice(Head->end(), Tail,
746 Tail->begin(), Tail->end());
748 RemoveBlocks.push_back(Tail);
749 if (Tail != &Tail->getParent()->back())
750 Tail->moveAfter(&Tail->getParent()->back());
751 } else {
752 // We need a branch to Tail, let code placement work it out later.
753 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
755 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
756 Head->addSuccessor(Tail);
757 }
758 LLVM_DEBUG(dbgs() << *Head);
759}
760
761//===----------------------------------------------------------------------===//
762// EarlyIfConverter Pass
763//===----------------------------------------------------------------------===//
764
765namespace {
766class EarlyIfConverter {
767 const CodeGenOptions &Opts;
768 const TargetInstrInfo *TII = nullptr;
769 const TargetRegisterInfo *TRI = nullptr;
770 const TargetSubtargetInfo *STI = nullptr;
771 MachineRegisterInfo *MRI = nullptr;
772 MachineDominatorTree *DomTree = nullptr;
773 MachineLoopInfo *Loops = nullptr;
774 MachineTraceMetrics *Traces = nullptr;
775 MachineTraceMetrics::Ensemble *MinInstr = nullptr;
776 MachineBranchProbabilityInfo &MBPI;
777 SSAIfConv IfConv;
778
779 /// Cache of basic blocks verified to contain no call instructions, mapping
780 /// each block to the number of instructions scanned in it.
781 DenseMap<const MachineBasicBlock *, unsigned> NoCallBlocksCache;
782
783public:
784 EarlyIfConverter(const CodeGenOptions &Opts, MachineDominatorTree &DT,
785 MachineLoopInfo &LI, MachineTraceMetrics &MTM,
786 MachineBranchProbabilityInfo &MBPI)
787 : Opts(Opts), DomTree(&DT), Loops(&LI), Traces(&MTM), MBPI(MBPI) {}
788 EarlyIfConverter() = delete;
789
790 bool run(MachineFunction &MF);
791
792private:
793 bool tryConvertIf(MachineBasicBlock *);
794 void invalidateTraces();
795 bool shouldConvertIf();
796 bool isConditionDataDependent();
797 bool doOperandsComeFromMemory(const MachineInstr *ConditionDef);
798 bool hasCallOrLoopInRange(const MachineInstr *From, const MachineInstr *To);
799};
800
801class EarlyIfConverterLegacy : public MachineFunctionPass {
802public:
803 static char ID;
804 EarlyIfConverterLegacy() : MachineFunctionPass(ID) {}
805 void getAnalysisUsage(AnalysisUsage &AU) const override;
806 bool runOnMachineFunction(MachineFunction &MF) override;
807 StringRef getPassName() const override { return "Early If-Conversion"; }
808};
809} // end anonymous namespace
810
811char EarlyIfConverterLegacy::ID = 0;
812char &llvm::EarlyIfConverterLegacyID = EarlyIfConverterLegacy::ID;
813
814INITIALIZE_PASS_BEGIN(EarlyIfConverterLegacy, DEBUG_TYPE, "Early If Converter",
815 false, false)
819INITIALIZE_PASS_END(EarlyIfConverterLegacy, DEBUG_TYPE, "Early If Converter",
821
822void EarlyIfConverterLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
823 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
825 AU.addRequired<MachineDominatorTreeWrapperPass>();
826 AU.addPreserved<MachineDominatorTreeWrapperPass>();
827 AU.addRequired<MachineLoopInfoWrapperPass>();
828 AU.addPreserved<MachineLoopInfoWrapperPass>();
829 AU.addRequired<MachineTraceMetricsWrapperPass>();
830 AU.addPreserved<MachineTraceMetricsWrapperPass>();
832}
833
834namespace {
835/// Update the dominator tree after if-conversion erased some blocks.
836void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
838 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
839 // TBB and FBB should not dominate any blocks.
840 // Tail children should be transferred to Head.
841 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
842 for (auto *B : Removed) {
843 MachineDomTreeNode *Node = DomTree->getNode(B);
844 assert(Node != HeadNode && "Cannot erase the head node");
845 while (!Node->isLeaf()) {
846 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
847 DomTree->changeImmediateDominator(*Node->begin(), HeadNode);
848 }
849 DomTree->eraseNode(B);
850 }
851}
852
853/// Update LoopInfo after if-conversion.
854void updateLoops(MachineLoopInfo *Loops,
856 // If-conversion doesn't change loop structure, and it doesn't mess with back
857 // edges, so updating LoopInfo is simply removing the dead blocks.
858 for (auto *B : Removed)
859 Loops->removeBlock(B);
860}
861} // namespace
862
863/// Invalidate MachineTraceMetrics before if-conversion.
864void EarlyIfConverter::invalidateTraces() {
865 Traces->verifyAnalysis();
866 Traces->invalidate(IfConv.Head);
867 Traces->invalidate(IfConv.Tail);
868 Traces->invalidate(IfConv.TBB);
869 Traces->invalidate(IfConv.FBB);
870 Traces->verifyAnalysis();
871}
872
873static bool isConstantPoolLoad(const MachineInstr *MI) {
874 return MI->mayLoad() && any_of(MI->memoperands(), [](MachineMemOperand *MOp) {
875 const PseudoSourceValue *PSV = MOp->getPseudoValue();
876 return PSV && PSV->isConstantPool();
877 });
878}
879
880/// Check whether the load in From and the condition in To are far apart, i.e.
881/// whether a call or a loop can be executed between them. This is done by first
882/// scanning the instructions within From and To MBBs. If no call is found, we
883/// then scan all blocks which are dominated by From (the load) and can reach To
884/// (the condition), looking for calls and for blocks belonging to a loop the
885/// condition is not part of.
886bool EarlyIfConverter::hasCallOrLoopInRange(const MachineInstr *From,
887 const MachineInstr *To) {
888 if (From == To)
889 return false;
890
891 LLVM_DEBUG(dbgs() << " checking for a call or loop between " << *From
892 << " and " << *To);
893 assert(DomTree->dominates(From, To) && "From is expected to dominate To");
894
895 const MachineBasicBlock *FromBB = From->getParent();
896 const MachineBasicBlock *ToBB = To->getParent();
897
898 unsigned NumScanned = 0;
899 auto HitSearchLimit = [&](unsigned N) {
900 NumScanned += N;
901 if (NumScanned <= Opts.early_ifcvt_max_region_instrs)
902 return false;
903 LLVM_DEBUG(dbgs() << " hasCallOrLoopInRange scanned more than "
904 << Opts.early_ifcvt_max_region_instrs
905 << " instructions\n");
906 return true;
907 };
908 auto FoundCall = [](const MachineInstr &MI) {
909 LLVM_DEBUG(dbgs() << " found a call before the condition: " << MI);
910 return true;
911 };
912 auto IsCallOrHitSearchLimit = [&](const MachineInstr &MI) {
913 if (HitSearchLimit(1))
914 return true;
915 if (!MI.isCall())
916 return false;
917 return FoundCall(MI);
918 };
919
920 // If From and To are in the same block, just check (From, To).
921 if (FromBB == ToBB) {
922 for (const MachineInstr &MI : instructionsWithoutDebug(
923 std::next(From->getIterator()), To->getIterator(),
924 /*SkipPseudoOp=*/false))
925 if (IsCallOrHitSearchLimit(MI))
926 return true;
927 return false;
928 }
929
930 // Check (From, end of From's block] and [start of To's block, To).
931 for (const MachineInstr &MI : instructionsWithoutDebug(
932 std::next(From->getIterator()), FromBB->instr_end(),
933 /*SkipPseudoOp=*/false))
934 if (IsCallOrHitSearchLimit(MI))
935 return true;
936 for (const MachineInstr &MI :
938 /*SkipPseudoOp=*/false))
939 if (IsCallOrHitSearchLimit(MI))
940 return true;
941
942 // Enqueued guards the traversal: the endpoint blocks are traversed through
943 // but their instructions were already handled above.
944 SmallPtrSet<const MachineBasicBlock *, 16> Enqueued = {FromBB, ToBB};
946 auto Enqueue = [&](const MachineBasicBlock *BB) {
947 if (DomTree->dominates(FromBB, BB) && Enqueued.insert(BB).second)
948 Worklist.push_back(BB);
949 };
950
951 for (const MachineBasicBlock *Pred : ToBB->predecessors())
952 Enqueue(Pred);
953
954 while (!Worklist.empty()) {
955 const MachineBasicBlock *BB = Worklist.pop_back_val();
956
957 // If the block belongs to a loop containing neither the load nor the
958 // condition, that loop is executed entirely between the two, so consider
959 // them far apart.
960 if (const MachineLoop *BBLoop = Loops->getLoopFor(BB)) {
961 if (!BBLoop->contains(ToBB) && !BBLoop->contains(FromBB)) {
962 LLVM_DEBUG(dbgs() << " found a loop before the condition in "
963 << printMBBReference(*BB) << '\n');
964 return true;
965 }
966 }
967
968 // Next check for calls in the block.
969 auto CacheIt = NoCallBlocksCache.find(BB);
970 if (CacheIt != NoCallBlocksCache.end()) {
971 if (HitSearchLimit(CacheIt->second))
972 return true;
973 } else {
974 unsigned NumBlockInstrs = 0;
975 for (const MachineInstr &MI :
977 /*SkipPseudoOp=*/false)) {
978 ++NumBlockInstrs;
979 if (IsCallOrHitSearchLimit(MI))
980 return true;
981 }
982 NoCallBlocksCache[BB] = NumBlockInstrs;
983 }
984
985 for (const MachineBasicBlock *Pred : BB->predecessors())
986 Enqueue(Pred);
987 }
988
989 return false;
990}
991
992/// Check if a register's value comes from a memory load by walking the
993/// def-use chain. We want to prioritize converting branches which
994/// depend on values loaded from memory (unless they are loop invariant,
995/// or come from a constant pool). The walk starts from the definition of
996/// ConditionDef's first operand, which is not ConditionDef itself for
997/// instructions such as FCMPSrr, where that operand is a use.
998bool EarlyIfConverter::doOperandsComeFromMemory(
999 const MachineInstr *ConditionDef) {
1000 Register Reg = ConditionDef->getOperand(0).getReg();
1001 if (!Reg.isVirtual())
1002 return false;
1003
1004 LLVM_DEBUG(dbgs() << " doOperandsComeFromMemory starting from reg "
1005 << printReg(Reg) << "\n");
1006
1007 // The condition is consumed by the branch terminating Head, so this is the
1008 // end of the interval a load has to survive without a call in between.
1009 const MachineInstr *Br = &*IfConv.Head->getFirstTerminator();
1010 MachineLoop *IfConvLoop = Loops->getLoopFor(IfConv.Head);
1011
1012 // Walk the def-use chain.
1013 SmallPtrSet<const MachineInstr *, 8> VisitedInstrs;
1014 SmallVector<const MachineInstr *> Worklist;
1015
1016 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1017 // The operand is defined outside of the function - it does not
1018 // come from memory access.
1019 if (!DefMI)
1020 return false;
1021
1022 Worklist.push_back(DefMI);
1023
1024 while (!Worklist.empty() &&
1025 VisitedInstrs.size() < Opts.early_ifcvt_max_steps) {
1026 const MachineInstr *MI = Worklist.pop_back_val();
1027 if (!VisitedInstrs.insert(MI).second)
1028 continue;
1029
1030 // Don't walk through PHIs: a value arriving on a back edge is loaded in a
1031 // previous iteration, so the interval between the load and the branch is
1032 // not the one hasCallOrLoopInRange measures.
1033 if (MI->isPHI())
1034 continue;
1035
1036 const MachineBasicBlock *Parent = MI->getParent();
1037 MachineLoop *ParentLoop = Loops->getLoopFor(Parent);
1038
1039 // If the instruction is outside the loop, skip it (loop-invariant).
1040 if (IfConvLoop && ParentLoop != IfConvLoop)
1041 continue;
1042
1043 // Check if this instruction is a load, and there are no calls or loops
1044 // between the load and the condition (which would break the "close in
1045 // time" assumption).
1046 if (MI->mayLoad() && !isConstantPoolLoad(MI) &&
1047 !MI->isDereferenceableInvariantLoad()) {
1048 // If the load doesn't dominate the branch (e.g., comes after it in
1049 // the same block via a loop back-edge), it can't affect this iteration.
1050 // If not - check if there is a call or a loop between the load
1051 // instruction and the branch.
1052 if (!DomTree->dominates(MI, Br) || hasCallOrLoopInRange(MI, Br))
1053 continue;
1054
1055 return true;
1056 }
1057
1058 // Walk through all register use operands and find their definitions.
1059 for (const MachineOperand &MO : MI->operands()) {
1060 if (!MO.isReg() || !MO.isUse())
1061 continue;
1062 Register UseReg = MO.getReg();
1063 if (!UseReg.isVirtual())
1064 continue;
1065
1066 if (MachineInstr *UseDef = MRI->getVRegDef(UseReg)) {
1067 if (!VisitedInstrs.count(UseDef)) {
1068 Worklist.push_back(UseDef);
1069 }
1070 }
1071 }
1072 }
1073
1074 return false;
1075}
1076
1077/// Check if the branch condition is data-dependent (comes from memory loads).
1078bool EarlyIfConverter::isConditionDataDependent() {
1079 TargetInstrInfo::MachineBranchPredicate MBP;
1080 if (TII->analyzeBranchPredicate(*IfConv.Head, MBP, /*AllowModify=*/false))
1081 return false;
1082
1083 if (!MBP.ConditionDef)
1084 return false;
1085
1086 // If the branch is biased (not 50/50), don't consider it data dependent.
1087 // This is to prevent converting unprofitable checks such as
1088 // `x[i] != 0;`
1089 auto TBBProb = MBPI.getEdgeProbability(IfConv.Head, IfConv.TBB);
1090 auto FBBProb = MBPI.getEdgeProbability(IfConv.Head, IfConv.FBB);
1091 if (TBBProb != FBBProb) {
1092 ++NumLikelyBiased;
1093 return false;
1094 }
1095
1096 // Check if operands used to compute the branch condition were loaded recently
1097 // from memory, starting by the ConditionDef itself and walking up the use-def
1098 // chain.
1099 if (doOperandsComeFromMemory(MBP.ConditionDef)) {
1100 ++NumDataDependant;
1101 return true;
1102 }
1103
1104 return false;
1105}
1106
1107// Adjust cycles with downward saturation.
1108static unsigned adjCycles(unsigned Cyc, int Delta) {
1109 if (Delta < 0 && Cyc + Delta > Cyc)
1110 return 0;
1111 return Cyc + Delta;
1112}
1113
1114namespace {
1115/// Helper class to simplify emission of cycle counts into optimization remarks.
1116struct Cycles {
1117 const char *Key;
1118 unsigned Value;
1119};
1120template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
1121 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
1122}
1123} // anonymous namespace
1124
1125/// Apply cost model and heuristics to the if-conversion in IfConv.
1126/// Return true if the conversion is a good idea.
1127///
1128bool EarlyIfConverter::shouldConvertIf() {
1129 // Stress testing mode disables all cost considerations.
1130 if (Opts.stress_early_ifcvt)
1131 return true;
1132
1133 // Do not try to if-convert if the condition has a high chance of being
1134 // predictable.
1135 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);
1136 // If the condition is in a loop, consider it predictable if the condition
1137 // itself or all its operands are loop-invariant. E.g. this considers a load
1138 // from a loop-invariant address predictable; we were unable to prove that it
1139 // doesn't alias any of the memory-writes in the loop, but it is likely to
1140 // read to same value multiple times.
1141 if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {
1142 if (!MO.isReg() || !MO.isUse())
1143 return false;
1144 Register Reg = MO.getReg();
1145 if (Reg.isPhysical())
1146 return false;
1147
1148 MachineInstr *Def = MRI->getVRegDef(Reg);
1149 return CurrentLoop->isLoopInvariant(*Def) ||
1150 all_of(Def->operands(), [&](MachineOperand &Op) {
1151 if (Op.isImm())
1152 return true;
1153 if (!Op.isReg() || !Op.isUse())
1154 return true;
1155 Register Reg = Op.getReg();
1156 if (Reg.isPhysical())
1157 return false;
1158
1159 MachineInstr *Def = MRI->getVRegDef(Reg);
1160 return CurrentLoop->isLoopInvariant(*Def);
1161 });
1162 }))
1163 return false;
1164
1165 if (!MinInstr)
1166 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
1167
1168 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
1169 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
1170 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
1171 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
1172 FBBTrace.getCriticalPath());
1173
1174 // Set a somewhat arbitrary limit on the critical path extension we accept.
1175 // Use the full misprediction penalty for data-dependent branches and half
1176 // for others. A branch with a cold edge below ColdEdgeThreshold gets no
1177 // extending the critical path: it is unlikely to mispredict often enough
1178 // to recover the extra latency from if-conversion.
1179 bool DataDependent = false;
1180 if (Opts.enable_early_ifcvt_data_dependent)
1181 DataDependent = isConditionDataDependent();
1182
1183 const unsigned MispredictPenalty = STI->getMispredictionPenalty();
1184 unsigned CritLimit =
1185 DataDependent ? MispredictPenalty : MispredictPenalty / 2;
1186 const BranchProbability ColdProb =
1187 std::min(MBPI.getEdgeProbability(IfConv.Head, IfConv.TBB),
1188 MBPI.getEdgeProbability(IfConv.Head, IfConv.FBB));
1189 const unsigned ColdEdgePercent =
1190 std::min(Opts.early_ifcvt_cold_edge_threshold, 50U);
1191 const bool StronglyBiased =
1192 ColdProb < BranchProbability(ColdEdgePercent, 100);
1193 if (StronglyBiased) {
1194 CritLimit = 0;
1195 ++NumStronglyBiased;
1196 }
1197
1198 MachineBasicBlock &MBB = *IfConv.Head;
1199 MachineOptimizationRemarkEmitter MORE(*MBB.getParent(), nullptr);
1200
1201 LLVM_DEBUG(dbgs() << "Cold edge probability: " << ColdProb
1202 << ", critical-path budget: " << CritLimit << " cycles\n");
1203 if (StronglyBiased) {
1204 MORE.emit([&]() {
1205 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE,
1206 "StronglyBiasedBranch",
1207 MBB.back().getDebugLoc(), &MBB)
1208 << "branch has a cold edge below "
1209 << ore::NV("ColdEdgeThreshold", ColdEdgePercent)
1210 << "%, using a critical-path "
1211 "extension budget of "
1212 << ore::NV("CritLimit", CritLimit) << " cycles";
1213 });
1214 }
1215
1216 // Emit analysis remark about data-dependent condition.
1217 if (DataDependent) {
1218 MORE.emit([&]() {
1219 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE,
1220 "DataDependentCondition",
1221 MBB.back().getDebugLoc(), &MBB)
1222 << "branch condition is data-dependent (from memory load), "
1223 << "using higher CritLimit of " << ore::NV("CritLimit", CritLimit)
1224 << " cycles";
1225 });
1226 }
1227
1228 // If-conversion only makes sense when there is unexploited ILP. Compute the
1229 // maximum-ILP resource length of the trace after if-conversion. Compare it
1230 // to the shortest critical path.
1232 if (IfConv.TBB != IfConv.Tail)
1233 ExtraBlocks.push_back(IfConv.TBB);
1234 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
1235 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
1236 << ", minimal critical path " << MinCrit << '\n');
1237 if (ResLength > MinCrit + CritLimit) {
1238 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
1239 MORE.emit([&]() {
1240 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",
1241 MBB.findDebugLoc(MBB.back()), &MBB);
1242 R << "did not if-convert branch: the resulting critical path ("
1243 << Cycles{"ResLength", ResLength}
1244 << ") would extend the shorter leg's critical path ("
1245 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "
1246 << Cycles{"CritLimit", CritLimit}
1247 << ", which cannot be hidden by available ILP.";
1248 return R;
1249 });
1250 return false;
1251 }
1252
1253 // Assume that the depth of the first head terminator will also be the depth
1254 // of the select instruction inserted, as determined by the flag dependency.
1255 // TBB / FBB data dependencies may delay the select even more.
1256 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
1257 unsigned BranchDepth =
1258 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
1259 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
1260
1261 // Look at all the tail phis, and compute the critical path extension caused
1262 // by inserting select instructions.
1263 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
1264 struct CriticalPathInfo {
1265 unsigned Extra; // Count of extra cycles that the component adds.
1266 unsigned Depth; // Absolute depth of the component in cycles.
1267 };
1268 CriticalPathInfo Cond{};
1269 CriticalPathInfo TBlock{};
1270 CriticalPathInfo FBlock{};
1271 bool ShouldConvert = true;
1272 for (SSAIfConv::PHIInfo &PI : IfConv.PHIs) {
1273 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
1274 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
1275 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
1276
1277 // The condition is pulled into the critical path.
1278 unsigned CondDepth = adjCycles(BranchDepth, PI.Select.CondCycles);
1279 if (CondDepth > MaxDepth) {
1280 unsigned Extra = CondDepth - MaxDepth;
1281 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
1282 if (Extra > Cond.Extra)
1283 Cond = {Extra, CondDepth};
1284 if (Extra > CritLimit) {
1285 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1286 ShouldConvert = false;
1287 }
1288 }
1289
1290 // The TBB value is pulled into the critical path.
1291 unsigned TDepth =
1292 adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.Select.TrueCycles);
1293 if (TDepth > MaxDepth) {
1294 unsigned Extra = TDepth - MaxDepth;
1295 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
1296 if (Extra > TBlock.Extra)
1297 TBlock = {Extra, TDepth};
1298 if (Extra > CritLimit) {
1299 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1300 ShouldConvert = false;
1301 }
1302 }
1303
1304 // The FBB value is pulled into the critical path.
1305 unsigned FDepth =
1306 adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.Select.FalseCycles);
1307 if (FDepth > MaxDepth) {
1308 unsigned Extra = FDepth - MaxDepth;
1309 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
1310 if (Extra > FBlock.Extra)
1311 FBlock = {Extra, FDepth};
1312 if (Extra > CritLimit) {
1313 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1314 ShouldConvert = false;
1315 }
1316 }
1317 }
1318
1319 // Organize by "short" and "long" legs, since the diagnostics get confusing
1320 // when referring to the "true" and "false" sides of the branch, given that
1321 // those don't always correlate with what the user wrote in source-terms.
1322 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1323 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1324
1325 if (ShouldConvert) {
1326 MORE.emit([&]() {
1327 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
1328 MBB.back().getDebugLoc(), &MBB);
1329 R << "performing if-conversion on branch: the condition adds "
1330 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1331 if (Short.Extra > 0)
1332 R << ", and the short leg adds another "
1333 << Cycles{"ShortCycles", Short.Extra};
1334 if (Long.Extra > 0)
1335 R << ", and the long leg adds another "
1336 << Cycles{"LongCycles", Long.Extra};
1337 R << ", each staying under the threshold of "
1338 << Cycles{"CritLimit", CritLimit} << ".";
1339 return R;
1340 });
1341 } else {
1342 MORE.emit([&]() {
1343 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",
1344 MBB.back().getDebugLoc(), &MBB);
1345 R << "did not if-convert branch: the condition would add "
1346 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1347 if (Cond.Extra > CritLimit)
1348 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1349 if (Short.Extra > 0) {
1350 R << ", and the short leg would add another "
1351 << Cycles{"ShortCycles", Short.Extra};
1352 if (Short.Extra > CritLimit)
1353 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1354 }
1355 if (Long.Extra > 0) {
1356 R << ", and the long leg would add another "
1357 << Cycles{"LongCycles", Long.Extra};
1358 if (Long.Extra > CritLimit)
1359 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1360 }
1361 R << ".";
1362 return R;
1363 });
1364 }
1365
1366 return ShouldConvert;
1367}
1368
1369/// Attempt repeated if-conversion on MBB, return true if successful.
1370///
1371bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1372 bool Changed = false;
1373 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1374 // If-convert MBB and update analyses.
1375 invalidateTraces();
1376 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1377 IfConv.convertIf(RemoveBlocks);
1378 Changed = true;
1379 updateDomTree(DomTree, IfConv, RemoveBlocks);
1380 updateLoops(Loops, RemoveBlocks);
1381 // Head absorbs the instructions of the removed blocks, including any calls,
1382 // so a Head cached as call-free may no longer be.
1383 NoCallBlocksCache.erase(IfConv.Head);
1384 for (MachineBasicBlock *MBB : RemoveBlocks) {
1385 NoCallBlocksCache.erase(MBB);
1387 }
1388 }
1389 return Changed;
1390}
1391
1392bool EarlyIfConverter::run(MachineFunction &MF) {
1393 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1394 << "********** Function: " << MF.getName() << '\n');
1395
1396 STI = &MF.getSubtarget();
1397 // Only run if conversion if the target wants it.
1398 if (!STI->enableEarlyIfConversion())
1399 return false;
1400
1401 TII = STI->getInstrInfo();
1402 TRI = STI->getRegisterInfo();
1403 MRI = &MF.getRegInfo();
1404 MinInstr = nullptr;
1405
1406 bool Changed = false;
1407 IfConv.init(MF);
1408
1409 // Visit blocks in dominator tree post-order. The post-order enables nested
1410 // if-conversion in a single pass. The tryConvertIf() function may erase
1411 // blocks, but only blocks dominated by the head block. This makes it safe to
1412 // update the dominator tree while the post-order iterator is still active.
1413 for (auto *DomNode : post_order(DomTree))
1414 if (tryConvertIf(DomNode->getBlock()))
1415 Changed = true;
1416
1417 return Changed;
1418}
1419
1420PreservedAnalyses
1428
1429 EarlyIfConverter Impl(getCodeGenOptions(MF), MDT, LI, MTM, MBPI);
1430 bool Changed = Impl.run(MF);
1431 if (!Changed)
1432 return PreservedAnalyses::all();
1433
1435 PA.preserve<MachineDominatorTreeAnalysis>();
1436 PA.preserve<MachineLoopAnalysis>();
1437 PA.preserve<MachineTraceMetricsAnalysis>();
1438 return PA;
1439}
1440
1441bool EarlyIfConverterLegacy::runOnMachineFunction(MachineFunction &MF) {
1442 if (skipFunction(MF.getFunction()))
1443 return false;
1444
1446 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1447 MachineLoopInfo &LI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1448 MachineTraceMetrics &MTM =
1449 getAnalysis<MachineTraceMetricsWrapperPass>().getMTM();
1451 getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1452
1453 return EarlyIfConverter(getCodeGenOptions(MF), MDT, LI, MTM, MBPI).run(MF);
1454}
1455
1456//===----------------------------------------------------------------------===//
1457// EarlyIfPredicator Pass
1458//===----------------------------------------------------------------------===//
1459
1460namespace {
1461class EarlyIfPredicator : public MachineFunctionPass {
1462 const TargetInstrInfo *TII = nullptr;
1463 const TargetRegisterInfo *TRI = nullptr;
1464 TargetSchedModel SchedModel;
1465 MachineRegisterInfo *MRI = nullptr;
1466 MachineDominatorTree *DomTree = nullptr;
1467 MachineBranchProbabilityInfo *MBPI = nullptr;
1468 MachineLoopInfo *Loops = nullptr;
1469 SSAIfConv IfConv;
1470
1471public:
1472 static char ID;
1473 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1474 void getAnalysisUsage(AnalysisUsage &AU) const override;
1475 bool runOnMachineFunction(MachineFunction &MF) override;
1476 StringRef getPassName() const override { return "Early If-predicator"; }
1477
1478protected:
1479 bool tryConvertIf(MachineBasicBlock *);
1480 bool shouldConvertIf();
1481};
1482} // end anonymous namespace
1483
1484#undef DEBUG_TYPE
1485#define DEBUG_TYPE "early-if-predicator"
1486
1487char EarlyIfPredicator::ID = 0;
1488char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1489
1490INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1491 false, false)
1494INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1495 false)
1496
1497void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1499 AU.addRequired<MachineDominatorTreeWrapperPass>();
1500 AU.addPreserved<MachineDominatorTreeWrapperPass>();
1501 AU.addRequired<MachineLoopInfoWrapperPass>();
1502 AU.addPreserved<MachineLoopInfoWrapperPass>();
1504}
1505
1506/// Apply the target heuristic to decide if the transformation is profitable.
1507bool EarlyIfPredicator::shouldConvertIf() {
1508 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
1509 if (IfConv.isTriangle()) {
1510 MachineBasicBlock &IfBlock =
1511 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1512
1513 unsigned ExtraPredCost = 0;
1514 unsigned Cycles = 0;
1515 for (MachineInstr &I : IfBlock) {
1516 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1517 if (NumCycles > 1)
1518 Cycles += NumCycles - 1;
1519 ExtraPredCost += TII->getPredicationCost(I);
1520 }
1521
1522 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1523 TrueProbability);
1524 }
1525 unsigned TExtra = 0;
1526 unsigned FExtra = 0;
1527 unsigned TCycle = 0;
1528 unsigned FCycle = 0;
1529 for (MachineInstr &I : *IfConv.TBB) {
1530 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1531 if (NumCycles > 1)
1532 TCycle += NumCycles - 1;
1533 TExtra += TII->getPredicationCost(I);
1534 }
1535 for (MachineInstr &I : *IfConv.FBB) {
1536 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1537 if (NumCycles > 1)
1538 FCycle += NumCycles - 1;
1539 FExtra += TII->getPredicationCost(I);
1540 }
1541 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1542 FCycle, FExtra, TrueProbability);
1543}
1544
1545/// Attempt repeated if-conversion on MBB, return true if successful.
1546///
1547bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1548 bool Changed = false;
1549 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1550 // If-convert MBB and update analyses.
1551 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1552 IfConv.convertIf(RemoveBlocks, /*Predicate*/ true);
1553 Changed = true;
1554 updateDomTree(DomTree, IfConv, RemoveBlocks);
1555 updateLoops(Loops, RemoveBlocks);
1556 for (MachineBasicBlock *MBB : RemoveBlocks)
1558 }
1559 return Changed;
1560}
1561
1562bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1563 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1564 << "********** Function: " << MF.getName() << '\n');
1565 if (skipFunction(MF.getFunction()))
1566 return false;
1567
1568 const TargetSubtargetInfo &STI = MF.getSubtarget();
1569 TII = STI.getInstrInfo();
1570 TRI = STI.getRegisterInfo();
1571 MRI = &MF.getRegInfo();
1572 SchedModel.init(&STI);
1573 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1574 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1575 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1576
1577 bool Changed = false;
1578 IfConv.init(MF);
1579
1580 // Visit blocks in dominator tree post-order. The post-order enables nested
1581 // if-conversion in a single pass. The tryConvertIf() function may erase
1582 // blocks, but only blocks dominated by the head block. This makes it safe to
1583 // update the dominator tree while the post-order iterator is still active.
1584 for (auto *DomNode : post_order(DomTree))
1585 if (tryConvertIf(DomNode->getBlock()))
1586 Changed = true;
1587
1588 return Changed;
1589}
MachineInstrBuilder MachineInstrBuilder & DefMI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
This file implements the BitVector class.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static unsigned InstrCount
This file defines the DenseMap class.
static bool hasSameValue(const MachineRegisterInfo &MRI, const TargetInstrInfo *TII, Register TReg, Register FReg)
static unsigned adjCycles(unsigned Cyc, int Delta)
static bool isConstantPoolLoad(const MachineInstr *MI)
#define DEBUG_TYPE
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
Hexagon Hardware Loops
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition MD5.cpp:57
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
SmallVector< MachineOperand, 4 > Cond
MachineRegisterInfo & MRI
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
This file defines the SmallPtrSet class.
This file defines the SparseSet class derived from the version described in Briggs,...
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:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Definition BitVector.h:483
BitVector & reset()
Reset all bits in the bitvector.
Definition BitVector.h:410
BitVector & set()
Set all bits in the bitvector.
Definition BitVector.h:367
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, BranchProbability Probability) const override
Return true if it's profitable to predicate instructions with accumulated instruction latency of "Num...
bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Cond) const override
Convert the instruction into a predicated instruction.
bool isPredicable(const MachineInstr &MI) const override
Return true if the specified instruction can be predicated.
LLVM_ABI void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
LLVM_ABI void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI void moveAfter(MachineBasicBlock *NewBefore)
LLVM_ABI BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineInstr *A, const MachineInstr *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & back() const
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
LLVM_ABI bool isDereferenceableInvariantLoad() const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
LLVM_ABI bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
mop_range uses()
Returns all operands which may be register uses.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
Analysis pass that exposes the MachineLoopInfo for a machine function.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
LLVM_ABI unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks={}, ArrayRef< const MCSchedClassDesc * > ExtraInstrs={}, ArrayRef< const MCSchedClassDesc * > RemoveInstrs={}) const
Return the resource length of the trace.
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
LLVM_ABI unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
unsigned getCriticalPath() const
Return the length of the (data dependency) critical path through the trace.
LLVM_ABI unsigned getPHIDepth(const MachineInstr &PHI) const
Return the Depth of a PHI instruction in a trace center block successor.
LLVM_ABI void verifyAnalysis() const
LLVM_ABI void invalidate(const MachineBasicBlock *MBB)
Invalidate cached information about MBB.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Wrapper class representing virtual and physical registers.
Definition Register.h:20
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition Register.h:107
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition Register.h:83
size_type size() const
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition SparseSet.h:288
void clear()
clear - Clears the set.
Definition SparseSet.h:191
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition SparseSet.h:254
bool empty() const
empty - Returns true if the set is empty.
Definition SparseSet.h:180
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
virtual bool enableEarlyIfConversion() const
Enable the use of the early if conversion pass.
self_iterator getIterator()
Definition ilist_node.h:123
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition CallingConv.h:76
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
constexpr double phi
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI char & EarlyIfConverterLegacyID
EarlyIfConverter - This pass performs if-conversion on SSA form by inserting cmov instructions.
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
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:1762
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
auto post_order(const T &G)
Post-order traversal of a graph.
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
LLVM_ABI char & EarlyIfPredicatorID
EarlyIfPredicator - This pass performs if-conversion on SSA form by predicating if/else block and ins...
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define N
#define MORE()
Definition regcomp.c:247
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...