IfConversion.cpp revision 96dd9a8b1b969ece5504559ec240930bcb1dddd9
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(NumSimple, "Number of simple if-conversions performed"); 28STATISTIC(NumSimpleRev, "Number of simple (reversed) if-conversions performed"); 29STATISTIC(NumTriangle, "Number of triangle if-conversions performed"); 30STATISTIC(NumDiamonds, "Number of diamond if-conversions performed"); 31STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 32 33namespace { 34 class IfConverter : public MachineFunctionPass { 35 enum BBICKind { 36 ICNotAnalyzed, // BB has not been analyzed. 37 ICReAnalyze, // BB must be re-analyzed. 38 ICNotClassfied, // BB data valid, but not classified. 39 ICSimple, // BB is entry of an one split, no rejoin sub-CFG. 40 ICSimpleFalse, // Same as ICSimple, but on the false path. 41 ICTriangle, // BB is entry of a triangle sub-CFG. 42 ICDiamond, // BB is entry of a diamond sub-CFG. 43 ICChild, // BB is part of the sub-CFG that'll be predicated. 44 ICDead // BB cannot be if-converted again. 45 }; 46 47 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 48 /// if-conversion feasibility analysis. This includes results from 49 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 50 /// classification, and common tail block of its successors (if it's a 51 /// diamond shape), its size, whether it's predicable, and whether any 52 /// instruction can clobber the 'would-be' predicate. 53 /// 54 /// Kind - Type of block. See BBICKind. 55 /// NonPredSize - Number of non-predicated instructions. 56 /// IsAnalyzable - True if AnalyzeBranch() returns false. 57 /// ModifyPredicate - True if BB would modify the predicate (e.g. has 58 /// cmp, call, etc.) 59 /// BB - Corresponding MachineBasicBlock. 60 /// TrueBB / FalseBB- See AnalyzeBranch(). 61 /// BrCond - Conditions for end of block conditional branches. 62 /// Predicate - Predicate used in the BB. 63 struct BBInfo { 64 BBICKind Kind; 65 unsigned NonPredSize; 66 bool IsAnalyzable; 67 bool ModifyPredicate; 68 MachineBasicBlock *BB; 69 MachineBasicBlock *TrueBB; 70 MachineBasicBlock *FalseBB; 71 MachineBasicBlock *TailBB; 72 std::vector<MachineOperand> BrCond; 73 std::vector<MachineOperand> Predicate; 74 BBInfo() : Kind(ICNotAnalyzed), NonPredSize(0), 75 IsAnalyzable(false), ModifyPredicate(false), 76 BB(0), TrueBB(0), FalseBB(0), TailBB(0) {} 77 }; 78 79 /// Roots - Basic blocks that do not have successors. These are the starting 80 /// points of Graph traversal. 81 std::vector<MachineBasicBlock*> Roots; 82 83 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 84 /// basic block number. 85 std::vector<BBInfo> BBAnalysis; 86 87 const TargetLowering *TLI; 88 const TargetInstrInfo *TII; 89 bool MadeChange; 90 public: 91 static char ID; 92 IfConverter() : MachineFunctionPass((intptr_t)&ID) {} 93 94 virtual bool runOnMachineFunction(MachineFunction &MF); 95 virtual const char *getPassName() const { return "If converter"; } 96 97 private: 98 bool ReverseBranchCondition(BBInfo &BBI); 99 bool BlockModifyPredicate(MachineBasicBlock *BB) const; 100 void StructuralAnalysis(MachineBasicBlock *BB); 101 bool FeasibilityAnalysis(BBInfo &BBI, 102 std::vector<MachineOperand> &Cond, 103 bool IgnoreTerm = false); 104 bool AttemptRestructuring(BBInfo &BBI); 105 bool AnalyzeBlocks(MachineFunction &MF, 106 std::vector<BBInfo*> &Candidates); 107 void ReTryPreds(MachineBasicBlock *BB); 108 bool IfConvertSimple(BBInfo &BBI); 109 bool IfConvertTriangle(BBInfo &BBI); 110 bool IfConvertDiamond(BBInfo &BBI); 111 void PredicateBlock(BBInfo &BBI, 112 std::vector<MachineOperand> &Cond, 113 bool IgnoreTerm = false); 114 void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI); 115 116 // blockFallsThrough - Block ends without a terminator. 117 bool blockFallsThrough(BBInfo &BBI) const { 118 return BBI.IsAnalyzable && BBI.TrueBB == NULL; 119 } 120 121 // IfcvtCandidateCmp - Used to sort if-conversion candidates. 122 static bool IfcvtCandidateCmp(BBInfo* C1, BBInfo* C2){ 123 // Favor diamond over triangle, etc. 124 return (unsigned)C1->Kind < (unsigned)C2->Kind; 125 } 126 }; 127 char IfConverter::ID = 0; 128} 129 130FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 131 132bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 133 TLI = MF.getTarget().getTargetLowering(); 134 TII = MF.getTarget().getInstrInfo(); 135 if (!TII) return false; 136 137 DOUT << "\nIfcvt: function \'" << MF.getFunction()->getName() << "\'\n"; 138 139 MF.RenumberBlocks(); 140 BBAnalysis.resize(MF.getNumBlockIDs()); 141 142 // Look for root nodes, i.e. blocks without successors. 143 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 144 if (I->succ_size() == 0) 145 Roots.push_back(I); 146 147 std::vector<BBInfo*> Candidates; 148 MadeChange = false; 149 while (true) { 150 // Do an intial analysis for each basic block and finding all the potential 151 // candidates to perform if-convesion. 152 bool Change = AnalyzeBlocks(MF, Candidates); 153 while (!Candidates.empty()) { 154 BBInfo &BBI = *Candidates.back(); 155 Candidates.pop_back(); 156 157 bool RetVal = false; 158 switch (BBI.Kind) { 159 default: assert(false && "Unexpected!"); 160 break; 161 case ICReAnalyze: 162 // One or more of 'children' have been modified, abort! 163 case ICDead: 164 // Block has been already been if-converted, abort! 165 break; 166 case ICSimple: 167 case ICSimpleFalse: { 168 bool isRev = BBI.Kind == ICSimpleFalse; 169 DOUT << "Ifcvt (Simple" << (BBI.Kind == ICSimpleFalse ? " false" : "") 170 << "): BB#" << BBI.BB->getNumber() << " (" 171 << ((BBI.Kind == ICSimpleFalse) 172 ? BBI.FalseBB->getNumber() : BBI.TrueBB->getNumber()) << ") "; 173 RetVal = IfConvertSimple(BBI); 174 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 175 if (RetVal) 176 if (isRev) NumSimpleRev++; 177 else NumSimple++; 178 break; 179 } 180 case ICTriangle: 181 DOUT << "Ifcvt (Triangle): BB#" << BBI.BB->getNumber() << " (T:" 182 << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber() 183 << ") "; 184 RetVal = IfConvertTriangle(BBI); 185 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 186 if (RetVal) NumTriangle++; 187 break; 188 case ICDiamond: 189 DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" 190 << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber(); 191 if (BBI.TailBB) 192 DOUT << "," << BBI.TailBB->getNumber() ; 193 DOUT << ") "; 194 RetVal = IfConvertDiamond(BBI); 195 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 196 if (RetVal) NumDiamonds++; 197 break; 198 } 199 Change |= RetVal; 200 } 201 202 if (!Change) 203 break; 204 MadeChange |= Change; 205 } 206 207 Roots.clear(); 208 BBAnalysis.clear(); 209 210 return MadeChange; 211} 212 213static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 214 MachineBasicBlock *TrueBB) { 215 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 216 E = BB->succ_end(); SI != E; ++SI) { 217 MachineBasicBlock *SuccBB = *SI; 218 if (SuccBB != TrueBB) 219 return SuccBB; 220 } 221 return NULL; 222} 223 224bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { 225 if (!TII->ReverseBranchCondition(BBI.BrCond)) { 226 TII->RemoveBranch(*BBI.BB); 227 TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond); 228 std::swap(BBI.TrueBB, BBI.FalseBB); 229 return true; 230 } 231 return false; 232} 233 234/// BlockModifyPredicate - Returns true if any instruction in the block may 235/// clobber the condition code or register(s) used to predicate instructions, 236/// e.g. call, cmp. 237bool IfConverter::BlockModifyPredicate(MachineBasicBlock *BB) const { 238 for (MachineBasicBlock::const_reverse_iterator I = BB->rbegin(), 239 E = BB->rend(); I != E; ++I) 240 if (I->getInstrDescriptor()->Flags & M_CLOBBERS_PRED) 241 return true; 242 return false; 243} 244 245/// StructuralAnalysis - Analyze the structure of the sub-CFG starting from 246/// the specified block. Record its successors and whether it looks like an 247/// if-conversion candidate. 248void IfConverter::StructuralAnalysis(MachineBasicBlock *BB) { 249 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 250 251 if (BBI.Kind == ICReAnalyze) { 252 BBI.BrCond.clear(); 253 BBI.TrueBB = BBI.FalseBB = NULL; 254 } else { 255 if (BBI.Kind != ICNotAnalyzed) 256 return; // Already analyzed. 257 BBI.BB = BB; 258 BBI.NonPredSize = std::distance(BB->begin(), BB->end()); 259 BBI.ModifyPredicate = BlockModifyPredicate(BB); 260 } 261 262 // Look for 'root' of a simple (non-nested) triangle or diamond. 263 BBI.Kind = ICNotClassfied; 264 BBI.IsAnalyzable = 265 !TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 266 if (!BBI.IsAnalyzable || BBI.BrCond.size() == 0) 267 return; 268 // Do not ifcvt if either path is a back edge to the entry block. 269 if (BBI.TrueBB == BB || BBI.FalseBB == BB) 270 return; 271 272 StructuralAnalysis(BBI.TrueBB); 273 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 274 275 // No false branch. This BB must end with a conditional branch and a 276 // fallthrough. 277 if (!BBI.FalseBB) 278 BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB); 279 assert(BBI.FalseBB && "Expected to find the fallthrough block!"); 280 281 StructuralAnalysis(BBI.FalseBB); 282 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 283 284 // If both paths are dead, then forget about it. 285 if (TrueBBI.Kind == ICDead && FalseBBI.Kind == ICDead) { 286 BBI.Kind = ICDead; 287 return; 288 } 289 290 // Look for more opportunities to if-convert a triangle. Try to restructure 291 // the CFG to form a triangle with the 'false' path. 292 std::vector<MachineOperand> RevCond(BBI.BrCond); 293 bool CanRevCond = !TII->ReverseBranchCondition(RevCond); 294 if (FalseBBI.FalseBB) { 295 if (TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB) 296 return; 297 std::vector<MachineOperand> Cond(BBI.BrCond); 298 if (CanRevCond && 299 FalseBBI.TrueBB && FalseBBI.BB->pred_size() == 1 && 300 FeasibilityAnalysis(FalseBBI, RevCond, true)) { 301 std::vector<MachineOperand> FalseCond(FalseBBI.BrCond); 302 if (FalseBBI.TrueBB == BBI.TrueBB && 303 TII->SubsumesPredicate(FalseCond, BBI.BrCond)) { 304 // Reverse 'true' and 'false' paths. 305 ReverseBranchCondition(BBI); 306 BBI.Kind = ICTriangle; 307 FalseBBI.Kind = ICChild; 308 } else if (FalseBBI.FalseBB == BBI.TrueBB && 309 !TII->ReverseBranchCondition(FalseCond) && 310 TII->SubsumesPredicate(FalseCond, BBI.BrCond)) { 311 // Reverse 'false' block's 'true' and 'false' paths and then 312 // reverse 'true' and 'false' paths. 313 ReverseBranchCondition(FalseBBI); 314 ReverseBranchCondition(BBI); 315 BBI.Kind = ICTriangle; 316 FalseBBI.Kind = ICChild; 317 } 318 } 319 } else if (TrueBBI.TrueBB == FalseBBI.TrueBB && CanRevCond && 320 TrueBBI.BB->pred_size() == 1 && 321 FalseBBI.BB->pred_size() == 1 && 322 // Check the 'true' and 'false' blocks if either isn't ended with 323 // a branch. If the block does not fallthrough to another block 324 // then we need to add a branch to its successor. 325 !(TrueBBI.ModifyPredicate && 326 !TrueBBI.TrueBB && TrueBBI.BB->succ_size()) && 327 !(FalseBBI.ModifyPredicate && 328 !FalseBBI.TrueBB && FalseBBI.BB->succ_size()) && 329 FeasibilityAnalysis(TrueBBI, BBI.BrCond) && 330 FeasibilityAnalysis(FalseBBI, RevCond)) { 331 // Diamond: 332 // EBB 333 // / \_ 334 // | | 335 // TBB FBB 336 // \ / 337 // TailBB 338 // Note TailBB can be empty. 339 BBI.Kind = ICDiamond; 340 TrueBBI.Kind = FalseBBI.Kind = ICChild; 341 BBI.TailBB = TrueBBI.TrueBB; 342 } else { 343 // FIXME: Consider duplicating if BB is small. 344 bool TryTriangle = TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB && 345 TrueBBI.BB->pred_size() == 1; 346 bool TrySimple = TrueBBI.BrCond.size() == 0 && TrueBBI.BB->pred_size() == 1; 347 if ((TryTriangle || TrySimple) && 348 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { 349 if (TryTriangle) { 350 // Triangle: 351 // EBB 352 // | \_ 353 // | | 354 // | TBB 355 // | / 356 // FBB 357 BBI.Kind = ICTriangle; 358 TrueBBI.Kind = ICChild; 359 } else { 360 // Simple (split, no rejoin): 361 // EBB 362 // | \_ 363 // | | 364 // | TBB---> exit 365 // | 366 // FBB 367 BBI.Kind = ICSimple; 368 TrueBBI.Kind = ICChild; 369 } 370 } else if (FalseBBI.BrCond.size() == 0 && FalseBBI.BB->pred_size() == 1) { 371 // Try the other path... 372 bool TryTriangle = FalseBBI.TrueBB && FalseBBI.TrueBB == BBI.TrueBB && 373 FalseBBI.BB->pred_size() == 1; 374 std::vector<MachineOperand> RevCond(BBI.BrCond); 375 if (!TII->ReverseBranchCondition(RevCond) && 376 FeasibilityAnalysis(FalseBBI, RevCond)) { 377 if (TryTriangle) { 378 // Reverse 'true' and 'false' paths. 379 ReverseBranchCondition(BBI); 380 BBI.Kind = ICTriangle; 381 FalseBBI.Kind = ICChild; 382 } else { 383 BBI.Kind = ICSimpleFalse; 384 FalseBBI.Kind = ICChild; 385 } 386 } 387 } 388 } 389 return; 390} 391 392/// FeasibilityAnalysis - Determine if the block is predicable. In most 393/// cases, that means all the instructions in the block has M_PREDICABLE flag. 394/// Also checks if the block contains any instruction which can clobber a 395/// predicate (e.g. condition code register). If so, the block is not 396/// predicable unless it's the last instruction. If IgnoreTerm is true then 397/// all the terminator instructions are skipped. 398bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, 399 std::vector<MachineOperand> &Cond, 400 bool IgnoreTerm) { 401 // If the block is dead, or it is going to be the entry block of a sub-CFG 402 // that will be if-converted, then it cannot be predicated. 403 if (BBI.Kind != ICNotAnalyzed && 404 BBI.Kind != ICNotClassfied && 405 BBI.Kind != ICChild) 406 return false; 407 408 // Check predication threshold. 409 if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit()) 410 return false; 411 412 // If it is already predicated, check if its predicate subsumes the new 413 // predicate. 414 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Cond)) 415 return false; 416 417 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 418 I != E; ++I) { 419 if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode())) 420 continue; 421 // TODO: check if instruction clobbers predicate. 422 if (!I->isPredicable()) 423 return false; 424 } 425 426 return true; 427} 428 429/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to 430/// expose more if-conversion opportunities. e.g. 431/// 432/// cmp 433/// b le BB1 434/// / \____ 435/// / | 436/// cmp | 437/// b eq BB1 | 438/// / \____ | 439/// / \ | 440/// BB1 441/// ==> 442/// 443/// cmp 444/// b eq BB1 445/// / \____ 446/// / | 447/// cmp | 448/// b le BB1 | 449/// / \____ | 450/// / \ | 451/// BB1 452bool IfConverter::AttemptRestructuring(BBInfo &BBI) { 453 return false; 454} 455 456/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 457/// candidates. It returns true if any CFG restructuring is done to expose more 458/// if-conversion opportunities. 459bool IfConverter::AnalyzeBlocks(MachineFunction &MF, 460 std::vector<BBInfo*> &Candidates) { 461 bool Change = false; 462 std::set<MachineBasicBlock*> Visited; 463 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 464 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 465 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 466 MachineBasicBlock *BB = *I; 467 StructuralAnalysis(BB); 468 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 469 switch (BBI.Kind) { 470 case ICSimple: 471 case ICSimpleFalse: 472 case ICTriangle: 473 case ICDiamond: 474 Candidates.push_back(&BBI); 475 break; 476 default: 477 Change |= AttemptRestructuring(BBI); 478 break; 479 } 480 } 481 } 482 483 // Sort to favor more complex ifcvt scheme. 484 std::stable_sort(Candidates.begin(), Candidates.end(), IfcvtCandidateCmp); 485 486 return Change; 487} 488 489/// isNextBlock - Returns true either if ToBB the next block after BB or 490/// that all the intervening blocks are empty. 491static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 492 MachineFunction::iterator I = BB; 493 MachineFunction::iterator TI = ToBB; 494 MachineFunction::iterator E = BB->getParent()->end(); 495 while (++I != TI) 496 if (I == E || !I->empty()) 497 return false; 498 return true; 499} 500 501/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed 502/// to determine if it can be if-converted. 503void IfConverter::ReTryPreds(MachineBasicBlock *BB) { 504 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 505 E = BB->pred_end(); PI != E; ++PI) { 506 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 507 PBBI.Kind = ICReAnalyze; 508 } 509} 510 511/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 512/// 513static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 514 const TargetInstrInfo *TII) { 515 std::vector<MachineOperand> NoCond; 516 TII->InsertBranch(*BB, ToBB, NULL, NoCond); 517} 518 519/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. 520/// 521bool IfConverter::IfConvertSimple(BBInfo &BBI) { 522 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 523 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 524 BBInfo *CvtBBI = &TrueBBI; 525 BBInfo *NextBBI = &FalseBBI; 526 527 std::vector<MachineOperand> Cond(BBI.BrCond); 528 if (BBI.Kind == ICSimpleFalse) { 529 std::swap(CvtBBI, NextBBI); 530 TII->ReverseBranchCondition(Cond); 531 } 532 533 PredicateBlock(*CvtBBI, Cond); 534 // If the 'true' block ends without a branch, add a conditional branch 535 // to its successor unless that happens to be the 'false' block. 536 if (CvtBBI->IsAnalyzable && CvtBBI->TrueBB == NULL) { 537 assert(CvtBBI->BB->succ_size() == 1 && "Unexpected!"); 538 MachineBasicBlock *SuccBB = *CvtBBI->BB->succ_begin(); 539 if (SuccBB != NextBBI->BB) 540 TII->InsertBranch(*CvtBBI->BB, SuccBB, NULL, Cond); 541 } 542 543 // Merge converted block into entry block. Also add an unconditional branch 544 // to the 'false' branch. 545 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 546 MergeBlocks(BBI, *CvtBBI); 547 bool IterIfcvt = true; 548 if (!isNextBlock(BBI.BB, NextBBI->BB)) { 549 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 550 if (BBI.ModifyPredicate) 551 // Now ifcvt'd block will look like this: 552 // BB: 553 // ... 554 // t, f = cmp 555 // if t op 556 // b BBf 557 // 558 // We cannot further ifcvt this block because the unconditional branch will 559 // have to be predicated on the new condition, that will not be available 560 // if cmp executes. 561 IterIfcvt = false; 562 } 563 std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate)); 564 565 // Update block info. BB can be iteratively if-converted. 566 if (IterIfcvt) 567 BBI.Kind = ICReAnalyze; 568 else 569 BBI.Kind = ICDead; 570 ReTryPreds(BBI.BB); 571 CvtBBI->Kind = ICDead; 572 573 // FIXME: Must maintain LiveIns. 574 return true; 575} 576 577/// IfConvertTriangle - If convert a triangle sub-CFG. 578/// 579bool IfConverter::IfConvertTriangle(BBInfo &BBI) { 580 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 581 582 // Predicate the 'true' block after removing its branch. 583 TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB); 584 PredicateBlock(TrueBBI, BBI.BrCond); 585 586 // If 'true' block has a 'false' successor, add an exit branch to it. 587 bool HasEarlyExit = TrueBBI.FalseBB != NULL; 588 if (HasEarlyExit) { 589 std::vector<MachineOperand> RevCond(TrueBBI.BrCond); 590 if (TII->ReverseBranchCondition(RevCond)) 591 assert(false && "Unable to reverse branch condition!"); 592 TII->InsertBranch(*BBI.TrueBB, TrueBBI.FalseBB, NULL, RevCond); 593 } 594 595 // Join the 'true' and 'false' blocks if the 'false' block has no other 596 // predecessors. Otherwise, add a unconditional branch from 'true' to 'false'. 597 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 598 bool FalseBBDead = false; 599 bool IterIfcvt = true; 600 if (!HasEarlyExit && FalseBBI.BB->pred_size() == 2) { 601 MergeBlocks(TrueBBI, FalseBBI); 602 FalseBBDead = true; 603 } else if (!isNextBlock(TrueBBI.BB, FalseBBI.BB)) { 604 InsertUncondBranch(TrueBBI.BB, FalseBBI.BB, TII); 605 if (BBI.ModifyPredicate || TrueBBI.ModifyPredicate) 606 // Now ifcvt'd block will look like this: 607 // BB: 608 // ... 609 // t, f = cmp 610 // if t op 611 // b BBf 612 // 613 // We cannot further ifcvt this block because the unconditional branch will 614 // have to be predicated on the new condition, that will not be available 615 // if cmp executes. 616 IterIfcvt = false; 617 } 618 619 // Now merge the entry of the triangle with the true block. 620 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 621 MergeBlocks(BBI, TrueBBI); 622 std::copy(BBI.BrCond.begin(), BBI.BrCond.end(), 623 std::back_inserter(BBI.Predicate)); 624 625 // Update block info. BB can be iteratively if-converted. 626 if (IterIfcvt) 627 BBI.Kind = ICReAnalyze; 628 else 629 BBI.Kind = ICDead; 630 ReTryPreds(BBI.BB); 631 TrueBBI.Kind = ICDead; 632 if (FalseBBDead) 633 FalseBBI.Kind = ICDead; 634 635 // FIXME: Must maintain LiveIns. 636 return true; 637} 638 639/// IfConvertDiamond - If convert a diamond sub-CFG. 640/// 641bool IfConverter::IfConvertDiamond(BBInfo &BBI) { 642 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 643 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 644 645 SmallVector<MachineInstr*, 2> Dups; 646 if (!BBI.TailBB) { 647 // No common merge block. Check if the terminators (e.g. return) are 648 // the same or predicable. 649 MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator(); 650 MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator(); 651 while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) { 652 if (TT->isIdenticalTo(FT)) 653 Dups.push_back(TT); // Will erase these later. 654 else if (!TT->isPredicable() && !FT->isPredicable()) 655 return false; // Can't if-convert. Abort! 656 ++TT; 657 ++FT; 658 } 659 660 // One of the two pathes have more terminators, make sure they are 661 // all predicable. 662 while (TT != BBI.TrueBB->end()) { 663 if (!TT->isPredicable()) { 664 return false; // Can't if-convert. Abort! 665 } 666 ++TT; 667 } 668 while (FT != BBI.FalseBB->end()) { 669 if (!FT->isPredicable()) { 670 return false; // Can't if-convert. Abort! 671 } 672 ++FT; 673 } 674 } 675 676 // Remove the duplicated instructions from the 'true' block. 677 for (unsigned i = 0, e = Dups.size(); i != e; ++i) { 678 Dups[i]->eraseFromParent(); 679 --TrueBBI.NonPredSize; 680 } 681 682 // Merge the 'true' and 'false' blocks by copying the instructions 683 // from the 'false' block to the 'true' block. That is, unless the true 684 // block would clobber the predicate, in that case, do the opposite. 685 BBInfo *BBI1 = &TrueBBI; 686 BBInfo *BBI2 = &FalseBBI; 687 std::vector<MachineOperand> RevCond(BBI.BrCond); 688 TII->ReverseBranchCondition(RevCond); 689 std::vector<MachineOperand> *Cond1 = &BBI.BrCond; 690 std::vector<MachineOperand> *Cond2 = &RevCond; 691 // Check the 'true' and 'false' blocks if either isn't ended with a branch. 692 // Either the block fallthrough to another block or it ends with a 693 // return. If it's the former, add a branch to its successor. 694 bool NeedBr1 = !BBI1->TrueBB && BBI1->BB->succ_size(); 695 bool NeedBr2 = !BBI2->TrueBB && BBI2->BB->succ_size(); 696 697 if ((TrueBBI.ModifyPredicate && !FalseBBI.ModifyPredicate) || 698 (!TrueBBI.ModifyPredicate && !FalseBBI.ModifyPredicate && 699 NeedBr1 && !NeedBr2)) { 700 std::swap(BBI1, BBI2); 701 std::swap(Cond1, Cond2); 702 std::swap(NeedBr1, NeedBr2); 703 } 704 705 // Predicate the 'true' block after removing its branch. 706 BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB); 707 PredicateBlock(*BBI1, *Cond1); 708 709 // Add an early exit branch if needed. 710 if (NeedBr1) 711 TII->InsertBranch(*BBI1->BB, *BBI1->BB->succ_begin(), NULL, *Cond1); 712 713 // Predicate the 'false' block. 714 PredicateBlock(*BBI2, *Cond2, true); 715 716 // Add an unconditional branch from 'false' to to 'false' successor if it 717 // will not be the fallthrough block. 718 if (NeedBr2 && !isNextBlock(BBI2->BB, *BBI2->BB->succ_begin())) 719 InsertUncondBranch(BBI2->BB, *BBI2->BB->succ_begin(), TII); 720 721 // Keep them as two separate blocks if there is an early exit. 722 if (!NeedBr1) 723 MergeBlocks(*BBI1, *BBI2); 724 725 // Remove the conditional branch from entry to the blocks. 726 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 727 728 // Merge the combined block into the entry of the diamond. 729 MergeBlocks(BBI, *BBI1); 730 731 // 'True' and 'false' aren't combined, see if we need to add a unconditional 732 // branch to the 'false' block. 733 if (NeedBr1 && !isNextBlock(BBI.BB, BBI2->BB)) 734 InsertUncondBranch(BBI1->BB, BBI2->BB, TII); 735 736 // If the if-converted block fallthrough or unconditionally branch into the 737 // tail block, and the tail block does not have other predecessors, then 738 // fold the tail block in as well. 739 BBInfo *CvtBBI = NeedBr1 ? BBI2 : &BBI; 740 if (BBI.TailBB && 741 BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) { 742 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 743 BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()]; 744 MergeBlocks(*CvtBBI, TailBBI); 745 TailBBI.Kind = ICDead; 746 } 747 748 // Update block info. 749 BBI.Kind = ICDead; 750 TrueBBI.Kind = ICDead; 751 FalseBBI.Kind = ICDead; 752 753 // FIXME: Must maintain LiveIns. 754 return true; 755} 756 757/// PredicateBlock - Predicate every instruction in the block with the specified 758/// condition. If IgnoreTerm is true, skip over all terminator instructions. 759void IfConverter::PredicateBlock(BBInfo &BBI, 760 std::vector<MachineOperand> &Cond, 761 bool IgnoreTerm) { 762 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 763 I != E; ++I) { 764 if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode())) 765 continue; 766 if (TII->isPredicated(I)) 767 continue; 768 if (!TII->PredicateInstruction(I, Cond)) { 769 cerr << "Unable to predicate " << *I << "!\n"; 770 abort(); 771 } 772 } 773 774 BBI.NonPredSize = 0; 775 NumIfConvBBs++; 776} 777 778/// TransferPreds - Transfer all the predecessors of FromBB to ToBB. 779/// 780static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 781 for (MachineBasicBlock::pred_iterator I = FromBB->pred_begin(), 782 E = FromBB->pred_end(); I != E; ++I) { 783 MachineBasicBlock *Pred = *I; 784 Pred->removeSuccessor(FromBB); 785 if (!Pred->isSuccessor(ToBB)) 786 Pred->addSuccessor(ToBB); 787 } 788} 789 790/// TransferSuccs - Transfer all the successors of FromBB to ToBB. 791/// 792static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) { 793 for (MachineBasicBlock::succ_iterator I = FromBB->succ_begin(), 794 E = FromBB->succ_end(); I != E; ++I) { 795 MachineBasicBlock *Succ = *I; 796 FromBB->removeSuccessor(Succ); 797 if (!ToBB->isSuccessor(Succ)) 798 ToBB->addSuccessor(Succ); 799 } 800} 801 802/// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 803/// 804void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { 805 ToBBI.BB->splice(ToBBI.BB->end(), 806 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 807 808 // If FromBBI is previously a successor, remove it from ToBBI's successor 809 // list and update its TrueBB / FalseBB field if needed. 810 if (ToBBI.BB->isSuccessor(FromBBI.BB)) 811 ToBBI.BB->removeSuccessor(FromBBI.BB); 812 813 // Redirect all branches to FromBB to ToBB. 814 std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(), 815 FromBBI.BB->pred_end()); 816 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 817 Preds[i]->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB); 818 819 // Transfer preds / succs and update size. 820 TransferPreds(ToBBI.BB, FromBBI.BB); 821 if (!blockFallsThrough(FromBBI)) 822 TransferSuccs(ToBBI.BB, FromBBI.BB); 823 ToBBI.NonPredSize += FromBBI.NonPredSize; 824 FromBBI.NonPredSize = 0; 825 826 ToBBI.ModifyPredicate |= FromBBI.ModifyPredicate; 827} 828