LLVM 17.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
18#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/SparseSet.h"
22#include "llvm/ADT/Statistic.h"
38#include "llvm/Support/Debug.h"
40
41using namespace llvm;
42
43#define DEBUG_TYPE "early-ifcvt"
44
45// Absolute maximum number of instructions allowed per speculated block.
46// This bypasses all other heuristics, so it should be set fairly high.
48BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
49 cl::desc("Maximum number of instructions per speculated block."));
50
51// Stress testing mode - disable heuristics.
52static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
53 cl::desc("Turn all knobs to 11"));
54
55STATISTIC(NumDiamondsSeen, "Number of diamonds");
56STATISTIC(NumDiamondsConv, "Number of diamonds converted");
57STATISTIC(NumTrianglesSeen, "Number of triangles");
58STATISTIC(NumTrianglesConv, "Number of triangles converted");
59
60//===----------------------------------------------------------------------===//
61// SSAIfConv
62//===----------------------------------------------------------------------===//
63//
64// The SSAIfConv class performs if-conversion on SSA form machine code after
65// determining if it is possible. The class contains no heuristics; external
66// code should be used to determine when if-conversion is a good idea.
67//
68// SSAIfConv can convert both triangles and diamonds:
69//
70// Triangle: Head Diamond: Head
71// | \ / \_
72// | \ / |
73// | [TF]BB FBB TBB
74// | / \ /
75// | / \ /
76// Tail Tail
77//
78// Instructions in the conditional blocks TBB and/or FBB are spliced into the
79// Head block, and phis in the Tail block are converted to select instructions.
80//
81namespace {
82class SSAIfConv {
83 const TargetInstrInfo *TII;
86
87public:
88 /// The block containing the conditional branch.
90
91 /// The block containing phis after the if-then-else.
93
94 /// The 'true' conditional block as determined by analyzeBranch.
96
97 /// The 'false' conditional block as determined by analyzeBranch.
99
100 /// isTriangle - When there is no 'else' block, either TBB or FBB will be
101 /// equal to Tail.
102 bool isTriangle() const { return TBB == Tail || FBB == Tail; }
103
104 /// Returns the Tail predecessor for the True side.
105 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
106
107 /// Returns the Tail predecessor for the False side.
108 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
109
110 /// Information about each phi in the Tail block.
111 struct PHIInfo {
113 unsigned TReg = 0, FReg = 0;
114 // Latencies from Cond+Branch, TReg, and FReg to DstReg.
115 int CondCycles = 0, TCycles = 0, FCycles = 0;
116
117 PHIInfo(MachineInstr *phi) : PHI(phi) {}
118 };
119
121
122private:
123 /// The branch condition determined by analyzeBranch.
125
126 /// Instructions in Head that define values used by the conditional blocks.
127 /// The hoisted instructions must be inserted after these instructions.
129
130 /// Register units clobbered by the conditional blocks.
131 BitVector ClobberedRegUnits;
132
133 // Scratch pad for findInsertionPoint.
135
136 /// Insertion point in Head for speculatively executed instructions form TBB
137 /// and FBB.
138 MachineBasicBlock::iterator InsertionPoint;
139
140 /// Return true if all non-terminator instructions in MBB can be safely
141 /// speculated.
142 bool canSpeculateInstrs(MachineBasicBlock *MBB);
143
144 /// Return true if all non-terminator instructions in MBB can be safely
145 /// predicated.
146 bool canPredicateInstrs(MachineBasicBlock *MBB);
147
148 /// Scan through instruction dependencies and update InsertAfter array.
149 /// Return false if any dependency is incompatible with if conversion.
150 bool InstrDependenciesAllowIfConv(MachineInstr *I);
151
152 /// Predicate all instructions of the basic block with current condition
153 /// except for terminators. Reverse the condition if ReversePredicate is set.
154 void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
155
156 /// Find a valid insertion point in Head.
157 bool findInsertionPoint();
158
159 /// Replace PHI instructions in Tail with selects.
160 void replacePHIInstrs();
161
162 /// Insert selects and rewrite PHI operands to use them.
163 void rewritePHIOperands();
164
165public:
166 /// runOnMachineFunction - Initialize per-function data structures.
167 void runOnMachineFunction(MachineFunction &MF) {
170 MRI = &MF.getRegInfo();
172 LiveRegUnits.setUniverse(TRI->getNumRegUnits());
173 ClobberedRegUnits.clear();
174 ClobberedRegUnits.resize(TRI->getNumRegUnits());
175 }
176
177 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
178 /// initialize the internal state, and return true.
179 /// If predicate is set try to predicate the block otherwise try to
180 /// speculatively execute it.
181 bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
182
183 /// convertIf - If-convert the last block passed to canConvertIf(), assuming
184 /// it is possible. Add any erased blocks to RemovedBlocks.
185 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
186 bool Predicate = false);
187};
188} // end anonymous namespace
189
190
191/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
192/// be speculated. The terminators are not considered.
193///
194/// If instructions use any values that are defined in the head basic block,
195/// the defining instructions are added to InsertAfter.
196///
197/// Any clobbered regunits are added to ClobberedRegUnits.
198///
199bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
200 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
201 // get right.
202 if (!MBB->livein_empty()) {
203 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
204 return false;
205 }
206
207 unsigned InstrCount = 0;
208
209 // Check all instructions, except the terminators. It is assumed that
210 // terminators never have side effects or define any used register values.
211 for (MachineInstr &MI :
213 if (MI.isDebugInstr())
214 continue;
215
216 if (++InstrCount > BlockInstrLimit && !Stress) {
217 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
218 << BlockInstrLimit << " instructions.\n");
219 return false;
220 }
221
222 // There shouldn't normally be any phis in a single-predecessor block.
223 if (MI.isPHI()) {
224 LLVM_DEBUG(dbgs() << "Can't hoist: " << MI);
225 return false;
226 }
227
228 // Don't speculate loads. Note that it may be possible and desirable to
229 // speculate GOT or constant pool loads that are guaranteed not to trap,
230 // but we don't support that for now.
231 if (MI.mayLoad()) {
232 LLVM_DEBUG(dbgs() << "Won't speculate load: " << MI);
233 return false;
234 }
235
236 // We never speculate stores, so an AA pointer isn't necessary.
237 bool DontMoveAcrossStore = true;
238 if (!MI.isSafeToMove(nullptr, DontMoveAcrossStore)) {
239 LLVM_DEBUG(dbgs() << "Can't speculate: " << MI);
240 return false;
241 }
242
243 // Check for any dependencies on Head instructions.
244 if (!InstrDependenciesAllowIfConv(&MI))
245 return false;
246 }
247 return true;
248}
249
250/// Check that there is no dependencies preventing if conversion.
251///
252/// If instruction uses any values that are defined in the head basic block,
253/// the defining instructions are added to InsertAfter.
254bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
255 for (const MachineOperand &MO : I->operands()) {
256 if (MO.isRegMask()) {
257 LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
258 return false;
259 }
260 if (!MO.isReg())
261 continue;
262 Register Reg = MO.getReg();
263
264 // Remember clobbered regunits.
265 if (MO.isDef() && Reg.isPhysical())
266 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
267 ++Units)
268 ClobberedRegUnits.set(*Units);
269
270 if (!MO.readsReg() || !Reg.isVirtual())
271 continue;
272 MachineInstr *DefMI = MRI->getVRegDef(Reg);
273 if (!DefMI || DefMI->getParent() != Head)
274 continue;
275 if (InsertAfter.insert(DefMI).second)
276 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
277 << *DefMI);
278 if (DefMI->isTerminator()) {
279 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
280 return false;
281 }
282 }
283 return true;
284}
285
286/// canPredicateInstrs - Returns true if all the instructions in MBB can safely
287/// be predicates. The terminators are not considered.
288///
289/// If instructions use any values that are defined in the head basic block,
290/// the defining instructions are added to InsertAfter.
291///
292/// Any clobbered regunits are added to ClobberedRegUnits.
293///
294bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
295 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
296 // get right.
297 if (!MBB->livein_empty()) {
298 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
299 return false;
300 }
301
302 unsigned InstrCount = 0;
303
304 // Check all instructions, except the terminators. It is assumed that
305 // terminators never have side effects or define any used register values.
308 I != E; ++I) {
309 if (I->isDebugInstr())
310 continue;
311
312 if (++InstrCount > BlockInstrLimit && !Stress) {
313 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
314 << BlockInstrLimit << " instructions.\n");
315 return false;
316 }
317
318 // There shouldn't normally be any phis in a single-predecessor block.
319 if (I->isPHI()) {
320 LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
321 return false;
322 }
323
324 // Check that instruction is predicable
325 if (!TII->isPredicable(*I)) {
326 LLVM_DEBUG(dbgs() << "Isn't predicable: " << *I);
327 return false;
328 }
329
330 // Check that instruction is not already predicated.
331 if (TII->isPredicated(*I) && !TII->canPredicatePredicatedInstr(*I)) {
332 LLVM_DEBUG(dbgs() << "Is already predicated: " << *I);
333 return false;
334 }
335
336 // Check for any dependencies on Head instructions.
337 if (!InstrDependenciesAllowIfConv(&(*I)))
338 return false;
339 }
340 return true;
341}
342
343// Apply predicate to all instructions in the machine block.
344void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
345 auto Condition = Cond;
346 if (ReversePredicate)
347 TII->reverseBranchCondition(Condition);
348 // Terminators don't need to be predicated as they will be removed.
351 I != E; ++I) {
352 if (I->isDebugInstr())
353 continue;
354 TII->PredicateInstruction(*I, Condition);
355 }
356}
357
358/// Find an insertion point in Head for the speculated instructions. The
359/// insertion point must be:
360///
361/// 1. Before any terminators.
362/// 2. After any instructions in InsertAfter.
363/// 3. Not have any clobbered regunits live.
364///
365/// This function sets InsertionPoint and returns true when successful, it
366/// returns false if no valid insertion point could be found.
367///
368bool SSAIfConv::findInsertionPoint() {
369 // Keep track of live regunits before the current position.
370 // Only track RegUnits that are also in ClobberedRegUnits.
376 while (I != B) {
377 --I;
378 // Some of the conditional code depends in I.
379 if (InsertAfter.count(&*I)) {
380 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
381 return false;
382 }
383
384 // Update live regunits.
385 for (const MachineOperand &MO : I->operands()) {
386 // We're ignoring regmask operands. That is conservatively correct.
387 if (!MO.isReg())
388 continue;
389 Register Reg = MO.getReg();
390 if (!Reg.isPhysical())
391 continue;
392 // I clobbers Reg, so it isn't live before I.
393 if (MO.isDef())
394 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
395 ++Units)
396 LiveRegUnits.erase(*Units);
397 // Unless I reads Reg.
398 if (MO.readsReg())
399 Reads.push_back(Reg.asMCReg());
400 }
401 // Anything read by I is live before I.
402 while (!Reads.empty())
403 for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
404 ++Units)
405 if (ClobberedRegUnits.test(*Units))
406 LiveRegUnits.insert(*Units);
407
408 // We can't insert before a terminator.
409 if (I != FirstTerm && I->isTerminator())
410 continue;
411
412 // Some of the clobbered registers are live before I, not a valid insertion
413 // point.
414 if (!LiveRegUnits.empty()) {
415 LLVM_DEBUG({
416 dbgs() << "Would clobber";
417 for (unsigned LRU : LiveRegUnits)
418 dbgs() << ' ' << printRegUnit(LRU, TRI);
419 dbgs() << " live before " << *I;
420 });
421 continue;
422 }
423
424 // This is a valid insertion point.
425 InsertionPoint = I;
426 LLVM_DEBUG(dbgs() << "Can insert before " << *I);
427 return true;
428 }
429 LLVM_DEBUG(dbgs() << "No legal insertion point found.\n");
430 return false;
431}
432
433
434
435/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
436/// a potential candidate for if-conversion. Fill out the internal state.
437///
438bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {
439 Head = MBB;
440 TBB = FBB = Tail = nullptr;
441
442 if (Head->succ_size() != 2)
443 return false;
444 MachineBasicBlock *Succ0 = Head->succ_begin()[0];
445 MachineBasicBlock *Succ1 = Head->succ_begin()[1];
446
447 // Canonicalize so Succ0 has MBB as its single predecessor.
448 if (Succ0->pred_size() != 1)
449 std::swap(Succ0, Succ1);
450
451 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
452 return false;
453
454 Tail = Succ0->succ_begin()[0];
455
456 // This is not a triangle.
457 if (Tail != Succ1) {
458 // Check for a diamond. We won't deal with any critical edges.
459 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
460 Succ1->succ_begin()[0] != Tail)
461 return false;
462 LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> "
463 << printMBBReference(*Succ0) << "/"
464 << printMBBReference(*Succ1) << " -> "
465 << printMBBReference(*Tail) << '\n');
466
467 // Live-in physregs are tricky to get right when speculating code.
468 if (!Tail->livein_empty()) {
469 LLVM_DEBUG(dbgs() << "Tail has live-ins.\n");
470 return false;
471 }
472 } else {
473 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
474 << printMBBReference(*Succ0) << " -> "
475 << printMBBReference(*Tail) << '\n');
476 }
477
478 // This is a triangle or a diamond.
479 // Skip if we cannot predicate and there are no phis skip as there must be
480 // side effects that can only be handled with predication.
481 if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) {
482 LLVM_DEBUG(dbgs() << "No phis in tail.\n");
483 return false;
484 }
485
486 // The branch we're looking to eliminate must be analyzable.
487 Cond.clear();
488 if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) {
489 LLVM_DEBUG(dbgs() << "Branch not analyzable.\n");
490 return false;
491 }
492
493 // This is weird, probably some sort of degenerate CFG.
494 if (!TBB) {
495 LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n");
496 return false;
497 }
498
499 // Make sure the analyzed branch is conditional; one of the successors
500 // could be a landing pad. (Empty landing pads can be generated on Windows.)
501 if (Cond.empty()) {
502 LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n");
503 return false;
504 }
505
506 // analyzeBranch doesn't set FBB on a fall-through branch.
507 // Make sure it is always set.
508 FBB = TBB == Succ0 ? Succ1 : Succ0;
509
510 // Any phis in the tail block must be convertible to selects.
511 PHIs.clear();
512 MachineBasicBlock *TPred = getTPred();
513 MachineBasicBlock *FPred = getFPred();
514 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
515 I != E && I->isPHI(); ++I) {
516 PHIs.push_back(&*I);
517 PHIInfo &PI = PHIs.back();
518 // Find PHI operands corresponding to TPred and FPred.
519 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
520 if (PI.PHI->getOperand(i+1).getMBB() == TPred)
521 PI.TReg = PI.PHI->getOperand(i).getReg();
522 if (PI.PHI->getOperand(i+1).getMBB() == FPred)
523 PI.FReg = PI.PHI->getOperand(i).getReg();
524 }
525 assert(Register::isVirtualRegister(PI.TReg) && "Bad PHI");
526 assert(Register::isVirtualRegister(PI.FReg) && "Bad PHI");
527
528 // Get target information.
529 if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(),
530 PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles,
531 PI.FCycles)) {
532 LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
533 return false;
534 }
535 }
536
537 // Check that the conditional instructions can be speculated.
538 InsertAfter.clear();
539 ClobberedRegUnits.reset();
540 if (Predicate) {
541 if (TBB != Tail && !canPredicateInstrs(TBB))
542 return false;
543 if (FBB != Tail && !canPredicateInstrs(FBB))
544 return false;
545 } else {
546 if (TBB != Tail && !canSpeculateInstrs(TBB))
547 return false;
548 if (FBB != Tail && !canSpeculateInstrs(FBB))
549 return false;
550 }
551
552 // Try to find a valid insertion point for the speculated instructions in the
553 // head basic block.
554 if (!findInsertionPoint())
555 return false;
556
557 if (isTriangle())
558 ++NumTrianglesSeen;
559 else
560 ++NumDiamondsSeen;
561 return true;
562}
563
564/// \return true iff the two registers are known to have the same value.
566 const TargetInstrInfo *TII, Register TReg,
567 Register FReg) {
568 if (TReg == FReg)
569 return true;
570
571 if (!TReg.isVirtual() || !FReg.isVirtual())
572 return false;
573
574 const MachineInstr *TDef = MRI.getUniqueVRegDef(TReg);
575 const MachineInstr *FDef = MRI.getUniqueVRegDef(FReg);
576 if (!TDef || !FDef)
577 return false;
578
579 // If there are side-effects, all bets are off.
580 if (TDef->hasUnmodeledSideEffects())
581 return false;
582
583 // If the instruction could modify memory, or there may be some intervening
584 // store between the two, we can't consider them to be equal.
585 if (TDef->mayLoadOrStore() && !TDef->isDereferenceableInvariantLoad())
586 return false;
587
588 // We also can't guarantee that they are the same if, for example, the
589 // instructions are both a copy from a physical reg, because some other
590 // instruction may have modified the value in that reg between the two
591 // defining insts.
592 if (any_of(TDef->uses(), [](const MachineOperand &MO) {
593 return MO.isReg() && MO.getReg().isPhysical();
594 }))
595 return false;
596
597 // Check whether the two defining instructions produce the same value(s).
598 if (!TII->produceSameValue(*TDef, *FDef, &MRI))
599 return false;
600
601 // Further, check that the two defs come from corresponding operands.
602 int TIdx = TDef->findRegisterDefOperandIdx(TReg);
603 int FIdx = FDef->findRegisterDefOperandIdx(FReg);
604 if (TIdx == -1 || FIdx == -1)
605 return false;
606
607 return TIdx == FIdx;
608}
609
610/// replacePHIInstrs - Completely replace PHI instructions with selects.
611/// This is possible when the only Tail predecessors are the if-converted
612/// blocks.
613void SSAIfConv::replacePHIInstrs() {
614 assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
616 assert(FirstTerm != Head->end() && "No terminators");
617 DebugLoc HeadDL = FirstTerm->getDebugLoc();
618
619 // Convert all PHIs to select instructions inserted before FirstTerm.
620 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
621 PHIInfo &PI = PHIs[i];
622 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
623 Register DstReg = PI.PHI->getOperand(0).getReg();
624 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
625 // We do not need the select instruction if both incoming values are
626 // equal, but we do need a COPY.
627 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)
628 .addReg(PI.TReg);
629 } else {
630 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,
631 PI.FReg);
632 }
633 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
634 PI.PHI->eraseFromParent();
635 PI.PHI = nullptr;
636 }
637}
638
639/// rewritePHIOperands - When there are additional Tail predecessors, insert
640/// select instructions in Head and rewrite PHI operands to use the selects.
641/// Keep the PHI instructions in Tail to handle the other predecessors.
642void SSAIfConv::rewritePHIOperands() {
644 assert(FirstTerm != Head->end() && "No terminators");
645 DebugLoc HeadDL = FirstTerm->getDebugLoc();
646
647 // Convert all PHIs to select instructions inserted before FirstTerm.
648 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
649 PHIInfo &PI = PHIs[i];
650 unsigned DstReg = 0;
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 erased will be added to RemovedBlocks.
684///
685void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
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 // Erase the now empty conditional blocks. It is likely that Head can fall
727 // through to Tail, and we can join the two blocks.
728 if (TBB != Tail) {
729 RemovedBlocks.push_back(TBB);
731 }
732 if (FBB != Tail) {
733 RemovedBlocks.push_back(FBB);
734 FBB->eraseFromParent();
735 }
736
737 assert(Head->succ_empty() && "Additional head successors?");
738 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
739 // Splice Tail onto the end of Head.
740 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
741 << " into head " << printMBBReference(*Head) << '\n');
742 Head->splice(Head->end(), Tail,
743 Tail->begin(), Tail->end());
745 RemovedBlocks.push_back(Tail);
746 Tail->eraseFromParent();
747 } else {
748 // We need a branch to Tail, let code placement work it out later.
749 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
751 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
752 Head->addSuccessor(Tail);
753 }
754 LLVM_DEBUG(dbgs() << *Head);
755}
756
757//===----------------------------------------------------------------------===//
758// EarlyIfConverter Pass
759//===----------------------------------------------------------------------===//
760
761namespace {
762class EarlyIfConverter : public MachineFunctionPass {
763 const TargetInstrInfo *TII;
764 const TargetRegisterInfo *TRI;
765 MCSchedModel SchedModel;
767 MachineDominatorTree *DomTree;
769 MachineTraceMetrics *Traces;
771 SSAIfConv IfConv;
772
773public:
774 static char ID;
775 EarlyIfConverter() : MachineFunctionPass(ID) {}
776 void getAnalysisUsage(AnalysisUsage &AU) const override;
777 bool runOnMachineFunction(MachineFunction &MF) override;
778 StringRef getPassName() const override { return "Early If-Conversion"; }
779
780private:
781 bool tryConvertIf(MachineBasicBlock*);
782 void invalidateTraces();
783 bool shouldConvertIf();
784};
785} // end anonymous namespace
786
787char EarlyIfConverter::ID = 0;
788char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
789
791 "Early If Converter", false, false)
796 "Early If Converter", false, false)
797
798void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
799 AU.addRequired<MachineBranchProbabilityInfo>();
800 AU.addRequired<MachineDominatorTree>();
801 AU.addPreserved<MachineDominatorTree>();
802 AU.addRequired<MachineLoopInfo>();
803 AU.addPreserved<MachineLoopInfo>();
804 AU.addRequired<MachineTraceMetrics>();
805 AU.addPreserved<MachineTraceMetrics>();
807}
808
809namespace {
810/// Update the dominator tree after if-conversion erased some blocks.
811void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
813 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
814 // TBB and FBB should not dominate any blocks.
815 // Tail children should be transferred to Head.
816 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
817 for (auto *B : Removed) {
818 MachineDomTreeNode *Node = DomTree->getNode(B);
819 assert(Node != HeadNode && "Cannot erase the head node");
820 while (Node->getNumChildren()) {
821 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
822 DomTree->changeImmediateDominator(Node->back(), HeadNode);
823 }
824 DomTree->eraseNode(B);
825 }
826}
827
828/// Update LoopInfo after if-conversion.
829void updateLoops(MachineLoopInfo *Loops,
831 if (!Loops)
832 return;
833 // If-conversion doesn't change loop structure, and it doesn't mess with back
834 // edges, so updating LoopInfo is simply removing the dead blocks.
835 for (auto *B : Removed)
836 Loops->removeBlock(B);
837}
838} // namespace
839
840/// Invalidate MachineTraceMetrics before if-conversion.
841void EarlyIfConverter::invalidateTraces() {
842 Traces->verifyAnalysis();
843 Traces->invalidate(IfConv.Head);
844 Traces->invalidate(IfConv.Tail);
845 Traces->invalidate(IfConv.TBB);
846 Traces->invalidate(IfConv.FBB);
847 Traces->verifyAnalysis();
848}
849
850// Adjust cycles with downward saturation.
851static unsigned adjCycles(unsigned Cyc, int Delta) {
852 if (Delta < 0 && Cyc + Delta > Cyc)
853 return 0;
854 return Cyc + Delta;
855}
856
857namespace {
858/// Helper class to simplify emission of cycle counts into optimization remarks.
859struct Cycles {
860 const char *Key;
861 unsigned Value;
862};
863template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
864 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
865}
866} // anonymous namespace
867
868/// Apply cost model and heuristics to the if-conversion in IfConv.
869/// Return true if the conversion is a good idea.
870///
871bool EarlyIfConverter::shouldConvertIf() {
872 // Stress testing mode disables all cost considerations.
873 if (Stress)
874 return true;
875
876 if (!MinInstr)
877 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
878
879 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
880 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
881 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
882 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
883 FBBTrace.getCriticalPath());
884
885 // Set a somewhat arbitrary limit on the critical path extension we accept.
886 unsigned CritLimit = SchedModel.MispredictPenalty/2;
887
888 MachineBasicBlock &MBB = *IfConv.Head;
890
891 // If-conversion only makes sense when there is unexploited ILP. Compute the
892 // maximum-ILP resource length of the trace after if-conversion. Compare it
893 // to the shortest critical path.
895 if (IfConv.TBB != IfConv.Tail)
896 ExtraBlocks.push_back(IfConv.TBB);
897 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
898 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
899 << ", minimal critical path " << MinCrit << '\n');
900 if (ResLength > MinCrit + CritLimit) {
901 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
902 MORE.emit([&]() {
905 R << "did not if-convert branch: the resulting critical path ("
906 << Cycles{"ResLength", ResLength}
907 << ") would extend the shorter leg's critical path ("
908 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "
909 << Cycles{"CritLimit", CritLimit}
910 << ", which cannot be hidden by available ILP.";
911 return R;
912 });
913 return false;
914 }
915
916 // Assume that the depth of the first head terminator will also be the depth
917 // of the select instruction inserted, as determined by the flag dependency.
918 // TBB / FBB data dependencies may delay the select even more.
919 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
920 unsigned BranchDepth =
921 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
922 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
923
924 // Look at all the tail phis, and compute the critical path extension caused
925 // by inserting select instructions.
926 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
927 struct CriticalPathInfo {
928 unsigned Extra; // Count of extra cycles that the component adds.
929 unsigned Depth; // Absolute depth of the component in cycles.
930 };
931 CriticalPathInfo Cond{};
932 CriticalPathInfo TBlock{};
933 CriticalPathInfo FBlock{};
934 bool ShouldConvert = true;
935 for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
936 SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
937 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
938 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
939 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
940
941 // The condition is pulled into the critical path.
942 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
943 if (CondDepth > MaxDepth) {
944 unsigned Extra = CondDepth - MaxDepth;
945 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
946 if (Extra > Cond.Extra)
947 Cond = {Extra, CondDepth};
948 if (Extra > CritLimit) {
949 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
950 ShouldConvert = false;
951 }
952 }
953
954 // The TBB value is pulled into the critical path.
955 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
956 if (TDepth > MaxDepth) {
957 unsigned Extra = TDepth - MaxDepth;
958 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
959 if (Extra > TBlock.Extra)
960 TBlock = {Extra, TDepth};
961 if (Extra > CritLimit) {
962 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
963 ShouldConvert = false;
964 }
965 }
966
967 // The FBB value is pulled into the critical path.
968 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
969 if (FDepth > MaxDepth) {
970 unsigned Extra = FDepth - MaxDepth;
971 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
972 if (Extra > FBlock.Extra)
973 FBlock = {Extra, FDepth};
974 if (Extra > CritLimit) {
975 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
976 ShouldConvert = false;
977 }
978 }
979 }
980
981 // Organize by "short" and "long" legs, since the diagnostics get confusing
982 // when referring to the "true" and "false" sides of the branch, given that
983 // those don't always correlate with what the user wrote in source-terms.
984 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
985 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
986
987 if (ShouldConvert) {
988 MORE.emit([&]() {
989 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
990 MBB.back().getDebugLoc(), &MBB);
991 R << "performing if-conversion on branch: the condition adds "
992 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
993 if (Short.Extra > 0)
994 R << ", and the short leg adds another "
995 << Cycles{"ShortCycles", Short.Extra};
996 if (Long.Extra > 0)
997 R << ", and the long leg adds another "
998 << Cycles{"LongCycles", Long.Extra};
999 R << ", each staying under the threshold of "
1000 << Cycles{"CritLimit", CritLimit} << ".";
1001 return R;
1002 });
1003 } else {
1004 MORE.emit([&]() {
1006 MBB.back().getDebugLoc(), &MBB);
1007 R << "did not if-convert branch: the condition would add "
1008 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1009 if (Cond.Extra > CritLimit)
1010 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1011 if (Short.Extra > 0) {
1012 R << ", and the short leg would add another "
1013 << Cycles{"ShortCycles", Short.Extra};
1014 if (Short.Extra > CritLimit)
1015 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1016 }
1017 if (Long.Extra > 0) {
1018 R << ", and the long leg would add another "
1019 << Cycles{"LongCycles", Long.Extra};
1020 if (Long.Extra > CritLimit)
1021 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1022 }
1023 R << ".";
1024 return R;
1025 });
1026 }
1027
1028 return ShouldConvert;
1029}
1030
1031/// Attempt repeated if-conversion on MBB, return true if successful.
1032///
1033bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1034 bool Changed = false;
1035 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1036 // If-convert MBB and update analyses.
1037 invalidateTraces();
1039 IfConv.convertIf(RemovedBlocks);
1040 Changed = true;
1041 updateDomTree(DomTree, IfConv, RemovedBlocks);
1042 updateLoops(Loops, RemovedBlocks);
1043 }
1044 return Changed;
1045}
1046
1047bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
1048 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1049 << "********** Function: " << MF.getName() << '\n');
1050 if (skipFunction(MF.getFunction()))
1051 return false;
1052
1053 // Only run if conversion if the target wants it.
1054 const TargetSubtargetInfo &STI = MF.getSubtarget();
1055 if (!STI.enableEarlyIfConversion())
1056 return false;
1057
1058 TII = STI.getInstrInfo();
1059 TRI = STI.getRegisterInfo();
1060 SchedModel = STI.getSchedModel();
1061 MRI = &MF.getRegInfo();
1062 DomTree = &getAnalysis<MachineDominatorTree>();
1063 Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1064 Traces = &getAnalysis<MachineTraceMetrics>();
1065 MinInstr = nullptr;
1066
1067 bool Changed = false;
1068 IfConv.runOnMachineFunction(MF);
1069
1070 // Visit blocks in dominator tree post-order. The post-order enables nested
1071 // if-conversion in a single pass. The tryConvertIf() function may erase
1072 // blocks, but only blocks dominated by the head block. This makes it safe to
1073 // update the dominator tree while the post-order iterator is still active.
1074 for (auto *DomNode : post_order(DomTree))
1075 if (tryConvertIf(DomNode->getBlock()))
1076 Changed = true;
1077
1078 return Changed;
1079}
1080
1081//===----------------------------------------------------------------------===//
1082// EarlyIfPredicator Pass
1083//===----------------------------------------------------------------------===//
1084
1085namespace {
1086class EarlyIfPredicator : public MachineFunctionPass {
1087 const TargetInstrInfo *TII;
1088 const TargetRegisterInfo *TRI;
1089 TargetSchedModel SchedModel;
1091 MachineDominatorTree *DomTree;
1094 SSAIfConv IfConv;
1095
1096public:
1097 static char ID;
1098 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1099 void getAnalysisUsage(AnalysisUsage &AU) const override;
1100 bool runOnMachineFunction(MachineFunction &MF) override;
1101 StringRef getPassName() const override { return "Early If-predicator"; }
1102
1103protected:
1104 bool tryConvertIf(MachineBasicBlock *);
1105 bool shouldConvertIf();
1106};
1107} // end anonymous namespace
1108
1109#undef DEBUG_TYPE
1110#define DEBUG_TYPE "early-if-predicator"
1111
1112char EarlyIfPredicator::ID = 0;
1113char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1114
1115INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1116 false, false)
1119INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1120 false)
1121
1122void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1123 AU.addRequired<MachineBranchProbabilityInfo>();
1124 AU.addRequired<MachineDominatorTree>();
1125 AU.addPreserved<MachineDominatorTree>();
1126 AU.addRequired<MachineLoopInfo>();
1127 AU.addPreserved<MachineLoopInfo>();
1129}
1130
1131/// Apply the target heuristic to decide if the transformation is profitable.
1132bool EarlyIfPredicator::shouldConvertIf() {
1133 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
1134 if (IfConv.isTriangle()) {
1135 MachineBasicBlock &IfBlock =
1136 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1137
1138 unsigned ExtraPredCost = 0;
1139 unsigned Cycles = 0;
1140 for (MachineInstr &I : IfBlock) {
1141 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1142 if (NumCycles > 1)
1143 Cycles += NumCycles - 1;
1144 ExtraPredCost += TII->getPredicationCost(I);
1145 }
1146
1147 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1148 TrueProbability);
1149 }
1150 unsigned TExtra = 0;
1151 unsigned FExtra = 0;
1152 unsigned TCycle = 0;
1153 unsigned FCycle = 0;
1154 for (MachineInstr &I : *IfConv.TBB) {
1155 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1156 if (NumCycles > 1)
1157 TCycle += NumCycles - 1;
1158 TExtra += TII->getPredicationCost(I);
1159 }
1160 for (MachineInstr &I : *IfConv.FBB) {
1161 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1162 if (NumCycles > 1)
1163 FCycle += NumCycles - 1;
1164 FExtra += TII->getPredicationCost(I);
1165 }
1166 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1167 FCycle, FExtra, TrueProbability);
1168}
1169
1170/// Attempt repeated if-conversion on MBB, return true if successful.
1171///
1172bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1173 bool Changed = false;
1174 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1175 // If-convert MBB and update analyses.
1177 IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1178 Changed = true;
1179 updateDomTree(DomTree, IfConv, RemovedBlocks);
1180 updateLoops(Loops, RemovedBlocks);
1181 }
1182 return Changed;
1183}
1184
1185bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1186 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1187 << "********** Function: " << MF.getName() << '\n');
1188 if (skipFunction(MF.getFunction()))
1189 return false;
1190
1191 const TargetSubtargetInfo &STI = MF.getSubtarget();
1192 TII = STI.getInstrInfo();
1193 TRI = STI.getRegisterInfo();
1194 MRI = &MF.getRegInfo();
1195 SchedModel.init(&STI);
1196 DomTree = &getAnalysis<MachineDominatorTree>();
1197 Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1198 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
1199
1200 bool Changed = false;
1201 IfConv.runOnMachineFunction(MF);
1202
1203 // Visit blocks in dominator tree post-order. The post-order enables nested
1204 // if-conversion in a single pass. The tryConvertIf() function may erase
1205 // blocks, but only blocks dominated by the head block. This makes it safe to
1206 // update the dominator tree while the post-order iterator is still active.
1207 for (auto *DomNode : post_order(DomTree))
1208 if (tryConvertIf(DomNode->getBlock()))
1209 Changed = true;
1210
1211 return Changed;
1212}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
Rewrite undef for PHI
for(auto &MBB :MF)
SmallVector< MachineOperand, 4 > Cond
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static unsigned InstrCount
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Early If Converter
Early If Predicator
static bool hasSameValue(const MachineRegisterInfo &MRI, const TargetInstrInfo *TII, Register TReg, Register FReg)
static unsigned adjCycles(unsigned Cyc, int Delta)
static cl::opt< bool > Stress("stress-early-ifcvt", cl::Hidden, cl::desc("Turn all knobs to 11"))
static cl::opt< unsigned > BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, cl::desc("Maximum number of instructions per speculated block."))
#define DEBUG_TYPE
const HexagonInstrInfo * TII
Hexagon Hardware Loops
IRTranslator LLVM IR MI
static const unsigned MaxDepth
#define I(x, y, z)
Definition: MD5.cpp:58
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:167
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & reset()
Definition: BitVector.h:392
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:341
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:335
BitVector & set()
Definition: BitVector.h:351
A debug info location.
Definition: DebugLoc.h:33
Base class for the actual dominator tree node.
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.
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
bool empty() const
Returns true if the set is empty.
Definition: LiveRegUnits.h:83
void clear()
Clears the set.
Definition: LiveRegUnits.h:80
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget's CPU.
unsigned pred_size() const
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions.
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
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 '...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void eraseNode(MachineBasicBlock *BB)
eraseNode - Removes a node from the dominator tree.
void changeImmediateDominator(MachineBasicBlock *N, MachineBasicBlock *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
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.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
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 MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:68
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:896
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
int findRegisterDefOperandIdx(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
bool isDereferenceableInvariantLoad() const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:689
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
MachineOperand class - Representation of each machine instruction operand.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A trace ensemble is a collection of traces selected using the same strategy, for example 'minimum res...
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks=std::nullopt, ArrayRef< const MCSchedClassDesc * > ExtraInstrs=std::nullopt, ArrayRef< const MCSchedClassDesc * > RemoveInstrs=std::nullopt) const
Return the resource length of the trace.
unsigned getCriticalPath() const
Return the length of the (data dependency) critical path through the trace.
unsigned getPHIDepth(const MachineInstr &PHI) const
Return the Depth of a PHI instruction in a trace center block successor.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:124
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
virtual bool enableEarlyIfConversion() const
Enable the use of the early if conversion pass.
LLVM Value Representation.
Definition: Value.h:74
Key
PAL metadata keys.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
constexpr double phi
Definition: MathExtras.h:45
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
iterator_range< po_iterator< T > > post_order(const T &G)
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:1826
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
char & EarlyIfPredicatorID
EarlyIfPredicator - This pass performs if-conversion on SSA form by predicating if/else block and ins...
char & EarlyIfConverterID
EarlyIfConverter - This pass performs if-conversion on SSA form by inserting cmov instructions.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define MORE()
Definition: regcomp.c:252
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...