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 (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
621 PHIInfo &PI = PHIs[i];
622 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
623 Register DstReg = PI.PHI->getOperand(0).getReg();
624 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
625 // We do not need the select instruction if both incoming values are
626 // equal, but we do need a COPY.
627 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)
628 .addReg(PI.TReg);
629 } else {
630 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,
631 PI.FReg);
632 }
633 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
634 PI.PHI->eraseFromParent();
635 PI.PHI = nullptr;
636 }
637}
638
639/// rewritePHIOperands - When there are additional Tail predecessors, insert
640/// select instructions in Head and rewrite PHI operands to use the selects.
641/// Keep the PHI instructions in Tail to handle the other predecessors.
642void SSAIfConv::rewritePHIOperands() {
644 assert(FirstTerm != Head->end() && "No terminators");
645 DebugLoc HeadDL = FirstTerm->getDebugLoc();
646
647 // Convert all PHIs to select instructions inserted before FirstTerm.
648 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
649 PHIInfo &PI = PHIs[i];
650 unsigned DstReg = 0;
651
652 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
653 if (hasSameValue(*MRI, TII, PI.TReg, PI.FReg)) {
654 // We do not need the select instruction if both incoming values are
655 // equal.
656 DstReg = PI.TReg;
657 } else {
658 Register PHIDst = PI.PHI->getOperand(0).getReg();
659 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
660 TII->insertSelect(*Head, FirstTerm, HeadDL,
661 DstReg, Cond, PI.TReg, PI.FReg);
662 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
663 }
664
665 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
666 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
667 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
668 if (MBB == getTPred()) {
669 PI.PHI->getOperand(i-1).setMBB(Head);
670 PI.PHI->getOperand(i-2).setReg(DstReg);
671 } else if (MBB == getFPred()) {
672 PI.PHI->removeOperand(i-1);
673 PI.PHI->removeOperand(i-2);
674 }
675 }
676 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
677 }
678}
679
680/// convertIf - Execute the if conversion after canConvertIf has determined the
681/// feasibility.
682///
683/// Any basic blocks erased will be added to RemovedBlocks.
684///
685void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
686 bool Predicate) {
687 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
688
689 // Update statistics.
690 if (isTriangle())
691 ++NumTrianglesConv;
692 else
693 ++NumDiamondsConv;
694
695 // Move all instructions into Head, except for the terminators.
696 if (TBB != Tail) {
697 if (Predicate)
698 PredicateBlock(TBB, /*ReversePredicate=*/false);
699 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
700 }
701 if (FBB != Tail) {
702 if (Predicate)
703 PredicateBlock(FBB, /*ReversePredicate=*/true);
704 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
705 }
706 // Are there extra Tail predecessors?
707 bool ExtraPreds = Tail->pred_size() != 2;
708 if (ExtraPreds)
709 rewritePHIOperands();
710 else
711 replacePHIInstrs();
712
713 // Fix up the CFG, temporarily leave Head without any successors.
714 Head->removeSuccessor(TBB);
715 Head->removeSuccessor(FBB, true);
716 if (TBB != Tail)
717 TBB->removeSuccessor(Tail, true);
718 if (FBB != Tail)
719 FBB->removeSuccessor(Tail, true);
720
721 // Fix up Head's terminators.
722 // It should become a single branch or a fallthrough.
723 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
724 TII->removeBranch(*Head);
725
726 // Erase the now empty conditional blocks. It is likely that Head can fall
727 // through to Tail, and we can join the two blocks.
728 if (TBB != Tail) {
729 RemovedBlocks.push_back(TBB);
731 }
732 if (FBB != Tail) {
733 RemovedBlocks.push_back(FBB);
734 FBB->eraseFromParent();
735 }
736
737 assert(Head->succ_empty() && "Additional head successors?");
738 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
739 // Splice Tail onto the end of Head.
740 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
741 << " into head " << printMBBReference(*Head) << '\n');
742 Head->splice(Head->end(), Tail,
743 Tail->begin(), Tail->end());
745 RemovedBlocks.push_back(Tail);
746 Tail->eraseFromParent();
747 } else {
748 // We need a branch to Tail, let code placement work it out later.
749 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
751 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
752 Head->addSuccessor(Tail);
753 }
754 LLVM_DEBUG(dbgs() << *Head);
755}
756
757//===----------------------------------------------------------------------===//
758// EarlyIfConverter Pass
759//===----------------------------------------------------------------------===//
760
761namespace {
762class EarlyIfConverter : public MachineFunctionPass {
763 const TargetInstrInfo *TII = nullptr;
764 const TargetRegisterInfo *TRI = nullptr;
765 MCSchedModel SchedModel;
766 MachineRegisterInfo *MRI = nullptr;
767 MachineDominatorTree *DomTree = nullptr;
768 MachineLoopInfo *Loops = nullptr;
769 MachineTraceMetrics *Traces = nullptr;
770 MachineTraceMetrics::Ensemble *MinInstr = nullptr;
771 SSAIfConv IfConv;
772
773public:
774 static char ID;
775 EarlyIfConverter() : MachineFunctionPass(ID) {}
776 void getAnalysisUsage(AnalysisUsage &AU) const override;
777 bool runOnMachineFunction(MachineFunction &MF) override;
778 StringRef getPassName() const override { return "Early If-Conversion"; }
779
780private:
781 bool tryConvertIf(MachineBasicBlock*);
782 void invalidateTraces();
783 bool shouldConvertIf();
784};
785} // end anonymous namespace
786
787char EarlyIfConverter::ID = 0;
788char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
789
791 "Early If Converter", false, false)
796 "Early If Converter", false, false)
797
798void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
799 AU.addRequired<MachineBranchProbabilityInfo>();
800 AU.addRequired<MachineDominatorTree>();
801 AU.addPreserved<MachineDominatorTree>();
802 AU.addRequired<MachineLoopInfo>();
803 AU.addPreserved<MachineLoopInfo>();
804 AU.addRequired<MachineTraceMetrics>();
805 AU.addPreserved<MachineTraceMetrics>();
807}
808
809namespace {
810/// Update the dominator tree after if-conversion erased some blocks.
811void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
813 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
814 // TBB and FBB should not dominate any blocks.
815 // Tail children should be transferred to Head.
816 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
817 for (auto *B : Removed) {
818 MachineDomTreeNode *Node = DomTree->getNode(B);
819 assert(Node != HeadNode && "Cannot erase the head node");
820 while (Node->getNumChildren()) {
821 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
822 DomTree->changeImmediateDominator(Node->back(), HeadNode);
823 }
824 DomTree->eraseNode(B);
825 }
826}
827
828/// Update LoopInfo after if-conversion.
829void updateLoops(MachineLoopInfo *Loops,
831 // If-conversion doesn't change loop structure, and it doesn't mess with back
832 // edges, so updating LoopInfo is simply removing the dead blocks.
833 for (auto *B : Removed)
834 Loops->removeBlock(B);
835}
836} // namespace
837
838/// Invalidate MachineTraceMetrics before if-conversion.
839void EarlyIfConverter::invalidateTraces() {
840 Traces->verifyAnalysis();
841 Traces->invalidate(IfConv.Head);
842 Traces->invalidate(IfConv.Tail);
843 Traces->invalidate(IfConv.TBB);
844 Traces->invalidate(IfConv.FBB);
845 Traces->verifyAnalysis();
846}
847
848// Adjust cycles with downward saturation.
849static unsigned adjCycles(unsigned Cyc, int Delta) {
850 if (Delta < 0 && Cyc + Delta > Cyc)
851 return 0;
852 return Cyc + Delta;
853}
854
855namespace {
856/// Helper class to simplify emission of cycle counts into optimization remarks.
857struct Cycles {
858 const char *Key;
859 unsigned Value;
860};
861template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
862 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
863}
864} // anonymous namespace
865
866/// Apply cost model and heuristics to the if-conversion in IfConv.
867/// Return true if the conversion is a good idea.
868///
869bool EarlyIfConverter::shouldConvertIf() {
870 // Stress testing mode disables all cost considerations.
871 if (Stress)
872 return true;
873
874 // Do not try to if-convert if the condition has a high chance of being
875 // predictable.
876 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);
877 // If the condition is in a loop, consider it predictable if the condition
878 // itself or all its operands are loop-invariant. E.g. this considers a load
879 // from a loop-invariant address predictable; we were unable to prove that it
880 // doesn't alias any of the memory-writes in the loop, but it is likely to
881 // read to same value multiple times.
882 if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {
883 if (!MO.isReg() || !MO.isUse())
884 return false;
885 Register Reg = MO.getReg();
886 if (Register::isPhysicalRegister(Reg))
887 return false;
888
889 MachineInstr *Def = MRI->getVRegDef(Reg);
890 return CurrentLoop->isLoopInvariant(*Def) ||
891 all_of(Def->operands(), [&](MachineOperand &Op) {
892 if (Op.isImm())
893 return true;
894 if (!MO.isReg() || !MO.isUse())
895 return false;
896 Register Reg = MO.getReg();
897 if (Register::isPhysicalRegister(Reg))
898 return false;
899
900 MachineInstr *Def = MRI->getVRegDef(Reg);
901 return CurrentLoop->isLoopInvariant(*Def);
902 });
903 }))
904 return false;
905
906 if (!MinInstr)
907 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
908
909 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
910 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
911 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
912 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
913 FBBTrace.getCriticalPath());
914
915 // Set a somewhat arbitrary limit on the critical path extension we accept.
916 unsigned CritLimit = SchedModel.MispredictPenalty/2;
917
918 MachineBasicBlock &MBB = *IfConv.Head;
920
921 // If-conversion only makes sense when there is unexploited ILP. Compute the
922 // maximum-ILP resource length of the trace after if-conversion. Compare it
923 // to the shortest critical path.
925 if (IfConv.TBB != IfConv.Tail)
926 ExtraBlocks.push_back(IfConv.TBB);
927 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
928 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
929 << ", minimal critical path " << MinCrit << '\n');
930 if (ResLength > MinCrit + CritLimit) {
931 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
932 MORE.emit([&]() {
935 R << "did not if-convert branch: the resulting critical path ("
936 << Cycles{"ResLength", ResLength}
937 << ") would extend the shorter leg's critical path ("
938 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "
939 << Cycles{"CritLimit", CritLimit}
940 << ", which cannot be hidden by available ILP.";
941 return R;
942 });
943 return false;
944 }
945
946 // Assume that the depth of the first head terminator will also be the depth
947 // of the select instruction inserted, as determined by the flag dependency.
948 // TBB / FBB data dependencies may delay the select even more.
949 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
950 unsigned BranchDepth =
951 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
952 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
953
954 // Look at all the tail phis, and compute the critical path extension caused
955 // by inserting select instructions.
956 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
957 struct CriticalPathInfo {
958 unsigned Extra; // Count of extra cycles that the component adds.
959 unsigned Depth; // Absolute depth of the component in cycles.
960 };
961 CriticalPathInfo Cond{};
962 CriticalPathInfo TBlock{};
963 CriticalPathInfo FBlock{};
964 bool ShouldConvert = true;
965 for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
966 SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
967 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
968 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
969 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
970
971 // The condition is pulled into the critical path.
972 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
973 if (CondDepth > MaxDepth) {
974 unsigned Extra = CondDepth - MaxDepth;
975 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
976 if (Extra > Cond.Extra)
977 Cond = {Extra, CondDepth};
978 if (Extra > CritLimit) {
979 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
980 ShouldConvert = false;
981 }
982 }
983
984 // The TBB value is pulled into the critical path.
985 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
986 if (TDepth > MaxDepth) {
987 unsigned Extra = TDepth - MaxDepth;
988 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
989 if (Extra > TBlock.Extra)
990 TBlock = {Extra, TDepth};
991 if (Extra > CritLimit) {
992 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
993 ShouldConvert = false;
994 }
995 }
996
997 // The FBB value is pulled into the critical path.
998 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
999 if (FDepth > MaxDepth) {
1000 unsigned Extra = FDepth - MaxDepth;
1001 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
1002 if (Extra > FBlock.Extra)
1003 FBlock = {Extra, FDepth};
1004 if (Extra > CritLimit) {
1005 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1006 ShouldConvert = false;
1007 }
1008 }
1009 }
1010
1011 // Organize by "short" and "long" legs, since the diagnostics get confusing
1012 // when referring to the "true" and "false" sides of the branch, given that
1013 // those don't always correlate with what the user wrote in source-terms.
1014 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1015 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1016
1017 if (ShouldConvert) {
1018 MORE.emit([&]() {
1019 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
1020 MBB.back().getDebugLoc(), &MBB);
1021 R << "performing if-conversion on branch: the condition adds "
1022 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1023 if (Short.Extra > 0)
1024 R << ", and the short leg adds another "
1025 << Cycles{"ShortCycles", Short.Extra};
1026 if (Long.Extra > 0)
1027 R << ", and the long leg adds another "
1028 << Cycles{"LongCycles", Long.Extra};
1029 R << ", each staying under the threshold of "
1030 << Cycles{"CritLimit", CritLimit} << ".";
1031 return R;
1032 });
1033 } else {
1034 MORE.emit([&]() {
1036 MBB.back().getDebugLoc(), &MBB);
1037 R << "did not if-convert branch: the condition would add "
1038 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";
1039 if (Cond.Extra > CritLimit)
1040 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1041 if (Short.Extra > 0) {
1042 R << ", and the short leg would add another "
1043 << Cycles{"ShortCycles", Short.Extra};
1044 if (Short.Extra > CritLimit)
1045 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1046 }
1047 if (Long.Extra > 0) {
1048 R << ", and the long leg would add another "
1049 << Cycles{"LongCycles", Long.Extra};
1050 if (Long.Extra > CritLimit)
1051 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};
1052 }
1053 R << ".";
1054 return R;
1055 });
1056 }
1057
1058 return ShouldConvert;
1059}
1060
1061/// Attempt repeated if-conversion on MBB, return true if successful.
1062///
1063bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1064 bool Changed = false;
1065 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1066 // If-convert MBB and update analyses.
1067 invalidateTraces();
1069 IfConv.convertIf(RemovedBlocks);
1070 Changed = true;
1071 updateDomTree(DomTree, IfConv, RemovedBlocks);
1072 updateLoops(Loops, RemovedBlocks);
1073 }
1074 return Changed;
1075}
1076
1077bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
1078 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1079 << "********** Function: " << MF.getName() << '\n');
1080 if (skipFunction(MF.getFunction()))
1081 return false;
1082
1083 // Only run if conversion if the target wants it.
1084 const TargetSubtargetInfo &STI = MF.getSubtarget();
1085 if (!STI.enableEarlyIfConversion())
1086 return false;
1087
1088 TII = STI.getInstrInfo();
1089 TRI = STI.getRegisterInfo();
1090 SchedModel = STI.getSchedModel();
1091 MRI = &MF.getRegInfo();
1092 DomTree = &getAnalysis<MachineDominatorTree>();
1093 Loops = &getAnalysis<MachineLoopInfo>();
1094 Traces = &getAnalysis<MachineTraceMetrics>();
1095 MinInstr = nullptr;
1096
1097 bool Changed = false;
1098 IfConv.runOnMachineFunction(MF);
1099
1100 // Visit blocks in dominator tree post-order. The post-order enables nested
1101 // if-conversion in a single pass. The tryConvertIf() function may erase
1102 // blocks, but only blocks dominated by the head block. This makes it safe to
1103 // update the dominator tree while the post-order iterator is still active.
1104 for (auto *DomNode : post_order(DomTree))
1105 if (tryConvertIf(DomNode->getBlock()))
1106 Changed = true;
1107
1108 return Changed;
1109}
1110
1111//===----------------------------------------------------------------------===//
1112// EarlyIfPredicator Pass
1113//===----------------------------------------------------------------------===//
1114
1115namespace {
1116class EarlyIfPredicator : public MachineFunctionPass {
1117 const TargetInstrInfo *TII = nullptr;
1118 const TargetRegisterInfo *TRI = nullptr;
1119 TargetSchedModel SchedModel;
1120 MachineRegisterInfo *MRI = nullptr;
1121 MachineDominatorTree *DomTree = nullptr;
1122 MachineBranchProbabilityInfo *MBPI = nullptr;
1123 MachineLoopInfo *Loops = nullptr;
1124 SSAIfConv IfConv;
1125
1126public:
1127 static char ID;
1128 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1129 void getAnalysisUsage(AnalysisUsage &AU) const override;
1130 bool runOnMachineFunction(MachineFunction &MF) override;
1131 StringRef getPassName() const override { return "Early If-predicator"; }
1132
1133protected:
1134 bool tryConvertIf(MachineBasicBlock *);
1135 bool shouldConvertIf();
1136};
1137} // end anonymous namespace
1138
1139#undef DEBUG_TYPE
1140#define DEBUG_TYPE "early-if-predicator"
1141
1142char EarlyIfPredicator::ID = 0;
1143char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1144
1145INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1146 false, false)
1149INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1150 false)
1151
1152void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1153 AU.addRequired<MachineBranchProbabilityInfo>();
1154 AU.addRequired<MachineDominatorTree>();
1155 AU.addPreserved<MachineDominatorTree>();
1156 AU.addRequired<MachineLoopInfo>();
1157 AU.addPreserved<MachineLoopInfo>();
1159}
1160
1161/// Apply the target heuristic to decide if the transformation is profitable.
1162bool EarlyIfPredicator::shouldConvertIf() {
1163 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
1164 if (IfConv.isTriangle()) {
1165 MachineBasicBlock &IfBlock =
1166 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1167
1168 unsigned ExtraPredCost = 0;
1169 unsigned Cycles = 0;
1170 for (MachineInstr &I : IfBlock) {
1171 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1172 if (NumCycles > 1)
1173 Cycles += NumCycles - 1;
1174 ExtraPredCost += TII->getPredicationCost(I);
1175 }
1176
1177 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1178 TrueProbability);
1179 }
1180 unsigned TExtra = 0;
1181 unsigned FExtra = 0;
1182 unsigned TCycle = 0;
1183 unsigned FCycle = 0;
1184 for (MachineInstr &I : *IfConv.TBB) {
1185 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1186 if (NumCycles > 1)
1187 TCycle += NumCycles - 1;
1188 TExtra += TII->getPredicationCost(I);
1189 }
1190 for (MachineInstr &I : *IfConv.FBB) {
1191 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1192 if (NumCycles > 1)
1193 FCycle += NumCycles - 1;
1194 FExtra += TII->getPredicationCost(I);
1195 }
1196 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1197 FCycle, FExtra, TrueProbability);
1198}
1199
1200/// Attempt repeated if-conversion on MBB, return true if successful.
1201///
1202bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1203 bool Changed = false;
1204 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1205 // If-convert MBB and update analyses.
1207 IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1208 Changed = true;
1209 updateDomTree(DomTree, IfConv, RemovedBlocks);
1210 updateLoops(Loops, RemovedBlocks);
1211 }
1212 return Changed;
1213}
1214
1215bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1216 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1217 << "********** Function: " << MF.getName() << '\n');
1218 if (skipFunction(MF.getFunction()))
1219 return false;
1220
1221 const TargetSubtargetInfo &STI = MF.getSubtarget();
1222 TII = STI.getInstrInfo();
1223 TRI = STI.getRegisterInfo();
1224 MRI = &MF.getRegInfo();
1225 SchedModel.init(&STI);
1226 DomTree = &getAnalysis<MachineDominatorTree>();
1227 Loops = &getAnalysis<MachineLoopInfo>();
1228 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
1229
1230 bool Changed = false;
1231 IfConv.runOnMachineFunction(MF);
1232
1233 // Visit blocks in dominator tree post-order. The post-order enables nested
1234 // if-conversion in a single pass. The tryConvertIf() function may erase
1235 // blocks, but only blocks dominated by the head block. This makes it safe to
1236 // update the dominator tree while the post-order iterator is still active.
1237 for (auto *DomNode : post_order(DomTree))
1238 if (tryConvertIf(DomNode->getBlock()))
1239 Changed = true;
1240
1241 return Changed;
1242}
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
Rewrite undef for PHI
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 '...
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:969
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:341
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:728
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:493
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:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:450
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: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 ...