1239310Sdim//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===// 2239310Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6239310Sdim// 7239310Sdim//===----------------------------------------------------------------------===// 8239310Sdim// 9239310Sdim// Early if-conversion is for out-of-order CPUs that don't have a lot of 10239310Sdim// predicable instructions. The goal is to eliminate conditional branches that 11239310Sdim// may mispredict. 12239310Sdim// 13239310Sdim// Instructions from both sides of the branch are executed specutatively, and a 14239310Sdim// cmov instruction selects the result. 15239310Sdim// 16239310Sdim//===----------------------------------------------------------------------===// 17239310Sdim 18239310Sdim#include "llvm/ADT/BitVector.h" 19239310Sdim#include "llvm/ADT/PostOrderIterator.h" 20239310Sdim#include "llvm/ADT/SetVector.h" 21239310Sdim#include "llvm/ADT/SmallPtrSet.h" 22239310Sdim#include "llvm/ADT/SparseSet.h" 23239310Sdim#include "llvm/ADT/Statistic.h" 24239310Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 25239310Sdim#include "llvm/CodeGen/MachineDominators.h" 26239310Sdim#include "llvm/CodeGen/MachineFunction.h" 27239310Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 28360784Sdim#include "llvm/CodeGen/MachineInstr.h" 29239310Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 30239310Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 31249423Sdim#include "llvm/CodeGen/MachineTraceMetrics.h" 32239310Sdim#include "llvm/CodeGen/Passes.h" 33327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 34327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 35327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 36360784Sdim#include "llvm/InitializePasses.h" 37249423Sdim#include "llvm/Support/CommandLine.h" 38249423Sdim#include "llvm/Support/Debug.h" 39249423Sdim#include "llvm/Support/raw_ostream.h" 40239310Sdim 41239310Sdimusing namespace llvm; 42239310Sdim 43276479Sdim#define DEBUG_TYPE "early-ifcvt" 44276479Sdim 45239310Sdim// Absolute maximum number of instructions allowed per speculated block. 46239310Sdim// This bypasses all other heuristics, so it should be set fairly high. 47239310Sdimstatic cl::opt<unsigned> 48239310SdimBlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, 49239310Sdim cl::desc("Maximum number of instructions per speculated block.")); 50239310Sdim 51239310Sdim// Stress testing mode - disable heuristics. 52239310Sdimstatic cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden, 53239310Sdim cl::desc("Turn all knobs to 11")); 54239310Sdim 55239310SdimSTATISTIC(NumDiamondsSeen, "Number of diamonds"); 56239310SdimSTATISTIC(NumDiamondsConv, "Number of diamonds converted"); 57239310SdimSTATISTIC(NumTrianglesSeen, "Number of triangles"); 58239310SdimSTATISTIC(NumTrianglesConv, "Number of triangles converted"); 59239310Sdim 60239310Sdim//===----------------------------------------------------------------------===// 61239310Sdim// SSAIfConv 62239310Sdim//===----------------------------------------------------------------------===// 63239310Sdim// 64239310Sdim// The SSAIfConv class performs if-conversion on SSA form machine code after 65239310Sdim// determining if it is possible. The class contains no heuristics; external 66239310Sdim// code should be used to determine when if-conversion is a good idea. 67239310Sdim// 68239310Sdim// SSAIfConv can convert both triangles and diamonds: 69239310Sdim// 70239310Sdim// Triangle: Head Diamond: Head 71239310Sdim// | \ / \_ 72239310Sdim// | \ / | 73239310Sdim// | [TF]BB FBB TBB 74239310Sdim// | / \ / 75239310Sdim// | / \ / 76239310Sdim// Tail Tail 77239310Sdim// 78239310Sdim// Instructions in the conditional blocks TBB and/or FBB are spliced into the 79239310Sdim// Head block, and phis in the Tail block are converted to select instructions. 80239310Sdim// 81239310Sdimnamespace { 82239310Sdimclass SSAIfConv { 83239310Sdim const TargetInstrInfo *TII; 84239310Sdim const TargetRegisterInfo *TRI; 85239310Sdim MachineRegisterInfo *MRI; 86239310Sdim 87239310Sdimpublic: 88239310Sdim /// The block containing the conditional branch. 89239310Sdim MachineBasicBlock *Head; 90239310Sdim 91239310Sdim /// The block containing phis after the if-then-else. 92239310Sdim MachineBasicBlock *Tail; 93239310Sdim 94239310Sdim /// The 'true' conditional block as determined by AnalyzeBranch. 95239310Sdim MachineBasicBlock *TBB; 96239310Sdim 97239310Sdim /// The 'false' conditional block as determined by AnalyzeBranch. 98239310Sdim MachineBasicBlock *FBB; 99239310Sdim 100239310Sdim /// isTriangle - When there is no 'else' block, either TBB or FBB will be 101239310Sdim /// equal to Tail. 102239310Sdim bool isTriangle() const { return TBB == Tail || FBB == Tail; } 103239310Sdim 104239310Sdim /// Returns the Tail predecessor for the True side. 105239310Sdim MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; } 106239310Sdim 107239310Sdim /// Returns the Tail predecessor for the False side. 108239310Sdim MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; } 109239310Sdim 110239310Sdim /// Information about each phi in the Tail block. 111239310Sdim struct PHIInfo { 112239310Sdim MachineInstr *PHI; 113239310Sdim unsigned TReg, FReg; 114239310Sdim // Latencies from Cond+Branch, TReg, and FReg to DstReg. 115239310Sdim int CondCycles, TCycles, FCycles; 116239310Sdim 117239310Sdim PHIInfo(MachineInstr *phi) 118239310Sdim : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {} 119239310Sdim }; 120239310Sdim 121239310Sdim SmallVector<PHIInfo, 8> PHIs; 122239310Sdim 123239310Sdimprivate: 124239310Sdim /// The branch condition determined by AnalyzeBranch. 125239310Sdim SmallVector<MachineOperand, 4> Cond; 126239310Sdim 127239310Sdim /// Instructions in Head that define values used by the conditional blocks. 128239310Sdim /// The hoisted instructions must be inserted after these instructions. 129239310Sdim SmallPtrSet<MachineInstr*, 8> InsertAfter; 130239310Sdim 131239310Sdim /// Register units clobbered by the conditional blocks. 132239310Sdim BitVector ClobberedRegUnits; 133239310Sdim 134239310Sdim // Scratch pad for findInsertionPoint. 135239310Sdim SparseSet<unsigned> LiveRegUnits; 136239310Sdim 137239310Sdim /// Insertion point in Head for speculatively executed instructions form TBB 138239310Sdim /// and FBB. 139239310Sdim MachineBasicBlock::iterator InsertionPoint; 140239310Sdim 141239310Sdim /// Return true if all non-terminator instructions in MBB can be safely 142239310Sdim /// speculated. 143239310Sdim bool canSpeculateInstrs(MachineBasicBlock *MBB); 144239310Sdim 145360784Sdim /// Return true if all non-terminator instructions in MBB can be safely 146360784Sdim /// predicated. 147360784Sdim bool canPredicateInstrs(MachineBasicBlock *MBB); 148360784Sdim 149360784Sdim /// Scan through instruction dependencies and update InsertAfter array. 150360784Sdim /// Return false if any dependency is incompatible with if conversion. 151360784Sdim bool InstrDependenciesAllowIfConv(MachineInstr *I); 152360784Sdim 153360784Sdim /// Predicate all instructions of the basic block with current condition 154360784Sdim /// except for terminators. Reverse the condition if ReversePredicate is set. 155360784Sdim void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate); 156360784Sdim 157239310Sdim /// Find a valid insertion point in Head. 158239310Sdim bool findInsertionPoint(); 159239310Sdim 160239310Sdim /// Replace PHI instructions in Tail with selects. 161239310Sdim void replacePHIInstrs(); 162239310Sdim 163239310Sdim /// Insert selects and rewrite PHI operands to use them. 164239310Sdim void rewritePHIOperands(); 165239310Sdim 166239310Sdimpublic: 167239310Sdim /// runOnMachineFunction - Initialize per-function data structures. 168239310Sdim void runOnMachineFunction(MachineFunction &MF) { 169280031Sdim TII = MF.getSubtarget().getInstrInfo(); 170280031Sdim TRI = MF.getSubtarget().getRegisterInfo(); 171239310Sdim MRI = &MF.getRegInfo(); 172239310Sdim LiveRegUnits.clear(); 173239310Sdim LiveRegUnits.setUniverse(TRI->getNumRegUnits()); 174239310Sdim ClobberedRegUnits.clear(); 175239310Sdim ClobberedRegUnits.resize(TRI->getNumRegUnits()); 176239310Sdim } 177239310Sdim 178239310Sdim /// canConvertIf - If the sub-CFG headed by MBB can be if-converted, 179239310Sdim /// initialize the internal state, and return true. 180360784Sdim /// If predicate is set try to predicate the block otherwise try to 181360784Sdim /// speculatively execute it. 182360784Sdim bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false); 183239310Sdim 184239310Sdim /// convertIf - If-convert the last block passed to canConvertIf(), assuming 185239310Sdim /// it is possible. Add any erased blocks to RemovedBlocks. 186360784Sdim void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks, 187360784Sdim bool Predicate = false); 188239310Sdim}; 189239310Sdim} // end anonymous namespace 190239310Sdim 191239310Sdim 192239310Sdim/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely 193239310Sdim/// be speculated. The terminators are not considered. 194239310Sdim/// 195239310Sdim/// If instructions use any values that are defined in the head basic block, 196239310Sdim/// the defining instructions are added to InsertAfter. 197239310Sdim/// 198239310Sdim/// Any clobbered regunits are added to ClobberedRegUnits. 199239310Sdim/// 200239310Sdimbool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { 201239310Sdim // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 202239310Sdim // get right. 203239310Sdim if (!MBB->livein_empty()) { 204341825Sdim LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); 205239310Sdim return false; 206239310Sdim } 207239310Sdim 208239310Sdim unsigned InstrCount = 0; 209239310Sdim 210239310Sdim // Check all instructions, except the terminators. It is assumed that 211239310Sdim // terminators never have side effects or define any used register values. 212239310Sdim for (MachineBasicBlock::iterator I = MBB->begin(), 213239310Sdim E = MBB->getFirstTerminator(); I != E; ++I) { 214341825Sdim if (I->isDebugInstr()) 215239310Sdim continue; 216239310Sdim 217239310Sdim if (++InstrCount > BlockInstrLimit && !Stress) { 218341825Sdim LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " 219341825Sdim << BlockInstrLimit << " instructions.\n"); 220239310Sdim return false; 221239310Sdim } 222239310Sdim 223239310Sdim // There shouldn't normally be any phis in a single-predecessor block. 224239310Sdim if (I->isPHI()) { 225341825Sdim LLVM_DEBUG(dbgs() << "Can't hoist: " << *I); 226239310Sdim return false; 227239310Sdim } 228239310Sdim 229239310Sdim // Don't speculate loads. Note that it may be possible and desirable to 230239310Sdim // speculate GOT or constant pool loads that are guaranteed not to trap, 231239310Sdim // but we don't support that for now. 232239310Sdim if (I->mayLoad()) { 233341825Sdim LLVM_DEBUG(dbgs() << "Won't speculate load: " << *I); 234239310Sdim return false; 235239310Sdim } 236239310Sdim 237239310Sdim // We never speculate stores, so an AA pointer isn't necessary. 238239310Sdim bool DontMoveAcrossStore = true; 239288943Sdim if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) { 240341825Sdim LLVM_DEBUG(dbgs() << "Can't speculate: " << *I); 241239310Sdim return false; 242239310Sdim } 243239310Sdim 244239310Sdim // Check for any dependencies on Head instructions. 245360784Sdim if (!InstrDependenciesAllowIfConv(&(*I))) 246360784Sdim return false; 247360784Sdim } 248360784Sdim return true; 249360784Sdim} 250239310Sdim 251360784Sdim/// Check that there is no dependencies preventing if conversion. 252360784Sdim/// 253360784Sdim/// If instruction uses any values that are defined in the head basic block, 254360784Sdim/// the defining instructions are added to InsertAfter. 255360784Sdimbool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) { 256360784Sdim for (const MachineOperand &MO : I->operands()) { 257360784Sdim if (MO.isRegMask()) { 258360784Sdim LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I); 259360784Sdim return false; 260360784Sdim } 261360784Sdim if (!MO.isReg()) 262360784Sdim continue; 263360784Sdim Register Reg = MO.getReg(); 264239310Sdim 265360784Sdim // Remember clobbered regunits. 266360784Sdim if (MO.isDef() && Register::isPhysicalRegister(Reg)) 267360784Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 268360784Sdim ClobberedRegUnits.set(*Units); 269360784Sdim 270360784Sdim if (!MO.readsReg() || !Register::isVirtualRegister(Reg)) 271360784Sdim continue; 272360784Sdim MachineInstr *DefMI = MRI->getVRegDef(Reg); 273360784Sdim if (!DefMI || DefMI->getParent() != Head) 274360784Sdim continue; 275360784Sdim if (InsertAfter.insert(DefMI).second) 276360784Sdim LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on " 277360784Sdim << *DefMI); 278360784Sdim if (DefMI->isTerminator()) { 279360784Sdim LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); 280360784Sdim return false; 281239310Sdim } 282239310Sdim } 283239310Sdim return true; 284239310Sdim} 285239310Sdim 286360784Sdim/// canPredicateInstrs - Returns true if all the instructions in MBB can safely 287360784Sdim/// be predicates. The terminators are not considered. 288360784Sdim/// 289360784Sdim/// If instructions use any values that are defined in the head basic block, 290360784Sdim/// the defining instructions are added to InsertAfter. 291360784Sdim/// 292360784Sdim/// Any clobbered regunits are added to ClobberedRegUnits. 293360784Sdim/// 294360784Sdimbool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) { 295360784Sdim // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 296360784Sdim // get right. 297360784Sdim if (!MBB->livein_empty()) { 298360784Sdim LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); 299360784Sdim return false; 300360784Sdim } 301239310Sdim 302360784Sdim unsigned InstrCount = 0; 303360784Sdim 304360784Sdim // Check all instructions, except the terminators. It is assumed that 305360784Sdim // terminators never have side effects or define any used register values. 306360784Sdim for (MachineBasicBlock::iterator I = MBB->begin(), 307360784Sdim E = MBB->getFirstTerminator(); 308360784Sdim I != E; ++I) { 309360784Sdim if (I->isDebugInstr()) 310360784Sdim continue; 311360784Sdim 312360784Sdim if (++InstrCount > BlockInstrLimit && !Stress) { 313360784Sdim LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " 314360784Sdim << BlockInstrLimit << " instructions.\n"); 315360784Sdim return false; 316360784Sdim } 317360784Sdim 318360784Sdim // There shouldn't normally be any phis in a single-predecessor block. 319360784Sdim if (I->isPHI()) { 320360784Sdim LLVM_DEBUG(dbgs() << "Can't predicate: " << *I); 321360784Sdim return false; 322360784Sdim } 323360784Sdim 324360784Sdim // Check that instruction is predicable and that it is not already 325360784Sdim // predicated. 326360784Sdim if (!TII->isPredicable(*I) || TII->isPredicated(*I)) { 327360784Sdim return false; 328360784Sdim } 329360784Sdim 330360784Sdim // Check for any dependencies on Head instructions. 331360784Sdim if (!InstrDependenciesAllowIfConv(&(*I))) 332360784Sdim return false; 333360784Sdim } 334360784Sdim return true; 335360784Sdim} 336360784Sdim 337360784Sdim// Apply predicate to all instructions in the machine block. 338360784Sdimvoid SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) { 339360784Sdim auto Condition = Cond; 340360784Sdim if (ReversePredicate) 341360784Sdim TII->reverseBranchCondition(Condition); 342360784Sdim // Terminators don't need to be predicated as they will be removed. 343360784Sdim for (MachineBasicBlock::iterator I = MBB->begin(), 344360784Sdim E = MBB->getFirstTerminator(); 345360784Sdim I != E; ++I) { 346360784Sdim if (I->isDebugInstr()) 347360784Sdim continue; 348360784Sdim TII->PredicateInstruction(*I, Condition); 349360784Sdim } 350360784Sdim} 351360784Sdim 352239310Sdim/// Find an insertion point in Head for the speculated instructions. The 353239310Sdim/// insertion point must be: 354239310Sdim/// 355239310Sdim/// 1. Before any terminators. 356239310Sdim/// 2. After any instructions in InsertAfter. 357239310Sdim/// 3. Not have any clobbered regunits live. 358239310Sdim/// 359239310Sdim/// This function sets InsertionPoint and returns true when successful, it 360239310Sdim/// returns false if no valid insertion point could be found. 361239310Sdim/// 362239310Sdimbool SSAIfConv::findInsertionPoint() { 363239310Sdim // Keep track of live regunits before the current position. 364239310Sdim // Only track RegUnits that are also in ClobberedRegUnits. 365239310Sdim LiveRegUnits.clear(); 366239310Sdim SmallVector<unsigned, 8> Reads; 367239310Sdim MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 368239310Sdim MachineBasicBlock::iterator I = Head->end(); 369239310Sdim MachineBasicBlock::iterator B = Head->begin(); 370239310Sdim while (I != B) { 371239310Sdim --I; 372239310Sdim // Some of the conditional code depends in I. 373309124Sdim if (InsertAfter.count(&*I)) { 374341825Sdim LLVM_DEBUG(dbgs() << "Can't insert code after " << *I); 375239310Sdim return false; 376239310Sdim } 377239310Sdim 378239310Sdim // Update live regunits. 379288943Sdim for (const MachineOperand &MO : I->operands()) { 380239310Sdim // We're ignoring regmask operands. That is conservatively correct. 381288943Sdim if (!MO.isReg()) 382239310Sdim continue; 383360784Sdim Register Reg = MO.getReg(); 384360784Sdim if (!Register::isPhysicalRegister(Reg)) 385239310Sdim continue; 386239310Sdim // I clobbers Reg, so it isn't live before I. 387288943Sdim if (MO.isDef()) 388239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 389239310Sdim LiveRegUnits.erase(*Units); 390239310Sdim // Unless I reads Reg. 391288943Sdim if (MO.readsReg()) 392239310Sdim Reads.push_back(Reg); 393239310Sdim } 394239310Sdim // Anything read by I is live before I. 395239310Sdim while (!Reads.empty()) 396239310Sdim for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid(); 397239310Sdim ++Units) 398239310Sdim if (ClobberedRegUnits.test(*Units)) 399239310Sdim LiveRegUnits.insert(*Units); 400239310Sdim 401239310Sdim // We can't insert before a terminator. 402239310Sdim if (I != FirstTerm && I->isTerminator()) 403239310Sdim continue; 404239310Sdim 405239310Sdim // Some of the clobbered registers are live before I, not a valid insertion 406239310Sdim // point. 407239310Sdim if (!LiveRegUnits.empty()) { 408341825Sdim LLVM_DEBUG({ 409239310Sdim dbgs() << "Would clobber"; 410239310Sdim for (SparseSet<unsigned>::const_iterator 411239310Sdim i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i) 412327952Sdim dbgs() << ' ' << printRegUnit(*i, TRI); 413239310Sdim dbgs() << " live before " << *I; 414239310Sdim }); 415239310Sdim continue; 416239310Sdim } 417239310Sdim 418239310Sdim // This is a valid insertion point. 419239310Sdim InsertionPoint = I; 420341825Sdim LLVM_DEBUG(dbgs() << "Can insert before " << *I); 421239310Sdim return true; 422239310Sdim } 423341825Sdim LLVM_DEBUG(dbgs() << "No legal insertion point found.\n"); 424239310Sdim return false; 425239310Sdim} 426239310Sdim 427239310Sdim 428239310Sdim 429239310Sdim/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is 430239310Sdim/// a potential candidate for if-conversion. Fill out the internal state. 431239310Sdim/// 432360784Sdimbool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) { 433239310Sdim Head = MBB; 434276479Sdim TBB = FBB = Tail = nullptr; 435239310Sdim 436239310Sdim if (Head->succ_size() != 2) 437239310Sdim return false; 438239310Sdim MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 439239310Sdim MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 440239310Sdim 441239310Sdim // Canonicalize so Succ0 has MBB as its single predecessor. 442239310Sdim if (Succ0->pred_size() != 1) 443239310Sdim std::swap(Succ0, Succ1); 444239310Sdim 445239310Sdim if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) 446239310Sdim return false; 447239310Sdim 448239310Sdim Tail = Succ0->succ_begin()[0]; 449239310Sdim 450239310Sdim // This is not a triangle. 451239310Sdim if (Tail != Succ1) { 452239310Sdim // Check for a diamond. We won't deal with any critical edges. 453239310Sdim if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || 454239310Sdim Succ1->succ_begin()[0] != Tail) 455239310Sdim return false; 456341825Sdim LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> " 457341825Sdim << printMBBReference(*Succ0) << "/" 458341825Sdim << printMBBReference(*Succ1) << " -> " 459341825Sdim << printMBBReference(*Tail) << '\n'); 460239310Sdim 461239310Sdim // Live-in physregs are tricky to get right when speculating code. 462239310Sdim if (!Tail->livein_empty()) { 463341825Sdim LLVM_DEBUG(dbgs() << "Tail has live-ins.\n"); 464239310Sdim return false; 465239310Sdim } 466239310Sdim } else { 467341825Sdim LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> " 468341825Sdim << printMBBReference(*Succ0) << " -> " 469341825Sdim << printMBBReference(*Tail) << '\n'); 470239310Sdim } 471239310Sdim 472239310Sdim // This is a triangle or a diamond. 473360784Sdim // Skip if we cannot predicate and there are no phis skip as there must be 474360784Sdim // side effects that can only be handled with predication. 475360784Sdim if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) { 476341825Sdim LLVM_DEBUG(dbgs() << "No phis in tail.\n"); 477239310Sdim return false; 478239310Sdim } 479239310Sdim 480239310Sdim // The branch we're looking to eliminate must be analyzable. 481239310Sdim Cond.clear(); 482309124Sdim if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) { 483341825Sdim LLVM_DEBUG(dbgs() << "Branch not analyzable.\n"); 484239310Sdim return false; 485239310Sdim } 486239310Sdim 487239310Sdim // This is weird, probably some sort of degenerate CFG. 488239310Sdim if (!TBB) { 489341825Sdim LLVM_DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n"); 490239310Sdim return false; 491239310Sdim } 492239310Sdim 493344779Sdim // Make sure the analyzed branch is conditional; one of the successors 494344779Sdim // could be a landing pad. (Empty landing pads can be generated on Windows.) 495344779Sdim if (Cond.empty()) { 496344779Sdim LLVM_DEBUG(dbgs() << "AnalyzeBranch found an unconditional branch.\n"); 497344779Sdim return false; 498344779Sdim } 499344779Sdim 500239310Sdim // AnalyzeBranch doesn't set FBB on a fall-through branch. 501239310Sdim // Make sure it is always set. 502239310Sdim FBB = TBB == Succ0 ? Succ1 : Succ0; 503239310Sdim 504239310Sdim // Any phis in the tail block must be convertible to selects. 505239310Sdim PHIs.clear(); 506239310Sdim MachineBasicBlock *TPred = getTPred(); 507239310Sdim MachineBasicBlock *FPred = getFPred(); 508239310Sdim for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); 509239310Sdim I != E && I->isPHI(); ++I) { 510239310Sdim PHIs.push_back(&*I); 511239310Sdim PHIInfo &PI = PHIs.back(); 512239310Sdim // Find PHI operands corresponding to TPred and FPred. 513239310Sdim for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { 514239310Sdim if (PI.PHI->getOperand(i+1).getMBB() == TPred) 515239310Sdim PI.TReg = PI.PHI->getOperand(i).getReg(); 516239310Sdim if (PI.PHI->getOperand(i+1).getMBB() == FPred) 517239310Sdim PI.FReg = PI.PHI->getOperand(i).getReg(); 518239310Sdim } 519360784Sdim assert(Register::isVirtualRegister(PI.TReg) && "Bad PHI"); 520360784Sdim assert(Register::isVirtualRegister(PI.FReg) && "Bad PHI"); 521239310Sdim 522239310Sdim // Get target information. 523239310Sdim if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg, 524239310Sdim PI.CondCycles, PI.TCycles, PI.FCycles)) { 525341825Sdim LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI); 526239310Sdim return false; 527239310Sdim } 528239310Sdim } 529239310Sdim 530239310Sdim // Check that the conditional instructions can be speculated. 531239310Sdim InsertAfter.clear(); 532239310Sdim ClobberedRegUnits.reset(); 533360784Sdim if (Predicate) { 534360784Sdim if (TBB != Tail && !canPredicateInstrs(TBB)) 535360784Sdim return false; 536360784Sdim if (FBB != Tail && !canPredicateInstrs(FBB)) 537360784Sdim return false; 538360784Sdim } else { 539360784Sdim if (TBB != Tail && !canSpeculateInstrs(TBB)) 540360784Sdim return false; 541360784Sdim if (FBB != Tail && !canSpeculateInstrs(FBB)) 542360784Sdim return false; 543360784Sdim } 544239310Sdim 545239310Sdim // Try to find a valid insertion point for the speculated instructions in the 546239310Sdim // head basic block. 547239310Sdim if (!findInsertionPoint()) 548239310Sdim return false; 549239310Sdim 550239310Sdim if (isTriangle()) 551239310Sdim ++NumTrianglesSeen; 552239310Sdim else 553239310Sdim ++NumDiamondsSeen; 554239310Sdim return true; 555239310Sdim} 556239310Sdim 557239310Sdim/// replacePHIInstrs - Completely replace PHI instructions with selects. 558239310Sdim/// This is possible when the only Tail predecessors are the if-converted 559239310Sdim/// blocks. 560239310Sdimvoid SSAIfConv::replacePHIInstrs() { 561239310Sdim assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); 562239310Sdim MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 563239310Sdim assert(FirstTerm != Head->end() && "No terminators"); 564239310Sdim DebugLoc HeadDL = FirstTerm->getDebugLoc(); 565239310Sdim 566239310Sdim // Convert all PHIs to select instructions inserted before FirstTerm. 567239310Sdim for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 568239310Sdim PHIInfo &PI = PHIs[i]; 569341825Sdim LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); 570360784Sdim Register DstReg = PI.PHI->getOperand(0).getReg(); 571239310Sdim TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 572341825Sdim LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); 573239310Sdim PI.PHI->eraseFromParent(); 574276479Sdim PI.PHI = nullptr; 575239310Sdim } 576239310Sdim} 577239310Sdim 578239310Sdim/// rewritePHIOperands - When there are additional Tail predecessors, insert 579239310Sdim/// select instructions in Head and rewrite PHI operands to use the selects. 580239310Sdim/// Keep the PHI instructions in Tail to handle the other predecessors. 581239310Sdimvoid SSAIfConv::rewritePHIOperands() { 582239310Sdim MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 583239310Sdim assert(FirstTerm != Head->end() && "No terminators"); 584239310Sdim DebugLoc HeadDL = FirstTerm->getDebugLoc(); 585239310Sdim 586239310Sdim // Convert all PHIs to select instructions inserted before FirstTerm. 587239310Sdim for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 588239310Sdim PHIInfo &PI = PHIs[i]; 589288943Sdim unsigned DstReg = 0; 590309124Sdim 591341825Sdim LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); 592288943Sdim if (PI.TReg == PI.FReg) { 593288943Sdim // We do not need the select instruction if both incoming values are 594288943Sdim // equal. 595288943Sdim DstReg = PI.TReg; 596288943Sdim } else { 597360784Sdim Register PHIDst = PI.PHI->getOperand(0).getReg(); 598288943Sdim DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); 599288943Sdim TII->insertSelect(*Head, FirstTerm, HeadDL, 600288943Sdim DstReg, Cond, PI.TReg, PI.FReg); 601341825Sdim LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); 602288943Sdim } 603239310Sdim 604239310Sdim // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. 605239310Sdim for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { 606239310Sdim MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); 607239310Sdim if (MBB == getTPred()) { 608239310Sdim PI.PHI->getOperand(i-1).setMBB(Head); 609239310Sdim PI.PHI->getOperand(i-2).setReg(DstReg); 610239310Sdim } else if (MBB == getFPred()) { 611239310Sdim PI.PHI->RemoveOperand(i-1); 612239310Sdim PI.PHI->RemoveOperand(i-2); 613239310Sdim } 614239310Sdim } 615341825Sdim LLVM_DEBUG(dbgs() << " --> " << *PI.PHI); 616239310Sdim } 617239310Sdim} 618239310Sdim 619239310Sdim/// convertIf - Execute the if conversion after canConvertIf has determined the 620239310Sdim/// feasibility. 621239310Sdim/// 622239310Sdim/// Any basic blocks erased will be added to RemovedBlocks. 623239310Sdim/// 624360784Sdimvoid SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks, 625360784Sdim bool Predicate) { 626239310Sdim assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); 627239310Sdim 628239310Sdim // Update statistics. 629239310Sdim if (isTriangle()) 630239310Sdim ++NumTrianglesConv; 631239310Sdim else 632239310Sdim ++NumDiamondsConv; 633239310Sdim 634239310Sdim // Move all instructions into Head, except for the terminators. 635360784Sdim if (TBB != Tail) { 636360784Sdim if (Predicate) 637360784Sdim PredicateBlock(TBB, /*ReversePredicate=*/false); 638239310Sdim Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); 639360784Sdim } 640360784Sdim if (FBB != Tail) { 641360784Sdim if (Predicate) 642360784Sdim PredicateBlock(FBB, /*ReversePredicate=*/true); 643239310Sdim Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); 644360784Sdim } 645239310Sdim // Are there extra Tail predecessors? 646239310Sdim bool ExtraPreds = Tail->pred_size() != 2; 647239310Sdim if (ExtraPreds) 648239310Sdim rewritePHIOperands(); 649239310Sdim else 650239310Sdim replacePHIInstrs(); 651239310Sdim 652239310Sdim // Fix up the CFG, temporarily leave Head without any successors. 653239310Sdim Head->removeSuccessor(TBB); 654296417Sdim Head->removeSuccessor(FBB, true); 655239310Sdim if (TBB != Tail) 656296417Sdim TBB->removeSuccessor(Tail, true); 657239310Sdim if (FBB != Tail) 658296417Sdim FBB->removeSuccessor(Tail, true); 659239310Sdim 660239310Sdim // Fix up Head's terminators. 661239310Sdim // It should become a single branch or a fallthrough. 662239310Sdim DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); 663314564Sdim TII->removeBranch(*Head); 664239310Sdim 665239310Sdim // Erase the now empty conditional blocks. It is likely that Head can fall 666239310Sdim // through to Tail, and we can join the two blocks. 667239310Sdim if (TBB != Tail) { 668239310Sdim RemovedBlocks.push_back(TBB); 669239310Sdim TBB->eraseFromParent(); 670239310Sdim } 671239310Sdim if (FBB != Tail) { 672239310Sdim RemovedBlocks.push_back(FBB); 673239310Sdim FBB->eraseFromParent(); 674239310Sdim } 675239310Sdim 676239310Sdim assert(Head->succ_empty() && "Additional head successors?"); 677239310Sdim if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { 678239310Sdim // Splice Tail onto the end of Head. 679341825Sdim LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail) 680341825Sdim << " into head " << printMBBReference(*Head) << '\n'); 681239310Sdim Head->splice(Head->end(), Tail, 682239310Sdim Tail->begin(), Tail->end()); 683239310Sdim Head->transferSuccessorsAndUpdatePHIs(Tail); 684239310Sdim RemovedBlocks.push_back(Tail); 685239310Sdim Tail->eraseFromParent(); 686239310Sdim } else { 687239310Sdim // We need a branch to Tail, let code placement work it out later. 688341825Sdim LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n"); 689239310Sdim SmallVector<MachineOperand, 0> EmptyCond; 690314564Sdim TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL); 691239310Sdim Head->addSuccessor(Tail); 692239310Sdim } 693341825Sdim LLVM_DEBUG(dbgs() << *Head); 694239310Sdim} 695239310Sdim 696239310Sdim//===----------------------------------------------------------------------===// 697239310Sdim// EarlyIfConverter Pass 698239310Sdim//===----------------------------------------------------------------------===// 699239310Sdim 700239310Sdimnamespace { 701239310Sdimclass EarlyIfConverter : public MachineFunctionPass { 702239310Sdim const TargetInstrInfo *TII; 703239310Sdim const TargetRegisterInfo *TRI; 704280031Sdim MCSchedModel SchedModel; 705239310Sdim MachineRegisterInfo *MRI; 706239310Sdim MachineDominatorTree *DomTree; 707239310Sdim MachineLoopInfo *Loops; 708239310Sdim MachineTraceMetrics *Traces; 709239310Sdim MachineTraceMetrics::Ensemble *MinInstr; 710239310Sdim SSAIfConv IfConv; 711239310Sdim 712239310Sdimpublic: 713239310Sdim static char ID; 714239310Sdim EarlyIfConverter() : MachineFunctionPass(ID) {} 715276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 716276479Sdim bool runOnMachineFunction(MachineFunction &MF) override; 717314564Sdim StringRef getPassName() const override { return "Early If-Conversion"; } 718239310Sdim 719239310Sdimprivate: 720239310Sdim bool tryConvertIf(MachineBasicBlock*); 721239310Sdim void invalidateTraces(); 722239310Sdim bool shouldConvertIf(); 723239310Sdim}; 724239310Sdim} // end anonymous namespace 725239310Sdim 726239310Sdimchar EarlyIfConverter::ID = 0; 727239310Sdimchar &llvm::EarlyIfConverterID = EarlyIfConverter::ID; 728239310Sdim 729321369SdimINITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE, 730321369Sdim "Early If Converter", false, false) 731239310SdimINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 732239310SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 733239310SdimINITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) 734321369SdimINITIALIZE_PASS_END(EarlyIfConverter, DEBUG_TYPE, 735321369Sdim "Early If Converter", false, false) 736239310Sdim 737239310Sdimvoid EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const { 738239310Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 739239310Sdim AU.addRequired<MachineDominatorTree>(); 740239310Sdim AU.addPreserved<MachineDominatorTree>(); 741239310Sdim AU.addRequired<MachineLoopInfo>(); 742239310Sdim AU.addPreserved<MachineLoopInfo>(); 743239310Sdim AU.addRequired<MachineTraceMetrics>(); 744239310Sdim AU.addPreserved<MachineTraceMetrics>(); 745239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 746239310Sdim} 747239310Sdim 748360784Sdimnamespace { 749239310Sdim/// Update the dominator tree after if-conversion erased some blocks. 750360784Sdimvoid updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv, 751360784Sdim ArrayRef<MachineBasicBlock *> Removed) { 752239310Sdim // convertIf can remove TBB, FBB, and Tail can be merged into Head. 753239310Sdim // TBB and FBB should not dominate any blocks. 754239310Sdim // Tail children should be transferred to Head. 755239310Sdim MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); 756360784Sdim for (auto B : Removed) { 757360784Sdim MachineDomTreeNode *Node = DomTree->getNode(B); 758239310Sdim assert(Node != HeadNode && "Cannot erase the head node"); 759239310Sdim while (Node->getNumChildren()) { 760239310Sdim assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); 761239310Sdim DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); 762239310Sdim } 763360784Sdim DomTree->eraseNode(B); 764239310Sdim } 765239310Sdim} 766239310Sdim 767239310Sdim/// Update LoopInfo after if-conversion. 768360784Sdimvoid updateLoops(MachineLoopInfo *Loops, 769360784Sdim ArrayRef<MachineBasicBlock *> Removed) { 770239310Sdim if (!Loops) 771239310Sdim return; 772239310Sdim // If-conversion doesn't change loop structure, and it doesn't mess with back 773239310Sdim // edges, so updating LoopInfo is simply removing the dead blocks. 774360784Sdim for (auto B : Removed) 775360784Sdim Loops->removeBlock(B); 776239310Sdim} 777360784Sdim} // namespace 778239310Sdim 779239310Sdim/// Invalidate MachineTraceMetrics before if-conversion. 780239310Sdimvoid EarlyIfConverter::invalidateTraces() { 781239310Sdim Traces->verifyAnalysis(); 782239310Sdim Traces->invalidate(IfConv.Head); 783239310Sdim Traces->invalidate(IfConv.Tail); 784239310Sdim Traces->invalidate(IfConv.TBB); 785239310Sdim Traces->invalidate(IfConv.FBB); 786239310Sdim Traces->verifyAnalysis(); 787239310Sdim} 788239310Sdim 789239310Sdim// Adjust cycles with downward saturation. 790239310Sdimstatic unsigned adjCycles(unsigned Cyc, int Delta) { 791239310Sdim if (Delta < 0 && Cyc + Delta > Cyc) 792239310Sdim return 0; 793239310Sdim return Cyc + Delta; 794239310Sdim} 795239310Sdim 796239310Sdim/// Apply cost model and heuristics to the if-conversion in IfConv. 797239310Sdim/// Return true if the conversion is a good idea. 798239310Sdim/// 799239310Sdimbool EarlyIfConverter::shouldConvertIf() { 800239310Sdim // Stress testing mode disables all cost considerations. 801239310Sdim if (Stress) 802239310Sdim return true; 803239310Sdim 804239310Sdim if (!MinInstr) 805239310Sdim MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); 806239310Sdim 807239310Sdim MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred()); 808239310Sdim MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred()); 809341825Sdim LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace); 810239310Sdim unsigned MinCrit = std::min(TBBTrace.getCriticalPath(), 811239310Sdim FBBTrace.getCriticalPath()); 812239310Sdim 813239310Sdim // Set a somewhat arbitrary limit on the critical path extension we accept. 814280031Sdim unsigned CritLimit = SchedModel.MispredictPenalty/2; 815239310Sdim 816239310Sdim // If-conversion only makes sense when there is unexploited ILP. Compute the 817239310Sdim // maximum-ILP resource length of the trace after if-conversion. Compare it 818239310Sdim // to the shortest critical path. 819239310Sdim SmallVector<const MachineBasicBlock*, 1> ExtraBlocks; 820239310Sdim if (IfConv.TBB != IfConv.Tail) 821239310Sdim ExtraBlocks.push_back(IfConv.TBB); 822239310Sdim unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks); 823341825Sdim LLVM_DEBUG(dbgs() << "Resource length " << ResLength 824341825Sdim << ", minimal critical path " << MinCrit << '\n'); 825239310Sdim if (ResLength > MinCrit + CritLimit) { 826341825Sdim LLVM_DEBUG(dbgs() << "Not enough available ILP.\n"); 827239310Sdim return false; 828239310Sdim } 829239310Sdim 830239310Sdim // Assume that the depth of the first head terminator will also be the depth 831239310Sdim // of the select instruction inserted, as determined by the flag dependency. 832239310Sdim // TBB / FBB data dependencies may delay the select even more. 833239310Sdim MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head); 834239310Sdim unsigned BranchDepth = 835309124Sdim HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth; 836341825Sdim LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n'); 837239310Sdim 838239310Sdim // Look at all the tail phis, and compute the critical path extension caused 839239310Sdim // by inserting select instructions. 840239310Sdim MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail); 841239310Sdim for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) { 842239310Sdim SSAIfConv::PHIInfo &PI = IfConv.PHIs[i]; 843309124Sdim unsigned Slack = TailTrace.getInstrSlack(*PI.PHI); 844309124Sdim unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth; 845341825Sdim LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI); 846239310Sdim 847239310Sdim // The condition is pulled into the critical path. 848239310Sdim unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles); 849239310Sdim if (CondDepth > MaxDepth) { 850239310Sdim unsigned Extra = CondDepth - MaxDepth; 851341825Sdim LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n"); 852239310Sdim if (Extra > CritLimit) { 853341825Sdim LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 854239310Sdim return false; 855239310Sdim } 856239310Sdim } 857239310Sdim 858239310Sdim // The TBB value is pulled into the critical path. 859309124Sdim unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles); 860239310Sdim if (TDepth > MaxDepth) { 861239310Sdim unsigned Extra = TDepth - MaxDepth; 862341825Sdim LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n"); 863239310Sdim if (Extra > CritLimit) { 864341825Sdim LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 865239310Sdim return false; 866239310Sdim } 867239310Sdim } 868239310Sdim 869239310Sdim // The FBB value is pulled into the critical path. 870309124Sdim unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles); 871239310Sdim if (FDepth > MaxDepth) { 872239310Sdim unsigned Extra = FDepth - MaxDepth; 873341825Sdim LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n"); 874239310Sdim if (Extra > CritLimit) { 875341825Sdim LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 876239310Sdim return false; 877239310Sdim } 878239310Sdim } 879239310Sdim } 880239310Sdim return true; 881239310Sdim} 882239310Sdim 883239310Sdim/// Attempt repeated if-conversion on MBB, return true if successful. 884239310Sdim/// 885239310Sdimbool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { 886239310Sdim bool Changed = false; 887239310Sdim while (IfConv.canConvertIf(MBB) && shouldConvertIf()) { 888239310Sdim // If-convert MBB and update analyses. 889239310Sdim invalidateTraces(); 890239310Sdim SmallVector<MachineBasicBlock*, 4> RemovedBlocks; 891239310Sdim IfConv.convertIf(RemovedBlocks); 892239310Sdim Changed = true; 893360784Sdim updateDomTree(DomTree, IfConv, RemovedBlocks); 894360784Sdim updateLoops(Loops, RemovedBlocks); 895239310Sdim } 896239310Sdim return Changed; 897239310Sdim} 898239310Sdim 899239310Sdimbool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { 900341825Sdim LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" 901341825Sdim << "********** Function: " << MF.getName() << '\n'); 902327952Sdim if (skipFunction(MF.getFunction())) 903309124Sdim return false; 904309124Sdim 905276479Sdim // Only run if conversion if the target wants it. 906288943Sdim const TargetSubtargetInfo &STI = MF.getSubtarget(); 907288943Sdim if (!STI.enableEarlyIfConversion()) 908276479Sdim return false; 909276479Sdim 910288943Sdim TII = STI.getInstrInfo(); 911288943Sdim TRI = STI.getRegisterInfo(); 912288943Sdim SchedModel = STI.getSchedModel(); 913239310Sdim MRI = &MF.getRegInfo(); 914239310Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 915239310Sdim Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 916239310Sdim Traces = &getAnalysis<MachineTraceMetrics>(); 917276479Sdim MinInstr = nullptr; 918239310Sdim 919239310Sdim bool Changed = false; 920239310Sdim IfConv.runOnMachineFunction(MF); 921239310Sdim 922239310Sdim // Visit blocks in dominator tree post-order. The post-order enables nested 923239310Sdim // if-conversion in a single pass. The tryConvertIf() function may erase 924239310Sdim // blocks, but only blocks dominated by the head block. This makes it safe to 925239310Sdim // update the dominator tree while the post-order iterator is still active. 926288943Sdim for (auto DomNode : post_order(DomTree)) 927288943Sdim if (tryConvertIf(DomNode->getBlock())) 928239310Sdim Changed = true; 929239310Sdim 930239310Sdim return Changed; 931239310Sdim} 932360784Sdim 933360784Sdim//===----------------------------------------------------------------------===// 934360784Sdim// EarlyIfPredicator Pass 935360784Sdim//===----------------------------------------------------------------------===// 936360784Sdim 937360784Sdimnamespace { 938360784Sdimclass EarlyIfPredicator : public MachineFunctionPass { 939360784Sdim const TargetInstrInfo *TII; 940360784Sdim const TargetRegisterInfo *TRI; 941360784Sdim TargetSchedModel SchedModel; 942360784Sdim MachineRegisterInfo *MRI; 943360784Sdim MachineDominatorTree *DomTree; 944360784Sdim MachineBranchProbabilityInfo *MBPI; 945360784Sdim MachineLoopInfo *Loops; 946360784Sdim SSAIfConv IfConv; 947360784Sdim 948360784Sdimpublic: 949360784Sdim static char ID; 950360784Sdim EarlyIfPredicator() : MachineFunctionPass(ID) {} 951360784Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 952360784Sdim bool runOnMachineFunction(MachineFunction &MF) override; 953360784Sdim StringRef getPassName() const override { return "Early If-predicator"; } 954360784Sdim 955360784Sdimprotected: 956360784Sdim bool tryConvertIf(MachineBasicBlock *); 957360784Sdim bool shouldConvertIf(); 958360784Sdim}; 959360784Sdim} // end anonymous namespace 960360784Sdim 961360784Sdim#undef DEBUG_TYPE 962360784Sdim#define DEBUG_TYPE "early-if-predicator" 963360784Sdim 964360784Sdimchar EarlyIfPredicator::ID = 0; 965360784Sdimchar &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID; 966360784Sdim 967360784SdimINITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", 968360784Sdim false, false) 969360784SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 970360784SdimINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 971360784SdimINITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false, 972360784Sdim false) 973360784Sdim 974360784Sdimvoid EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const { 975360784Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 976360784Sdim AU.addRequired<MachineDominatorTree>(); 977360784Sdim AU.addPreserved<MachineDominatorTree>(); 978360784Sdim AU.addRequired<MachineLoopInfo>(); 979360784Sdim AU.addPreserved<MachineLoopInfo>(); 980360784Sdim MachineFunctionPass::getAnalysisUsage(AU); 981360784Sdim} 982360784Sdim 983360784Sdim/// Apply the target heuristic to decide if the transformation is profitable. 984360784Sdimbool EarlyIfPredicator::shouldConvertIf() { 985360784Sdim auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB); 986360784Sdim if (IfConv.isTriangle()) { 987360784Sdim MachineBasicBlock &IfBlock = 988360784Sdim (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB; 989360784Sdim 990360784Sdim unsigned ExtraPredCost = 0; 991360784Sdim unsigned Cycles = 0; 992360784Sdim for (MachineInstr &I : IfBlock) { 993360784Sdim unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 994360784Sdim if (NumCycles > 1) 995360784Sdim Cycles += NumCycles - 1; 996360784Sdim ExtraPredCost += TII->getPredicationCost(I); 997360784Sdim } 998360784Sdim 999360784Sdim return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost, 1000360784Sdim TrueProbability); 1001360784Sdim } 1002360784Sdim unsigned TExtra = 0; 1003360784Sdim unsigned FExtra = 0; 1004360784Sdim unsigned TCycle = 0; 1005360784Sdim unsigned FCycle = 0; 1006360784Sdim for (MachineInstr &I : *IfConv.TBB) { 1007360784Sdim unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 1008360784Sdim if (NumCycles > 1) 1009360784Sdim TCycle += NumCycles - 1; 1010360784Sdim TExtra += TII->getPredicationCost(I); 1011360784Sdim } 1012360784Sdim for (MachineInstr &I : *IfConv.FBB) { 1013360784Sdim unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 1014360784Sdim if (NumCycles > 1) 1015360784Sdim FCycle += NumCycles - 1; 1016360784Sdim FExtra += TII->getPredicationCost(I); 1017360784Sdim } 1018360784Sdim return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB, 1019360784Sdim FCycle, FExtra, TrueProbability); 1020360784Sdim} 1021360784Sdim 1022360784Sdim/// Attempt repeated if-conversion on MBB, return true if successful. 1023360784Sdim/// 1024360784Sdimbool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) { 1025360784Sdim bool Changed = false; 1026360784Sdim while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) { 1027360784Sdim // If-convert MBB and update analyses. 1028360784Sdim SmallVector<MachineBasicBlock *, 4> RemovedBlocks; 1029360784Sdim IfConv.convertIf(RemovedBlocks, /*Predicate*/ true); 1030360784Sdim Changed = true; 1031360784Sdim updateDomTree(DomTree, IfConv, RemovedBlocks); 1032360784Sdim updateLoops(Loops, RemovedBlocks); 1033360784Sdim } 1034360784Sdim return Changed; 1035360784Sdim} 1036360784Sdim 1037360784Sdimbool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) { 1038360784Sdim LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n" 1039360784Sdim << "********** Function: " << MF.getName() << '\n'); 1040360784Sdim if (skipFunction(MF.getFunction())) 1041360784Sdim return false; 1042360784Sdim 1043360784Sdim const TargetSubtargetInfo &STI = MF.getSubtarget(); 1044360784Sdim TII = STI.getInstrInfo(); 1045360784Sdim TRI = STI.getRegisterInfo(); 1046360784Sdim MRI = &MF.getRegInfo(); 1047360784Sdim SchedModel.init(&STI); 1048360784Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 1049360784Sdim Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 1050360784Sdim MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1051360784Sdim 1052360784Sdim bool Changed = false; 1053360784Sdim IfConv.runOnMachineFunction(MF); 1054360784Sdim 1055360784Sdim // Visit blocks in dominator tree post-order. The post-order enables nested 1056360784Sdim // if-conversion in a single pass. The tryConvertIf() function may erase 1057360784Sdim // blocks, but only blocks dominated by the head block. This makes it safe to 1058360784Sdim // update the dominator tree while the post-order iterator is still active. 1059360784Sdim for (auto DomNode : post_order(DomTree)) 1060360784Sdim if (tryConvertIf(DomNode->getBlock())) 1061360784Sdim Changed = true; 1062360784Sdim 1063360784Sdim return Changed; 1064360784Sdim} 1065