EarlyIfConversion.cpp revision 870da6de2c3f3f40360e04882b9ddf42ded0930a
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/Function.h" 22#include "llvm/ADT/BitVector.h" 23#include "llvm/ADT/PostOrderIterator.h" 24#include "llvm/ADT/SetVector.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include "llvm/ADT/SparseSet.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 53typedef SmallSetVector<MachineBasicBlock*, 8> BlockSetVector; 54 55//===----------------------------------------------------------------------===// 56// SSAIfConv 57//===----------------------------------------------------------------------===// 58// 59// The SSAIfConv class performs if-conversion on SSA form machine code after 60// determining if it is possible. The class contains no heuristics; external 61// code should be used to determine when if-conversion is a good idea. 62// 63// SSAIfConv can convert both triangles and diamonds: 64// 65// Triangle: Head Diamond: Head 66// | \ / \_ 67// | \ / | 68// | [TF]BB FBB TBB 69// | / \ / 70// | / \ / 71// Tail Tail 72// 73// Instructions in the conditional blocks TBB and/or FBB are spliced into the 74// Head block, and phis in the Tail block are converted to select instructions. 75// 76namespace { 77class SSAIfConv { 78 const TargetInstrInfo *TII; 79 const TargetRegisterInfo *TRI; 80 MachineRegisterInfo *MRI; 81 82public: 83 /// The block containing the conditional branch. 84 MachineBasicBlock *Head; 85 86 /// The block containing phis after the if-then-else. 87 MachineBasicBlock *Tail; 88 89 /// The 'true' conditional block as determined by AnalyzeBranch. 90 MachineBasicBlock *TBB; 91 92 /// The 'false' conditional block as determined by AnalyzeBranch. 93 MachineBasicBlock *FBB; 94 95 /// isTriangle - When there is no 'else' block, either TBB or FBB will be 96 /// equal to Tail. 97 bool isTriangle() const { return TBB == Tail || FBB == Tail; } 98 99 /// Returns the Tail predecessor for the True side. 100 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; } 101 102 /// Returns the Tail predecessor for the False side. 103 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; } 104 105 /// Information about each phi in the Tail block. 106 struct PHIInfo { 107 MachineInstr *PHI; 108 unsigned TReg, FReg; 109 // Latencies from Cond+Branch, TReg, and FReg to DstReg. 110 int CondCycles, TCycles, FCycles; 111 112 PHIInfo(MachineInstr *phi) 113 : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {} 114 }; 115 116 SmallVector<PHIInfo, 8> PHIs; 117 118private: 119 /// The branch condition determined by AnalyzeBranch. 120 SmallVector<MachineOperand, 4> Cond; 121 122 /// Instructions in Head that define values used by the conditional blocks. 123 /// The hoisted instructions must be inserted after these instructions. 124 SmallPtrSet<MachineInstr*, 8> InsertAfter; 125 126 /// Register units clobbered by the conditional blocks. 127 BitVector ClobberedRegUnits; 128 129 // Scratch pad for findInsertionPoint. 130 SparseSet<unsigned> LiveRegUnits; 131 132 /// Insertion point in Head for speculatively executed instructions form TBB 133 /// and FBB. 134 MachineBasicBlock::iterator InsertionPoint; 135 136 /// Return true if all non-terminator instructions in MBB can be safely 137 /// speculated. 138 bool canSpeculateInstrs(MachineBasicBlock *MBB); 139 140 /// Find a valid insertion point in Head. 141 bool findInsertionPoint(); 142 143public: 144 /// runOnMachineFunction - Initialize per-function data structures. 145 void runOnMachineFunction(MachineFunction &MF) { 146 TII = MF.getTarget().getInstrInfo(); 147 TRI = MF.getTarget().getRegisterInfo(); 148 MRI = &MF.getRegInfo(); 149 LiveRegUnits.clear(); 150 LiveRegUnits.setUniverse(TRI->getNumRegUnits()); 151 ClobberedRegUnits.clear(); 152 ClobberedRegUnits.resize(TRI->getNumRegUnits()); 153 } 154 155 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted, 156 /// initialize the internal state, and return true. 157 bool canConvertIf(MachineBasicBlock *MBB); 158 159 /// convertIf - If-convert the last block passed to canConvertIf(), assuming 160 /// it is possible. Add any erased blocks to RemovedBlocks. 161 void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks); 162}; 163} // end anonymous namespace 164 165 166/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely 167/// be speculated. The terminators are not considered. 168/// 169/// If instructions use any values that are defined in the head basic block, 170/// the defining instructions are added to InsertAfter. 171/// 172/// Any clobbered regunits are added to ClobberedRegUnits. 173/// 174bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { 175 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 176 // get right. 177 if (!MBB->livein_empty()) { 178 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n"); 179 return false; 180 } 181 182 unsigned InstrCount = 0; 183 184 // Check all instructions, except the terminators. It is assumed that 185 // terminators never have side effects or define any used register values. 186 for (MachineBasicBlock::iterator I = MBB->begin(), 187 E = MBB->getFirstTerminator(); I != E; ++I) { 188 if (I->isDebugValue()) 189 continue; 190 191 if (++InstrCount > BlockInstrLimit && !Stress) { 192 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than " 193 << BlockInstrLimit << " instructions.\n"); 194 return false; 195 } 196 197 // There shouldn't normally be any phis in a single-predecessor block. 198 if (I->isPHI()) { 199 DEBUG(dbgs() << "Can't hoist: " << *I); 200 return false; 201 } 202 203 // Don't speculate loads. Note that it may be possible and desirable to 204 // speculate GOT or constant pool loads that are guaranteed not to trap, 205 // but we don't support that for now. 206 if (I->mayLoad()) { 207 DEBUG(dbgs() << "Won't speculate load: " << *I); 208 return false; 209 } 210 211 // We never speculate stores, so an AA pointer isn't necessary. 212 bool DontMoveAcrossStore = true; 213 if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) { 214 DEBUG(dbgs() << "Can't speculate: " << *I); 215 return false; 216 } 217 218 // Check for any dependencies on Head instructions. 219 for (MIOperands MO(I); MO.isValid(); ++MO) { 220 if (MO->isRegMask()) { 221 DEBUG(dbgs() << "Won't speculate regmask: " << *I); 222 return false; 223 } 224 if (!MO->isReg()) 225 continue; 226 unsigned Reg = MO->getReg(); 227 228 // Remember clobbered regunits. 229 if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) 230 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 231 ClobberedRegUnits.set(*Units); 232 233 if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg)) 234 continue; 235 MachineInstr *DefMI = MRI->getVRegDef(Reg); 236 if (!DefMI || DefMI->getParent() != Head) 237 continue; 238 if (InsertAfter.insert(DefMI)) 239 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI); 240 if (DefMI->isTerminator()) { 241 DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); 242 return false; 243 } 244 } 245 } 246 return true; 247} 248 249 250/// Find an insertion point in Head for the speculated instructions. The 251/// insertion point must be: 252/// 253/// 1. Before any terminators. 254/// 2. After any instructions in InsertAfter. 255/// 3. Not have any clobbered regunits live. 256/// 257/// This function sets InsertionPoint and returns true when successful, it 258/// returns false if no valid insertion point could be found. 259/// 260bool SSAIfConv::findInsertionPoint() { 261 // Keep track of live regunits before the current position. 262 // Only track RegUnits that are also in ClobberedRegUnits. 263 LiveRegUnits.clear(); 264 SmallVector<unsigned, 8> Reads; 265 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 266 MachineBasicBlock::iterator I = Head->end(); 267 MachineBasicBlock::iterator B = Head->begin(); 268 while (I != B) { 269 --I; 270 // Some of the conditional code depends in I. 271 if (InsertAfter.count(I)) { 272 DEBUG(dbgs() << "Can't insert code after " << *I); 273 return false; 274 } 275 276 // Update live regunits. 277 for (MIOperands MO(I); MO.isValid(); ++MO) { 278 // We're ignoring regmask operands. That is conservatively correct. 279 if (!MO->isReg()) 280 continue; 281 unsigned Reg = MO->getReg(); 282 if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 283 continue; 284 // I clobbers Reg, so it isn't live before I. 285 if (MO->isDef()) 286 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 287 LiveRegUnits.erase(*Units); 288 // Unless I reads Reg. 289 if (MO->readsReg()) 290 Reads.push_back(Reg); 291 } 292 // Anything read by I is live before I. 293 while (!Reads.empty()) 294 for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid(); 295 ++Units) 296 if (ClobberedRegUnits.test(*Units)) 297 LiveRegUnits.insert(*Units); 298 299 // We can't insert before a terminator. 300 if (I != FirstTerm && I->isTerminator()) 301 continue; 302 303 // Some of the clobbered registers are live before I, not a valid insertion 304 // point. 305 if (!LiveRegUnits.empty()) { 306 DEBUG({ 307 dbgs() << "Would clobber"; 308 for (SparseSet<unsigned>::const_iterator 309 i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i) 310 dbgs() << ' ' << PrintRegUnit(*i, TRI); 311 dbgs() << " live before " << *I; 312 }); 313 continue; 314 } 315 316 // This is a valid insertion point. 317 InsertionPoint = I; 318 DEBUG(dbgs() << "Can insert before " << *I); 319 return true; 320 } 321 DEBUG(dbgs() << "No legal insertion point found.\n"); 322 return false; 323} 324 325 326 327/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is 328/// a potential candidate for if-conversion. Fill out the internal state. 329/// 330bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { 331 Head = MBB; 332 TBB = FBB = Tail = 0; 333 334 if (Head->succ_size() != 2) 335 return false; 336 MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 337 MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 338 339 // Canonicalize so Succ0 has MBB as its single predecessor. 340 if (Succ0->pred_size() != 1) 341 std::swap(Succ0, Succ1); 342 343 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) 344 return false; 345 346 // We could support additional Tail predecessors by updating phis instead of 347 // eliminating them. Let's see an example where it matters first. 348 Tail = Succ0->succ_begin()[0]; 349 if (Tail->pred_size() != 2) 350 return false; 351 352 // This is not a triangle. 353 if (Tail != Succ1) { 354 // Check for a diamond. We won't deal with any critical edges. 355 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || 356 Succ1->succ_begin()[0] != Tail) 357 return false; 358 DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber() 359 << " -> BB#" << Succ0->getNumber() 360 << "/BB#" << Succ1->getNumber() 361 << " -> BB#" << Tail->getNumber() << '\n'); 362 363 // Live-in physregs are tricky to get right when speculating code. 364 if (!Tail->livein_empty()) { 365 DEBUG(dbgs() << "Tail has live-ins.\n"); 366 return false; 367 } 368 } else { 369 DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() 370 << " -> BB#" << Succ0->getNumber() 371 << " -> BB#" << Tail->getNumber() << '\n'); 372 } 373 374 // This is a triangle or a diamond. 375 // If Tail doesn't have any phis, there must be side effects. 376 if (Tail->empty() || !Tail->front().isPHI()) { 377 DEBUG(dbgs() << "No phis in tail.\n"); 378 return false; 379 } 380 381 // The branch we're looking to eliminate must be analyzable. 382 Cond.clear(); 383 if (TII->AnalyzeBranch(*Head, TBB, FBB, Cond)) { 384 DEBUG(dbgs() << "Branch not analyzable.\n"); 385 return false; 386 } 387 388 // This is weird, probably some sort of degenerate CFG. 389 if (!TBB) { 390 DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n"); 391 return false; 392 } 393 394 // AnalyzeBranch doesn't set FBB on a fall-through branch. 395 // Make sure it is always set. 396 FBB = TBB == Succ0 ? Succ1 : Succ0; 397 398 // Any phis in the tail block must be convertible to selects. 399 PHIs.clear(); 400 MachineBasicBlock *TPred = getTPred(); 401 MachineBasicBlock *FPred = getFPred(); 402 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); 403 I != E && I->isPHI(); ++I) { 404 PHIs.push_back(&*I); 405 PHIInfo &PI = PHIs.back(); 406 // Find PHI operands corresponding to TPred and FPred. 407 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { 408 if (PI.PHI->getOperand(i+1).getMBB() == TPred) 409 PI.TReg = PI.PHI->getOperand(i).getReg(); 410 if (PI.PHI->getOperand(i+1).getMBB() == FPred) 411 PI.FReg = PI.PHI->getOperand(i).getReg(); 412 } 413 assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI"); 414 assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI"); 415 416 // Get target information. 417 if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg, 418 PI.CondCycles, PI.TCycles, PI.FCycles)) { 419 DEBUG(dbgs() << "Can't convert: " << *PI.PHI); 420 return false; 421 } 422 } 423 424 // Check that the conditional instructions can be speculated. 425 InsertAfter.clear(); 426 ClobberedRegUnits.reset(); 427 if (TBB != Tail && !canSpeculateInstrs(TBB)) 428 return false; 429 if (FBB != Tail && !canSpeculateInstrs(FBB)) 430 return false; 431 432 // Try to find a valid insertion point for the speculated instructions in the 433 // head basic block. 434 if (!findInsertionPoint()) 435 return false; 436 437 return true; 438} 439 440 441/// convertIf - Execute the if conversion after canConvertIf has determined the 442/// feasibility. 443/// 444/// Any basic blocks erased will be added to RemovedBlocks. 445/// 446void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) { 447 assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); 448 449 // Move all instructions into Head, except for the terminators. 450 if (TBB != Tail) 451 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); 452 if (FBB != Tail) 453 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); 454 455 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 456 assert(FirstTerm != Head->end() && "No terminators"); 457 DebugLoc HeadDL = FirstTerm->getDebugLoc(); 458 459 // Convert all PHIs to select instructions inserted before FirstTerm. 460 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 461 PHIInfo &PI = PHIs[i]; 462 DEBUG(dbgs() << "If-converting " << *PI.PHI); 463 assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands."); 464 unsigned DstReg = PI.PHI->getOperand(0).getReg(); 465 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 466 DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm)); 467 PI.PHI->eraseFromParent(); 468 PI.PHI = 0; 469 } 470 471 // Fix up the CFG, temporarily leave Head without any successors. 472 Head->removeSuccessor(TBB); 473 Head->removeSuccessor(FBB); 474 if (TBB != Tail) 475 TBB->removeSuccessor(Tail); 476 if (FBB != Tail) 477 FBB->removeSuccessor(Tail); 478 479 // Fix up Head's terminators. 480 // It should become a single branch or a fallthrough. 481 TII->RemoveBranch(*Head); 482 483 // Erase the now empty conditional blocks. It is likely that Head can fall 484 // through to Tail, and we can join the two blocks. 485 if (TBB != Tail) { 486 RemovedBlocks.push_back(TBB); 487 TBB->eraseFromParent(); 488 } 489 if (FBB != Tail) { 490 RemovedBlocks.push_back(FBB); 491 FBB->eraseFromParent(); 492 } 493 494 assert(Head->succ_empty() && "Additional head successors?"); 495 if (Head->isLayoutSuccessor(Tail)) { 496 // Splice Tail onto the end of Head. 497 DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber() 498 << " into head BB#" << Head->getNumber() << '\n'); 499 Head->splice(Head->end(), Tail, 500 Tail->begin(), Tail->end()); 501 Head->transferSuccessorsAndUpdatePHIs(Tail); 502 RemovedBlocks.push_back(Tail); 503 Tail->eraseFromParent(); 504 } else { 505 // We need a branch to Tail, let code placement work it out later. 506 DEBUG(dbgs() << "Converting to unconditional branch.\n"); 507 SmallVector<MachineOperand, 0> EmptyCond; 508 TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL); 509 Head->addSuccessor(Tail); 510 } 511 DEBUG(dbgs() << *Head); 512} 513 514 515//===----------------------------------------------------------------------===// 516// EarlyIfConverter Pass 517//===----------------------------------------------------------------------===// 518 519namespace { 520class EarlyIfConverter : public MachineFunctionPass { 521 const TargetInstrInfo *TII; 522 const TargetRegisterInfo *TRI; 523 const MCSchedModel *SchedModel; 524 MachineRegisterInfo *MRI; 525 MachineDominatorTree *DomTree; 526 MachineLoopInfo *Loops; 527 MachineTraceMetrics *Traces; 528 MachineTraceMetrics::Ensemble *MinInstr; 529 SSAIfConv IfConv; 530 531public: 532 static char ID; 533 EarlyIfConverter() : MachineFunctionPass(ID) {} 534 void getAnalysisUsage(AnalysisUsage &AU) const; 535 bool runOnMachineFunction(MachineFunction &MF); 536 537private: 538 bool tryConvertIf(MachineBasicBlock*); 539 void updateDomTree(ArrayRef<MachineBasicBlock*> Removed); 540 void updateLoops(ArrayRef<MachineBasicBlock*> Removed); 541 void invalidateTraces(); 542 bool shouldConvertIf(); 543}; 544} // end anonymous namespace 545 546char EarlyIfConverter::ID = 0; 547char &llvm::EarlyIfConverterID = EarlyIfConverter::ID; 548 549INITIALIZE_PASS_BEGIN(EarlyIfConverter, 550 "early-ifcvt", "Early If Converter", false, false) 551INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 552INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 553INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) 554INITIALIZE_PASS_END(EarlyIfConverter, 555 "early-ifcvt", "Early If Converter", false, false) 556 557void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const { 558 AU.addRequired<MachineBranchProbabilityInfo>(); 559 AU.addRequired<MachineDominatorTree>(); 560 AU.addPreserved<MachineDominatorTree>(); 561 AU.addRequired<MachineLoopInfo>(); 562 AU.addPreserved<MachineLoopInfo>(); 563 AU.addRequired<MachineTraceMetrics>(); 564 AU.addPreserved<MachineTraceMetrics>(); 565 MachineFunctionPass::getAnalysisUsage(AU); 566} 567 568/// Update the dominator tree after if-conversion erased some blocks. 569void EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) { 570 // convertIf can remove TBB, FBB, and Tail can be merged into Head. 571 // TBB and FBB should not dominate any blocks. 572 // Tail children should be transferred to Head. 573 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); 574 for (unsigned i = 0, e = Removed.size(); i != e; ++i) { 575 MachineDomTreeNode *Node = DomTree->getNode(Removed[i]); 576 assert(Node != HeadNode && "Cannot erase the head node"); 577 while (Node->getNumChildren()) { 578 assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); 579 DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); 580 } 581 DomTree->eraseNode(Removed[i]); 582 } 583} 584 585/// Update LoopInfo after if-conversion. 586void EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) { 587 if (!Loops) 588 return; 589 // If-conversion doesn't change loop structure, and it doesn't mess with back 590 // edges, so updating LoopInfo is simply removing the dead blocks. 591 for (unsigned i = 0, e = Removed.size(); i != e; ++i) 592 Loops->removeBlock(Removed[i]); 593} 594 595/// Invalidate MachineTraceMetrics before if-conversion. 596void EarlyIfConverter::invalidateTraces() { 597 Traces->verifyAnalysis(); 598 Traces->invalidate(IfConv.Head); 599 Traces->invalidate(IfConv.Tail); 600 Traces->invalidate(IfConv.TBB); 601 Traces->invalidate(IfConv.FBB); 602 DEBUG(if (MinInstr) MinInstr->print(dbgs())); 603 Traces->verifyAnalysis(); 604} 605 606/// Apply cost model and heuristics to the if-conversion in IfConv. 607/// Return true if the conversion is a good idea. 608/// 609bool EarlyIfConverter::shouldConvertIf() { 610 // Stress testing mode disables all cost considerations. 611 if (Stress) 612 return true; 613 614 if (!MinInstr) 615 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); 616 617 // Compare the critical path through TBB and FBB. If the difference is 618 // greater than the branch misprediction penalty, it would never pay to 619 // if-convert. The triangle/diamond topology guarantees that these traces 620 // have the same head and tail, so they can be compared. 621 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.TBB); 622 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.FBB); 623 DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace); 624 unsigned TBBCrit = TBBTrace.getCriticalPath(); 625 unsigned FBBCrit = FBBTrace.getCriticalPath(); 626 unsigned ExtraCrit = TBBCrit > FBBCrit ? TBBCrit-FBBCrit : FBBCrit-TBBCrit; 627 if (ExtraCrit >= SchedModel->MispredictPenalty) { 628 DEBUG(dbgs() << "Critical path difference larger than " 629 << SchedModel->MispredictPenalty << ".\n"); 630 return false; 631 } 632 return true; 633} 634 635/// Attempt repeated if-conversion on MBB, return true if successful. 636/// 637bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { 638 bool Changed = false; 639 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) { 640 // If-convert MBB and update analyses. 641 invalidateTraces(); 642 SmallVector<MachineBasicBlock*, 4> RemovedBlocks; 643 IfConv.convertIf(RemovedBlocks); 644 Changed = true; 645 updateDomTree(RemovedBlocks); 646 updateLoops(RemovedBlocks); 647 } 648 return Changed; 649} 650 651bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { 652 DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" 653 << "********** Function: " 654 << ((Value*)MF.getFunction())->getName() << '\n'); 655 TII = MF.getTarget().getInstrInfo(); 656 TRI = MF.getTarget().getRegisterInfo(); 657 SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel; 658 MRI = &MF.getRegInfo(); 659 DomTree = &getAnalysis<MachineDominatorTree>(); 660 Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 661 Traces = &getAnalysis<MachineTraceMetrics>(); 662 MinInstr = 0; 663 664 bool Changed = false; 665 IfConv.runOnMachineFunction(MF); 666 667 // Visit blocks in dominator tree post-order. The post-order enables nested 668 // if-conversion in a single pass. The tryConvertIf() function may erase 669 // blocks, but only blocks dominated by the head block. This makes it safe to 670 // update the dominator tree while the post-order iterator is still active. 671 for (po_iterator<MachineDominatorTree*> 672 I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I) 673 if (tryConvertIf(I->getBlock())) 674 Changed = true; 675 676 MF.verify(this, "After early if-conversion"); 677 return Changed; 678} 679