1//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Early if-conversion is for out-of-order CPUs that don't have a lot of 11// predicable instructions. The goal is to eliminate conditional branches that 12// may mispredict. 13// 14// Instructions from both sides of the branch are executed specutatively, and a 15// cmov instruction selects the result. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "early-ifcvt" 20#include "MachineTraceMetrics.h" 21#include "llvm/ADT/BitVector.h" 22#include "llvm/ADT/PostOrderIterator.h" 23#include "llvm/ADT/SetVector.h" 24#include "llvm/ADT/SmallPtrSet.h" 25#include "llvm/ADT/SparseSet.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 28#include "llvm/CodeGen/MachineDominators.h" 29#include "llvm/CodeGen/MachineFunction.h" 30#include "llvm/CodeGen/MachineFunctionPass.h" 31#include "llvm/CodeGen/MachineLoopInfo.h" 32#include "llvm/CodeGen/MachineRegisterInfo.h" 33#include "llvm/CodeGen/Passes.h" 34#include "llvm/MC/MCInstrItineraries.h" 35#include "llvm/Target/TargetInstrInfo.h" 36#include "llvm/Target/TargetRegisterInfo.h" 37#include "llvm/Support/CommandLine.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/Support/raw_ostream.h" 40 41using namespace llvm; 42 43// Absolute maximum number of instructions allowed per speculated block. 44// This bypasses all other heuristics, so it should be set fairly high. 45static cl::opt<unsigned> 46BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, 47 cl::desc("Maximum number of instructions per speculated block.")); 48 49// Stress testing mode - disable heuristics. 50static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden, 51 cl::desc("Turn all knobs to 11")); 52 53STATISTIC(NumDiamondsSeen, "Number of diamonds"); 54STATISTIC(NumDiamondsConv, "Number of diamonds converted"); 55STATISTIC(NumTrianglesSeen, "Number of triangles"); 56STATISTIC(NumTrianglesConv, "Number of triangles converted"); 57 58//===----------------------------------------------------------------------===// 59// SSAIfConv 60//===----------------------------------------------------------------------===// 61// 62// The SSAIfConv class performs if-conversion on SSA form machine code after 63// determining if it is possible. The class contains no heuristics; external 64// code should be used to determine when if-conversion is a good idea. 65// 66// SSAIfConv can convert both triangles and diamonds: 67// 68// Triangle: Head Diamond: Head 69// | \ / \_ 70// | \ / | 71// | [TF]BB FBB TBB 72// | / \ / 73// | / \ / 74// Tail Tail 75// 76// Instructions in the conditional blocks TBB and/or FBB are spliced into the 77// Head block, and phis in the Tail block are converted to select instructions. 78// 79namespace { 80class SSAIfConv { 81 const TargetInstrInfo *TII; 82 const TargetRegisterInfo *TRI; 83 MachineRegisterInfo *MRI; 84 85public: 86 /// The block containing the conditional branch. 87 MachineBasicBlock *Head; 88 89 /// The block containing phis after the if-then-else. 90 MachineBasicBlock *Tail; 91 92 /// The 'true' conditional block as determined by AnalyzeBranch. 93 MachineBasicBlock *TBB; 94 95 /// The 'false' conditional block as determined by AnalyzeBranch. 96 MachineBasicBlock *FBB; 97 98 /// isTriangle - When there is no 'else' block, either TBB or FBB will be 99 /// equal to Tail. 100 bool isTriangle() const { return TBB == Tail || FBB == Tail; } 101 102 /// Returns the Tail predecessor for the True side. 103 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; } 104 105 /// Returns the Tail predecessor for the False side. 106 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; } 107 108 /// Information about each phi in the Tail block. 109 struct PHIInfo { 110 MachineInstr *PHI; 111 unsigned TReg, FReg; 112 // Latencies from Cond+Branch, TReg, and FReg to DstReg. 113 int CondCycles, TCycles, FCycles; 114 115 PHIInfo(MachineInstr *phi) 116 : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {} 117 }; 118 119 SmallVector<PHIInfo, 8> PHIs; 120 121private: 122 /// The branch condition determined by AnalyzeBranch. 123 SmallVector<MachineOperand, 4> Cond; 124 125 /// Instructions in Head that define values used by the conditional blocks. 126 /// The hoisted instructions must be inserted after these instructions. 127 SmallPtrSet<MachineInstr*, 8> InsertAfter; 128 129 /// Register units clobbered by the conditional blocks. 130 BitVector ClobberedRegUnits; 131 132 // Scratch pad for findInsertionPoint. 133 SparseSet<unsigned> LiveRegUnits; 134 135 /// Insertion point in Head for speculatively executed instructions form TBB 136 /// and FBB. 137 MachineBasicBlock::iterator InsertionPoint; 138 139 /// Return true if all non-terminator instructions in MBB can be safely 140 /// speculated. 141 bool canSpeculateInstrs(MachineBasicBlock *MBB); 142 143 /// Find a valid insertion point in Head. 144 bool findInsertionPoint(); 145 146 /// Replace PHI instructions in Tail with selects. 147 void replacePHIInstrs(); 148 149 /// Insert selects and rewrite PHI operands to use them. 150 void rewritePHIOperands(); 151 152public: 153 /// runOnMachineFunction - Initialize per-function data structures. 154 void runOnMachineFunction(MachineFunction &MF) { 155 TII = MF.getTarget().getInstrInfo(); 156 TRI = MF.getTarget().getRegisterInfo(); 157 MRI = &MF.getRegInfo(); 158 LiveRegUnits.clear(); 159 LiveRegUnits.setUniverse(TRI->getNumRegUnits()); 160 ClobberedRegUnits.clear(); 161 ClobberedRegUnits.resize(TRI->getNumRegUnits()); 162 } 163 164 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted, 165 /// initialize the internal state, and return true. 166 bool canConvertIf(MachineBasicBlock *MBB); 167 168 /// convertIf - If-convert the last block passed to canConvertIf(), assuming 169 /// it is possible. Add any erased blocks to RemovedBlocks. 170 void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks); 171}; 172} // end anonymous namespace 173 174 175/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely 176/// be speculated. The terminators are not considered. 177/// 178/// If instructions use any values that are defined in the head basic block, 179/// the defining instructions are added to InsertAfter. 180/// 181/// Any clobbered regunits are added to ClobberedRegUnits. 182/// 183bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { 184 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 185 // get right. 186 if (!MBB->livein_empty()) { 187 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n"); 188 return false; 189 } 190 191 unsigned InstrCount = 0; 192 193 // Check all instructions, except the terminators. It is assumed that 194 // terminators never have side effects or define any used register values. 195 for (MachineBasicBlock::iterator I = MBB->begin(), 196 E = MBB->getFirstTerminator(); I != E; ++I) { 197 if (I->isDebugValue()) 198 continue; 199 200 if (++InstrCount > BlockInstrLimit && !Stress) { 201 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than " 202 << BlockInstrLimit << " instructions.\n"); 203 return false; 204 } 205 206 // There shouldn't normally be any phis in a single-predecessor block. 207 if (I->isPHI()) { 208 DEBUG(dbgs() << "Can't hoist: " << *I); 209 return false; 210 } 211 212 // Don't speculate loads. Note that it may be possible and desirable to 213 // speculate GOT or constant pool loads that are guaranteed not to trap, 214 // but we don't support that for now. 215 if (I->mayLoad()) { 216 DEBUG(dbgs() << "Won't speculate load: " << *I); 217 return false; 218 } 219 220 // We never speculate stores, so an AA pointer isn't necessary. 221 bool DontMoveAcrossStore = true; 222 if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) { 223 DEBUG(dbgs() << "Can't speculate: " << *I); 224 return false; 225 } 226 227 // Check for any dependencies on Head instructions. 228 for (MIOperands MO(I); MO.isValid(); ++MO) { 229 if (MO->isRegMask()) { 230 DEBUG(dbgs() << "Won't speculate regmask: " << *I); 231 return false; 232 } 233 if (!MO->isReg()) 234 continue; 235 unsigned Reg = MO->getReg(); 236 237 // Remember clobbered regunits. 238 if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) 239 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 240 ClobberedRegUnits.set(*Units); 241 242 if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg)) 243 continue; 244 MachineInstr *DefMI = MRI->getVRegDef(Reg); 245 if (!DefMI || DefMI->getParent() != Head) 246 continue; 247 if (InsertAfter.insert(DefMI)) 248 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI); 249 if (DefMI->isTerminator()) { 250 DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); 251 return false; 252 } 253 } 254 } 255 return true; 256} 257 258 259/// Find an insertion point in Head for the speculated instructions. The 260/// insertion point must be: 261/// 262/// 1. Before any terminators. 263/// 2. After any instructions in InsertAfter. 264/// 3. Not have any clobbered regunits live. 265/// 266/// This function sets InsertionPoint and returns true when successful, it 267/// returns false if no valid insertion point could be found. 268/// 269bool SSAIfConv::findInsertionPoint() { 270 // Keep track of live regunits before the current position. 271 // Only track RegUnits that are also in ClobberedRegUnits. 272 LiveRegUnits.clear(); 273 SmallVector<unsigned, 8> Reads; 274 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 275 MachineBasicBlock::iterator I = Head->end(); 276 MachineBasicBlock::iterator B = Head->begin(); 277 while (I != B) { 278 --I; 279 // Some of the conditional code depends in I. 280 if (InsertAfter.count(I)) { 281 DEBUG(dbgs() << "Can't insert code after " << *I); 282 return false; 283 } 284 285 // Update live regunits. 286 for (MIOperands MO(I); MO.isValid(); ++MO) { 287 // We're ignoring regmask operands. That is conservatively correct. 288 if (!MO->isReg()) 289 continue; 290 unsigned Reg = MO->getReg(); 291 if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 292 continue; 293 // I clobbers Reg, so it isn't live before I. 294 if (MO->isDef()) 295 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 296 LiveRegUnits.erase(*Units); 297 // Unless I reads Reg. 298 if (MO->readsReg()) 299 Reads.push_back(Reg); 300 } 301 // Anything read by I is live before I. 302 while (!Reads.empty()) 303 for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid(); 304 ++Units) 305 if (ClobberedRegUnits.test(*Units)) 306 LiveRegUnits.insert(*Units); 307 308 // We can't insert before a terminator. 309 if (I != FirstTerm && I->isTerminator()) 310 continue; 311 312 // Some of the clobbered registers are live before I, not a valid insertion 313 // point. 314 if (!LiveRegUnits.empty()) { 315 DEBUG({ 316 dbgs() << "Would clobber"; 317 for (SparseSet<unsigned>::const_iterator 318 i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i) 319 dbgs() << ' ' << PrintRegUnit(*i, TRI); 320 dbgs() << " live before " << *I; 321 }); 322 continue; 323 } 324 325 // This is a valid insertion point. 326 InsertionPoint = I; 327 DEBUG(dbgs() << "Can insert before " << *I); 328 return true; 329 } 330 DEBUG(dbgs() << "No legal insertion point found.\n"); 331 return false; 332} 333 334 335 336/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is 337/// a potential candidate for if-conversion. Fill out the internal state. 338/// 339bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { 340 Head = MBB; 341 TBB = FBB = Tail = 0; 342 343 if (Head->succ_size() != 2) 344 return false; 345 MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 346 MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 347 348 // Canonicalize so Succ0 has MBB as its single predecessor. 349 if (Succ0->pred_size() != 1) 350 std::swap(Succ0, Succ1); 351 352 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) 353 return false; 354 355 Tail = Succ0->succ_begin()[0]; 356 357 // This is not a triangle. 358 if (Tail != Succ1) { 359 // Check for a diamond. We won't deal with any critical edges. 360 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || 361 Succ1->succ_begin()[0] != Tail) 362 return false; 363 DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber() 364 << " -> BB#" << Succ0->getNumber() 365 << "/BB#" << Succ1->getNumber() 366 << " -> BB#" << Tail->getNumber() << '\n'); 367 368 // Live-in physregs are tricky to get right when speculating code. 369 if (!Tail->livein_empty()) { 370 DEBUG(dbgs() << "Tail has live-ins.\n"); 371 return false; 372 } 373 } else { 374 DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() 375 << " -> BB#" << Succ0->getNumber() 376 << " -> BB#" << Tail->getNumber() << '\n'); 377 } 378 379 // This is a triangle or a diamond. 380 // If Tail doesn't have any phis, there must be side effects. 381 if (Tail->empty() || !Tail->front().isPHI()) { 382 DEBUG(dbgs() << "No phis in tail.\n"); 383 return false; 384 } 385 386 // The branch we're looking to eliminate must be analyzable. 387 Cond.clear(); 388 if (TII->AnalyzeBranch(*Head, TBB, FBB, Cond)) { 389 DEBUG(dbgs() << "Branch not analyzable.\n"); 390 return false; 391 } 392 393 // This is weird, probably some sort of degenerate CFG. 394 if (!TBB) { 395 DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n"); 396 return false; 397 } 398 399 // AnalyzeBranch doesn't set FBB on a fall-through branch. 400 // Make sure it is always set. 401 FBB = TBB == Succ0 ? Succ1 : Succ0; 402 403 // Any phis in the tail block must be convertible to selects. 404 PHIs.clear(); 405 MachineBasicBlock *TPred = getTPred(); 406 MachineBasicBlock *FPred = getFPred(); 407 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); 408 I != E && I->isPHI(); ++I) { 409 PHIs.push_back(&*I); 410 PHIInfo &PI = PHIs.back(); 411 // Find PHI operands corresponding to TPred and FPred. 412 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { 413 if (PI.PHI->getOperand(i+1).getMBB() == TPred) 414 PI.TReg = PI.PHI->getOperand(i).getReg(); 415 if (PI.PHI->getOperand(i+1).getMBB() == FPred) 416 PI.FReg = PI.PHI->getOperand(i).getReg(); 417 } 418 assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI"); 419 assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI"); 420 421 // Get target information. 422 if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg, 423 PI.CondCycles, PI.TCycles, PI.FCycles)) { 424 DEBUG(dbgs() << "Can't convert: " << *PI.PHI); 425 return false; 426 } 427 } 428 429 // Check that the conditional instructions can be speculated. 430 InsertAfter.clear(); 431 ClobberedRegUnits.reset(); 432 if (TBB != Tail && !canSpeculateInstrs(TBB)) 433 return false; 434 if (FBB != Tail && !canSpeculateInstrs(FBB)) 435 return false; 436 437 // Try to find a valid insertion point for the speculated instructions in the 438 // head basic block. 439 if (!findInsertionPoint()) 440 return false; 441 442 if (isTriangle()) 443 ++NumTrianglesSeen; 444 else 445 ++NumDiamondsSeen; 446 return true; 447} 448 449/// replacePHIInstrs - Completely replace PHI instructions with selects. 450/// This is possible when the only Tail predecessors are the if-converted 451/// blocks. 452void SSAIfConv::replacePHIInstrs() { 453 assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); 454 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 455 assert(FirstTerm != Head->end() && "No terminators"); 456 DebugLoc HeadDL = FirstTerm->getDebugLoc(); 457 458 // Convert all PHIs to select instructions inserted before FirstTerm. 459 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 460 PHIInfo &PI = PHIs[i]; 461 DEBUG(dbgs() << "If-converting " << *PI.PHI); 462 assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands."); 463 unsigned DstReg = PI.PHI->getOperand(0).getReg(); 464 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 465 DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm)); 466 PI.PHI->eraseFromParent(); 467 PI.PHI = 0; 468 } 469} 470 471/// rewritePHIOperands - When there are additional Tail predecessors, insert 472/// select instructions in Head and rewrite PHI operands to use the selects. 473/// Keep the PHI instructions in Tail to handle the other predecessors. 474void SSAIfConv::rewritePHIOperands() { 475 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 476 assert(FirstTerm != Head->end() && "No terminators"); 477 DebugLoc HeadDL = FirstTerm->getDebugLoc(); 478 479 // Convert all PHIs to select instructions inserted before FirstTerm. 480 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 481 PHIInfo &PI = PHIs[i]; 482 DEBUG(dbgs() << "If-converting " << *PI.PHI); 483 unsigned PHIDst = PI.PHI->getOperand(0).getReg(); 484 unsigned DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); 485 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 486 DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm)); 487 488 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. 489 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { 490 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); 491 if (MBB == getTPred()) { 492 PI.PHI->getOperand(i-1).setMBB(Head); 493 PI.PHI->getOperand(i-2).setReg(DstReg); 494 } else if (MBB == getFPred()) { 495 PI.PHI->RemoveOperand(i-1); 496 PI.PHI->RemoveOperand(i-2); 497 } 498 } 499 DEBUG(dbgs() << " --> " << *PI.PHI); 500 } 501} 502 503/// convertIf - Execute the if conversion after canConvertIf has determined the 504/// feasibility. 505/// 506/// Any basic blocks erased will be added to RemovedBlocks. 507/// 508void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) { 509 assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); 510 511 // Update statistics. 512 if (isTriangle()) 513 ++NumTrianglesConv; 514 else 515 ++NumDiamondsConv; 516 517 // Move all instructions into Head, except for the terminators. 518 if (TBB != Tail) 519 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); 520 if (FBB != Tail) 521 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); 522 523 // Are there extra Tail predecessors? 524 bool ExtraPreds = Tail->pred_size() != 2; 525 if (ExtraPreds) 526 rewritePHIOperands(); 527 else 528 replacePHIInstrs(); 529 530 // Fix up the CFG, temporarily leave Head without any successors. 531 Head->removeSuccessor(TBB); 532 Head->removeSuccessor(FBB); 533 if (TBB != Tail) 534 TBB->removeSuccessor(Tail); 535 if (FBB != Tail) 536 FBB->removeSuccessor(Tail); 537 538 // Fix up Head's terminators. 539 // It should become a single branch or a fallthrough. 540 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); 541 TII->RemoveBranch(*Head); 542 543 // Erase the now empty conditional blocks. It is likely that Head can fall 544 // through to Tail, and we can join the two blocks. 545 if (TBB != Tail) { 546 RemovedBlocks.push_back(TBB); 547 TBB->eraseFromParent(); 548 } 549 if (FBB != Tail) { 550 RemovedBlocks.push_back(FBB); 551 FBB->eraseFromParent(); 552 } 553 554 assert(Head->succ_empty() && "Additional head successors?"); 555 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { 556 // Splice Tail onto the end of Head. 557 DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber() 558 << " into head BB#" << Head->getNumber() << '\n'); 559 Head->splice(Head->end(), Tail, 560 Tail->begin(), Tail->end()); 561 Head->transferSuccessorsAndUpdatePHIs(Tail); 562 RemovedBlocks.push_back(Tail); 563 Tail->eraseFromParent(); 564 } else { 565 // We need a branch to Tail, let code placement work it out later. 566 DEBUG(dbgs() << "Converting to unconditional branch.\n"); 567 SmallVector<MachineOperand, 0> EmptyCond; 568 TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL); 569 Head->addSuccessor(Tail); 570 } 571 DEBUG(dbgs() << *Head); 572} 573 574 575//===----------------------------------------------------------------------===// 576// EarlyIfConverter Pass 577//===----------------------------------------------------------------------===// 578 579namespace { 580class EarlyIfConverter : public MachineFunctionPass { 581 const TargetInstrInfo *TII; 582 const TargetRegisterInfo *TRI; 583 const MCSchedModel *SchedModel; 584 MachineRegisterInfo *MRI; 585 MachineDominatorTree *DomTree; 586 MachineLoopInfo *Loops; 587 MachineTraceMetrics *Traces; 588 MachineTraceMetrics::Ensemble *MinInstr; 589 SSAIfConv IfConv; 590 591public: 592 static char ID; 593 EarlyIfConverter() : MachineFunctionPass(ID) {} 594 void getAnalysisUsage(AnalysisUsage &AU) const; 595 bool runOnMachineFunction(MachineFunction &MF); 596 597private: 598 bool tryConvertIf(MachineBasicBlock*); 599 void updateDomTree(ArrayRef<MachineBasicBlock*> Removed); 600 void updateLoops(ArrayRef<MachineBasicBlock*> Removed); 601 void invalidateTraces(); 602 bool shouldConvertIf(); 603}; 604} // end anonymous namespace 605 606char EarlyIfConverter::ID = 0; 607char &llvm::EarlyIfConverterID = EarlyIfConverter::ID; 608 609INITIALIZE_PASS_BEGIN(EarlyIfConverter, 610 "early-ifcvt", "Early If Converter", false, false) 611INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 612INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 613INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) 614INITIALIZE_PASS_END(EarlyIfConverter, 615 "early-ifcvt", "Early If Converter", false, false) 616 617void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const { 618 AU.addRequired<MachineBranchProbabilityInfo>(); 619 AU.addRequired<MachineDominatorTree>(); 620 AU.addPreserved<MachineDominatorTree>(); 621 AU.addRequired<MachineLoopInfo>(); 622 AU.addPreserved<MachineLoopInfo>(); 623 AU.addRequired<MachineTraceMetrics>(); 624 AU.addPreserved<MachineTraceMetrics>(); 625 MachineFunctionPass::getAnalysisUsage(AU); 626} 627 628/// Update the dominator tree after if-conversion erased some blocks. 629void EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) { 630 // convertIf can remove TBB, FBB, and Tail can be merged into Head. 631 // TBB and FBB should not dominate any blocks. 632 // Tail children should be transferred to Head. 633 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); 634 for (unsigned i = 0, e = Removed.size(); i != e; ++i) { 635 MachineDomTreeNode *Node = DomTree->getNode(Removed[i]); 636 assert(Node != HeadNode && "Cannot erase the head node"); 637 while (Node->getNumChildren()) { 638 assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); 639 DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); 640 } 641 DomTree->eraseNode(Removed[i]); 642 } 643} 644 645/// Update LoopInfo after if-conversion. 646void EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) { 647 if (!Loops) 648 return; 649 // If-conversion doesn't change loop structure, and it doesn't mess with back 650 // edges, so updating LoopInfo is simply removing the dead blocks. 651 for (unsigned i = 0, e = Removed.size(); i != e; ++i) 652 Loops->removeBlock(Removed[i]); 653} 654 655/// Invalidate MachineTraceMetrics before if-conversion. 656void EarlyIfConverter::invalidateTraces() { 657 Traces->verifyAnalysis(); 658 Traces->invalidate(IfConv.Head); 659 Traces->invalidate(IfConv.Tail); 660 Traces->invalidate(IfConv.TBB); 661 Traces->invalidate(IfConv.FBB); 662 Traces->verifyAnalysis(); 663} 664 665// Adjust cycles with downward saturation. 666static unsigned adjCycles(unsigned Cyc, int Delta) { 667 if (Delta < 0 && Cyc + Delta > Cyc) 668 return 0; 669 return Cyc + Delta; 670} 671 672/// Apply cost model and heuristics to the if-conversion in IfConv. 673/// Return true if the conversion is a good idea. 674/// 675bool EarlyIfConverter::shouldConvertIf() { 676 // Stress testing mode disables all cost considerations. 677 if (Stress) 678 return true; 679 680 if (!MinInstr) 681 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); 682 683 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred()); 684 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred()); 685 DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace); 686 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(), 687 FBBTrace.getCriticalPath()); 688 689 // Set a somewhat arbitrary limit on the critical path extension we accept. 690 unsigned CritLimit = SchedModel->MispredictPenalty/2; 691 692 // If-conversion only makes sense when there is unexploited ILP. Compute the 693 // maximum-ILP resource length of the trace after if-conversion. Compare it 694 // to the shortest critical path. 695 SmallVector<const MachineBasicBlock*, 1> ExtraBlocks; 696 if (IfConv.TBB != IfConv.Tail) 697 ExtraBlocks.push_back(IfConv.TBB); 698 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks); 699 DEBUG(dbgs() << "Resource length " << ResLength 700 << ", minimal critical path " << MinCrit << '\n'); 701 if (ResLength > MinCrit + CritLimit) { 702 DEBUG(dbgs() << "Not enough available ILP.\n"); 703 return false; 704 } 705 706 // Assume that the depth of the first head terminator will also be the depth 707 // of the select instruction inserted, as determined by the flag dependency. 708 // TBB / FBB data dependencies may delay the select even more. 709 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head); 710 unsigned BranchDepth = 711 HeadTrace.getInstrCycles(IfConv.Head->getFirstTerminator()).Depth; 712 DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n'); 713 714 // Look at all the tail phis, and compute the critical path extension caused 715 // by inserting select instructions. 716 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail); 717 for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) { 718 SSAIfConv::PHIInfo &PI = IfConv.PHIs[i]; 719 unsigned Slack = TailTrace.getInstrSlack(PI.PHI); 720 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(PI.PHI).Depth; 721 DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI); 722 723 // The condition is pulled into the critical path. 724 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles); 725 if (CondDepth > MaxDepth) { 726 unsigned Extra = CondDepth - MaxDepth; 727 DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n"); 728 if (Extra > CritLimit) { 729 DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 730 return false; 731 } 732 } 733 734 // The TBB value is pulled into the critical path. 735 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(PI.PHI), PI.TCycles); 736 if (TDepth > MaxDepth) { 737 unsigned Extra = TDepth - MaxDepth; 738 DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n"); 739 if (Extra > CritLimit) { 740 DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 741 return false; 742 } 743 } 744 745 // The FBB value is pulled into the critical path. 746 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(PI.PHI), PI.FCycles); 747 if (FDepth > MaxDepth) { 748 unsigned Extra = FDepth - MaxDepth; 749 DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n"); 750 if (Extra > CritLimit) { 751 DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 752 return false; 753 } 754 } 755 } 756 return true; 757} 758 759/// Attempt repeated if-conversion on MBB, return true if successful. 760/// 761bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { 762 bool Changed = false; 763 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) { 764 // If-convert MBB and update analyses. 765 invalidateTraces(); 766 SmallVector<MachineBasicBlock*, 4> RemovedBlocks; 767 IfConv.convertIf(RemovedBlocks); 768 Changed = true; 769 updateDomTree(RemovedBlocks); 770 updateLoops(RemovedBlocks); 771 } 772 return Changed; 773} 774 775bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { 776 DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" 777 << "********** Function: " << MF.getName() << '\n'); 778 TII = MF.getTarget().getInstrInfo(); 779 TRI = MF.getTarget().getRegisterInfo(); 780 SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel; 781 MRI = &MF.getRegInfo(); 782 DomTree = &getAnalysis<MachineDominatorTree>(); 783 Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 784 Traces = &getAnalysis<MachineTraceMetrics>(); 785 MinInstr = 0; 786 787 bool Changed = false; 788 IfConv.runOnMachineFunction(MF); 789 790 // Visit blocks in dominator tree post-order. The post-order enables nested 791 // if-conversion in a single pass. The tryConvertIf() function may erase 792 // blocks, but only blocks dominated by the head block. This makes it safe to 793 // update the dominator tree while the post-order iterator is still active. 794 for (po_iterator<MachineDominatorTree*> 795 I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I) 796 if (tryConvertIf(I->getBlock())) 797 Changed = true; 798 799 MF.verify(this, "After early if-conversion"); 800 return Changed; 801} 802