IfConversion.cpp revision 5f70218c7534d7214cc23b7151ab25771bd3151b
1//===-- IfConversion.cpp - Machine code if conversion pass. ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the Evan Cheng and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the machine instruction level if-conversion pass. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "ifcvt" 15#include "llvm/Function.h" 16#include "llvm/CodeGen/Passes.h" 17#include "llvm/CodeGen/MachineModuleInfo.h" 18#include "llvm/CodeGen/MachineFunctionPass.h" 19#include "llvm/Target/TargetInstrInfo.h" 20#include "llvm/Target/TargetLowering.h" 21#include "llvm/Target/TargetMachine.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/ADT/DepthFirstIterator.h" 24#include "llvm/ADT/Statistic.h" 25using namespace llvm; 26 27STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 28 29namespace { 30 class IfConverter : public MachineFunctionPass { 31 enum BBICKind { 32 ICNotAnalyzed, // BB has not been analyzed. 33 ICReAnalyze, // BB must be re-analyzed. 34 ICNotClassfied, // BB data valid, but not classified. 35 ICEarlyExit, // BB is entry of an early-exit sub-CFG. 36 ICTriangle, // BB is entry of a triangle sub-CFG. 37 ICDiamond, // BB is entry of a diamond sub-CFG. 38 ICChild, // BB is part of the sub-CFG that'll be predicated. 39 ICDead // BB has been converted and merged, it's now dead. 40 }; 41 42 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 43 /// if-conversion feasibility analysis. This includes results from 44 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 45 /// classification, and common tail block of its successors (if it's a 46 /// diamond shape), its size, whether it's predicable, and whether any 47 /// instruction can clobber the 'would-be' predicate. 48 /// 49 /// Kind - Type of block. See BBICKind. 50 /// NonPredSize - Number of non-predicated instructions. 51 /// isPredicable - Is it predicable. (FIXME: Remove.) 52 /// hasEarlyExit - Ends with a return, indirect jump or br to jumptable. 53 /// ModifyPredicate - FIXME: Not used right now. True if BB would modify 54 /// the predicate (e.g. has cmp, call, etc.) 55 /// BB - Corresponding MachineBasicBlock. 56 /// TrueBB / FalseBB- See AnalyzeBranch(). 57 /// BrCond - Conditions for end of block conditional branches. 58 /// Predicate - Predicate used in the BB. 59 struct BBInfo { 60 BBICKind Kind; 61 unsigned NonPredSize; 62 bool isPredicable; 63 bool hasEarlyExit; 64 bool ModifyPredicate; 65 MachineBasicBlock *BB; 66 MachineBasicBlock *TrueBB; 67 MachineBasicBlock *FalseBB; 68 MachineBasicBlock *TailBB; 69 std::vector<MachineOperand> BrCond; 70 std::vector<MachineOperand> Predicate; 71 BBInfo() : Kind(ICNotAnalyzed), NonPredSize(0), isPredicable(false), 72 hasEarlyExit(false), ModifyPredicate(false), 73 BB(0), TrueBB(0), FalseBB(0), TailBB(0) {} 74 }; 75 76 /// Roots - Basic blocks that do not have successors. These are the starting 77 /// points of Graph traversal. 78 std::vector<MachineBasicBlock*> Roots; 79 80 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 81 /// basic block number. 82 std::vector<BBInfo> BBAnalysis; 83 84 const TargetLowering *TLI; 85 const TargetInstrInfo *TII; 86 bool MadeChange; 87 public: 88 static char ID; 89 IfConverter() : MachineFunctionPass((intptr_t)&ID) {} 90 91 virtual bool runOnMachineFunction(MachineFunction &MF); 92 virtual const char *getPassName() const { return "If converter"; } 93 94 private: 95 void StructuralAnalysis(MachineBasicBlock *BB); 96 void FeasibilityAnalysis(BBInfo &BBI, 97 std::vector<MachineOperand> &Cond); 98 bool AttemptRestructuring(BBInfo &BBI); 99 bool AnalyzeBlocks(MachineFunction &MF, 100 std::vector<BBInfo*> &Candidates); 101 void ReTryPreds(MachineBasicBlock *BB); 102 bool IfConvertEarlyExit(BBInfo &BBI); 103 bool IfConvertTriangle(BBInfo &BBI); 104 bool IfConvertDiamond(BBInfo &BBI); 105 void PredicateBlock(BBInfo &BBI, 106 std::vector<MachineOperand> &Cond, 107 bool IgnoreTerm = false); 108 void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI); 109 110 // IfcvtCandidateCmp - Used to sort if-conversion candidates. 111 static bool IfcvtCandidateCmp(BBInfo* C1, BBInfo* C2){ 112 // Favor diamond over triangle, etc. 113 return (unsigned)C1->Kind < (unsigned)C2->Kind; 114 } 115 }; 116 char IfConverter::ID = 0; 117} 118 119FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 120 121bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 122 TLI = MF.getTarget().getTargetLowering(); 123 TII = MF.getTarget().getInstrInfo(); 124 if (!TII) return false; 125 126 DOUT << "\nIfcvt: function \'" << MF.getFunction()->getName() << "\'\n"; 127 128 MF.RenumberBlocks(); 129 BBAnalysis.resize(MF.getNumBlockIDs()); 130 131 // Look for root nodes, i.e. blocks without successors. 132 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 133 if (I->succ_size() == 0) 134 Roots.push_back(I); 135 136 std::vector<BBInfo*> Candidates; 137 MadeChange = false; 138 while (true) { 139 bool Change = false; 140 141 // Do an intial analysis for each basic block and finding all the potential 142 // candidates to perform if-convesion. 143 Change |= AnalyzeBlocks(MF, Candidates); 144 while (!Candidates.empty()) { 145 BBInfo &BBI = *Candidates.back(); 146 Candidates.pop_back(); 147 switch (BBI.Kind) { 148 default: assert(false && "Unexpected!"); 149 break; 150 case ICReAnalyze: 151 // One or more of 'childrean' have been modified, abort! 152 break; 153 case ICEarlyExit: 154 DOUT << "Ifcvt (Early exit): BB#" << BBI.BB->getNumber() << "\n"; 155 Change |= IfConvertEarlyExit(BBI); 156 break; 157 case ICTriangle: 158 DOUT << "Ifcvt (Triangle): BB#" << BBI.BB->getNumber() << "\n"; 159 Change |= IfConvertTriangle(BBI); 160 break; 161 case ICDiamond: 162 DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << "\n"; 163 Change |= IfConvertDiamond(BBI); 164 break; 165 } 166 } 167 168 MadeChange |= Change; 169 if (!Change) 170 break; 171 } 172 173 Roots.clear(); 174 BBAnalysis.clear(); 175 176 return MadeChange; 177} 178 179static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 180 MachineBasicBlock *TrueBB) { 181 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 182 E = BB->succ_end(); SI != E; ++SI) { 183 MachineBasicBlock *SuccBB = *SI; 184 if (SuccBB != TrueBB) 185 return SuccBB; 186 } 187 return NULL; 188} 189 190/// StructuralAnalysis - Analyze the structure of the sub-CFG starting from 191/// the specified block. Record its successors and whether it looks like an 192/// if-conversion candidate. 193void IfConverter::StructuralAnalysis(MachineBasicBlock *BB) { 194 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 195 196 if (BBI.Kind != ICReAnalyze) { 197 if (BBI.Kind != ICNotAnalyzed) 198 return; // Already analyzed. 199 BBI.BB = BB; 200 BBI.NonPredSize = std::distance(BB->begin(), BB->end()); 201 } 202 203 // Look for 'root' of a simple (non-nested) triangle or diamond. 204 BBI.Kind = ICNotClassfied; 205 bool CanAnalyze = !TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB, 206 BBI.BrCond); 207 // Does it end with a return, indirect jump, or jumptable branch? 208 BBI.hasEarlyExit = TII->BlockHasNoFallThrough(*BB) && !BBI.TrueBB; 209 if (!CanAnalyze || !BBI.TrueBB || BBI.BrCond.size() == 0) 210 return; 211 212 // Not a candidate if 'true' block is going to be if-converted. 213 StructuralAnalysis(BBI.TrueBB); 214 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 215 216 // TODO: Only handle very simple cases for now. 217 if (TrueBBI.FalseBB || TrueBBI.BrCond.size()) 218 return; 219 220 // No false branch. This BB must end with a conditional branch and a 221 // fallthrough. 222 if (!BBI.FalseBB) 223 BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB); 224 assert(BBI.FalseBB && "Expected to find the fallthrough block!"); 225 226 // Not a candidate if 'false' block is going to be if-converted. 227 StructuralAnalysis(BBI.FalseBB); 228 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 229 230 // TODO: Only handle very simple cases for now. 231 if (FalseBBI.FalseBB || FalseBBI.BrCond.size()) 232 return; 233 234 unsigned TrueNumPreds = BBI.TrueBB->pred_size(); 235 unsigned FalseNumPreds = BBI.FalseBB->pred_size(); 236 if ((TrueBBI.hasEarlyExit && TrueNumPreds <= 1) && 237 !(FalseBBI.hasEarlyExit && FalseNumPreds <=1)) { 238 BBI.Kind = ICEarlyExit; 239 TrueBBI.Kind = ICChild; 240 } else if (!(TrueBBI.hasEarlyExit && TrueNumPreds <= 1) && 241 (FalseBBI.hasEarlyExit && FalseNumPreds <=1)) { 242 BBI.Kind = ICEarlyExit; 243 FalseBBI.Kind = ICChild; 244 } else if (TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB) { 245 // Triangle: 246 // EBB 247 // | \_ 248 // | | 249 // | TBB 250 // | / 251 // FBB 252 BBI.Kind = ICTriangle; 253 TrueBBI.Kind = FalseBBI.Kind = ICChild; 254 } else if (TrueBBI.TrueBB == FalseBBI.TrueBB && 255 TrueNumPreds <= 1 && FalseNumPreds <= 1) { 256 // Diamond: 257 // EBB 258 // / \_ 259 // | | 260 // TBB FBB 261 // \ / 262 // TailBB 263 // Note MBB can be empty in case both TBB and FBB are return blocks. 264 BBI.Kind = ICDiamond; 265 TrueBBI.Kind = FalseBBI.Kind = ICChild; 266 BBI.TailBB = TrueBBI.TrueBB; 267 } 268 return; 269} 270 271/// FeasibilityAnalysis - Determine if the block is predicable. In most 272/// cases, that means all the instructions in the block has M_PREDICABLE flag. 273/// Also checks if the block contains any instruction which can clobber a 274/// predicate (e.g. condition code register). If so, the block is not 275/// predicable unless it's the last instruction. Note, this function assumes 276/// all the terminator instructions can be converted or deleted so it ignore 277/// them. 278void IfConverter::FeasibilityAnalysis(BBInfo &BBI, 279 std::vector<MachineOperand> &Cond) { 280 if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit()) 281 return; 282 283 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 284 I != E; ++I) { 285 // TODO: check if instruction clobbers predicate. 286 if (TII->isTerminatorInstr(I->getOpcode())) 287 break; 288 if (!I->isPredicable()) 289 return; 290 } 291 292 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Cond)) 293 return; 294 295 BBI.isPredicable = true; 296} 297 298/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to 299/// expose more if-conversion opportunities. e.g. 300/// 301/// cmp 302/// b le BB1 303/// / \____ 304/// / | 305/// cmp | 306/// b eq BB1 | 307/// / \____ | 308/// / \ | 309/// BB1 310/// ==> 311/// 312/// cmp 313/// b eq BB1 314/// / \____ 315/// / | 316/// cmp | 317/// b le BB1 | 318/// / \____ | 319/// / \ | 320/// BB1 321bool IfConverter::AttemptRestructuring(BBInfo &BBI) { 322 return false; 323} 324 325/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 326/// candidates. It returns true if any CFG restructuring is done to expose more 327/// if-conversion opportunities. 328bool IfConverter::AnalyzeBlocks(MachineFunction &MF, 329 std::vector<BBInfo*> &Candidates) { 330 bool Change = false; 331 std::set<MachineBasicBlock*> Visited; 332 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 333 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 334 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 335 MachineBasicBlock *BB = *I; 336 StructuralAnalysis(BB); 337 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 338 switch (BBI.Kind) { 339 case ICEarlyExit: 340 case ICTriangle: 341 case ICDiamond: 342 Candidates.push_back(&BBI); 343 break; 344 default: 345 Change |= AttemptRestructuring(BBI); 346 break; 347 } 348 } 349 } 350 351 // Sort to favor more complex ifcvt scheme. 352 std::stable_sort(Candidates.begin(), Candidates.end(), IfcvtCandidateCmp); 353 354 return Change; 355} 356 357/// TransferPreds - Transfer all the predecessors of FromBB to ToBB. 358/// 359static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 360 std::vector<MachineBasicBlock*> Preds(FromBB->pred_begin(), 361 FromBB->pred_end()); 362 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 363 MachineBasicBlock *Pred = Preds[i]; 364 Pred->removeSuccessor(FromBB); 365 if (!Pred->isSuccessor(ToBB)) 366 Pred->addSuccessor(ToBB); 367 } 368} 369 370/// TransferSuccs - Transfer all the successors of FromBB to ToBB. 371/// 372static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 373 std::vector<MachineBasicBlock*> Succs(FromBB->succ_begin(), 374 FromBB->succ_end()); 375 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 376 MachineBasicBlock *Succ = Succs[i]; 377 FromBB->removeSuccessor(Succ); 378 if (!ToBB->isSuccessor(Succ)) 379 ToBB->addSuccessor(Succ); 380 } 381} 382 383/// isNextBlock - Returns true if ToBB the next basic block after BB. 384/// 385static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 386 MachineFunction::iterator Fallthrough = BB; 387 return MachineFunction::iterator(ToBB) == ++Fallthrough; 388} 389 390/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed 391/// to determine if it can be if-converted. 392void IfConverter::ReTryPreds(MachineBasicBlock *BB) { 393 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 394 E = BB->pred_end(); PI != E; ++PI) { 395 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 396 PBBI.Kind = ICReAnalyze; 397 } 398} 399 400/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 401/// 402static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 403 const TargetInstrInfo *TII) { 404 std::vector<MachineOperand> NoCond; 405 TII->InsertBranch(*BB, ToBB, NULL, NoCond); 406} 407 408/// IfConvertEarlyExit - If convert a early exit sub-CFG. 409/// 410bool IfConverter::IfConvertEarlyExit(BBInfo &BBI) { 411 BBI.Kind = ICNotClassfied; 412 413 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 414 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 415 BBInfo *CvtBBI = &TrueBBI; 416 BBInfo *NextBBI = &FalseBBI; 417 418 bool ReserveCond = false; 419 if (TrueBBI.Kind != ICChild) { 420 std::swap(CvtBBI, NextBBI); 421 ReserveCond = true; 422 } 423 424 std::vector<MachineOperand> NewCond(BBI.BrCond); 425 if (ReserveCond) 426 TII->ReverseBranchCondition(NewCond); 427 FeasibilityAnalysis(*CvtBBI, NewCond); 428 if (!CvtBBI->isPredicable) 429 return false; 430 431 PredicateBlock(*CvtBBI, NewCond); 432 433 // Merge converted block into entry block. Also convert the end of the 434 // block conditional branch (to the non-converted block) into an 435 // unconditional one. 436 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 437 MergeBlocks(BBI, *CvtBBI); 438 if (!isNextBlock(BBI.BB, NextBBI->BB)) 439 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 440 std::copy(NewCond.begin(), NewCond.end(), std::back_inserter(BBI.Predicate)); 441 442 // Update block info. BB can be iteratively if-converted. 443 BBI.Kind = ICNotAnalyzed; 444 BBI.TrueBB = BBI.FalseBB = NULL; 445 BBI.BrCond.clear(); 446 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 447 ReTryPreds(BBI.BB); 448 CvtBBI->Kind = ICDead; 449 450 // FIXME: Must maintain LiveIns. 451 NumIfConvBBs++; 452 return true; 453} 454 455/// IfConvertTriangle - If convert a triangle sub-CFG. 456/// 457bool IfConverter::IfConvertTriangle(BBInfo &BBI) { 458 BBI.Kind = ICNotClassfied; 459 460 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 461 FeasibilityAnalysis(TrueBBI, BBI.BrCond); 462 if (!TrueBBI.isPredicable) 463 return false; 464 465 // Predicate the 'true' block after removing its branch. 466 TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB); 467 PredicateBlock(TrueBBI, BBI.BrCond); 468 469 // Join the 'true' and 'false' blocks by copying the instructions 470 // from the 'false' block to the 'true' block. 471 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 472 MergeBlocks(TrueBBI, FalseBBI); 473 474 // Now merge the entry of the triangle with the true block. 475 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 476 MergeBlocks(BBI, TrueBBI); 477 std::copy(BBI.BrCond.begin(), BBI.BrCond.end(), 478 std::back_inserter(BBI.Predicate)); 479 480 // Update block info. BB can be iteratively if-converted. 481 BBI.Kind = ICNotClassfied; 482 BBI.TrueBB = BBI.FalseBB = NULL; 483 BBI.BrCond.clear(); 484 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 485 ReTryPreds(BBI.BB); 486 TrueBBI.Kind = ICDead; 487 488 // FIXME: Must maintain LiveIns. 489 NumIfConvBBs++; 490 return true; 491} 492 493/// IfConvertDiamond - If convert a diamond sub-CFG. 494/// 495bool IfConverter::IfConvertDiamond(BBInfo &BBI) { 496 BBI.Kind = ICNotClassfied; 497 498 bool TrueNeedBr; 499 bool FalseNeedBr; 500 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 501 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 502 FeasibilityAnalysis(TrueBBI, BBI.BrCond); 503 std::vector<MachineOperand> RevCond(BBI.BrCond); 504 TII->ReverseBranchCondition(RevCond); 505 FeasibilityAnalysis(FalseBBI, RevCond); 506 507 SmallVector<MachineInstr*, 2> Dups; 508 bool Proceed = TrueBBI.isPredicable && FalseBBI.isPredicable; 509 if (Proceed) { 510 // Check the 'true' and 'false' blocks if either isn't ended with a branch. 511 // Either the block fallthrough to another block or it ends with a 512 // return. If it's the former, add a branch to its successor. 513 TrueNeedBr = !TrueBBI.TrueBB && BBI.TrueBB->succ_size(); 514 FalseNeedBr = !FalseBBI.TrueBB && BBI.FalseBB->succ_size(); 515 if (TrueNeedBr && TrueBBI.ModifyPredicate) { 516 TrueBBI.isPredicable = false; 517 Proceed = false; 518 } 519 if (FalseNeedBr && FalseBBI.ModifyPredicate) { 520 FalseBBI.isPredicable = false; 521 Proceed = false; 522 } 523 524 if (Proceed) { 525 if (!BBI.TailBB) { 526 // No common merge block. Check if the terminators (e.g. return) are 527 // the same or predicable. 528 MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator(); 529 MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator(); 530 while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) { 531 if (TT->isIdenticalTo(FT)) 532 Dups.push_back(TT); // Will erase these later. 533 else if (!TT->isPredicable() && !FT->isPredicable()) { 534 Proceed = false; 535 break; // Can't if-convert. Abort! 536 } 537 ++TT; 538 ++FT; 539 } 540 541 // One of the two pathes have more terminators, make sure they are 542 // all predicable. 543 while (Proceed && TT != BBI.TrueBB->end()) 544 if (!TT->isPredicable()) { 545 Proceed = false; 546 break; // Can't if-convert. Abort! 547 } 548 while (Proceed && FT != BBI.FalseBB->end()) 549 if (!FT->isPredicable()) { 550 Proceed = false; 551 break; // Can't if-convert. Abort! 552 } 553 } 554 } 555 } 556 557 if (!Proceed) 558 return false; 559 560 // Remove the duplicated instructions from the 'true' block. 561 for (unsigned i = 0, e = Dups.size(); i != e; ++i) { 562 Dups[i]->eraseFromParent(); 563 --TrueBBI.NonPredSize; 564 } 565 566 // Predicate the 'true' block after removing its branch. 567 TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB); 568 PredicateBlock(TrueBBI, BBI.BrCond); 569 570 // Predicate the 'false' block. 571 PredicateBlock(FalseBBI, RevCond, true); 572 573 // Merge the 'true' and 'false' blocks by copying the instructions 574 // from the 'false' block to the 'true' block. That is, unless the true 575 // block would clobber the predicate, in that case, do the opposite. 576 BBInfo *CvtBBI; 577 if (!TrueBBI.ModifyPredicate) { 578 // Add a conditional branch from 'true' to 'true' successor if needed. 579 if (TrueNeedBr) 580 TII->InsertBranch(*BBI.TrueBB, *BBI.TrueBB->succ_begin(), NULL, 581 BBI.BrCond); 582 // Add an unconditional branch from 'false' to to 'false' successor if it 583 // will not be the fallthrough block. 584 if (FalseNeedBr && 585 !isNextBlock(BBI.BB, *BBI.FalseBB->succ_begin())) 586 InsertUncondBranch(BBI.FalseBB, *BBI.FalseBB->succ_begin(), TII); 587 MergeBlocks(TrueBBI, FalseBBI); 588 CvtBBI = &TrueBBI; 589 } else { 590 // Add a conditional branch from 'false' to 'false' successor if needed. 591 if (FalseNeedBr) 592 TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL, 593 RevCond); 594 // Add an unconditional branch from 'true' to to 'true' successor if it 595 // will not be the fallthrough block. 596 if (TrueNeedBr && 597 !isNextBlock(BBI.BB, *BBI.TrueBB->succ_begin())) 598 InsertUncondBranch(BBI.TrueBB, *BBI.TrueBB->succ_begin(), TII); 599 MergeBlocks(FalseBBI, TrueBBI); 600 CvtBBI = &FalseBBI; 601 } 602 603 // Remove the conditional branch from entry to the blocks. 604 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 605 606 bool OkToIfcvt = true; 607 // Merge the combined block into the entry of the diamond if the entry 608 // block is its only predecessor. Otherwise, insert an unconditional 609 // branch from entry to the if-converted block. 610 if (CvtBBI->BB->pred_size() == 1) { 611 MergeBlocks(BBI, *CvtBBI); 612 CvtBBI = &BBI; 613 OkToIfcvt = false; 614 } else 615 InsertUncondBranch(BBI.BB, CvtBBI->BB, TII); 616 617 // If the if-converted block fallthrough or unconditionally branch into the 618 // tail block, and the tail block does not have other predecessors, then 619 // fold the tail block in as well. 620 if (BBI.TailBB && 621 BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) { 622 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 623 BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()]; 624 MergeBlocks(*CvtBBI, TailBBI); 625 TailBBI.Kind = ICDead; 626 } 627 628 // Update block info. BB may be iteratively if-converted. 629 if (OkToIfcvt) { 630 BBI.Kind = ICNotClassfied; 631 BBI.TrueBB = BBI.FalseBB = NULL; 632 BBI.BrCond.clear(); 633 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 634 ReTryPreds(BBI.BB); 635 } 636 TrueBBI.Kind = ICDead; 637 FalseBBI.Kind = ICDead; 638 639 // FIXME: Must maintain LiveIns. 640 NumIfConvBBs += 2; 641 return true; 642} 643 644/// PredicateBlock - Predicate every instruction in the block with the specified 645/// condition. If IgnoreTerm is true, skip over all terminator instructions. 646void IfConverter::PredicateBlock(BBInfo &BBI, 647 std::vector<MachineOperand> &Cond, 648 bool IgnoreTerm) { 649 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 650 I != E; ++I) { 651 MachineInstr *MI = I; 652 if (IgnoreTerm && TII->isTerminatorInstr(MI->getOpcode())) 653 continue; 654 if (TII->isPredicated(MI)) 655 continue; 656 if (!TII->PredicateInstruction(MI, Cond)) { 657 cerr << "Unable to predication " << *I << "!\n"; 658 abort(); 659 } 660 } 661 662 BBI.NonPredSize = 0; 663} 664 665/// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 666/// 667void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { 668 ToBBI.BB->splice(ToBBI.BB->end(), 669 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 670 671 // If FromBBI is previously a successor, remove it from ToBBI's successor 672 // list and update its TrueBB / FalseBB field if needed. 673 if (ToBBI.BB->isSuccessor(FromBBI.BB)) 674 ToBBI.BB->removeSuccessor(FromBBI.BB); 675 676 // Transfer preds / succs and update size. 677 TransferPreds(ToBBI.BB, FromBBI.BB); 678 TransferSuccs(ToBBI.BB, FromBBI.BB); 679 ToBBI.NonPredSize += FromBBI.NonPredSize; 680 FromBBI.NonPredSize = 0; 681} 682