IfConversion.cpp revision 9618bcaf7d3e6fd4a26fab47efb0bd2409b69e0f
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/CommandLine.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/ADT/DepthFirstIterator.h" 25#include "llvm/ADT/Statistic.h" 26using namespace llvm; 27 28namespace { 29 // Hidden options for help debugging. 30 cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); 31 cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); 32 cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); 33 cl::opt<bool> DisableSimple("disable-ifcvt-simple", 34 cl::init(false), cl::Hidden); 35 cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 36 cl::init(false), cl::Hidden); 37 cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 38 cl::init(false), cl::Hidden); 39 cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 40 cl::init(false), cl::Hidden); 41 cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 42 cl::init(false), cl::Hidden); 43 cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 44 cl::init(false), cl::Hidden); 45} 46 47STATISTIC(NumSimple, "Number of simple if-conversions performed"); 48STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed"); 49STATISTIC(NumTriangle, "Number of triangle if-conversions performed"); 50STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed"); 51STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed"); 52STATISTIC(NumDiamonds, "Number of diamond if-conversions performed"); 53STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 54 55namespace { 56 class IfConverter : public MachineFunctionPass { 57 enum BBICKind { 58 ICNotClassfied, // BB data valid, but not classified. 59 ICSimple, // BB is entry of an one split, no rejoin sub-CFG. 60 ICSimpleFalse, // Same as ICSimple, but on the false path. 61 ICTriangle, // BB is entry of a triangle sub-CFG. 62 ICTriangleFalse, // Same as ICTriangle, but on the false path. 63 ICTriangleFRev, // Same as ICTriangleFalse, but false path rev condition. 64 ICDiamond // BB is entry of a diamond sub-CFG. 65 }; 66 67 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 68 /// if-conversion feasibility analysis. This includes results from 69 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 70 /// classification, and common tail block of its successors (if it's a 71 /// diamond shape), its size, whether it's predicable, and whether any 72 /// instruction can clobber the 'would-be' predicate. 73 /// 74 /// Kind - Type of block. See BBICKind. 75 /// IsDone - True if BB is not to be considered for ifcvt. 76 /// IsBeingAnalyzed - True if BB is currently being analyzed. 77 /// IsAnalyzed - True if BB has been analyzed (info is still valid). 78 /// IsEnqueued - True if BB has been enqueued to be ifcvt'ed. 79 /// IsBrAnalyzable - True if AnalyzeBranch() returns false. 80 /// HasFallThrough - True if BB may fallthrough to the following BB. 81 /// IsUnpredicable - True if BB is known to be unpredicable. 82 /// ClobbersPredicate- True if BB would modify the predicate (e.g. has 83 /// cmp, call, etc.) 84 /// NonPredSize - Number of non-predicated instructions. 85 /// BB - Corresponding MachineBasicBlock. 86 /// TrueBB / FalseBB- See AnalyzeBranch(). 87 /// BrCond - Conditions for end of block conditional branches. 88 /// Predicate - Predicate used in the BB. 89 struct BBInfo { 90 BBICKind Kind; 91 bool IsDone : 1; 92 bool IsBeingAnalyzed : 1; 93 bool IsAnalyzed : 1; 94 bool IsEnqueued : 1; 95 bool IsBrAnalyzable : 1; 96 bool HasFallThrough : 1; 97 bool IsUnpredicable : 1; 98 bool ClobbersPred : 1; 99 unsigned NonPredSize; 100 MachineBasicBlock *BB; 101 MachineBasicBlock *TrueBB; 102 MachineBasicBlock *FalseBB; 103 MachineBasicBlock *TailBB; 104 std::vector<MachineOperand> BrCond; 105 std::vector<MachineOperand> Predicate; 106 BBInfo() : Kind(ICNotClassfied), IsDone(false), IsBeingAnalyzed(false), 107 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), 108 HasFallThrough(false), IsUnpredicable(false), 109 ClobbersPred(false), NonPredSize(0), 110 BB(0), TrueBB(0), FalseBB(0), TailBB(0) {} 111 }; 112 113 /// Roots - Basic blocks that do not have successors. These are the starting 114 /// points of Graph traversal. 115 std::vector<MachineBasicBlock*> Roots; 116 117 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 118 /// basic block number. 119 std::vector<BBInfo> BBAnalysis; 120 121 const TargetLowering *TLI; 122 const TargetInstrInfo *TII; 123 bool MadeChange; 124 public: 125 static char ID; 126 IfConverter() : MachineFunctionPass((intptr_t)&ID) {} 127 128 virtual bool runOnMachineFunction(MachineFunction &MF); 129 virtual const char *getPassName() const { return "If converter"; } 130 131 private: 132 bool ReverseBranchCondition(BBInfo &BBI); 133 bool ValidSimple(BBInfo &TrueBBI) const; 134 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 135 bool FalseBranch = false) const; 136 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI) const; 137 void ScanInstructions(BBInfo &BBI); 138 BBInfo &AnalyzeBlock(MachineBasicBlock *BB); 139 bool FeasibilityAnalysis(BBInfo &BBI, std::vector<MachineOperand> &Cond, 140 bool isTriangle = false, bool RevBranch = false); 141 bool AttemptRestructuring(BBInfo &BBI); 142 bool AnalyzeBlocks(MachineFunction &MF, 143 std::vector<BBInfo*> &Candidates); 144 void ReTryPreds(MachineBasicBlock *BB); 145 void RemoveExtraEdges(BBInfo &BBI); 146 bool IfConvertSimple(BBInfo &BBI); 147 bool IfConvertTriangle(BBInfo &BBI); 148 bool IfConvertDiamond(BBInfo &BBI); 149 void PredicateBlock(BBInfo &BBI, 150 std::vector<MachineOperand> &Cond, 151 bool IgnoreTerm = false); 152 void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI); 153 154 // blockAlwaysFallThrough - Block ends without a terminator. 155 bool blockAlwaysFallThrough(BBInfo &BBI) const { 156 return BBI.IsBrAnalyzable && BBI.TrueBB == NULL; 157 } 158 159 // IfcvtCandidateCmp - Used to sort if-conversion candidates. 160 static bool IfcvtCandidateCmp(BBInfo* C1, BBInfo* C2){ 161 // Favor diamond over triangle, etc. 162 return (unsigned)C1->Kind < (unsigned)C2->Kind; 163 } 164 }; 165 char IfConverter::ID = 0; 166} 167 168FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 169 170bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 171 TLI = MF.getTarget().getTargetLowering(); 172 TII = MF.getTarget().getInstrInfo(); 173 if (!TII) return false; 174 175 static int FnNum = -1; 176 DOUT << "\nIfcvt: function (" << ++FnNum << ") \'" 177 << MF.getFunction()->getName() << "\'"; 178 179 if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { 180 DOUT << " skipped\n"; 181 return false; 182 } 183 DOUT << "\n"; 184 185 MF.RenumberBlocks(); 186 BBAnalysis.resize(MF.getNumBlockIDs()); 187 188 // Look for root nodes, i.e. blocks without successors. 189 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 190 if (I->succ_size() == 0) 191 Roots.push_back(I); 192 193 std::vector<BBInfo*> Candidates; 194 MadeChange = false; 195 while (IfCvtLimit == -1 || (int)NumIfConvBBs < IfCvtLimit) { 196 // Do an intial analysis for each basic block and finding all the potential 197 // candidates to perform if-convesion. 198 bool Change = AnalyzeBlocks(MF, Candidates); 199 while (!Candidates.empty()) { 200 BBInfo &BBI = *Candidates.back(); 201 Candidates.pop_back(); 202 203 // If the block has been evicted out of the queue or it has already been 204 // marked dead (due to it being predicated), then skip it. 205 if (!BBI.IsEnqueued || BBI.IsDone) 206 continue; 207 208 bool RetVal = false; 209 switch (BBI.Kind) { 210 default: assert(false && "Unexpected!"); 211 break; 212 case ICSimple: 213 case ICSimpleFalse: { 214 bool isFalse = BBI.Kind == ICSimpleFalse; 215 if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break; 216 DOUT << "Ifcvt (Simple" << (BBI.Kind == ICSimpleFalse ? " false" : "") 217 << "): BB#" << BBI.BB->getNumber() << " (" 218 << ((BBI.Kind == ICSimpleFalse) 219 ? BBI.FalseBB->getNumber() : BBI.TrueBB->getNumber()) << ") "; 220 RetVal = IfConvertSimple(BBI); 221 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 222 if (RetVal) 223 if (isFalse) NumSimpleFalse++; 224 else NumSimple++; 225 break; 226 } 227 case ICTriangle: 228 case ICTriangleFalse: 229 case ICTriangleFRev: { 230 bool isFalse = BBI.Kind == ICTriangleFalse; 231 bool isFalseRev = BBI.Kind == ICTriangleFRev; 232 if (DisableTriangle && !isFalse && !isFalseRev) break; 233 if (DisableTriangleF && isFalse) break; 234 if (DisableTriangleFR && isFalseRev) break; 235 DOUT << "Ifcvt (Triangle"; 236 if (isFalse) 237 DOUT << " false"; 238 if (isFalseRev) 239 DOUT << " false/rev"; 240 DOUT << "): BB#" << BBI.BB->getNumber() << " (T:" 241 << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber() 242 << ") "; 243 RetVal = IfConvertTriangle(BBI); 244 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 245 if (RetVal) { 246 if (isFalseRev) NumTriangleFRev++; 247 else if (isFalse) NumTriangleFalse++; 248 else NumTriangle++; 249 } 250 break; 251 } 252 case ICDiamond: 253 if (DisableDiamond) break; 254 DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" 255 << BBI.TrueBB->getNumber() << ",F:" << BBI.FalseBB->getNumber(); 256 if (BBI.TailBB) 257 DOUT << "," << BBI.TailBB->getNumber() ; 258 DOUT << ") "; 259 RetVal = IfConvertDiamond(BBI); 260 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 261 if (RetVal) NumDiamonds++; 262 break; 263 } 264 Change |= RetVal; 265 266 if (IfCvtLimit != -1 && (int)NumIfConvBBs >= IfCvtLimit) 267 break; 268 } 269 270 if (!Change) 271 break; 272 MadeChange |= Change; 273 } 274 275 Roots.clear(); 276 BBAnalysis.clear(); 277 278 return MadeChange; 279} 280 281static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 282 MachineBasicBlock *TrueBB) { 283 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 284 E = BB->succ_end(); SI != E; ++SI) { 285 MachineBasicBlock *SuccBB = *SI; 286 if (SuccBB != TrueBB) 287 return SuccBB; 288 } 289 return NULL; 290} 291 292bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { 293 if (!TII->ReverseBranchCondition(BBI.BrCond)) { 294 TII->RemoveBranch(*BBI.BB); 295 TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond); 296 std::swap(BBI.TrueBB, BBI.FalseBB); 297 return true; 298 } 299 return false; 300} 301 302/// getNextBlock - Returns the next block in the function blocks ordering. If 303/// it is the end, returns NULL. 304static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) { 305 MachineFunction::iterator I = BB; 306 MachineFunction::iterator E = BB->getParent()->end(); 307 if (++I == E) 308 return NULL; 309 return I; 310} 311 312/// ValidSimple - Returns true if the 'true' block (along with its 313/// predecessor) forms a valid simple shape for ifcvt. 314bool IfConverter::ValidSimple(BBInfo &TrueBBI) const { 315 if (TrueBBI.IsBeingAnalyzed) 316 return false; 317 318 return !blockAlwaysFallThrough(TrueBBI) && 319 TrueBBI.BrCond.size() == 0 && TrueBBI.BB->pred_size() == 1; 320} 321 322/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along 323/// with their common predecessor) forms a valid triangle shape for ifcvt. 324bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 325 bool FalseBranch) const { 326 if (TrueBBI.IsBeingAnalyzed) 327 return false; 328 329 if (TrueBBI.BB->pred_size() != 1) 330 return false; 331 332 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB; 333 if (!TExit && blockAlwaysFallThrough(TrueBBI)) { 334 MachineFunction::iterator I = TrueBBI.BB; 335 if (++I == TrueBBI.BB->getParent()->end()) 336 return false; 337 TExit = I; 338 } 339 return TExit && TExit == FalseBBI.BB; 340} 341 342/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along 343/// with their common predecessor) forms a valid diamond shape for ifcvt. 344bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI) const { 345 if (TrueBBI.IsBeingAnalyzed || FalseBBI.IsBeingAnalyzed) 346 return false; 347 348 MachineBasicBlock *TT = TrueBBI.TrueBB; 349 MachineBasicBlock *FT = FalseBBI.TrueBB; 350 351 if (!TT && blockAlwaysFallThrough(TrueBBI)) 352 TT = getNextBlock(TrueBBI.BB); 353 if (!FT && blockAlwaysFallThrough(FalseBBI)) 354 FT = getNextBlock(FalseBBI.BB); 355 if (TT != FT) 356 return false; 357 if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable)) 358 return false; 359 // FIXME: Allow false block to have an early exit? 360 return (TrueBBI.BB->pred_size() == 1 && 361 FalseBBI.BB->pred_size() == 1 && 362 !TrueBBI.FalseBB && !FalseBBI.FalseBB); 363} 364 365/// ScanInstructions - Scan all the instructions in the block to determine if 366/// the block is predicable. In most cases, that means all the instructions 367/// in the block has M_PREDICABLE flag. Also checks if the block contains any 368/// instruction which can clobber a predicate (e.g. condition code register). 369/// If so, the block is not predicable unless it's the last instruction. 370void IfConverter::ScanInstructions(BBInfo &BBI) { 371 if (BBI.IsDone) 372 return; 373 374 // First analyze the end of BB branches. 375 BBI.TrueBB = BBI.FalseBB; 376 BBI.BrCond.clear(); 377 BBI.IsBrAnalyzable = 378 !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 379 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL; 380 381 if (BBI.BrCond.size()) { 382 // No false branch. This BB must end with a conditional branch and a 383 // fallthrough. 384 if (!BBI.FalseBB) 385 BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB); 386 assert(BBI.FalseBB && "Expected to find the fallthrough block!"); 387 } 388 389 // Then scan all the instructions. 390 BBI.NonPredSize = 0; 391 BBI.ClobbersPred = false; 392 bool SeenCondBr = false; 393 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 394 I != E; ++I) { 395 const TargetInstrDescriptor *TID = I->getInstrDescriptor(); 396 bool isPredicated = TII->isPredicated(I); 397 bool isCondBr = BBI.IsBrAnalyzable && 398 (TID->Flags & M_BRANCH_FLAG) != 0 && (TID->Flags & M_BARRIER_FLAG) == 0; 399 400 if (!isPredicated && !isCondBr) 401 BBI.NonPredSize++; 402 403 if (BBI.ClobbersPred && !isPredicated) { 404 // Predicate modification instruction should end the block (except for 405 // already predicated instructions and end of block branches). 406 if (isCondBr) { 407 SeenCondBr = true; 408 409 // Conditional branches is not predicable. But it may be eliminated. 410 continue; 411 } 412 413 // Predicate may have been modified, the subsequent (currently) 414 // unpredocated instructions cannot be correctly predicated. 415 BBI.IsUnpredicable = true; 416 return; 417 } 418 419 if (TID->Flags & M_CLOBBERS_PRED) 420 BBI.ClobbersPred = true; 421 422 if (!I->isPredicable()) { 423 BBI.IsUnpredicable = true; 424 return; 425 } 426 } 427} 428 429/// FeasibilityAnalysis - Determine if the block is a suitable candidate to be 430/// predicated by the specified predicate. 431bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, 432 std::vector<MachineOperand> &Pred, 433 bool isTriangle, bool RevBranch) { 434 // Forget about it if it's unpredicable. 435 if (BBI.IsUnpredicable) 436 return false; 437 438 // If the block is dead, or it is going to be the entry block of a sub-CFG 439 // that will be if-converted, then it cannot be predicated. 440 if (BBI.IsDone || BBI.IsEnqueued) 441 return false; 442 443 // Check predication threshold. 444 if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit()) 445 return false; 446 447 // If it is already predicated, check if its predicate subsumes the new 448 // predicate. 449 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred)) 450 return false; 451 452 if (BBI.BrCond.size()) { 453 if (!isTriangle) 454 return false; 455 456 // Test predicate subsumsion. 457 std::vector<MachineOperand> RevPred(Pred); 458 std::vector<MachineOperand> Cond(BBI.BrCond); 459 if (RevBranch) { 460 if (TII->ReverseBranchCondition(Cond)) 461 return false; 462 } 463 if (TII->ReverseBranchCondition(RevPred) || 464 !TII->SubsumesPredicate(Cond, RevPred)) 465 return false; 466 } 467 468 return true; 469} 470 471/// AnalyzeBlock - Analyze the structure of the sub-CFG starting from 472/// the specified block. Record its successors and whether it looks like an 473/// if-conversion candidate. 474IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB) { 475 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 476 477 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) 478 return BBI; 479 480 BBI.BB = BB; 481 BBI.IsBeingAnalyzed = true; 482 BBI.Kind = ICNotClassfied; 483 484 ScanInstructions(BBI); 485 486 // Unanalyable or ends with fallthrough or unconditional branch. 487 if (!BBI.IsBrAnalyzable || BBI.BrCond.size() == 0) { 488 BBI.IsBeingAnalyzed = false; 489 BBI.IsAnalyzed = true; 490 return BBI; 491 } 492 493 // Do not ifcvt if either path is a back edge to the entry block. 494 if (BBI.TrueBB == BB || BBI.FalseBB == BB) { 495 BBI.IsBeingAnalyzed = false; 496 BBI.IsAnalyzed = true; 497 return BBI; 498 } 499 500 BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB); 501 BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB); 502 503 if (TrueBBI.IsDone && FalseBBI.IsDone) { 504 BBI.IsBeingAnalyzed = false; 505 BBI.IsAnalyzed = true; 506 return BBI; 507 } 508 509 std::vector<MachineOperand> RevCond(BBI.BrCond); 510 bool CanRevCond = !TII->ReverseBranchCondition(RevCond); 511 512 if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI) && 513 !(TrueBBI.ClobbersPred && FalseBBI.ClobbersPred) && 514 FeasibilityAnalysis(TrueBBI, BBI.BrCond) && 515 FeasibilityAnalysis(FalseBBI, RevCond)) { 516 // Diamond: 517 // EBB 518 // / \_ 519 // | | 520 // TBB FBB 521 // \ / 522 // TailBB 523 // Note TailBB can be empty. 524 BBI.Kind = ICDiamond; 525 BBI.TailBB = TrueBBI.TrueBB; 526 } else { 527 // FIXME: Consider duplicating if BB is small. 528 if (ValidTriangle(TrueBBI, FalseBBI) && 529 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { 530 // Triangle: 531 // EBB 532 // | \_ 533 // | | 534 // | TBB 535 // | / 536 // FBB 537 BBI.Kind = ICTriangle; 538 } else if (ValidSimple(TrueBBI) && 539 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { 540 // Simple (split, no rejoin): 541 // EBB 542 // | \_ 543 // | | 544 // | TBB---> exit 545 // | 546 // FBB 547 BBI.Kind = ICSimple; 548 } else if (CanRevCond) { 549 // Try the other path... 550 if (ValidTriangle(FalseBBI, TrueBBI) && 551 FeasibilityAnalysis(FalseBBI, RevCond, true)) { 552 BBI.Kind = ICTriangleFalse; 553 } else if (ValidTriangle(FalseBBI, TrueBBI, true) && 554 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { 555 BBI.Kind = ICTriangleFRev; 556 } else if (ValidSimple(FalseBBI) && 557 FeasibilityAnalysis(FalseBBI, RevCond)) { 558 BBI.Kind = ICSimpleFalse; 559 } 560 } 561 } 562 563 BBI.IsBeingAnalyzed = false; 564 BBI.IsAnalyzed = true; 565 return BBI; 566} 567 568/// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to 569/// expose more if-conversion opportunities. e.g. 570/// 571/// cmp 572/// b le BB1 573/// / \____ 574/// / | 575/// cmp | 576/// b eq BB1 | 577/// / \____ | 578/// / \ | 579/// BB1 580/// ==> 581/// 582/// cmp 583/// b eq BB1 584/// / \____ 585/// / | 586/// cmp | 587/// b le BB1 | 588/// / \____ | 589/// / \ | 590/// BB1 591bool IfConverter::AttemptRestructuring(BBInfo &BBI) { 592 return false; 593} 594 595/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 596/// candidates. It returns true if any CFG restructuring is done to expose more 597/// if-conversion opportunities. 598bool IfConverter::AnalyzeBlocks(MachineFunction &MF, 599 std::vector<BBInfo*> &Candidates) { 600 bool Change = false; 601 std::set<MachineBasicBlock*> Visited; 602 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 603 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 604 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 605 MachineBasicBlock *BB = *I; 606 BBInfo &BBI = AnalyzeBlock(BB); 607 switch (BBI.Kind) { 608 case ICSimple: 609 case ICSimpleFalse: 610 case ICTriangle: 611 case ICDiamond: 612 Candidates.push_back(&BBI); 613 break; 614 default: 615 Change |= AttemptRestructuring(BBI); 616 break; 617 } 618 } 619 } 620 621 // Sort to favor more complex ifcvt scheme. 622 std::stable_sort(Candidates.begin(), Candidates.end(), IfcvtCandidateCmp); 623 624 return Change; 625} 626 627/// canFallThroughTo - Returns true either if ToBB is the next block after BB or 628/// that all the intervening blocks are empty (given BB can fall through to its 629/// next block). 630static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 631 MachineFunction::iterator I = BB; 632 MachineFunction::iterator TI = ToBB; 633 MachineFunction::iterator E = BB->getParent()->end(); 634 while (++I != TI) 635 if (I == E || !I->empty()) 636 return false; 637 return true; 638} 639 640/// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed 641/// to determine if it can be if-converted. 642void IfConverter::ReTryPreds(MachineBasicBlock *BB) { 643 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 644 E = BB->pred_end(); PI != E; ++PI) { 645 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 646 if (!PBBI.IsDone && PBBI.Kind == ICNotClassfied) { 647 assert(PBBI.IsEnqueued && "Unexpected"); 648 PBBI.IsAnalyzed = false; 649 } 650 } 651} 652 653/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 654/// 655static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 656 const TargetInstrInfo *TII) { 657 std::vector<MachineOperand> NoCond; 658 TII->InsertBranch(*BB, ToBB, NULL, NoCond); 659} 660 661/// RemoveExtraEdges - Remove true / false edges if either / both are no longer 662/// successors. 663void IfConverter::RemoveExtraEdges(BBInfo &BBI) { 664 MachineBasicBlock *TBB = NULL, *FBB = NULL; 665 std::vector<MachineOperand> Cond; 666 bool isAnalyzable = !TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond); 667 bool CanFallthrough = isAnalyzable && (TBB == NULL || FBB == NULL); 668 if (BBI.TrueBB && BBI.BB->isSuccessor(BBI.TrueBB)) 669 if (!(BBI.TrueBB == TBB || BBI.TrueBB == FBB || 670 (CanFallthrough && getNextBlock(BBI.BB) == BBI.TrueBB))) 671 BBI.BB->removeSuccessor(BBI.TrueBB); 672 if (BBI.FalseBB && BBI.BB->isSuccessor(BBI.FalseBB)) 673 if (!(BBI.FalseBB == TBB || BBI.FalseBB == FBB || 674 (CanFallthrough && getNextBlock(BBI.BB) == BBI.FalseBB))) 675 BBI.BB->removeSuccessor(BBI.FalseBB); 676} 677 678/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. 679/// 680bool IfConverter::IfConvertSimple(BBInfo &BBI) { 681 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 682 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 683 BBInfo *CvtBBI = &TrueBBI; 684 BBInfo *NextBBI = &FalseBBI; 685 686 std::vector<MachineOperand> Cond(BBI.BrCond); 687 if (BBI.Kind == ICSimpleFalse) { 688 std::swap(CvtBBI, NextBBI); 689 TII->ReverseBranchCondition(Cond); 690 } 691 692 PredicateBlock(*CvtBBI, Cond); 693 694 // Merge converted block into entry block. 695 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 696 MergeBlocks(BBI, *CvtBBI); 697 698 bool IterIfcvt = true; 699 if (!canFallThroughTo(BBI.BB, NextBBI->BB)) { 700 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 701 BBI.HasFallThrough = false; 702 // Now ifcvt'd block will look like this: 703 // BB: 704 // ... 705 // t, f = cmp 706 // if t op 707 // b BBf 708 // 709 // We cannot further ifcvt this block because the unconditional branch 710 // will have to be predicated on the new condition, that will not be 711 // available if cmp executes. 712 IterIfcvt = false; 713 } 714 715 RemoveExtraEdges(BBI); 716 717 // Update block info. BB can be iteratively if-converted. 718 if (!IterIfcvt) 719 BBI.IsDone = true; 720 ReTryPreds(BBI.BB); 721 CvtBBI->IsDone = true; 722 723 // FIXME: Must maintain LiveIns. 724 return true; 725} 726 727/// IfConvertTriangle - If convert a triangle sub-CFG. 728/// 729bool IfConverter::IfConvertTriangle(BBInfo &BBI) { 730 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 731 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 732 BBInfo *CvtBBI = &TrueBBI; 733 BBInfo *NextBBI = &FalseBBI; 734 735 std::vector<MachineOperand> Cond(BBI.BrCond); 736 if (BBI.Kind == ICTriangleFalse || BBI.Kind == ICTriangleFRev) { 737 if (BBI.Kind == ICTriangleFRev) { 738 ReverseBranchCondition(*NextBBI); 739 // False BB has been changed, modify its predecessors (except for this 740 // one) so they don't get ifcvt'ed based on bad intel. 741 for (MachineBasicBlock::pred_iterator PI = NextBBI->BB->pred_begin(), 742 E = NextBBI->BB->pred_end(); PI != E; ++PI) { 743 MachineBasicBlock *PBB = *PI; 744 if (PBB == BBI.BB) 745 continue; 746 BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; 747 if (PBBI.IsEnqueued) 748 PBBI.IsEnqueued = false; 749 } 750 } 751 std::swap(CvtBBI, NextBBI); 752 TII->ReverseBranchCondition(Cond); 753 } 754 755 // Predicate the 'true' block after removing its branch. 756 TrueBBI.NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 757 PredicateBlock(*CvtBBI, Cond); 758 759 // If 'true' block has a 'false' successor, add an exit branch to it. 760 bool HasEarlyExit = CvtBBI->FalseBB != NULL; 761 if (HasEarlyExit) { 762 std::vector<MachineOperand> RevCond(CvtBBI->BrCond); 763 if (TII->ReverseBranchCondition(RevCond)) 764 assert(false && "Unable to reverse branch condition!"); 765 TII->InsertBranch(*CvtBBI->BB, CvtBBI->FalseBB, NULL, RevCond); 766 } 767 768 // Now merge the entry of the triangle with the true block. 769 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 770 MergeBlocks(BBI, *CvtBBI); 771 772 // Merge in the 'false' block if the 'false' block has no other 773 // predecessors. Otherwise, add a unconditional branch from to 'false'. 774 bool FalseBBDead = false; 775 bool IterIfcvt = true; 776 bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB); 777 if (!isFallThrough) { 778 // Only merge them if the true block does not fallthrough to the false 779 // block. By not merging them, we make it possible to iteratively 780 // ifcvt the blocks. 781 if (!HasEarlyExit && NextBBI->BB->pred_size() == 1) { 782 MergeBlocks(BBI, *NextBBI); 783 FalseBBDead = true; 784 } else { 785 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 786 BBI.HasFallThrough = false; 787 } 788 // Mixed predicated and unpredicated code. This cannot be iteratively 789 // predicated. 790 IterIfcvt = false; 791 } 792 793 RemoveExtraEdges(BBI); 794 795 // Update block info. BB can be iteratively if-converted. 796 if (!IterIfcvt) 797 BBI.IsDone = true; 798 ReTryPreds(BBI.BB); 799 CvtBBI->IsDone = true; 800 if (FalseBBDead) 801 NextBBI->IsDone = true; 802 803 // FIXME: Must maintain LiveIns. 804 return true; 805} 806 807/// IfConvertDiamond - If convert a diamond sub-CFG. 808/// 809bool IfConverter::IfConvertDiamond(BBInfo &BBI) { 810 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 811 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 812 813 SmallVector<MachineInstr*, 2> Dups; 814 if (!BBI.TailBB) { 815 // No common merge block. Check if the terminators (e.g. return) are 816 // the same or predicable. 817 MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator(); 818 MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator(); 819 while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) { 820 if (TT->isIdenticalTo(FT)) 821 Dups.push_back(TT); // Will erase these later. 822 else if (!TT->isPredicable() && !FT->isPredicable()) 823 return false; // Can't if-convert. Abort! 824 ++TT; 825 ++FT; 826 } 827 828 // One of the two pathes have more terminators, make sure they are 829 // all predicable. 830 while (TT != BBI.TrueBB->end()) { 831 if (!TT->isPredicable()) { 832 return false; // Can't if-convert. Abort! 833 } 834 ++TT; 835 } 836 while (FT != BBI.FalseBB->end()) { 837 if (!FT->isPredicable()) { 838 return false; // Can't if-convert. Abort! 839 } 840 ++FT; 841 } 842 } 843 844 // Remove the duplicated instructions from the 'true' block. 845 for (unsigned i = 0, e = Dups.size(); i != e; ++i) { 846 Dups[i]->eraseFromParent(); 847 --TrueBBI.NonPredSize; 848 } 849 850 // Merge the 'true' and 'false' blocks by copying the instructions 851 // from the 'false' block to the 'true' block. That is, unless the true 852 // block would clobber the predicate, in that case, do the opposite. 853 BBInfo *BBI1 = &TrueBBI; 854 BBInfo *BBI2 = &FalseBBI; 855 std::vector<MachineOperand> RevCond(BBI.BrCond); 856 TII->ReverseBranchCondition(RevCond); 857 std::vector<MachineOperand> *Cond1 = &BBI.BrCond; 858 std::vector<MachineOperand> *Cond2 = &RevCond; 859 // Check the 'true' and 'false' blocks if either isn't ended with a branch. 860 // Either the block fallthrough to another block or it ends with a 861 // return. If it's the former, add a branch to its successor. 862 bool NeedBr1 = !BBI1->TrueBB && BBI1->BB->succ_size(); 863 bool NeedBr2 = !BBI2->TrueBB && BBI2->BB->succ_size(); 864 865 if ((TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred) || 866 (!TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred && 867 NeedBr1 && !NeedBr2)) { 868 std::swap(BBI1, BBI2); 869 std::swap(Cond1, Cond2); 870 std::swap(NeedBr1, NeedBr2); 871 } 872 873 // Predicate the 'true' block after removing its branch. 874 BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB); 875 PredicateBlock(*BBI1, *Cond1); 876 877 // Add an early exit branch if needed. 878 if (NeedBr1) 879 TII->InsertBranch(*BBI1->BB, *BBI1->BB->succ_begin(), NULL, *Cond1); 880 881 // Predicate the 'false' block. 882 PredicateBlock(*BBI2, *Cond2, true); 883 884 // Add an unconditional branch from 'false' to to 'false' successor if it 885 // will not be the fallthrough block. 886 if (NeedBr2 && !NeedBr1) { 887 // If BBI2 isn't going to be merged in, then the existing fallthrough 888 // or branch is fine. 889 if (!canFallThroughTo(BBI.BB, *BBI2->BB->succ_begin())) { 890 InsertUncondBranch(BBI2->BB, *BBI2->BB->succ_begin(), TII); 891 BBI2->HasFallThrough = false; 892 } 893 } 894 895 // Keep them as two separate blocks if there is an early exit. 896 if (!NeedBr1) 897 MergeBlocks(*BBI1, *BBI2); 898 899 // Remove the conditional branch from entry to the blocks. 900 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 901 902 // Merge the combined block into the entry of the diamond. 903 MergeBlocks(BBI, *BBI1); 904 905 // 'True' and 'false' aren't combined, see if we need to add a unconditional 906 // branch to the 'false' block. 907 if (NeedBr1 && !canFallThroughTo(BBI.BB, BBI2->BB)) { 908 InsertUncondBranch(BBI.BB, BBI2->BB, TII); 909 BBI1->HasFallThrough = false; 910 } 911 912 // If the if-converted block fallthrough or unconditionally branch into the 913 // tail block, and the tail block does not have other predecessors, then 914 // fold the tail block in as well. 915 BBInfo *CvtBBI = NeedBr1 ? BBI2 : &BBI; 916 if (BBI.TailBB && 917 BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) { 918 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 919 BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()]; 920 MergeBlocks(*CvtBBI, TailBBI); 921 TailBBI.IsDone = true; 922 } 923 924 RemoveExtraEdges(BBI); 925 926 // Update block info. 927 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true; 928 929 // FIXME: Must maintain LiveIns. 930 return true; 931} 932 933/// PredicateBlock - Predicate every instruction in the block with the specified 934/// condition. If IgnoreTerm is true, skip over all terminator instructions. 935void IfConverter::PredicateBlock(BBInfo &BBI, 936 std::vector<MachineOperand> &Cond, 937 bool IgnoreTerm) { 938 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 939 I != E; ++I) { 940 if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode())) 941 continue; 942 if (TII->isPredicated(I)) 943 continue; 944 if (!TII->PredicateInstruction(I, Cond)) { 945 cerr << "Unable to predicate " << *I << "!\n"; 946 abort(); 947 } 948 } 949 950 BBI.NonPredSize = 0; 951 std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate)); 952 953 NumIfConvBBs++; 954} 955 956/// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 957/// 958void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { 959 ToBBI.BB->splice(ToBBI.BB->end(), 960 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 961 962 // Redirect all branches to FromBB to ToBB. 963 std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(), 964 FromBBI.BB->pred_end()); 965 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 966 MachineBasicBlock *Pred = Preds[i]; 967 if (Pred == ToBBI.BB) 968 continue; 969 Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB); 970 } 971 972 std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), 973 FromBBI.BB->succ_end()); 974 MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); 975 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; 976 977 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 978 MachineBasicBlock *Succ = Succs[i]; 979 // Fallthrough edge can't be transferred. 980 if (Succ == FallThrough) 981 continue; 982 FromBBI.BB->removeSuccessor(Succ); 983 if (!ToBBI.BB->isSuccessor(Succ)) 984 ToBBI.BB->addSuccessor(Succ); 985 } 986 987 // Now FromBBI always fall through to the next block! 988 if (NBB) 989 FromBBI.BB->addSuccessor(NBB); 990 991 ToBBI.NonPredSize += FromBBI.NonPredSize; 992 FromBBI.NonPredSize = 0; 993 994 ToBBI.ClobbersPred |= FromBBI.ClobbersPred; 995 ToBBI.HasFallThrough = FromBBI.HasFallThrough; 996 997 std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), 998 std::back_inserter(ToBBI.Predicate)); 999 FromBBI.Predicate.clear(); 1000} 1001