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