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
122 /// The branch condition determined by analyzeBranch.
124
125private:
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 bool CanRevCond = !TII->reverseBranchCondition(Condition);
348 assert(CanRevCond && "Reversed predicate is not supported");
349 (void)CanRevCond;
350 }
351 // Terminators don't need to be predicated as they will be removed.
354 I != E; ++I) {
355 if (I->isDebugInstr())
356 continue;
357 TII->PredicateInstruction(*I, Condition);
358 }
359}
360
361/// Find an insertion point in Head for the speculated instructions. The
362/// insertion point must be:
363///
364/// 1. Before any terminators.
365/// 2. After any instructions in InsertAfter.
366/// 3. Not have any clobbered regunits live.
367///
368/// This function sets InsertionPoint and returns true when successful, it
369/// returns false if no valid insertion point could be found.
370///
371bool SSAIfConv::findInsertionPoint() {
372 // Keep track of live regunits before the current position.
373 // Only track RegUnits that are also in ClobberedRegUnits.
379 while (I != B) {
380 --I;
381 // Some of the conditional code depends in I.
382 if (InsertAfter.count(&*I)) {
383 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
384 return false;
385 }
386
387 // Update live regunits.
388 for (const MachineOperand &MO : I->operands()) {
389 // We're ignoring regmask operands. That is conservatively correct.
390 if (!MO.isReg())
391 continue;
392 Register Reg = MO.getReg();
393 if (!Reg.isPhysical())
394 continue;
395 // I clobbers Reg, so it isn't live before I.
396 if (MO.isDef())
397 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
398 ++Units)
399 LiveRegUnits.erase(*Units);
400 // Unless I reads Reg.
401 if (MO.readsReg())
402 Reads.push_back(Reg.asMCReg());
403 }
404 // Anything read by I is live before I.
405 while (!Reads.empty())
406 for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
407 ++Units)
408 if (ClobberedRegUnits.test(*Units))
409 LiveRegUnits.insert(*Units);
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 (unsigned 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(Register::isVirtualRegister(PI.TReg) && "Bad PHI");
529 assert(Register::isVirtualRegister(PI.FReg) && "Bad PHI");
530
531 // Get target information.
532 if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(),
533 PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles,
534 PI.FCycles)) {
535 LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
536 return false;
537 }
538 }
539
540 // Check that the conditional instructions can be speculated.
541 InsertAfter.clear();
542 ClobberedRegUnits.reset();
543 if (Predicate) {
544 if (TBB != Tail && !canPredicateInstrs(TBB))
545 return false;
546 if (FBB != Tail && !canPredicateInstrs(FBB))
547 return false;
548 } else {
549 if (TBB != Tail && !canSpeculateInstrs(TBB))
550 return false;
551 if (FBB != Tail && !canSpeculateInstrs(FBB))
552 return false;
553 }
554
555 // Try to find a valid insertion point for the speculated instructions in the
556 // head basic block.
557 if (!findInsertionPoint())
558 return false;
559
560 if (isTriangle())
561 ++NumTrianglesSeen;
562 else
563 ++NumDiamondsSeen;
564 return true;
565}
566
567/// \return true iff the two registers are known to have the same value.
569 const TargetInstrInfo *TII, Register TReg,
570 Register FReg) {
571 if (TReg == FReg)
572 return true;
573
574 if (!TReg.isVirtual() || !FReg.isVirtual())
575 return false;
576
577 const MachineInstr *TDef = MRI.getUniqueVRegDef(TReg);
578 const MachineInstr *FDef = MRI.getUniqueVRegDef(FReg);
579 if (!TDef || !FDef)
580 return false;
581
582 // If there are side-effects, all bets are off.
583 if (TDef->hasUnmodeledSideEffects())
584 return false;
585
586 // If the instruction could modify memory, or there may be some intervening
587 // store between the two, we can't consider them to be equal.
588 if (TDef->mayLoadOrStore() && !TDef->isDereferenceableInvariantLoad())
589 return false;
590
591 // We also can't guarantee that they are the same if, for example, the
592 // instructions are both a copy from a physical reg, because some other
593 // instruction may have modified the value in that reg between the two
594 // defining insts.
595 if (any_of(TDef->uses(), [](const MachineOperand &MO) {
596 return MO.isReg() && MO.getReg().isPhysical();
597 }))
598 return false;
599
600 // Check whether the two defining instructions produce the same value(s).
601 if (!TII->produceSameValue(*TDef, *FDef, &MRI))
602 return false;
603
604 // Further, check that the two defs come from corresponding operands.
605 int TIdx = TDef->findRegisterDefOperandIdx(TReg);
606 int FIdx = FDef->findRegisterDefOperandIdx(FReg);
607 if (TIdx == -1 || FIdx == -1)
608 return false;
609
610 return TIdx == FIdx;
611}
612
613/// replacePHIInstrs - Completely replace PHI instructions with selects.
614/// This is possible when the only Tail predecessors are the if-converted
615/// blocks.
616void SSAIfConv::replacePHIInstrs() {
617 assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
619 assert(FirstTerm != Head->end() && "No terminators");
620 DebugLoc HeadDL = FirstTerm->getDebugLoc();
621
622 // Convert all PHIs to select instructions inserted before FirstTerm.
623 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
624 PHIInfo &PI = PHIs[i];
625 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
626 Register DstReg = PI.PHI->getOperand(0).getReg();
627 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
628 // We do not need the select instruction if both incoming values are
629 // equal, but we do need a COPY.
630 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)
631 .addReg(PI.TReg);
632 } else {
633 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,
634 PI.FReg);
635 }
636 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
637 PI.PHI->eraseFromParent();
638 PI.PHI = nullptr;
639 }
640}
641
642/// rewritePHIOperands - When there are additional Tail predecessors, insert
643/// select instructions in Head and rewrite PHI operands to use the selects.
644/// Keep the PHI instructions in Tail to handle the other predecessors.
645void SSAIfConv::rewritePHIOperands() {
647 assert(FirstTerm != Head->end() && "No terminators");
648 DebugLoc HeadDL = FirstTerm->getDebugLoc();
649
650 // Convert all PHIs to select instructions inserted before FirstTerm.
651 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
652 PHIInfo &PI = PHIs[i];
653 unsigned DstReg = 0;
654
655 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
656 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
657 // We do not need the select instruction if both incoming values are
658 // equal.
659 DstReg = PI.TReg;
660 } else {
661 Register PHIDst = PI.PHI->getOperand(0).getReg();
662 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
663 TII->insertSelect(*Head, FirstTerm, HeadDL,
664 DstReg, Cond, PI.TReg, PI.FReg);
665 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
666 }
667
668 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
669 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
670 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
671 if (MBB == getTPred()) {
672 PI.PHI->getOperand(i-1).setMBB(Head);
673 PI.PHI->getOperand(i-2).setReg(DstReg);
674 } else if (MBB == getFPred()) {
675 PI.PHI->removeOperand(i-1);
676 PI.PHI->removeOperand(i-2);
677 }
678 }
679 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
680 }
681}
682
683/// convertIf - Execute the if conversion after canConvertIf has determined the
684/// feasibility.
685///
686/// Any basic blocks erased will be added to RemovedBlocks.
687///
688void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
689 bool Predicate) {
690 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
691
692 // Update statistics.
693 if (isTriangle())
694 ++NumTrianglesConv;
695 else
696 ++NumDiamondsConv;
697
698 // Move all instructions into Head, except for the terminators.
699 if (TBB != Tail) {
700 if (Predicate)
701 PredicateBlock(TBB, /*ReversePredicate=*/false);
702 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
703 }
704 if (FBB != Tail) {
705 if (Predicate)
706 PredicateBlock(FBB, /*ReversePredicate=*/true);
707 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
708 }
709 // Are there extra Tail predecessors?
710 bool ExtraPreds = Tail->pred_size() != 2;
711 if (ExtraPreds)
712 rewritePHIOperands();
713 else
714 replacePHIInstrs();
715
716 // Fix up the CFG, temporarily leave Head without any successors.
717 Head->removeSuccessor(TBB);
718 Head->removeSuccessor(FBB, true);
719 if (TBB != Tail)
720 TBB->removeSuccessor(Tail, true);
721 if (FBB != Tail)
722 FBB->removeSuccessor(Tail, true);
723
724 // Fix up Head's terminators.
725 // It should become a single branch or a fallthrough.
726 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
727 TII->removeBranch(*Head);
728
729 // Erase the now empty conditional blocks. It is likely that Head can fall
730 // through to Tail, and we can join the two blocks.
731 if (TBB != Tail) {
732 RemovedBlocks.push_back(TBB);
734 }
735 if (FBB != Tail) {
736 RemovedBlocks.push_back(FBB);
737 FBB->eraseFromParent();
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 RemovedBlocks.push_back(Tail);
749 Tail->eraseFromParent();
750 } else {
751 // We need a branch to Tail, let code placement work it out later.
752 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
754 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
755 Head->addSuccessor(Tail);
756 }
757 LLVM_DEBUG(dbgs() << *Head);
758}
759
760//===----------------------------------------------------------------------===//
761// EarlyIfConverter Pass
762//===----------------------------------------------------------------------===//
763
764namespace {
765class EarlyIfConverter : public MachineFunctionPass {
766 const TargetInstrInfo *TII = nullptr;
767 const TargetRegisterInfo *TRI = nullptr;
768 MCSchedModel SchedModel;
769 MachineRegisterInfo *MRI = nullptr;
770 MachineDominatorTree *DomTree = nullptr;
771 MachineLoopInfo *Loops = nullptr;
772 MachineTraceMetrics *Traces = nullptr;
773 MachineTraceMetrics::Ensemble *MinInstr = nullptr;
774 SSAIfConv IfConv;
775
776public:
777 static char ID;
778 EarlyIfConverter() : MachineFunctionPass(ID) {}
779 void getAnalysisUsage(AnalysisUsage &AU) const override;
780 bool runOnMachineFunction(MachineFunction &MF) override;
781 StringRef getPassName() const override { return "Early If-Conversion"; }
782
783private:
784 bool tryConvertIf(MachineBasicBlock*);
785 void invalidateTraces();
786 bool shouldConvertIf();
787};
788} // end anonymous namespace
789
790char EarlyIfConverter::ID = 0;
791char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
792
794 "Early If Converter", false, false)
799 "Early If Converter", false, false)
800
801void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
802 AU.addRequired<MachineBranchProbabilityInfo>();
803 AU.addRequired<MachineDominatorTree>();
804 AU.addPreserved<MachineDominatorTree>();
805 AU.addRequired<MachineLoopInfo>();
806 AU.addPreserved<MachineLoopInfo>();
807 AU.addRequired<MachineTraceMetrics>();
808 AU.addPreserved<MachineTraceMetrics>();
810}
811
812namespace {
813/// Update the dominator tree after if-conversion erased some blocks.
814void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
816 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
817 // TBB and FBB should not dominate any blocks.
818 // Tail children should be transferred to Head.
819 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
820 for (auto *B : Removed) {
821 MachineDomTreeNode *Node = DomTree->getNode(B);
822 assert(Node != HeadNode && "Cannot erase the head node");
823 while (Node->getNumChildren()) {
824 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
825 DomTree->changeImmediateDominator(Node->back(), HeadNode);
826 }
827 DomTree->eraseNode(B);
828 }
829}
830
831/// Update LoopInfo after if-conversion.
832void updateLoops(MachineLoopInfo *Loops,
834 if (!Loops)
835 return;
836 // If-conversion doesn't change loop structure, and it doesn't mess with back
837 // edges, so updating LoopInfo is simply removing the dead blocks.
838 for (auto *B : Removed)
839 Loops->removeBlock(B);
840}
841} // namespace
842
843/// Invalidate MachineTraceMetrics before if-conversion.
844void EarlyIfConverter::invalidateTraces() {
845 Traces->verifyAnalysis();
846 Traces->invalidate(IfConv.Head);
847 Traces->invalidate(IfConv.Tail);
848 Traces->invalidate(IfConv.TBB);
849 Traces->invalidate(IfConv.FBB);
850 Traces->verifyAnalysis();
851}
852
853// Adjust cycles with downward saturation.
854static unsigned adjCycles(unsigned Cyc, int Delta) {
855 if (Delta < 0 && Cyc + Delta > Cyc)
856 return 0;
857 return Cyc + Delta;
858}
859
860namespace {
861/// Helper class to simplify emission of cycle counts into optimization remarks.
862struct Cycles {
863 const char *Key;
864 unsigned Value;
865};
866template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
867 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
868}
869} // anonymous namespace
870
871/// Apply cost model and heuristics to the if-conversion in IfConv.
872/// Return true if the conversion is a good idea.
873///
874bool EarlyIfConverter::shouldConvertIf() {
875 // Stress testing mode disables all cost considerations.
876 if (Stress)
877 return true;
878
879 // Do not try to if-convert if the condition has a high chance of being
880 // predictable.
881 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);
882 // If the condition is in a loop, consider it predictable if the condition
883 // itself or all its operands are loop-invariant. E.g. this considers a load
884 // from a loop-invariant address predictable; we were unable to prove that it
885 // doesn't alias any of the memory-writes in the loop, but it is likely to
886 // read to same value multiple times.
887 if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {
888 if (!MO.isReg() || !MO.isUse())
889 return false;
890 Register Reg = MO.getReg();
891 if (Register::isPhysicalRegister(Reg))
892 return false;
893
894 MachineInstr *Def = MRI->getVRegDef(Reg);
895 return CurrentLoop->isLoopInvariant(*Def) ||
896 all_of(Def->operands(), [&](MachineOperand &Op) {
897 if (Op.isImm())
898 return true;
899 if (!MO.isReg() || !MO.isUse())
900 return false;
901 Register Reg = MO.getReg();
902 if (Register::isPhysicalRegister(Reg))
903 return false;
904
905 MachineInstr *Def = MRI->getVRegDef(Reg);
906 return CurrentLoop->isLoopInvariant(*Def);
907 });
908 }))
909 return false;
910
911 if (!MinInstr)
912 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
913
914 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
915 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
916 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
917 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
918 FBBTrace.getCriticalPath());
919
920 // Set a somewhat arbitrary limit on the critical path extension we accept.
921 unsigned CritLimit = SchedModel.MispredictPenalty/2;
922
923 MachineBasicBlock &MBB = *IfConv.Head;
925
926 // If-conversion only makes sense when there is unexploited ILP. Compute the
927 // maximum-ILP resource length of the trace after if-conversion. Compare it
928 // to the shortest critical path.
930 if (IfConv.TBB != IfConv.Tail)
931 ExtraBlocks.push_back(IfConv.TBB);
932 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
933 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
934 << ", minimal critical path " << MinCrit << '\n');
935 if (ResLength > MinCrit + CritLimit) {
936 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
937 MORE.emit([&]() {
940 R << "did not if-convert branch: the resulting critical path ("
941 << Cycles{"ResLength", ResLength}
942 << ") would extend the shorter leg's critical path ("
943 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "
944 << Cycles{"CritLimit", CritLimit}
945 << ", which cannot be hidden by available ILP.";
946 return R;
947 });
948 return false;
949 }
950
951 // Assume that the depth of the first head terminator will also be the depth
952 // of the select instruction inserted, as determined by the flag dependency.
953 // TBB / FBB data dependencies may delay the select even more.
954 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
955 unsigned BranchDepth =
956 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
957 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
958
959 // Look at all the tail phis, and compute the critical path extension caused
960 // by inserting select instructions.
961 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
962 struct CriticalPathInfo {
963 unsigned Extra; // Count of extra cycles that the component adds.
964 unsigned Depth; // Absolute depth of the component in cycles.
965 };
966 CriticalPathInfo Cond{};
967 CriticalPathInfo TBlock{};
968 CriticalPathInfo FBlock{};
969 bool ShouldConvert = true;
970 for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
971 SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
972 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
973 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
974 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
975
976 // The condition is pulled into the critical path.
977 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
978 if (CondDepth > MaxDepth) {
979 unsigned Extra = CondDepth - MaxDepth;
980 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
981 if (Extra > Cond.Extra)
982 Cond = {Extra, CondDepth};
983 if (Extra > CritLimit) {
984 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
985 ShouldConvert = false;
986 }
987 }
988
989 // The TBB value is pulled into the critical path.
990 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
991 if (TDepth > MaxDepth) {
992 unsigned Extra = TDepth - MaxDepth;
993 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
994 if (Extra > TBlock.Extra)
995 TBlock = {Extra, TDepth};
996 if (Extra > CritLimit) {
997 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
998 ShouldConvert = false;
999 }
1000 }
1001
1002 // The FBB value is pulled into the critical path.
1003 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
1004 if (FDepth > MaxDepth) {
1005 unsigned Extra = FDepth - MaxDepth;
1006 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
1007 if (Extra > FBlock.Extra)
1008 FBlock = {Extra, FDepth};
1009 if (Extra > CritLimit) {
1010 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1011 ShouldConvert = false;
1012 }
1013 }
1014 }
1015
1016 // Organize by "short" and "long" legs, since the diagnostics get confusing
1017 // when referring to the "true" and "false" sides of the branch, given that
1018 // those don't always correlate with what the user wrote in source-terms.
1019 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1020 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1021
1022 if (ShouldConvert) {
1023 MORE.emit([&]() {
1024 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
1025 MBB.back().getDebugLoc(), &MBB);
1026 R << "performing if-conversion on branch: the condition adds "
1027 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1028 if (Short.Extra > 0)
1029 R << ", and the short leg adds another "
1030 << Cycles{"ShortCycles", Short.Extra};
1031 if (Long.Extra > 0)
1032 R << ", and the long leg adds another "
1033 << Cycles{"LongCycles", Long.Extra};
1034 R << ", each staying under the threshold of "
1035 << Cycles{"CritLimit", CritLimit} << ".";
1036 return R;
1037 });
1038 } else {
1039 MORE.emit([&]() {
1041 MBB.back().getDebugLoc(), &MBB);
1042 R << "did not if-convert branch: the condition would add "
1043 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1044 if (Cond.Extra > CritLimit)
1045 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1046 if (Short.Extra > 0) {
1047 R << ", and the short leg would add another "
1048 << Cycles{"ShortCycles", Short.Extra};
1049 if (Short.Extra > CritLimit)
1050 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1051 }
1052 if (Long.Extra > 0) {
1053 R << ", and the long leg would add another "
1054 << Cycles{"LongCycles", Long.Extra};
1055 if (Long.Extra > CritLimit)
1056 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1057 }
1058 R << ".";
1059 return R;
1060 });
1061 }
1062
1063 return ShouldConvert;
1064}
1065
1066/// Attempt repeated if-conversion on MBB, return true if successful.
1067///
1068bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1069 bool Changed = false;
1070 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1071 // If-convert MBB and update analyses.
1072 invalidateTraces();
1074 IfConv.convertIf(RemovedBlocks);
1075 Changed = true;
1076 updateDomTree(DomTree, IfConv, RemovedBlocks);
1077 updateLoops(Loops, RemovedBlocks);
1078 }
1079 return Changed;
1080}
1081
1082bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
1083 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1084 << "********** Function: " << MF.getName() << '\n');
1085 if (skipFunction(MF.getFunction()))
1086 return false;
1087
1088 // Only run if conversion if the target wants it.
1089 const TargetSubtargetInfo &STI = MF.getSubtarget();
1090 if (!STI.enableEarlyIfConversion())
1091 return false;
1092
1093 TII = STI.getInstrInfo();
1094 TRI = STI.getRegisterInfo();
1095 SchedModel = STI.getSchedModel();
1096 MRI = &MF.getRegInfo();
1097 DomTree = &getAnalysis<MachineDominatorTree>();
1098 Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1099 Traces = &getAnalysis<MachineTraceMetrics>();
1100 MinInstr = nullptr;
1101
1102 bool Changed = false;
1103 IfConv.runOnMachineFunction(MF);
1104
1105 // Visit blocks in dominator tree post-order. The post-order enables nested
1106 // if-conversion in a single pass. The tryConvertIf() function may erase
1107 // blocks, but only blocks dominated by the head block. This makes it safe to
1108 // update the dominator tree while the post-order iterator is still active.
1109 for (auto *DomNode : post_order(DomTree))
1110 if (tryConvertIf(DomNode->getBlock()))
1111 Changed = true;
1112
1113 return Changed;
1114}
1115
1116//===----------------------------------------------------------------------===//
1117// EarlyIfPredicator Pass
1118//===----------------------------------------------------------------------===//
1119
1120namespace {
1121class EarlyIfPredicator : public MachineFunctionPass {
1122 const TargetInstrInfo *TII = nullptr;
1123 const TargetRegisterInfo *TRI = nullptr;
1124 TargetSchedModel SchedModel;
1125 MachineRegisterInfo *MRI = nullptr;
1126 MachineDominatorTree *DomTree = nullptr;
1127 MachineBranchProbabilityInfo *MBPI = nullptr;
1128 MachineLoopInfo *Loops = nullptr;
1129 SSAIfConv IfConv;
1130
1131public:
1132 static char ID;
1133 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1134 void getAnalysisUsage(AnalysisUsage &AU) const override;
1135 bool runOnMachineFunction(MachineFunction &MF) override;
1136 StringRef getPassName() const override { return "Early If-predicator"; }
1137
1138protected:
1139 bool tryConvertIf(MachineBasicBlock *);
1140 bool shouldConvertIf();
1141};
1142} // end anonymous namespace
1143
1144#undef DEBUG_TYPE
1145#define DEBUG_TYPE "early-if-predicator"
1146
1147char EarlyIfPredicator::ID = 0;
1148char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1149
1150INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1151 false, false)
1154INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1155 false)
1156
1157void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1158 AU.addRequired<MachineBranchProbabilityInfo>();
1159 AU.addRequired<MachineDominatorTree>();
1160 AU.addPreserved<MachineDominatorTree>();
1161 AU.addRequired<MachineLoopInfo>();
1162 AU.addPreserved<MachineLoopInfo>();
1164}
1165
1166/// Apply the target heuristic to decide if the transformation is profitable.
1167bool EarlyIfPredicator::shouldConvertIf() {
1168 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
1169 if (IfConv.isTriangle()) {
1170 MachineBasicBlock &IfBlock =
1171 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1172
1173 unsigned ExtraPredCost = 0;
1174 unsigned Cycles = 0;
1175 for (MachineInstr &I : IfBlock) {
1176 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1177 if (NumCycles > 1)
1178 Cycles += NumCycles - 1;
1179 ExtraPredCost += TII->getPredicationCost(I);
1180 }
1181
1182 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1183 TrueProbability);
1184 }
1185 unsigned TExtra = 0;
1186 unsigned FExtra = 0;
1187 unsigned TCycle = 0;
1188 unsigned FCycle = 0;
1189 for (MachineInstr &I : *IfConv.TBB) {
1190 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1191 if (NumCycles > 1)
1192 TCycle += NumCycles - 1;
1193 TExtra += TII->getPredicationCost(I);
1194 }
1195 for (MachineInstr &I : *IfConv.FBB) {
1196 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1197 if (NumCycles > 1)
1198 FCycle += NumCycles - 1;
1199 FExtra += TII->getPredicationCost(I);
1200 }
1201 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1202 FCycle, FExtra, TrueProbability);
1203}
1204
1205/// Attempt repeated if-conversion on MBB, return true if successful.
1206///
1207bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1208 bool Changed = false;
1209 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1210 // If-convert MBB and update analyses.
1212 IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1213 Changed = true;
1214 updateDomTree(DomTree, IfConv, RemovedBlocks);
1215 updateLoops(Loops, RemovedBlocks);
1216 }
1217 return Changed;
1218}
1219
1220bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1221 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1222 << "********** Function: " << MF.getName() << '\n');
1223 if (skipFunction(MF.getFunction()))
1224 return false;
1225
1226 const TargetSubtargetInfo &STI = MF.getSubtarget();
1227 TII = STI.getInstrInfo();
1228 TRI = STI.getRegisterInfo();
1229 MRI = &MF.getRegInfo();
1230 SchedModel.init(&STI);
1231 DomTree = &getAnalysis<MachineDominatorTree>();
1232 Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1233 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
1234
1235 bool Changed = false;
1236 IfConv.runOnMachineFunction(MF);
1237
1238 // Visit blocks in dominator tree post-order. The post-order enables nested
1239 // if-conversion in a single pass. The tryConvertIf() function may erase
1240 // blocks, but only blocks dominated by the head block. This makes it safe to
1241 // update the dominator tree while the post-order iterator is still active.
1242 for (auto *DomNode : post_order(DomTree))
1243 if (tryConvertIf(DomNode->getBlock()))
1244 Changed = true;
1245
1246 return Changed;
1247}
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 debug 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:928
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:320
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:696
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:452
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:249
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...