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