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