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