IfConversion.cpp revision 212904
1//===-- IfConversion.cpp - Machine code if conversion pass. ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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 "BranchFolding.h" 16#include "llvm/Function.h" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/CodeGen/MachineModuleInfo.h" 19#include "llvm/CodeGen/MachineFunctionPass.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Target/TargetLowering.h" 22#include "llvm/Target/TargetMachine.h" 23#include "llvm/Target/TargetRegisterInfo.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/ErrorHandling.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/ADT/DepthFirstIterator.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/ADT/STLExtras.h" 31using namespace llvm; 32 33// Hidden options for help debugging. 34static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); 35static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); 36static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); 37static cl::opt<bool> DisableSimple("disable-ifcvt-simple", 38 cl::init(false), cl::Hidden); 39static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 40 cl::init(false), cl::Hidden); 41static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 42 cl::init(false), cl::Hidden); 43static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", 44 cl::init(false), cl::Hidden); 45static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 46 cl::init(false), cl::Hidden); 47static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 48 cl::init(false), cl::Hidden); 49static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 50 cl::init(false), cl::Hidden); 51static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold", 52 cl::init(true), cl::Hidden); 53 54STATISTIC(NumSimple, "Number of simple if-conversions performed"); 55STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed"); 56STATISTIC(NumTriangle, "Number of triangle if-conversions performed"); 57STATISTIC(NumTriangleRev, "Number of triangle (R) if-conversions performed"); 58STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed"); 59STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed"); 60STATISTIC(NumDiamonds, "Number of diamond if-conversions performed"); 61STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 62STATISTIC(NumDupBBs, "Number of duplicated blocks"); 63 64namespace { 65 class IfConverter : public MachineFunctionPass { 66 enum IfcvtKind { 67 ICNotClassfied, // BB data valid, but not classified. 68 ICSimpleFalse, // Same as ICSimple, but on the false path. 69 ICSimple, // BB is entry of an one split, no rejoin sub-CFG. 70 ICTriangleFRev, // Same as ICTriangleFalse, but false path rev condition. 71 ICTriangleRev, // Same as ICTriangle, but true path rev condition. 72 ICTriangleFalse, // Same as ICTriangle, but on the false path. 73 ICTriangle, // BB is entry of a triangle sub-CFG. 74 ICDiamond // BB is entry of a diamond sub-CFG. 75 }; 76 77 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 78 /// if-conversion feasibility analysis. This includes results from 79 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 80 /// classification, and common tail block of its successors (if it's a 81 /// diamond shape), its size, whether it's predicable, and whether any 82 /// instruction can clobber the 'would-be' predicate. 83 /// 84 /// IsDone - True if BB is not to be considered for ifcvt. 85 /// IsBeingAnalyzed - True if BB is currently being analyzed. 86 /// IsAnalyzed - True if BB has been analyzed (info is still valid). 87 /// IsEnqueued - True if BB has been enqueued to be ifcvt'ed. 88 /// IsBrAnalyzable - True if AnalyzeBranch() returns false. 89 /// HasFallThrough - True if BB may fallthrough to the following BB. 90 /// IsUnpredicable - True if BB is known to be unpredicable. 91 /// ClobbersPred - True if BB could modify predicates (e.g. has 92 /// cmp, call, etc.) 93 /// NonPredSize - Number of non-predicated instructions. 94 /// BB - Corresponding MachineBasicBlock. 95 /// TrueBB / FalseBB- See AnalyzeBranch(). 96 /// BrCond - Conditions for end of block conditional branches. 97 /// Predicate - Predicate used in the BB. 98 struct BBInfo { 99 bool IsDone : 1; 100 bool IsBeingAnalyzed : 1; 101 bool IsAnalyzed : 1; 102 bool IsEnqueued : 1; 103 bool IsBrAnalyzable : 1; 104 bool HasFallThrough : 1; 105 bool IsUnpredicable : 1; 106 bool CannotBeCopied : 1; 107 bool ClobbersPred : 1; 108 unsigned NonPredSize; 109 MachineBasicBlock *BB; 110 MachineBasicBlock *TrueBB; 111 MachineBasicBlock *FalseBB; 112 SmallVector<MachineOperand, 4> BrCond; 113 SmallVector<MachineOperand, 4> Predicate; 114 BBInfo() : IsDone(false), IsBeingAnalyzed(false), 115 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), 116 HasFallThrough(false), IsUnpredicable(false), 117 CannotBeCopied(false), ClobbersPred(false), NonPredSize(0), 118 BB(0), TrueBB(0), FalseBB(0) {} 119 }; 120 121 /// IfcvtToken - Record information about pending if-conversions to attempt: 122 /// BBI - Corresponding BBInfo. 123 /// Kind - Type of block. See IfcvtKind. 124 /// NeedSubsumption - True if the to-be-predicated BB has already been 125 /// predicated. 126 /// NumDups - Number of instructions that would be duplicated due 127 /// to this if-conversion. (For diamonds, the number of 128 /// identical instructions at the beginnings of both 129 /// paths). 130 /// NumDups2 - For diamonds, the number of identical instructions 131 /// at the ends of both paths. 132 struct IfcvtToken { 133 BBInfo &BBI; 134 IfcvtKind Kind; 135 bool NeedSubsumption; 136 unsigned NumDups; 137 unsigned NumDups2; 138 IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0) 139 : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {} 140 }; 141 142 /// Roots - Basic blocks that do not have successors. These are the starting 143 /// points of Graph traversal. 144 std::vector<MachineBasicBlock*> Roots; 145 146 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 147 /// basic block number. 148 std::vector<BBInfo> BBAnalysis; 149 150 const TargetLowering *TLI; 151 const TargetInstrInfo *TII; 152 const TargetRegisterInfo *TRI; 153 bool MadeChange; 154 int FnNum; 155 public: 156 static char ID; 157 IfConverter() : MachineFunctionPass(ID), FnNum(-1) {} 158 159 virtual bool runOnMachineFunction(MachineFunction &MF); 160 virtual const char *getPassName() const { return "If Converter"; } 161 162 private: 163 bool ReverseBranchCondition(BBInfo &BBI); 164 bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const; 165 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 166 bool FalseBranch, unsigned &Dups) const; 167 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, 168 unsigned &Dups1, unsigned &Dups2) const; 169 void ScanInstructions(BBInfo &BBI); 170 BBInfo &AnalyzeBlock(MachineBasicBlock *BB, 171 std::vector<IfcvtToken*> &Tokens); 172 bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond, 173 bool isTriangle = false, bool RevBranch = false); 174 void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens); 175 void InvalidatePreds(MachineBasicBlock *BB); 176 void RemoveExtraEdges(BBInfo &BBI); 177 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind); 178 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind); 179 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, 180 unsigned NumDups1, unsigned NumDups2); 181 void PredicateBlock(BBInfo &BBI, 182 MachineBasicBlock::iterator E, 183 SmallVectorImpl<MachineOperand> &Cond, 184 SmallSet<unsigned, 4> &Redefs); 185 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, 186 SmallVectorImpl<MachineOperand> &Cond, 187 SmallSet<unsigned, 4> &Redefs, 188 bool IgnoreBr = false); 189 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true); 190 191 bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, unsigned Size) const { 192 return Size > 0 && TII->isProfitableToIfCvt(BB, Size); 193 } 194 195 bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, unsigned TSize, 196 MachineBasicBlock &FBB, unsigned FSize) const { 197 return TSize > 0 && FSize > 0 && 198 TII->isProfitableToIfCvt(TBB, TSize, FBB, FSize); 199 } 200 201 // blockAlwaysFallThrough - Block ends without a terminator. 202 bool blockAlwaysFallThrough(BBInfo &BBI) const { 203 return BBI.IsBrAnalyzable && BBI.TrueBB == NULL; 204 } 205 206 // IfcvtTokenCmp - Used to sort if-conversion candidates. 207 static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) { 208 int Incr1 = (C1->Kind == ICDiamond) 209 ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups; 210 int Incr2 = (C2->Kind == ICDiamond) 211 ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups; 212 if (Incr1 > Incr2) 213 return true; 214 else if (Incr1 == Incr2) { 215 // Favors subsumption. 216 if (C1->NeedSubsumption == false && C2->NeedSubsumption == true) 217 return true; 218 else if (C1->NeedSubsumption == C2->NeedSubsumption) { 219 // Favors diamond over triangle, etc. 220 if ((unsigned)C1->Kind < (unsigned)C2->Kind) 221 return true; 222 else if (C1->Kind == C2->Kind) 223 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber(); 224 } 225 } 226 return false; 227 } 228 }; 229 230 char IfConverter::ID = 0; 231} 232 233INITIALIZE_PASS(IfConverter, "if-converter", "If Converter", false, false); 234 235FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 236 237bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 238 TLI = MF.getTarget().getTargetLowering(); 239 TII = MF.getTarget().getInstrInfo(); 240 TRI = MF.getTarget().getRegisterInfo(); 241 if (!TII) return false; 242 243 // Tail merge tend to expose more if-conversion opportunities. 244 BranchFolder BF(true); 245 bool BFChange = BF.OptimizeFunction(MF, TII, 246 MF.getTarget().getRegisterInfo(), 247 getAnalysisIfAvailable<MachineModuleInfo>()); 248 249 DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'" 250 << MF.getFunction()->getName() << "\'"); 251 252 if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { 253 DEBUG(dbgs() << " skipped\n"); 254 return false; 255 } 256 DEBUG(dbgs() << "\n"); 257 258 MF.RenumberBlocks(); 259 BBAnalysis.resize(MF.getNumBlockIDs()); 260 261 // Look for root nodes, i.e. blocks without successors. 262 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 263 if (I->succ_empty()) 264 Roots.push_back(I); 265 266 std::vector<IfcvtToken*> Tokens; 267 MadeChange = false; 268 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + 269 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds; 270 while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) { 271 // Do an initial analysis for each basic block and find all the potential 272 // candidates to perform if-conversion. 273 bool Change = false; 274 AnalyzeBlocks(MF, Tokens); 275 while (!Tokens.empty()) { 276 IfcvtToken *Token = Tokens.back(); 277 Tokens.pop_back(); 278 BBInfo &BBI = Token->BBI; 279 IfcvtKind Kind = Token->Kind; 280 unsigned NumDups = Token->NumDups; 281 unsigned NumDups2 = Token->NumDups2; 282 283 delete Token; 284 285 // If the block has been evicted out of the queue or it has already been 286 // marked dead (due to it being predicated), then skip it. 287 if (BBI.IsDone) 288 BBI.IsEnqueued = false; 289 if (!BBI.IsEnqueued) 290 continue; 291 292 BBI.IsEnqueued = false; 293 294 bool RetVal = false; 295 switch (Kind) { 296 default: assert(false && "Unexpected!"); 297 break; 298 case ICSimple: 299 case ICSimpleFalse: { 300 bool isFalse = Kind == ICSimpleFalse; 301 if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break; 302 DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? 303 " false" : "") 304 << "): BB#" << BBI.BB->getNumber() << " (" 305 << ((Kind == ICSimpleFalse) 306 ? BBI.FalseBB->getNumber() 307 : BBI.TrueBB->getNumber()) << ") "); 308 RetVal = IfConvertSimple(BBI, Kind); 309 DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); 310 if (RetVal) { 311 if (isFalse) ++NumSimpleFalse; 312 else ++NumSimple; 313 } 314 break; 315 } 316 case ICTriangle: 317 case ICTriangleRev: 318 case ICTriangleFalse: 319 case ICTriangleFRev: { 320 bool isFalse = Kind == ICTriangleFalse; 321 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev); 322 if (DisableTriangle && !isFalse && !isRev) break; 323 if (DisableTriangleR && !isFalse && isRev) break; 324 if (DisableTriangleF && isFalse && !isRev) break; 325 if (DisableTriangleFR && isFalse && isRev) break; 326 DEBUG(dbgs() << "Ifcvt (Triangle"); 327 if (isFalse) 328 DEBUG(dbgs() << " false"); 329 if (isRev) 330 DEBUG(dbgs() << " rev"); 331 DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:" 332 << BBI.TrueBB->getNumber() << ",F:" 333 << BBI.FalseBB->getNumber() << ") "); 334 RetVal = IfConvertTriangle(BBI, Kind); 335 DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); 336 if (RetVal) { 337 if (isFalse) { 338 if (isRev) ++NumTriangleFRev; 339 else ++NumTriangleFalse; 340 } else { 341 if (isRev) ++NumTriangleRev; 342 else ++NumTriangle; 343 } 344 } 345 break; 346 } 347 case ICDiamond: { 348 if (DisableDiamond) break; 349 DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" 350 << BBI.TrueBB->getNumber() << ",F:" 351 << BBI.FalseBB->getNumber() << ") "); 352 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2); 353 DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); 354 if (RetVal) ++NumDiamonds; 355 break; 356 } 357 } 358 359 Change |= RetVal; 360 361 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev + 362 NumTriangleFalse + NumTriangleFRev + NumDiamonds; 363 if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit) 364 break; 365 } 366 367 if (!Change) 368 break; 369 MadeChange |= Change; 370 } 371 372 // Delete tokens in case of early exit. 373 while (!Tokens.empty()) { 374 IfcvtToken *Token = Tokens.back(); 375 Tokens.pop_back(); 376 delete Token; 377 } 378 379 Tokens.clear(); 380 Roots.clear(); 381 BBAnalysis.clear(); 382 383 if (MadeChange && IfCvtBranchFold) { 384 BranchFolder BF(false); 385 BF.OptimizeFunction(MF, TII, 386 MF.getTarget().getRegisterInfo(), 387 getAnalysisIfAvailable<MachineModuleInfo>()); 388 } 389 390 MadeChange |= BFChange; 391 return MadeChange; 392} 393 394/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given 395/// its 'true' successor. 396static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 397 MachineBasicBlock *TrueBB) { 398 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 399 E = BB->succ_end(); SI != E; ++SI) { 400 MachineBasicBlock *SuccBB = *SI; 401 if (SuccBB != TrueBB) 402 return SuccBB; 403 } 404 return NULL; 405} 406 407/// ReverseBranchCondition - Reverse the condition of the end of the block 408/// branch. Swap block's 'true' and 'false' successors. 409bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { 410 DebugLoc dl; // FIXME: this is nowhere 411 if (!TII->ReverseBranchCondition(BBI.BrCond)) { 412 TII->RemoveBranch(*BBI.BB); 413 TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl); 414 std::swap(BBI.TrueBB, BBI.FalseBB); 415 return true; 416 } 417 return false; 418} 419 420/// getNextBlock - Returns the next block in the function blocks ordering. If 421/// it is the end, returns NULL. 422static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) { 423 MachineFunction::iterator I = BB; 424 MachineFunction::iterator E = BB->getParent()->end(); 425 if (++I == E) 426 return NULL; 427 return I; 428} 429 430/// ValidSimple - Returns true if the 'true' block (along with its 431/// predecessor) forms a valid simple shape for ifcvt. It also returns the 432/// number of instructions that the ifcvt would need to duplicate if performed 433/// in Dups. 434bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const { 435 Dups = 0; 436 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) 437 return false; 438 439 if (TrueBBI.IsBrAnalyzable) 440 return false; 441 442 if (TrueBBI.BB->pred_size() > 1) { 443 if (TrueBBI.CannotBeCopied || 444 !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize)) 445 return false; 446 Dups = TrueBBI.NonPredSize; 447 } 448 449 return true; 450} 451 452/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along 453/// with their common predecessor) forms a valid triangle shape for ifcvt. 454/// If 'FalseBranch' is true, it checks if 'true' block's false branch 455/// branches to the 'false' block rather than the other way around. It also 456/// returns the number of instructions that the ifcvt would need to duplicate 457/// if performed in 'Dups'. 458bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 459 bool FalseBranch, unsigned &Dups) const { 460 Dups = 0; 461 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) 462 return false; 463 464 if (TrueBBI.BB->pred_size() > 1) { 465 if (TrueBBI.CannotBeCopied) 466 return false; 467 468 unsigned Size = TrueBBI.NonPredSize; 469 if (TrueBBI.IsBrAnalyzable) { 470 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty()) 471 // Ends with an unconditional branch. It will be removed. 472 --Size; 473 else { 474 MachineBasicBlock *FExit = FalseBranch 475 ? TrueBBI.TrueBB : TrueBBI.FalseBB; 476 if (FExit) 477 // Require a conditional branch 478 ++Size; 479 } 480 } 481 if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size)) 482 return false; 483 Dups = Size; 484 } 485 486 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB; 487 if (!TExit && blockAlwaysFallThrough(TrueBBI)) { 488 MachineFunction::iterator I = TrueBBI.BB; 489 if (++I == TrueBBI.BB->getParent()->end()) 490 return false; 491 TExit = I; 492 } 493 return TExit && TExit == FalseBBI.BB; 494} 495 496static 497MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB, 498 const TargetInstrInfo *TII) { 499 MachineBasicBlock::iterator I = BB->end(); 500 while (I != BB->begin()) { 501 --I; 502 if (!I->getDesc().isBranch()) 503 break; 504 } 505 return I; 506} 507 508/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along 509/// with their common predecessor) forms a valid diamond shape for ifcvt. 510bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, 511 unsigned &Dups1, unsigned &Dups2) const { 512 Dups1 = Dups2 = 0; 513 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone || 514 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone) 515 return false; 516 517 MachineBasicBlock *TT = TrueBBI.TrueBB; 518 MachineBasicBlock *FT = FalseBBI.TrueBB; 519 520 if (!TT && blockAlwaysFallThrough(TrueBBI)) 521 TT = getNextBlock(TrueBBI.BB); 522 if (!FT && blockAlwaysFallThrough(FalseBBI)) 523 FT = getNextBlock(FalseBBI.BB); 524 if (TT != FT) 525 return false; 526 if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable)) 527 return false; 528 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) 529 return false; 530 531 // FIXME: Allow true block to have an early exit? 532 if (TrueBBI.FalseBB || FalseBBI.FalseBB || 533 (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) 534 return false; 535 536 MachineBasicBlock::iterator TI = TrueBBI.BB->begin(); 537 MachineBasicBlock::iterator FI = FalseBBI.BB->begin(); 538 MachineBasicBlock::iterator TIE = TrueBBI.BB->end(); 539 MachineBasicBlock::iterator FIE = FalseBBI.BB->end(); 540 // Skip dbg_value instructions 541 while (TI != TIE && TI->isDebugValue()) 542 ++TI; 543 while (FI != FIE && FI->isDebugValue()) 544 ++FI; 545 while (TI != TIE && FI != FIE) { 546 // Skip dbg_value instructions. These do not count. 547 if (TI->isDebugValue()) { 548 while (TI != TIE && TI->isDebugValue()) 549 ++TI; 550 if (TI == TIE) 551 break; 552 } 553 if (FI->isDebugValue()) { 554 while (FI != FIE && FI->isDebugValue()) 555 ++FI; 556 if (FI == FIE) 557 break; 558 } 559 if (!TI->isIdenticalTo(FI)) 560 break; 561 ++Dups1; 562 ++TI; 563 ++FI; 564 } 565 566 TI = firstNonBranchInst(TrueBBI.BB, TII); 567 FI = firstNonBranchInst(FalseBBI.BB, TII); 568 MachineBasicBlock::iterator TIB = TrueBBI.BB->begin(); 569 MachineBasicBlock::iterator FIB = FalseBBI.BB->begin(); 570 // Skip dbg_value instructions at end of the bb's. 571 while (TI != TIB && TI->isDebugValue()) 572 --TI; 573 while (FI != FIB && FI->isDebugValue()) 574 --FI; 575 while (TI != TIB && FI != FIB) { 576 // Skip dbg_value instructions. These do not count. 577 if (TI->isDebugValue()) { 578 while (TI != TIB && TI->isDebugValue()) 579 --TI; 580 if (TI == TIB) 581 break; 582 } 583 if (FI->isDebugValue()) { 584 while (FI != FIB && FI->isDebugValue()) 585 --FI; 586 if (FI == FIB) 587 break; 588 } 589 if (!TI->isIdenticalTo(FI)) 590 break; 591 ++Dups2; 592 --TI; 593 --FI; 594 } 595 596 return true; 597} 598 599/// ScanInstructions - Scan all the instructions in the block to determine if 600/// the block is predicable. In most cases, that means all the instructions 601/// in the block are isPredicable(). Also checks if the block contains any 602/// instruction which can clobber a predicate (e.g. condition code register). 603/// If so, the block is not predicable unless it's the last instruction. 604void IfConverter::ScanInstructions(BBInfo &BBI) { 605 if (BBI.IsDone) 606 return; 607 608 bool AlreadyPredicated = BBI.Predicate.size() > 0; 609 // First analyze the end of BB branches. 610 BBI.TrueBB = BBI.FalseBB = NULL; 611 BBI.BrCond.clear(); 612 BBI.IsBrAnalyzable = 613 !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 614 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL; 615 616 if (BBI.BrCond.size()) { 617 // No false branch. This BB must end with a conditional branch and a 618 // fallthrough. 619 if (!BBI.FalseBB) 620 BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB); 621 if (!BBI.FalseBB) { 622 // Malformed bcc? True and false blocks are the same? 623 BBI.IsUnpredicable = true; 624 return; 625 } 626 } 627 628 // Then scan all the instructions. 629 BBI.NonPredSize = 0; 630 BBI.ClobbersPred = false; 631 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 632 I != E; ++I) { 633 if (I->isDebugValue()) 634 continue; 635 636 const TargetInstrDesc &TID = I->getDesc(); 637 if (TID.isNotDuplicable()) 638 BBI.CannotBeCopied = true; 639 640 bool isPredicated = TII->isPredicated(I); 641 bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch(); 642 643 if (!isCondBr) { 644 if (!isPredicated) 645 BBI.NonPredSize++; 646 else if (!AlreadyPredicated) { 647 // FIXME: This instruction is already predicated before the 648 // if-conversion pass. It's probably something like a conditional move. 649 // Mark this block unpredicable for now. 650 BBI.IsUnpredicable = true; 651 return; 652 } 653 } 654 655 if (BBI.ClobbersPred && !isPredicated) { 656 // Predicate modification instruction should end the block (except for 657 // already predicated instructions and end of block branches). 658 if (isCondBr) { 659 // A conditional branch is not predicable, but it may be eliminated. 660 continue; 661 } 662 663 // Predicate may have been modified, the subsequent (currently) 664 // unpredicated instructions cannot be correctly predicated. 665 BBI.IsUnpredicable = true; 666 return; 667 } 668 669 // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are 670 // still potentially predicable. 671 std::vector<MachineOperand> PredDefs; 672 if (TII->DefinesPredicate(I, PredDefs)) 673 BBI.ClobbersPred = true; 674 675 if (!TII->isPredicable(I)) { 676 BBI.IsUnpredicable = true; 677 return; 678 } 679 } 680} 681 682/// FeasibilityAnalysis - Determine if the block is a suitable candidate to be 683/// predicated by the specified predicate. 684bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, 685 SmallVectorImpl<MachineOperand> &Pred, 686 bool isTriangle, bool RevBranch) { 687 // If the block is dead or unpredicable, then it cannot be predicated. 688 if (BBI.IsDone || BBI.IsUnpredicable) 689 return false; 690 691 // If it is already predicated, check if its predicate subsumes the new 692 // predicate. 693 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred)) 694 return false; 695 696 if (BBI.BrCond.size()) { 697 if (!isTriangle) 698 return false; 699 700 // Test predicate subsumption. 701 SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end()); 702 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 703 if (RevBranch) { 704 if (TII->ReverseBranchCondition(Cond)) 705 return false; 706 } 707 if (TII->ReverseBranchCondition(RevPred) || 708 !TII->SubsumesPredicate(Cond, RevPred)) 709 return false; 710 } 711 712 return true; 713} 714 715/// AnalyzeBlock - Analyze the structure of the sub-CFG starting from 716/// the specified block. Record its successors and whether it looks like an 717/// if-conversion candidate. 718IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, 719 std::vector<IfcvtToken*> &Tokens) { 720 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 721 722 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) 723 return BBI; 724 725 BBI.BB = BB; 726 BBI.IsBeingAnalyzed = true; 727 728 ScanInstructions(BBI); 729 730 // Unanalyzable or ends with fallthrough or unconditional branch. 731 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) { 732 BBI.IsBeingAnalyzed = false; 733 BBI.IsAnalyzed = true; 734 return BBI; 735 } 736 737 // Do not ifcvt if either path is a back edge to the entry block. 738 if (BBI.TrueBB == BB || BBI.FalseBB == BB) { 739 BBI.IsBeingAnalyzed = false; 740 BBI.IsAnalyzed = true; 741 return BBI; 742 } 743 744 // Do not ifcvt if true and false fallthrough blocks are the same. 745 if (!BBI.FalseBB) { 746 BBI.IsBeingAnalyzed = false; 747 BBI.IsAnalyzed = true; 748 return BBI; 749 } 750 751 BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens); 752 BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens); 753 754 if (TrueBBI.IsDone && FalseBBI.IsDone) { 755 BBI.IsBeingAnalyzed = false; 756 BBI.IsAnalyzed = true; 757 return BBI; 758 } 759 760 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); 761 bool CanRevCond = !TII->ReverseBranchCondition(RevCond); 762 763 unsigned Dups = 0; 764 unsigned Dups2 = 0; 765 bool TNeedSub = TrueBBI.Predicate.size() > 0; 766 bool FNeedSub = FalseBBI.Predicate.size() > 0; 767 bool Enqueued = false; 768 if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) && 769 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize - (Dups + Dups2), 770 *FalseBBI.BB, FalseBBI.NonPredSize - (Dups + Dups2)) && 771 FeasibilityAnalysis(TrueBBI, BBI.BrCond) && 772 FeasibilityAnalysis(FalseBBI, RevCond)) { 773 // Diamond: 774 // EBB 775 // / \_ 776 // | | 777 // TBB FBB 778 // \ / 779 // TailBB 780 // Note TailBB can be empty. 781 Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups, 782 Dups2)); 783 Enqueued = true; 784 } 785 786 if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) && 787 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) && 788 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { 789 // Triangle: 790 // EBB 791 // | \_ 792 // | | 793 // | TBB 794 // | / 795 // FBB 796 Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups)); 797 Enqueued = true; 798 } 799 800 if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) && 801 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) && 802 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) { 803 Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups)); 804 Enqueued = true; 805 } 806 807 if (ValidSimple(TrueBBI, Dups) && 808 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) && 809 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { 810 // Simple (split, no rejoin): 811 // EBB 812 // | \_ 813 // | | 814 // | TBB---> exit 815 // | 816 // FBB 817 Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups)); 818 Enqueued = true; 819 } 820 821 if (CanRevCond) { 822 // Try the other path... 823 if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) && 824 MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) && 825 FeasibilityAnalysis(FalseBBI, RevCond, true)) { 826 Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups)); 827 Enqueued = true; 828 } 829 830 if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) && 831 MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) && 832 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { 833 Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups)); 834 Enqueued = true; 835 } 836 837 if (ValidSimple(FalseBBI, Dups) && 838 MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) && 839 FeasibilityAnalysis(FalseBBI, RevCond)) { 840 Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups)); 841 Enqueued = true; 842 } 843 } 844 845 BBI.IsEnqueued = Enqueued; 846 BBI.IsBeingAnalyzed = false; 847 BBI.IsAnalyzed = true; 848 return BBI; 849} 850 851/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 852/// candidates. 853void IfConverter::AnalyzeBlocks(MachineFunction &MF, 854 std::vector<IfcvtToken*> &Tokens) { 855 std::set<MachineBasicBlock*> Visited; 856 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 857 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 858 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 859 MachineBasicBlock *BB = *I; 860 AnalyzeBlock(BB, Tokens); 861 } 862 } 863 864 // Sort to favor more complex ifcvt scheme. 865 std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp); 866} 867 868/// canFallThroughTo - Returns true either if ToBB is the next block after BB or 869/// that all the intervening blocks are empty (given BB can fall through to its 870/// next block). 871static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 872 MachineFunction::iterator PI = BB; 873 MachineFunction::iterator I = llvm::next(PI); 874 MachineFunction::iterator TI = ToBB; 875 MachineFunction::iterator E = BB->getParent()->end(); 876 while (I != TI) { 877 // Check isSuccessor to avoid case where the next block is empty, but 878 // it's not a successor. 879 if (I == E || !I->empty() || !PI->isSuccessor(I)) 880 return false; 881 PI = I++; 882 } 883 return true; 884} 885 886/// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed 887/// to determine if it can be if-converted. If predecessor is already enqueued, 888/// dequeue it! 889void IfConverter::InvalidatePreds(MachineBasicBlock *BB) { 890 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 891 E = BB->pred_end(); PI != E; ++PI) { 892 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 893 if (PBBI.IsDone || PBBI.BB == BB) 894 continue; 895 PBBI.IsAnalyzed = false; 896 PBBI.IsEnqueued = false; 897 } 898} 899 900/// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 901/// 902static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 903 const TargetInstrInfo *TII) { 904 DebugLoc dl; // FIXME: this is nowhere 905 SmallVector<MachineOperand, 0> NoCond; 906 TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl); 907} 908 909/// RemoveExtraEdges - Remove true / false edges if either / both are no longer 910/// successors. 911void IfConverter::RemoveExtraEdges(BBInfo &BBI) { 912 MachineBasicBlock *TBB = NULL, *FBB = NULL; 913 SmallVector<MachineOperand, 4> Cond; 914 if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond)) 915 BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 916} 917 918/// InitPredRedefs / UpdatePredRedefs - Defs by predicated instructions are 919/// modeled as read + write (sort like two-address instructions). These 920/// routines track register liveness and add implicit uses to if-converted 921/// instructions to conform to the model. 922static void InitPredRedefs(MachineBasicBlock *BB, SmallSet<unsigned,4> &Redefs, 923 const TargetRegisterInfo *TRI) { 924 for (MachineBasicBlock::livein_iterator I = BB->livein_begin(), 925 E = BB->livein_end(); I != E; ++I) { 926 unsigned Reg = *I; 927 Redefs.insert(Reg); 928 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 929 *Subreg; ++Subreg) 930 Redefs.insert(*Subreg); 931 } 932} 933 934static void UpdatePredRedefs(MachineInstr *MI, SmallSet<unsigned,4> &Redefs, 935 const TargetRegisterInfo *TRI, 936 bool AddImpUse = false) { 937 SmallVector<unsigned, 4> Defs; 938 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 939 const MachineOperand &MO = MI->getOperand(i); 940 if (!MO.isReg()) 941 continue; 942 unsigned Reg = MO.getReg(); 943 if (!Reg) 944 continue; 945 if (MO.isDef()) 946 Defs.push_back(Reg); 947 else if (MO.isKill()) { 948 Redefs.erase(Reg); 949 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 950 Redefs.erase(*SR); 951 } 952 } 953 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 954 unsigned Reg = Defs[i]; 955 if (Redefs.count(Reg)) { 956 if (AddImpUse) 957 // Treat predicated update as read + write. 958 MI->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, 959 true/*IsImp*/,false/*IsKill*/)); 960 } else { 961 Redefs.insert(Reg); 962 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 963 Redefs.insert(*SR); 964 } 965 } 966} 967 968static void UpdatePredRedefs(MachineBasicBlock::iterator I, 969 MachineBasicBlock::iterator E, 970 SmallSet<unsigned,4> &Redefs, 971 const TargetRegisterInfo *TRI) { 972 while (I != E) { 973 UpdatePredRedefs(I, Redefs, TRI); 974 ++I; 975 } 976} 977 978/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. 979/// 980bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { 981 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 982 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 983 BBInfo *CvtBBI = &TrueBBI; 984 BBInfo *NextBBI = &FalseBBI; 985 986 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 987 if (Kind == ICSimpleFalse) 988 std::swap(CvtBBI, NextBBI); 989 990 if (CvtBBI->IsDone || 991 (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { 992 // Something has changed. It's no longer safe to predicate this block. 993 BBI.IsAnalyzed = false; 994 CvtBBI->IsAnalyzed = false; 995 return false; 996 } 997 998 if (Kind == ICSimpleFalse) 999 if (TII->ReverseBranchCondition(Cond)) 1000 assert(false && "Unable to reverse branch condition!"); 1001 1002 // Initialize liveins to the first BB. These are potentiall redefined by 1003 // predicated instructions. 1004 SmallSet<unsigned, 4> Redefs; 1005 InitPredRedefs(CvtBBI->BB, Redefs, TRI); 1006 InitPredRedefs(NextBBI->BB, Redefs, TRI); 1007 1008 if (CvtBBI->BB->pred_size() > 1) { 1009 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 1010 // Copy instructions in the true block, predicate them, and add them to 1011 // the entry block. 1012 CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs); 1013 } else { 1014 PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs); 1015 1016 // Merge converted block into entry block. 1017 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 1018 MergeBlocks(BBI, *CvtBBI); 1019 } 1020 1021 bool IterIfcvt = true; 1022 if (!canFallThroughTo(BBI.BB, NextBBI->BB)) { 1023 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 1024 BBI.HasFallThrough = false; 1025 // Now ifcvt'd block will look like this: 1026 // BB: 1027 // ... 1028 // t, f = cmp 1029 // if t op 1030 // b BBf 1031 // 1032 // We cannot further ifcvt this block because the unconditional branch 1033 // will have to be predicated on the new condition, that will not be 1034 // available if cmp executes. 1035 IterIfcvt = false; 1036 } 1037 1038 RemoveExtraEdges(BBI); 1039 1040 // Update block info. BB can be iteratively if-converted. 1041 if (!IterIfcvt) 1042 BBI.IsDone = true; 1043 InvalidatePreds(BBI.BB); 1044 CvtBBI->IsDone = true; 1045 1046 // FIXME: Must maintain LiveIns. 1047 return true; 1048} 1049 1050/// IfConvertTriangle - If convert a triangle sub-CFG. 1051/// 1052bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { 1053 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 1054 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 1055 BBInfo *CvtBBI = &TrueBBI; 1056 BBInfo *NextBBI = &FalseBBI; 1057 DebugLoc dl; // FIXME: this is nowhere 1058 1059 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 1060 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) 1061 std::swap(CvtBBI, NextBBI); 1062 1063 if (CvtBBI->IsDone || 1064 (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { 1065 // Something has changed. It's no longer safe to predicate this block. 1066 BBI.IsAnalyzed = false; 1067 CvtBBI->IsAnalyzed = false; 1068 return false; 1069 } 1070 1071 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) 1072 if (TII->ReverseBranchCondition(Cond)) 1073 assert(false && "Unable to reverse branch condition!"); 1074 1075 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) { 1076 if (ReverseBranchCondition(*CvtBBI)) { 1077 // BB has been changed, modify its predecessors (except for this 1078 // one) so they don't get ifcvt'ed based on bad intel. 1079 for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(), 1080 E = CvtBBI->BB->pred_end(); PI != E; ++PI) { 1081 MachineBasicBlock *PBB = *PI; 1082 if (PBB == BBI.BB) 1083 continue; 1084 BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; 1085 if (PBBI.IsEnqueued) { 1086 PBBI.IsAnalyzed = false; 1087 PBBI.IsEnqueued = false; 1088 } 1089 } 1090 } 1091 } 1092 1093 // Initialize liveins to the first BB. These are potentially redefined by 1094 // predicated instructions. 1095 SmallSet<unsigned, 4> Redefs; 1096 InitPredRedefs(CvtBBI->BB, Redefs, TRI); 1097 InitPredRedefs(NextBBI->BB, Redefs, TRI); 1098 1099 bool HasEarlyExit = CvtBBI->FalseBB != NULL; 1100 if (CvtBBI->BB->pred_size() > 1) { 1101 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 1102 // Copy instructions in the true block, predicate them, and add them to 1103 // the entry block. 1104 CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true); 1105 } else { 1106 // Predicate the 'true' block after removing its branch. 1107 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 1108 PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs); 1109 1110 // Now merge the entry of the triangle with the true block. 1111 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 1112 MergeBlocks(BBI, *CvtBBI, false); 1113 } 1114 1115 // If 'true' block has a 'false' successor, add an exit branch to it. 1116 if (HasEarlyExit) { 1117 SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(), 1118 CvtBBI->BrCond.end()); 1119 if (TII->ReverseBranchCondition(RevCond)) 1120 assert(false && "Unable to reverse branch condition!"); 1121 TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl); 1122 BBI.BB->addSuccessor(CvtBBI->FalseBB); 1123 } 1124 1125 // Merge in the 'false' block if the 'false' block has no other 1126 // predecessors. Otherwise, add an unconditional branch to 'false'. 1127 bool FalseBBDead = false; 1128 bool IterIfcvt = true; 1129 bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB); 1130 if (!isFallThrough) { 1131 // Only merge them if the true block does not fallthrough to the false 1132 // block. By not merging them, we make it possible to iteratively 1133 // ifcvt the blocks. 1134 if (!HasEarlyExit && 1135 NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) { 1136 MergeBlocks(BBI, *NextBBI); 1137 FalseBBDead = true; 1138 } else { 1139 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 1140 BBI.HasFallThrough = false; 1141 } 1142 // Mixed predicated and unpredicated code. This cannot be iteratively 1143 // predicated. 1144 IterIfcvt = false; 1145 } 1146 1147 RemoveExtraEdges(BBI); 1148 1149 // Update block info. BB can be iteratively if-converted. 1150 if (!IterIfcvt) 1151 BBI.IsDone = true; 1152 InvalidatePreds(BBI.BB); 1153 CvtBBI->IsDone = true; 1154 if (FalseBBDead) 1155 NextBBI->IsDone = true; 1156 1157 // FIXME: Must maintain LiveIns. 1158 return true; 1159} 1160 1161/// IfConvertDiamond - If convert a diamond sub-CFG. 1162/// 1163bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, 1164 unsigned NumDups1, unsigned NumDups2) { 1165 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 1166 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 1167 MachineBasicBlock *TailBB = TrueBBI.TrueBB; 1168 // True block must fall through or end with an unanalyzable terminator. 1169 if (!TailBB) { 1170 if (blockAlwaysFallThrough(TrueBBI)) 1171 TailBB = FalseBBI.TrueBB; 1172 assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!"); 1173 } 1174 1175 if (TrueBBI.IsDone || FalseBBI.IsDone || 1176 TrueBBI.BB->pred_size() > 1 || 1177 FalseBBI.BB->pred_size() > 1) { 1178 // Something has changed. It's no longer safe to predicate these blocks. 1179 BBI.IsAnalyzed = false; 1180 TrueBBI.IsAnalyzed = false; 1181 FalseBBI.IsAnalyzed = false; 1182 return false; 1183 } 1184 1185 // Put the predicated instructions from the 'true' block before the 1186 // instructions from the 'false' block, unless the true block would clobber 1187 // the predicate, in which case, do the opposite. 1188 BBInfo *BBI1 = &TrueBBI; 1189 BBInfo *BBI2 = &FalseBBI; 1190 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); 1191 if (TII->ReverseBranchCondition(RevCond)) 1192 assert(false && "Unable to reverse branch condition!"); 1193 SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond; 1194 SmallVector<MachineOperand, 4> *Cond2 = &RevCond; 1195 1196 // Figure out the more profitable ordering. 1197 bool DoSwap = false; 1198 if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred) 1199 DoSwap = true; 1200 else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) { 1201 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize) 1202 DoSwap = true; 1203 } 1204 if (DoSwap) { 1205 std::swap(BBI1, BBI2); 1206 std::swap(Cond1, Cond2); 1207 } 1208 1209 // Remove the conditional branch from entry to the blocks. 1210 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 1211 1212 // Initialize liveins to the first BB. These are potentially redefined by 1213 // predicated instructions. 1214 SmallSet<unsigned, 4> Redefs; 1215 InitPredRedefs(BBI1->BB, Redefs, TRI); 1216 1217 // Remove the duplicated instructions at the beginnings of both paths. 1218 MachineBasicBlock::iterator DI1 = BBI1->BB->begin(); 1219 MachineBasicBlock::iterator DI2 = BBI2->BB->begin(); 1220 MachineBasicBlock::iterator DIE1 = BBI1->BB->end(); 1221 MachineBasicBlock::iterator DIE2 = BBI2->BB->end(); 1222 // Skip dbg_value instructions 1223 while (DI1 != DIE1 && DI1->isDebugValue()) 1224 ++DI1; 1225 while (DI2 != DIE2 && DI2->isDebugValue()) 1226 ++DI2; 1227 BBI1->NonPredSize -= NumDups1; 1228 BBI2->NonPredSize -= NumDups1; 1229 1230 // Skip past the dups on each side separately since there may be 1231 // differing dbg_value entries. 1232 for (unsigned i = 0; i < NumDups1; ++DI1) { 1233 if (!DI1->isDebugValue()) 1234 ++i; 1235 } 1236 while (NumDups1 != 0) { 1237 ++DI2; 1238 if (!DI2->isDebugValue()) 1239 --NumDups1; 1240 } 1241 1242 UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI); 1243 BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1); 1244 BBI2->BB->erase(BBI2->BB->begin(), DI2); 1245 1246 // Predicate the 'true' block after removing its branch. 1247 BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB); 1248 DI1 = BBI1->BB->end(); 1249 for (unsigned i = 0; i != NumDups2; ) { 1250 // NumDups2 only counted non-dbg_value instructions, so this won't 1251 // run off the head of the list. 1252 assert (DI1 != BBI1->BB->begin()); 1253 --DI1; 1254 // skip dbg_value instructions 1255 if (!DI1->isDebugValue()) 1256 ++i; 1257 } 1258 BBI1->BB->erase(DI1, BBI1->BB->end()); 1259 PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs); 1260 1261 // Predicate the 'false' block. 1262 BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB); 1263 DI2 = BBI2->BB->end(); 1264 while (NumDups2 != 0) { 1265 // NumDups2 only counted non-dbg_value instructions, so this won't 1266 // run off the head of the list. 1267 assert (DI2 != BBI2->BB->begin()); 1268 --DI2; 1269 // skip dbg_value instructions 1270 if (!DI2->isDebugValue()) 1271 --NumDups2; 1272 } 1273 PredicateBlock(*BBI2, DI2, *Cond2, Redefs); 1274 1275 // Merge the true block into the entry of the diamond. 1276 MergeBlocks(BBI, *BBI1, TailBB == 0); 1277 MergeBlocks(BBI, *BBI2, TailBB == 0); 1278 1279 // If the if-converted block falls through or unconditionally branches into 1280 // the tail block, and the tail block does not have other predecessors, then 1281 // fold the tail block in as well. Otherwise, unless it falls through to the 1282 // tail, add a unconditional branch to it. 1283 if (TailBB) { 1284 BBInfo TailBBI = BBAnalysis[TailBB->getNumber()]; 1285 bool CanMergeTail = !TailBBI.HasFallThrough; 1286 // There may still be a fall-through edge from BBI1 or BBI2 to TailBB; 1287 // check if there are any other predecessors besides those. 1288 unsigned NumPreds = TailBB->pred_size(); 1289 if (NumPreds > 1) 1290 CanMergeTail = false; 1291 else if (NumPreds == 1 && CanMergeTail) { 1292 MachineBasicBlock::pred_iterator PI = TailBB->pred_begin(); 1293 if (*PI != BBI1->BB && *PI != BBI2->BB) 1294 CanMergeTail = false; 1295 } 1296 if (CanMergeTail) { 1297 MergeBlocks(BBI, TailBBI); 1298 TailBBI.IsDone = true; 1299 } else { 1300 BBI.BB->addSuccessor(TailBB); 1301 InsertUncondBranch(BBI.BB, TailBB, TII); 1302 BBI.HasFallThrough = false; 1303 } 1304 } 1305 1306 // RemoveExtraEdges won't work if the block has an unanalyzable branch, 1307 // which can happen here if TailBB is unanalyzable and is merged, so 1308 // explicitly remove BBI1 and BBI2 as successors. 1309 BBI.BB->removeSuccessor(BBI1->BB); 1310 BBI.BB->removeSuccessor(BBI2->BB); 1311 RemoveExtraEdges(BBI); 1312 1313 // Update block info. 1314 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true; 1315 InvalidatePreds(BBI.BB); 1316 1317 // FIXME: Must maintain LiveIns. 1318 return true; 1319} 1320 1321/// PredicateBlock - Predicate instructions from the start of the block to the 1322/// specified end with the specified condition. 1323void IfConverter::PredicateBlock(BBInfo &BBI, 1324 MachineBasicBlock::iterator E, 1325 SmallVectorImpl<MachineOperand> &Cond, 1326 SmallSet<unsigned, 4> &Redefs) { 1327 for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) { 1328 if (I->isDebugValue() || TII->isPredicated(I)) 1329 continue; 1330 if (!TII->PredicateInstruction(I, Cond)) { 1331#ifndef NDEBUG 1332 dbgs() << "Unable to predicate " << *I << "!\n"; 1333#endif 1334 llvm_unreachable(0); 1335 } 1336 1337 // If the predicated instruction now redefines a register as the result of 1338 // if-conversion, add an implicit kill. 1339 UpdatePredRedefs(I, Redefs, TRI, true); 1340 } 1341 1342 std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate)); 1343 1344 BBI.IsAnalyzed = false; 1345 BBI.NonPredSize = 0; 1346 1347 ++NumIfConvBBs; 1348} 1349 1350/// CopyAndPredicateBlock - Copy and predicate instructions from source BB to 1351/// the destination block. Skip end of block branches if IgnoreBr is true. 1352void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, 1353 SmallVectorImpl<MachineOperand> &Cond, 1354 SmallSet<unsigned, 4> &Redefs, 1355 bool IgnoreBr) { 1356 MachineFunction &MF = *ToBBI.BB->getParent(); 1357 1358 for (MachineBasicBlock::iterator I = FromBBI.BB->begin(), 1359 E = FromBBI.BB->end(); I != E; ++I) { 1360 const TargetInstrDesc &TID = I->getDesc(); 1361 // Do not copy the end of the block branches. 1362 if (IgnoreBr && TID.isBranch()) 1363 break; 1364 1365 MachineInstr *MI = MF.CloneMachineInstr(I); 1366 ToBBI.BB->insert(ToBBI.BB->end(), MI); 1367 ToBBI.NonPredSize++; 1368 1369 if (!TII->isPredicated(I) && !MI->isDebugValue()) { 1370 if (!TII->PredicateInstruction(MI, Cond)) { 1371#ifndef NDEBUG 1372 dbgs() << "Unable to predicate " << *I << "!\n"; 1373#endif 1374 llvm_unreachable(0); 1375 } 1376 } 1377 1378 // If the predicated instruction now redefines a register as the result of 1379 // if-conversion, add an implicit kill. 1380 UpdatePredRedefs(MI, Redefs, TRI, true); 1381 } 1382 1383 if (!IgnoreBr) { 1384 std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), 1385 FromBBI.BB->succ_end()); 1386 MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); 1387 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; 1388 1389 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 1390 MachineBasicBlock *Succ = Succs[i]; 1391 // Fallthrough edge can't be transferred. 1392 if (Succ == FallThrough) 1393 continue; 1394 ToBBI.BB->addSuccessor(Succ); 1395 } 1396 } 1397 1398 std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), 1399 std::back_inserter(ToBBI.Predicate)); 1400 std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate)); 1401 1402 ToBBI.ClobbersPred |= FromBBI.ClobbersPred; 1403 ToBBI.IsAnalyzed = false; 1404 1405 ++NumDupBBs; 1406} 1407 1408/// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 1409/// This will leave FromBB as an empty block, so remove all of its 1410/// successor edges except for the fall-through edge. If AddEdges is true, 1411/// i.e., when FromBBI's branch is being moved, add those successor edges to 1412/// ToBBI. 1413void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { 1414 ToBBI.BB->splice(ToBBI.BB->end(), 1415 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 1416 1417 std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), 1418 FromBBI.BB->succ_end()); 1419 MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); 1420 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; 1421 1422 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 1423 MachineBasicBlock *Succ = Succs[i]; 1424 // Fallthrough edge can't be transferred. 1425 if (Succ == FallThrough) 1426 continue; 1427 FromBBI.BB->removeSuccessor(Succ); 1428 if (AddEdges) 1429 ToBBI.BB->addSuccessor(Succ); 1430 } 1431 1432 // Now FromBBI always falls through to the next block! 1433 if (NBB && !FromBBI.BB->isSuccessor(NBB)) 1434 FromBBI.BB->addSuccessor(NBB); 1435 1436 std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), 1437 std::back_inserter(ToBBI.Predicate)); 1438 FromBBI.Predicate.clear(); 1439 1440 ToBBI.NonPredSize += FromBBI.NonPredSize; 1441 FromBBI.NonPredSize = 0; 1442 1443 ToBBI.ClobbersPred |= FromBBI.ClobbersPred; 1444 ToBBI.HasFallThrough = FromBBI.HasFallThrough; 1445 ToBBI.IsAnalyzed = false; 1446 FromBBI.IsAnalyzed = false; 1447} 1448