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