LLVM 19.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 (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
267 ClobberedRegUnits.set(Unit);
268
269 if (!MO.readsReg() || !Reg.isVirtual())
270 continue;
271 MachineInstr *DefMI = MRI->getVRegDef(Reg);
272 if (!DefMI || DefMI->getParent() != Head)
273 continue;
274 if (InsertAfter.insert(DefMI).second)
275 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
276 << *DefMI);
277 if (DefMI->isTerminator()) {
278 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
279 return false;
280 }
281 }
282 return true;
283}
284
285/// canPredicateInstrs - Returns true if all the instructions in MBB can safely
286/// be predicates. The terminators are not considered.
287///
288/// If instructions use any values that are defined in the head basic block,
289/// the defining instructions are added to InsertAfter.
290///
291/// Any clobbered regunits are added to ClobberedRegUnits.
292///
293bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
294 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
295 // get right.
296 if (!MBB->livein_empty()) {
297 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
298 return false;
299 }
300
301 unsigned InstrCount = 0;
302
303 // Check all instructions, except the terminators. It is assumed that
304 // terminators never have side effects or define any used register values.
306 E = MBB->getFirstTerminator();
307 I != E; ++I) {
308 if (I->isDebugInstr())
309 continue;
310
311 if (++InstrCount > BlockInstrLimit && !Stress) {
312 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
313 << BlockInstrLimit << " instructions.\n");
314 return false;
315 }
316
317 // There shouldn't normally be any phis in a single-predecessor block.
318 if (I->isPHI()) {
319 LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
320 return false;
321 }
322
323 // Check that instruction is predicable
324 if (!TII->isPredicable(*I)) {
325 LLVM_DEBUG(dbgs() << "Isn't predicable: " << *I);
326 return false;
327 }
328
329 // Check that instruction is not already predicated.
330 if (TII->isPredicated(*I) && !TII->canPredicatePredicatedInstr(*I)) {
331 LLVM_DEBUG(dbgs() << "Is already predicated: " << *I);
332 return false;
333 }
334
335 // Check for any dependencies on Head instructions.
336 if (!InstrDependenciesAllowIfConv(&(*I)))
337 return false;
338 }
339 return true;
340}
341
342// Apply predicate to all instructions in the machine block.
343void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
344 auto Condition = Cond;
345 if (ReversePredicate) {
346 bool CanRevCond = !TII->reverseBranchCondition(Condition);
347 assert(CanRevCond && "Reversed predicate is not supported");
348 (void)CanRevCond;
349 }
350 // Terminators don't need to be predicated as they will be removed.
352 E = MBB->getFirstTerminator();
353 I != E; ++I) {
354 if (I->isDebugInstr())
355 continue;
356 TII->PredicateInstruction(*I, Condition);
357 }
358}
359
360/// Find an insertion point in Head for the speculated instructions. The
361/// insertion point must be:
362///
363/// 1. Before any terminators.
364/// 2. After any instructions in InsertAfter.
365/// 3. Not have any clobbered regunits live.
366///
367/// This function sets InsertionPoint and returns true when successful, it
368/// returns false if no valid insertion point could be found.
369///
370bool SSAIfConv::findInsertionPoint() {
371 // Keep track of live regunits before the current position.
372 // Only track RegUnits that are also in ClobberedRegUnits.
378 while (I != B) {
379 --I;
380 // Some of the conditional code depends in I.
381 if (InsertAfter.count(&*I)) {
382 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
383 return false;
384 }
385
386 // Update live regunits.
387 for (const MachineOperand &MO : I->operands()) {
388 // We're ignoring regmask operands. That is conservatively correct.
389 if (!MO.isReg())
390 continue;
391 Register Reg = MO.getReg();
392 if (!Reg.isPhysical())
393 continue;
394 // I clobbers Reg, so it isn't live before I.
395 if (MO.isDef())
396 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
397 LiveRegUnits.erase(Unit);
398 // Unless I reads Reg.
399 if (MO.readsReg())
400 Reads.push_back(Reg.asMCReg());
401 }
402 // Anything read by I is live before I.
403 while (!Reads.empty())
404 for (MCRegUnit Unit : TRI->regunits(Reads.pop_back_val()))
405 if (ClobberedRegUnits.test(Unit))
406 LiveRegUnits.insert(Unit);
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, /*TRI=*/nullptr);
603 int FIdx = FDef->findRegisterDefOperandIdx(FReg, /*TRI=*/nullptr);
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 (PHIInfo &PI : PHIs) {
621 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
622 Register DstReg = PI.PHI->getOperand(0).getReg();
623 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
624 // We do not need the select instruction if both incoming values are
625 // equal, but we do need a COPY.
626 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)
627 .addReg(PI.TReg);
628 } else {
629 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,
630 PI.FReg);
631 }
632 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
633 PI.PHI->eraseFromParent();
634 PI.PHI = nullptr;
635 }
636}
637
638/// rewritePHIOperands - When there are additional Tail predecessors, insert
639/// select instructions in Head and rewrite PHI operands to use the selects.
640/// Keep the PHI instructions in Tail to handle the other predecessors.
641void SSAIfConv::rewritePHIOperands() {
643 assert(FirstTerm != Head->end() && "No terminators");
644 DebugLoc HeadDL = FirstTerm->getDebugLoc();
645
646 // Convert all PHIs to select instructions inserted before FirstTerm.
647 for (PHIInfo &PI : PHIs) {
648 unsigned DstReg = 0;
649
650 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
651 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
652 // We do not need the select instruction if both incoming values are
653 // equal.
654 DstReg = PI.TReg;
655 } else {
656 Register PHIDst = PI.PHI->getOperand(0).getReg();
657 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
658 TII->insertSelect(*Head, FirstTerm, HeadDL,
659 DstReg, Cond, PI.TReg, PI.FReg);
660 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
661 }
662
663 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
664 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
665 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
666 if (MBB == getTPred()) {
667 PI.PHI->getOperand(i-1).setMBB(Head);
668 PI.PHI->getOperand(i-2).setReg(DstReg);
669 } else if (MBB == getFPred()) {
670 PI.PHI->removeOperand(i-1);
671 PI.PHI->removeOperand(i-2);
672 }
673 }
674 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
675 }
676}
677
678/// convertIf - Execute the if conversion after canConvertIf has determined the
679/// feasibility.
680///
681/// Any basic blocks erased will be added to RemovedBlocks.
682///
683void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
684 bool Predicate) {
685 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
686
687 // Update statistics.
688 if (isTriangle())
689 ++NumTrianglesConv;
690 else
691 ++NumDiamondsConv;
692
693 // Move all instructions into Head, except for the terminators.
694 if (TBB != Tail) {
695 if (Predicate)
696 PredicateBlock(TBB, /*ReversePredicate=*/false);
697 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
698 }
699 if (FBB != Tail) {
700 if (Predicate)
701 PredicateBlock(FBB, /*ReversePredicate=*/true);
702 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
703 }
704 // Are there extra Tail predecessors?
705 bool ExtraPreds = Tail->pred_size() != 2;
706 if (ExtraPreds)
707 rewritePHIOperands();
708 else
709 replacePHIInstrs();
710
711 // Fix up the CFG, temporarily leave Head without any successors.
712 Head->removeSuccessor(TBB);
713 Head->removeSuccessor(FBB, true);
714 if (TBB != Tail)
715 TBB->removeSuccessor(Tail, true);
716 if (FBB != Tail)
717 FBB->removeSuccessor(Tail, true);
718
719 // Fix up Head's terminators.
720 // It should become a single branch or a fallthrough.
721 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
722 TII->removeBranch(*Head);
723
724 // Erase the now empty conditional blocks. It is likely that Head can fall
725 // through to Tail, and we can join the two blocks.
726 if (TBB != Tail) {
727 RemovedBlocks.push_back(TBB);
729 }
730 if (FBB != Tail) {
731 RemovedBlocks.push_back(FBB);
732 FBB->eraseFromParent();
733 }
734
735 assert(Head->succ_empty() && "Additional head successors?");
736 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
737 // Splice Tail onto the end of Head.
738 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
739 << " into head " << printMBBReference(*Head) << '\n');
740 Head->splice(Head->end(), Tail,
741 Tail->begin(), Tail->end());
743 RemovedBlocks.push_back(Tail);
744 Tail->eraseFromParent();
745 } else {
746 // We need a branch to Tail, let code placement work it out later.
747 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
749 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
750 Head->addSuccessor(Tail);
751 }
752 LLVM_DEBUG(dbgs() << *Head);
753}
754
755//===----------------------------------------------------------------------===//
756// EarlyIfConverter Pass
757//===----------------------------------------------------------------------===//
758
759namespace {
760class EarlyIfConverter : public MachineFunctionPass {
761 const TargetInstrInfo *TII = nullptr;
762 const TargetRegisterInfo *TRI = nullptr;
763 MCSchedModel SchedModel;
764 MachineRegisterInfo *MRI = nullptr;
765 MachineDominatorTree *DomTree = nullptr;
766 MachineLoopInfo *Loops = nullptr;
767 MachineTraceMetrics *Traces = nullptr;
768 MachineTraceMetrics::Ensemble *MinInstr = nullptr;
769 SSAIfConv IfConv;
770
771public:
772 static char ID;
773 EarlyIfConverter() : MachineFunctionPass(ID) {}
774 void getAnalysisUsage(AnalysisUsage &AU) const override;
775 bool runOnMachineFunction(MachineFunction &MF) override;
776 StringRef getPassName() const override { return "Early If-Conversion"; }
777
778private:
779 bool tryConvertIf(MachineBasicBlock*);
780 void invalidateTraces();
781 bool shouldConvertIf();
782};
783} // end anonymous namespace
784
785char EarlyIfConverter::ID = 0;
786char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
787
789 "Early If Converter", false, false)
794 "Early If Converter", false, false)
795
796void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
798 AU.addRequired<MachineDominatorTreeWrapperPass>();
799 AU.addPreserved<MachineDominatorTreeWrapperPass>();
800 AU.addRequired<MachineLoopInfoWrapperPass>();
801 AU.addPreserved<MachineLoopInfoWrapperPass>();
802 AU.addRequired<MachineTraceMetrics>();
803 AU.addPreserved<MachineTraceMetrics>();
805}
806
807namespace {
808/// Update the dominator tree after if-conversion erased some blocks.
809void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
811 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
812 // TBB and FBB should not dominate any blocks.
813 // Tail children should be transferred to Head.
814 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
815 for (auto *B : Removed) {
816 MachineDomTreeNode *Node = DomTree->getNode(B);
817 assert(Node != HeadNode && "Cannot erase the head node");
818 while (Node->getNumChildren()) {
819 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
820 DomTree->changeImmediateDominator(Node->back(), HeadNode);
821 }
822 DomTree->eraseNode(B);
823 }
824}
825
826/// Update LoopInfo after if-conversion.
827void updateLoops(MachineLoopInfo *Loops,
829 // If-conversion doesn't change loop structure, and it doesn't mess with back
830 // edges, so updating LoopInfo is simply removing the dead blocks.
831 for (auto *B : Removed)
832 Loops->removeBlock(B);
833}
834} // namespace
835
836/// Invalidate MachineTraceMetrics before if-conversion.
837void EarlyIfConverter::invalidateTraces() {
838 Traces->verifyAnalysis();
839 Traces->invalidate(IfConv.Head);
840 Traces->invalidate(IfConv.Tail);
841 Traces->invalidate(IfConv.TBB);
842 Traces->invalidate(IfConv.FBB);
843 Traces->verifyAnalysis();
844}
845
846// Adjust cycles with downward saturation.
847static unsigned adjCycles(unsigned Cyc, int Delta) {
848 if (Delta < 0 && Cyc + Delta > Cyc)
849 return 0;
850 return Cyc + Delta;
851}
852
853namespace {
854/// Helper class to simplify emission of cycle counts into optimization remarks.
855struct Cycles {
856 const char *Key;
857 unsigned Value;
858};
859template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
860 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
861}
862} // anonymous namespace
863
864/// Apply cost model and heuristics to the if-conversion in IfConv.
865/// Return true if the conversion is a good idea.
866///
867bool EarlyIfConverter::shouldConvertIf() {
868 // Stress testing mode disables all cost considerations.
869 if (Stress)
870 return true;
871
872 // Do not try to if-convert if the condition has a high chance of being
873 // predictable.
874 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);
875 // If the condition is in a loop, consider it predictable if the condition
876 // itself or all its operands are loop-invariant. E.g. this considers a load
877 // from a loop-invariant address predictable; we were unable to prove that it
878 // doesn't alias any of the memory-writes in the loop, but it is likely to
879 // read to same value multiple times.
880 if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {
881 if (!MO.isReg() || !MO.isUse())
882 return false;
883 Register Reg = MO.getReg();
884 if (Register::isPhysicalRegister(Reg))
885 return false;
886
887 MachineInstr *Def = MRI->getVRegDef(Reg);
888 return CurrentLoop->isLoopInvariant(*Def) ||
889 all_of(Def->operands(), [&](MachineOperand &Op) {
890 if (Op.isImm())
891 return true;
892 if (!MO.isReg() || !MO.isUse())
893 return false;
894 Register Reg = MO.getReg();
895 if (Register::isPhysicalRegister(Reg))
896 return false;
897
898 MachineInstr *Def = MRI->getVRegDef(Reg);
899 return CurrentLoop->isLoopInvariant(*Def);
900 });
901 }))
902 return false;
903
904 if (!MinInstr)
905 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
906
907 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
908 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
909 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
910 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
911 FBBTrace.getCriticalPath());
912
913 // Set a somewhat arbitrary limit on the critical path extension we accept.
914 unsigned CritLimit = SchedModel.MispredictPenalty/2;
915
916 MachineBasicBlock &MBB = *IfConv.Head;
918
919 // If-conversion only makes sense when there is unexploited ILP. Compute the
920 // maximum-ILP resource length of the trace after if-conversion. Compare it
921 // to the shortest critical path.
923 if (IfConv.TBB != IfConv.Tail)
924 ExtraBlocks.push_back(IfConv.TBB);
925 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
926 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
927 << ", minimal critical path " << MinCrit << '\n');
928 if (ResLength > MinCrit + CritLimit) {
929 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
930 MORE.emit([&]() {
933 R << "did not if-convert branch: the resulting critical path ("
934 << Cycles{"ResLength", ResLength}
935 << ") would extend the shorter leg's critical path ("
936 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "
937 << Cycles{"CritLimit", CritLimit}
938 << ", which cannot be hidden by available ILP.";
939 return R;
940 });
941 return false;
942 }
943
944 // Assume that the depth of the first head terminator will also be the depth
945 // of the select instruction inserted, as determined by the flag dependency.
946 // TBB / FBB data dependencies may delay the select even more.
947 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
948 unsigned BranchDepth =
949 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
950 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
951
952 // Look at all the tail phis, and compute the critical path extension caused
953 // by inserting select instructions.
954 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
955 struct CriticalPathInfo {
956 unsigned Extra; // Count of extra cycles that the component adds.
957 unsigned Depth; // Absolute depth of the component in cycles.
958 };
959 CriticalPathInfo Cond{};
960 CriticalPathInfo TBlock{};
961 CriticalPathInfo FBlock{};
962 bool ShouldConvert = true;
963 for (SSAIfConv::PHIInfo &PI : IfConv.PHIs) {
964 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
965 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
966 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
967
968 // The condition is pulled into the critical path.
969 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
970 if (CondDepth > MaxDepth) {
971 unsigned Extra = CondDepth - MaxDepth;
972 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
973 if (Extra > Cond.Extra)
974 Cond = {Extra, CondDepth};
975 if (Extra > CritLimit) {
976 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
977 ShouldConvert = false;
978 }
979 }
980
981 // The TBB value is pulled into the critical path.
982 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
983 if (TDepth > MaxDepth) {
984 unsigned Extra = TDepth - MaxDepth;
985 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
986 if (Extra > TBlock.Extra)
987 TBlock = {Extra, TDepth};
988 if (Extra > CritLimit) {
989 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
990 ShouldConvert = false;
991 }
992 }
993
994 // The FBB value is pulled into the critical path.
995 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
996 if (FDepth > MaxDepth) {
997 unsigned Extra = FDepth - MaxDepth;
998 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
999 if (Extra > FBlock.Extra)
1000 FBlock = {Extra, FDepth};
1001 if (Extra > CritLimit) {
1002 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1003 ShouldConvert = false;
1004 }
1005 }
1006 }
1007
1008 // Organize by "short" and "long" legs, since the diagnostics get confusing
1009 // when referring to the "true" and "false" sides of the branch, given that
1010 // those don't always correlate with what the user wrote in source-terms.
1011 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1012 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1013
1014 if (ShouldConvert) {
1015 MORE.emit([&]() {
1016 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
1017 MBB.back().getDebugLoc(), &MBB);
1018 R << "performing if-conversion on branch: the condition adds "
1019 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1020 if (Short.Extra > 0)
1021 R << ", and the short leg adds another "
1022 << Cycles{"ShortCycles", Short.Extra};
1023 if (Long.Extra > 0)
1024 R << ", and the long leg adds another "
1025 << Cycles{"LongCycles", Long.Extra};
1026 R << ", each staying under the threshold of "
1027 << Cycles{"CritLimit", CritLimit} << ".";
1028 return R;
1029 });
1030 } else {
1031 MORE.emit([&]() {
1033 MBB.back().getDebugLoc(), &MBB);
1034 R << "did not if-convert branch: the condition would add "
1035 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1036 if (Cond.Extra > CritLimit)
1037 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1038 if (Short.Extra > 0) {
1039 R << ", and the short leg would add another "
1040 << Cycles{"ShortCycles", Short.Extra};
1041 if (Short.Extra > CritLimit)
1042 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1043 }
1044 if (Long.Extra > 0) {
1045 R << ", and the long leg would add another "
1046 << Cycles{"LongCycles", Long.Extra};
1047 if (Long.Extra > CritLimit)
1048 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1049 }
1050 R << ".";
1051 return R;
1052 });
1053 }
1054
1055 return ShouldConvert;
1056}
1057
1058/// Attempt repeated if-conversion on MBB, return true if successful.
1059///
1060bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1061 bool Changed = false;
1062 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1063 // If-convert MBB and update analyses.
1064 invalidateTraces();
1066 IfConv.convertIf(RemovedBlocks);
1067 Changed = true;
1068 updateDomTree(DomTree, IfConv, RemovedBlocks);
1069 updateLoops(Loops, RemovedBlocks);
1070 }
1071 return Changed;
1072}
1073
1074bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
1075 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1076 << "********** Function: " << MF.getName() << '\n');
1077 if (skipFunction(MF.getFunction()))
1078 return false;
1079
1080 // Only run if conversion if the target wants it.
1081 const TargetSubtargetInfo &STI = MF.getSubtarget();
1082 if (!STI.enableEarlyIfConversion())
1083 return false;
1084
1085 TII = STI.getInstrInfo();
1086 TRI = STI.getRegisterInfo();
1087 SchedModel = STI.getSchedModel();
1088 MRI = &MF.getRegInfo();
1089 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1090 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1091 Traces = &getAnalysis<MachineTraceMetrics>();
1092 MinInstr = nullptr;
1093
1094 bool Changed = false;
1095 IfConv.runOnMachineFunction(MF);
1096
1097 // Visit blocks in dominator tree post-order. The post-order enables nested
1098 // if-conversion in a single pass. The tryConvertIf() function may erase
1099 // blocks, but only blocks dominated by the head block. This makes it safe to
1100 // update the dominator tree while the post-order iterator is still active.
1101 for (auto *DomNode : post_order(DomTree))
1102 if (tryConvertIf(DomNode->getBlock()))
1103 Changed = true;
1104
1105 return Changed;
1106}
1107
1108//===----------------------------------------------------------------------===//
1109// EarlyIfPredicator Pass
1110//===----------------------------------------------------------------------===//
1111
1112namespace {
1113class EarlyIfPredicator : public MachineFunctionPass {
1114 const TargetInstrInfo *TII = nullptr;
1115 const TargetRegisterInfo *TRI = nullptr;
1116 TargetSchedModel SchedModel;
1117 MachineRegisterInfo *MRI = nullptr;
1118 MachineDominatorTree *DomTree = nullptr;
1119 MachineBranchProbabilityInfo *MBPI = nullptr;
1120 MachineLoopInfo *Loops = nullptr;
1121 SSAIfConv IfConv;
1122
1123public:
1124 static char ID;
1125 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1126 void getAnalysisUsage(AnalysisUsage &AU) const override;
1127 bool runOnMachineFunction(MachineFunction &MF) override;
1128 StringRef getPassName() const override { return "Early If-predicator"; }
1129
1130protected:
1131 bool tryConvertIf(MachineBasicBlock *);
1132 bool shouldConvertIf();
1133};
1134} // end anonymous namespace
1135
1136#undef DEBUG_TYPE
1137#define DEBUG_TYPE "early-if-predicator"
1138
1139char EarlyIfPredicator::ID = 0;
1140char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1141
1142INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1143 false, false)
1146INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1147 false)
1148
1149void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1151 AU.addRequired<MachineDominatorTreeWrapperPass>();
1152 AU.addPreserved<MachineDominatorTreeWrapperPass>();
1153 AU.addRequired<MachineLoopInfoWrapperPass>();
1154 AU.addPreserved<MachineLoopInfoWrapperPass>();
1156}
1157
1158/// Apply the target heuristic to decide if the transformation is profitable.
1159bool EarlyIfPredicator::shouldConvertIf() {
1160 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
1161 if (IfConv.isTriangle()) {
1162 MachineBasicBlock &IfBlock =
1163 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1164
1165 unsigned ExtraPredCost = 0;
1166 unsigned Cycles = 0;
1167 for (MachineInstr &I : IfBlock) {
1168 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1169 if (NumCycles > 1)
1170 Cycles += NumCycles - 1;
1171 ExtraPredCost += TII->getPredicationCost(I);
1172 }
1173
1174 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1175 TrueProbability);
1176 }
1177 unsigned TExtra = 0;
1178 unsigned FExtra = 0;
1179 unsigned TCycle = 0;
1180 unsigned FCycle = 0;
1181 for (MachineInstr &I : *IfConv.TBB) {
1182 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1183 if (NumCycles > 1)
1184 TCycle += NumCycles - 1;
1185 TExtra += TII->getPredicationCost(I);
1186 }
1187 for (MachineInstr &I : *IfConv.FBB) {
1188 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1189 if (NumCycles > 1)
1190 FCycle += NumCycles - 1;
1191 FExtra += TII->getPredicationCost(I);
1192 }
1193 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1194 FCycle, FExtra, TrueProbability);
1195}
1196
1197/// Attempt repeated if-conversion on MBB, return true if successful.
1198///
1199bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1200 bool Changed = false;
1201 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1202 // If-convert MBB and update analyses.
1204 IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1205 Changed = true;
1206 updateDomTree(DomTree, IfConv, RemovedBlocks);
1207 updateLoops(Loops, RemovedBlocks);
1208 }
1209 return Changed;
1210}
1211
1212bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1213 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1214 << "********** Function: " << MF.getName() << '\n');
1215 if (skipFunction(MF.getFunction()))
1216 return false;
1217
1218 const TargetSubtargetInfo &STI = MF.getSubtarget();
1219 TII = STI.getInstrInfo();
1220 TRI = STI.getRegisterInfo();
1221 MRI = &MF.getRegInfo();
1222 SchedModel.init(&STI);
1223 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1224 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1225 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1226
1227 bool Changed = false;
1228 IfConv.runOnMachineFunction(MF);
1229
1230 // Visit blocks in dominator tree post-order. The post-order enables nested
1231 // if-conversion in a single pass. The tryConvertIf() function may erase
1232 // blocks, but only blocks dominated by the head block. This makes it safe to
1233 // update the dominator tree while the post-order iterator is still active.
1234 for (auto *DomNode : post_order(DomTree))
1235 if (tryConvertIf(DomNode->getBlock()))
1236 Changed = true;
1237
1238 return Changed;
1239}
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder MachineInstrBuilder & DefMI
Rewrite undef for PHI
MachineBasicBlock & MBB
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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
const SmallVectorImpl< MachineOperand > & Cond
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
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 '...
Analysis pass which computes a MachineDominatorTree.
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:69
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:974
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:346
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:733
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:498
int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
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
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:412
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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.
@ 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
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
constexpr double phi
Definition: MathExtras.h:61
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:1729
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:293
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:253
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...