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