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