IfConversion.cpp revision fe57a7e4df512f3a40b8ff463f5362a59908becc
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 (!I->isPredicable()) 287 return; 288 } 289 290 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Cond)) 291 return; 292 293 BBI.isPredicable = true; 294} 295 296/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to 297/// expose more if-conversion opportunities. e.g. 298/// 299/// cmp 300/// b le BB1 301/// / \____ 302/// / | 303/// cmp | 304/// b eq BB1 | 305/// / \____ | 306/// / \ | 307/// BB1 308/// ==> 309/// 310/// cmp 311/// b eq BB1 312/// / \____ 313/// / | 314/// cmp | 315/// b le BB1 | 316/// / \____ | 317/// / \ | 318/// BB1 319bool IfConverter::AttemptRestructuring(BBInfo &BBI) { 320 return false; 321} 322 323/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 324/// candidates. It returns true if any CFG restructuring is done to expose more 325/// if-conversion opportunities. 326bool IfConverter::AnalyzeBlocks(MachineFunction &MF, 327 std::vector<BBInfo*> &Candidates) { 328 bool Change = false; 329 std::set<MachineBasicBlock*> Visited; 330 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 331 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 332 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 333 MachineBasicBlock *BB = *I; 334 StructuralAnalysis(BB); 335 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 336 switch (BBI.Kind) { 337 case ICEarlyExit: 338 case ICTriangle: 339 case ICDiamond: 340 Candidates.push_back(&BBI); 341 break; 342 default: 343 Change |= AttemptRestructuring(BBI); 344 break; 345 } 346 } 347 } 348 349 // Sort to favor more complex ifcvt scheme. 350 std::stable_sort(Candidates.begin(), Candidates.end(), IfcvtCandidateCmp); 351 352 return Change; 353} 354 355/// TransferPreds - Transfer all the predecessors of FromBB to ToBB. 356/// 357static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 358 std::vector<MachineBasicBlock*> Preds(FromBB->pred_begin(), 359 FromBB->pred_end()); 360 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 361 MachineBasicBlock *Pred = Preds[i]; 362 Pred->removeSuccessor(FromBB); 363 if (!Pred->isSuccessor(ToBB)) 364 Pred->addSuccessor(ToBB); 365 } 366} 367 368/// TransferSuccs - Transfer all the successors of FromBB to ToBB. 369/// 370static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 371 std::vector<MachineBasicBlock*> Succs(FromBB->succ_begin(), 372 FromBB->succ_end()); 373 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 374 MachineBasicBlock *Succ = Succs[i]; 375 FromBB->removeSuccessor(Succ); 376 if (!ToBB->isSuccessor(Succ)) 377 ToBB->addSuccessor(Succ); 378 } 379} 380 381/// isNextBlock - Returns true if ToBB the next basic block after BB. 382/// 383static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 384 MachineFunction::iterator Fallthrough = BB; 385 return MachineFunction::iterator(ToBB) == ++Fallthrough; 386} 387 388/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed 389/// to determine if it can be if-converted. 390void IfConverter::ReTryPreds(MachineBasicBlock *BB) { 391 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 392 E = BB->pred_end(); PI != E; ++PI) { 393 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 394 PBBI.Kind = ICReAnalyze; 395 } 396} 397 398/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 399/// 400static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 401 const TargetInstrInfo *TII) { 402 std::vector<MachineOperand> NoCond; 403 TII->InsertBranch(*BB, ToBB, NULL, NoCond); 404} 405 406/// IfConvertEarlyExit - If convert a early exit sub-CFG. 407/// 408bool IfConverter::IfConvertEarlyExit(BBInfo &BBI) { 409 BBI.Kind = ICNotClassfied; 410 411 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 412 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 413 BBInfo *CvtBBI = &TrueBBI; 414 BBInfo *NextBBI = &FalseBBI; 415 416 bool ReserveCond = false; 417 if (TrueBBI.Kind != ICChild) { 418 std::swap(CvtBBI, NextBBI); 419 ReserveCond = true; 420 } 421 422 std::vector<MachineOperand> NewCond(BBI.BrCond); 423 if (ReserveCond) 424 TII->ReverseBranchCondition(NewCond); 425 FeasibilityAnalysis(*CvtBBI, NewCond); 426 if (!CvtBBI->isPredicable) 427 return false; 428 429 PredicateBlock(*CvtBBI, NewCond); 430 431 // Merge converted block into entry block. Also convert the end of the 432 // block conditional branch (to the non-converted block) into an 433 // unconditional one. 434 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 435 MergeBlocks(BBI, *CvtBBI); 436 if (!isNextBlock(BBI.BB, NextBBI->BB)) 437 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 438 std::copy(NewCond.begin(), NewCond.end(), std::back_inserter(BBI.Predicate)); 439 440 // Update block info. BB can be iteratively if-converted. 441 BBI.Kind = ICNotAnalyzed; 442 BBI.TrueBB = BBI.FalseBB = NULL; 443 BBI.BrCond.clear(); 444 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 445 ReTryPreds(BBI.BB); 446 CvtBBI->Kind = ICDead; 447 448 // FIXME: Must maintain LiveIns. 449 NumIfConvBBs++; 450 return true; 451} 452 453/// IfConvertTriangle - If convert a triangle sub-CFG. 454/// 455bool IfConverter::IfConvertTriangle(BBInfo &BBI) { 456 BBI.Kind = ICNotClassfied; 457 458 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 459 FeasibilityAnalysis(TrueBBI, BBI.BrCond); 460 if (!TrueBBI.isPredicable) 461 return false; 462 463 // Predicate the 'true' block after removing its branch. 464 TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB); 465 PredicateBlock(TrueBBI, BBI.BrCond); 466 467 // Join the 'true' and 'false' blocks by copying the instructions 468 // from the 'false' block to the 'true' block. 469 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 470 MergeBlocks(TrueBBI, FalseBBI); 471 472 // Now merge the entry of the triangle with the true block. 473 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 474 MergeBlocks(BBI, TrueBBI); 475 std::copy(BBI.BrCond.begin(), BBI.BrCond.end(), 476 std::back_inserter(BBI.Predicate)); 477 478 // Update block info. BB can be iteratively if-converted. 479 BBI.Kind = ICNotClassfied; 480 BBI.TrueBB = BBI.FalseBB = NULL; 481 BBI.BrCond.clear(); 482 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 483 ReTryPreds(BBI.BB); 484 TrueBBI.Kind = ICDead; 485 486 // FIXME: Must maintain LiveIns. 487 NumIfConvBBs++; 488 return true; 489} 490 491/// IfConvertDiamond - If convert a diamond sub-CFG. 492/// 493bool IfConverter::IfConvertDiamond(BBInfo &BBI) { 494 BBI.Kind = ICNotClassfied; 495 496 bool TrueNeedBr; 497 bool FalseNeedBr; 498 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 499 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 500 FeasibilityAnalysis(TrueBBI, BBI.BrCond); 501 std::vector<MachineOperand> RevCond(BBI.BrCond); 502 TII->ReverseBranchCondition(RevCond); 503 FeasibilityAnalysis(FalseBBI, RevCond); 504 505 SmallVector<MachineInstr*, 2> Dups; 506 bool Proceed = TrueBBI.isPredicable && FalseBBI.isPredicable; 507 if (Proceed) { 508 // Check the 'true' and 'false' blocks if either isn't ended with a branch. 509 // Either the block fallthrough to another block or it ends with a 510 // return. If it's the former, add a branch to its successor. 511 TrueNeedBr = !TrueBBI.TrueBB && BBI.TrueBB->succ_size(); 512 FalseNeedBr = !FalseBBI.TrueBB && BBI.FalseBB->succ_size(); 513 if (TrueNeedBr && TrueBBI.ModifyPredicate) { 514 TrueBBI.isPredicable = false; 515 Proceed = false; 516 } 517 if (FalseNeedBr && FalseBBI.ModifyPredicate) { 518 FalseBBI.isPredicable = false; 519 Proceed = false; 520 } 521 522 if (Proceed) { 523 if (!BBI.TailBB) { 524 // No common merge block. Check if the terminators (e.g. return) are 525 // the same or predicable. 526 MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator(); 527 MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator(); 528 while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) { 529 if (TT->isIdenticalTo(FT)) 530 Dups.push_back(TT); // Will erase these later. 531 else if (!TT->isPredicable() && !FT->isPredicable()) { 532 Proceed = false; 533 break; // Can't if-convert. Abort! 534 } 535 ++TT; 536 ++FT; 537 } 538 539 // One of the two pathes have more terminators, make sure they are 540 // all predicable. 541 while (Proceed && TT != BBI.TrueBB->end()) 542 if (!TT->isPredicable()) { 543 Proceed = false; 544 break; // Can't if-convert. Abort! 545 } 546 while (Proceed && FT != BBI.FalseBB->end()) 547 if (!FT->isPredicable()) { 548 Proceed = false; 549 break; // Can't if-convert. Abort! 550 } 551 } 552 } 553 } 554 555 if (!Proceed) 556 return false; 557 558 // Remove the duplicated instructions from the 'true' block. 559 for (unsigned i = 0, e = Dups.size(); i != e; ++i) { 560 Dups[i]->eraseFromParent(); 561 --TrueBBI.NonPredSize; 562 } 563 564 // Predicate the 'true' block after removing its branch. 565 TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB); 566 PredicateBlock(TrueBBI, BBI.BrCond); 567 568 // Predicate the 'false' block. 569 PredicateBlock(FalseBBI, RevCond, true); 570 571 // Merge the 'true' and 'false' blocks by copying the instructions 572 // from the 'false' block to the 'true' block. That is, unless the true 573 // block would clobber the predicate, in that case, do the opposite. 574 BBInfo *CvtBBI; 575 if (!TrueBBI.ModifyPredicate) { 576 // Add a conditional branch from 'true' to 'true' successor if needed. 577 if (TrueNeedBr) 578 TII->InsertBranch(*BBI.TrueBB, *BBI.TrueBB->succ_begin(), NULL, 579 BBI.BrCond); 580 // Add an unconditional branch from 'false' to to 'false' successor if it 581 // will not be the fallthrough block. 582 if (FalseNeedBr && 583 !isNextBlock(BBI.BB, *BBI.FalseBB->succ_begin())) 584 InsertUncondBranch(BBI.FalseBB, *BBI.FalseBB->succ_begin(), TII); 585 MergeBlocks(TrueBBI, FalseBBI); 586 CvtBBI = &TrueBBI; 587 } else { 588 // Add a conditional branch from 'false' to 'false' successor if needed. 589 if (FalseNeedBr) 590 TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL, 591 RevCond); 592 // Add an unconditional branch from 'true' to to 'true' successor if it 593 // will not be the fallthrough block. 594 if (TrueNeedBr && 595 !isNextBlock(BBI.BB, *BBI.TrueBB->succ_begin())) 596 InsertUncondBranch(BBI.TrueBB, *BBI.TrueBB->succ_begin(), TII); 597 MergeBlocks(FalseBBI, TrueBBI); 598 CvtBBI = &FalseBBI; 599 } 600 601 // Remove the conditional branch from entry to the blocks. 602 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 603 604 bool OkToIfcvt = true; 605 // Merge the combined block into the entry of the diamond if the entry 606 // block is its only predecessor. Otherwise, insert an unconditional 607 // branch from entry to the if-converted block. 608 if (CvtBBI->BB->pred_size() == 1) { 609 MergeBlocks(BBI, *CvtBBI); 610 CvtBBI = &BBI; 611 OkToIfcvt = false; 612 } else 613 InsertUncondBranch(BBI.BB, CvtBBI->BB, TII); 614 615 // If the if-converted block fallthrough or unconditionally branch into the 616 // tail block, and the tail block does not have other predecessors, then 617 // fold the tail block in as well. 618 if (BBI.TailBB && 619 BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) { 620 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 621 BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()]; 622 MergeBlocks(*CvtBBI, TailBBI); 623 TailBBI.Kind = ICDead; 624 } 625 626 // Update block info. BB may be iteratively if-converted. 627 if (OkToIfcvt) { 628 BBI.Kind = ICNotClassfied; 629 BBI.TrueBB = BBI.FalseBB = NULL; 630 BBI.BrCond.clear(); 631 TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 632 ReTryPreds(BBI.BB); 633 } 634 TrueBBI.Kind = ICDead; 635 FalseBBI.Kind = ICDead; 636 637 // FIXME: Must maintain LiveIns. 638 NumIfConvBBs += 2; 639 return true; 640} 641 642/// PredicateBlock - Predicate every instruction in the block with the specified 643/// condition. If IgnoreTerm is true, skip over all terminator instructions. 644void IfConverter::PredicateBlock(BBInfo &BBI, 645 std::vector<MachineOperand> &Cond, 646 bool IgnoreTerm) { 647 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 648 I != E; ++I) { 649 MachineInstr *MI = I; 650 if (IgnoreTerm && TII->isTerminatorInstr(MI->getOpcode())) 651 continue; 652 if (TII->isPredicated(MI)) 653 continue; 654 if (!TII->PredicateInstruction(MI, Cond)) { 655 cerr << "Unable to predicate " << *I << "!\n"; 656 abort(); 657 } 658 } 659 660 BBI.NonPredSize = 0; 661} 662 663/// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 664/// 665void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { 666 ToBBI.BB->splice(ToBBI.BB->end(), 667 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 668 669 // If FromBBI is previously a successor, remove it from ToBBI's successor 670 // list and update its TrueBB / FalseBB field if needed. 671 if (ToBBI.BB->isSuccessor(FromBBI.BB)) 672 ToBBI.BB->removeSuccessor(FromBBI.BB); 673 674 // Transfer preds / succs and update size. 675 TransferPreds(ToBBI.BB, FromBBI.BB); 676 TransferSuccs(ToBBI.BB, FromBBI.BB); 677 ToBBI.NonPredSize += FromBBI.NonPredSize; 678 FromBBI.NonPredSize = 0; 679} 680