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