LLVM API Documentation
00001 //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the machine instruction level if-conversion pass. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "ifcvt" 00015 #include "llvm/Function.h" 00016 #include "llvm/CodeGen/Passes.h" 00017 #include "llvm/CodeGen/MachineModuleInfo.h" 00018 #include "llvm/CodeGen/MachineFunctionPass.h" 00019 #include "llvm/Target/TargetInstrInfo.h" 00020 #include "llvm/Target/TargetLowering.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "llvm/Support/CommandLine.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "llvm/Support/ErrorHandling.h" 00025 #include "llvm/Support/raw_ostream.h" 00026 #include "llvm/ADT/DepthFirstIterator.h" 00027 #include "llvm/ADT/Statistic.h" 00028 #include "llvm/ADT/STLExtras.h" 00029 using namespace llvm; 00030 00031 // Hidden options for help debugging. 00032 static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); 00033 static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); 00034 static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); 00035 static cl::opt<bool> DisableSimple("disable-ifcvt-simple", 00036 cl::init(false), cl::Hidden); 00037 static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 00038 cl::init(false), cl::Hidden); 00039 static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 00040 cl::init(false), cl::Hidden); 00041 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", 00042 cl::init(false), cl::Hidden); 00043 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 00044 cl::init(false), cl::Hidden); 00045 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 00046 cl::init(false), cl::Hidden); 00047 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 00048 cl::init(false), cl::Hidden); 00049 00050 STATISTIC(NumSimple, "Number of simple if-conversions performed"); 00051 STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed"); 00052 STATISTIC(NumTriangle, "Number of triangle if-conversions performed"); 00053 STATISTIC(NumTriangleRev, "Number of triangle (R) if-conversions performed"); 00054 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed"); 00055 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed"); 00056 STATISTIC(NumDiamonds, "Number of diamond if-conversions performed"); 00057 STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 00058 STATISTIC(NumDupBBs, "Number of duplicated blocks"); 00059 00060 namespace { 00061 class VISIBILITY_HIDDEN IfConverter : public MachineFunctionPass { 00062 enum IfcvtKind { 00063 ICNotClassfied, // BB data valid, but not classified. 00064 ICSimpleFalse, // Same as ICSimple, but on the false path. 00065 ICSimple, // BB is entry of an one split, no rejoin sub-CFG. 00066 ICTriangleFRev, // Same as ICTriangleFalse, but false path rev condition. 00067 ICTriangleRev, // Same as ICTriangle, but true path rev condition. 00068 ICTriangleFalse, // Same as ICTriangle, but on the false path. 00069 ICTriangle, // BB is entry of a triangle sub-CFG. 00070 ICDiamond // BB is entry of a diamond sub-CFG. 00071 }; 00072 00073 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 00074 /// if-conversion feasibility analysis. This includes results from 00075 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 00076 /// classification, and common tail block of its successors (if it's a 00077 /// diamond shape), its size, whether it's predicable, and whether any 00078 /// instruction can clobber the 'would-be' predicate. 00079 /// 00080 /// IsDone - True if BB is not to be considered for ifcvt. 00081 /// IsBeingAnalyzed - True if BB is currently being analyzed. 00082 /// IsAnalyzed - True if BB has been analyzed (info is still valid). 00083 /// IsEnqueued - True if BB has been enqueued to be ifcvt'ed. 00084 /// IsBrAnalyzable - True if AnalyzeBranch() returns false. 00085 /// HasFallThrough - True if BB may fallthrough to the following BB. 00086 /// IsUnpredicable - True if BB is known to be unpredicable. 00087 /// ClobbersPred - True if BB could modify predicates (e.g. has 00088 /// cmp, call, etc.) 00089 /// NonPredSize - Number of non-predicated instructions. 00090 /// BB - Corresponding MachineBasicBlock. 00091 /// TrueBB / FalseBB- See AnalyzeBranch(). 00092 /// BrCond - Conditions for end of block conditional branches. 00093 /// Predicate - Predicate used in the BB. 00094 struct BBInfo { 00095 bool IsDone : 1; 00096 bool IsBeingAnalyzed : 1; 00097 bool IsAnalyzed : 1; 00098 bool IsEnqueued : 1; 00099 bool IsBrAnalyzable : 1; 00100 bool HasFallThrough : 1; 00101 bool IsUnpredicable : 1; 00102 bool CannotBeCopied : 1; 00103 bool ClobbersPred : 1; 00104 unsigned NonPredSize; 00105 MachineBasicBlock *BB; 00106 MachineBasicBlock *TrueBB; 00107 MachineBasicBlock *FalseBB; 00108 SmallVector<MachineOperand, 4> BrCond; 00109 SmallVector<MachineOperand, 4> Predicate; 00110 BBInfo() : IsDone(false), IsBeingAnalyzed(false), 00111 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), 00112 HasFallThrough(false), IsUnpredicable(false), 00113 CannotBeCopied(false), ClobbersPred(false), NonPredSize(0), 00114 BB(0), TrueBB(0), FalseBB(0) {} 00115 }; 00116 00117 /// IfcvtToken - Record information about pending if-conversions to attemp: 00118 /// BBI - Corresponding BBInfo. 00119 /// Kind - Type of block. See IfcvtKind. 00120 /// NeedSubsumption - True if the to-be-predicated BB has already been 00121 /// predicated. 00122 /// NumDups - Number of instructions that would be duplicated due 00123 /// to this if-conversion. (For diamonds, the number of 00124 /// identical instructions at the beginnings of both 00125 /// paths). 00126 /// NumDups2 - For diamonds, the number of identical instructions 00127 /// at the ends of both paths. 00128 struct IfcvtToken { 00129 BBInfo &BBI; 00130 IfcvtKind Kind; 00131 bool NeedSubsumption; 00132 unsigned NumDups; 00133 unsigned NumDups2; 00134 IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0) 00135 : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {} 00136 }; 00137 00138 /// Roots - Basic blocks that do not have successors. These are the starting 00139 /// points of Graph traversal. 00140 std::vector<MachineBasicBlock*> Roots; 00141 00142 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 00143 /// basic block number. 00144 std::vector<BBInfo> BBAnalysis; 00145 00146 const TargetLowering *TLI; 00147 const TargetInstrInfo *TII; 00148 bool MadeChange; 00149 int FnNum; 00150 public: 00151 static char ID; 00152 IfConverter() : MachineFunctionPass(&ID), FnNum(-1) {} 00153 00154 virtual bool runOnMachineFunction(MachineFunction &MF); 00155 virtual const char *getPassName() const { return "If Converter"; } 00156 00157 private: 00158 bool ReverseBranchCondition(BBInfo &BBI); 00159 bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const; 00160 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 00161 bool FalseBranch, unsigned &Dups) const; 00162 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, 00163 unsigned &Dups1, unsigned &Dups2) const; 00164 void ScanInstructions(BBInfo &BBI); 00165 BBInfo &AnalyzeBlock(MachineBasicBlock *BB, 00166 std::vector<IfcvtToken*> &Tokens); 00167 bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond, 00168 bool isTriangle = false, bool RevBranch = false); 00169 bool AnalyzeBlocks(MachineFunction &MF, 00170 std::vector<IfcvtToken*> &Tokens); 00171 void InvalidatePreds(MachineBasicBlock *BB); 00172 void RemoveExtraEdges(BBInfo &BBI); 00173 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind); 00174 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind); 00175 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, 00176 unsigned NumDups1, unsigned NumDups2); 00177 void PredicateBlock(BBInfo &BBI, 00178 MachineBasicBlock::iterator E, 00179 SmallVectorImpl<MachineOperand> &Cond); 00180 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, 00181 SmallVectorImpl<MachineOperand> &Cond, 00182 bool IgnoreBr = false); 00183 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI); 00184 00185 bool MeetIfcvtSizeLimit(unsigned Size) const { 00186 return Size > 0 && Size <= TLI->getIfCvtBlockSizeLimit(); 00187 } 00188 00189 // blockAlwaysFallThrough - Block ends without a terminator. 00190 bool blockAlwaysFallThrough(BBInfo &BBI) const { 00191 return BBI.IsBrAnalyzable && BBI.TrueBB == NULL; 00192 } 00193 00194 // IfcvtTokenCmp - Used to sort if-conversion candidates. 00195 static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) { 00196 int Incr1 = (C1->Kind == ICDiamond) 00197 ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups; 00198 int Incr2 = (C2->Kind == ICDiamond) 00199 ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups; 00200 if (Incr1 > Incr2) 00201 return true; 00202 else if (Incr1 == Incr2) { 00203 // Favors subsumption. 00204 if (C1->NeedSubsumption == false && C2->NeedSubsumption == true) 00205 return true; 00206 else if (C1->NeedSubsumption == C2->NeedSubsumption) { 00207 // Favors diamond over triangle, etc. 00208 if ((unsigned)C1->Kind < (unsigned)C2->Kind) 00209 return true; 00210 else if (C1->Kind == C2->Kind) 00211 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber(); 00212 } 00213 } 00214 return false; 00215 } 00216 }; 00217 00218 char IfConverter::ID = 0; 00219 } 00220 00221 static RegisterPass<IfConverter> 00222 X("if-converter", "If Converter"); 00223 00224 FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 00225 00226 bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 00227 TLI = MF.getTarget().getTargetLowering(); 00228 TII = MF.getTarget().getInstrInfo(); 00229 if (!TII) return false; 00230 00231 DEBUG(errs() << "\nIfcvt: function (" << ++FnNum << ") \'" 00232 << MF.getFunction()->getName() << "\'"); 00233 00234 if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { 00235 DOUT << " skipped\n"; 00236 return false; 00237 } 00238 DOUT << "\n"; 00239 00240 MF.RenumberBlocks(); 00241 BBAnalysis.resize(MF.getNumBlockIDs()); 00242 00243 // Look for root nodes, i.e. blocks without successors. 00244 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 00245 if (I->succ_empty()) 00246 Roots.push_back(I); 00247 00248 std::vector<IfcvtToken*> Tokens; 00249 MadeChange = false; 00250 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + 00251 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds; 00252 while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) { 00253 // Do an initial analysis for each basic block and find all the potential 00254 // candidates to perform if-conversion. 00255 bool Change = AnalyzeBlocks(MF, Tokens); 00256 while (!Tokens.empty()) { 00257 IfcvtToken *Token = Tokens.back(); 00258 Tokens.pop_back(); 00259 BBInfo &BBI = Token->BBI; 00260 IfcvtKind Kind = Token->Kind; 00261 unsigned NumDups = Token->NumDups; 00262 unsigned NumDups2 = Token->NumDups2; 00263 00264 delete Token; 00265 00266 // If the block has been evicted out of the queue or it has already been 00267 // marked dead (due to it being predicated), then skip it. 00268 if (BBI.IsDone) 00269 BBI.IsEnqueued = false; 00270 if (!BBI.IsEnqueued) 00271 continue; 00272 00273 BBI.IsEnqueued = false; 00274 00275 bool RetVal = false; 00276 switch (Kind) { 00277 default: assert(false && "Unexpected!"); 00278 break; 00279 case ICSimple: 00280 case ICSimpleFalse: { 00281 bool isFalse = Kind == ICSimpleFalse; 00282 if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break; 00283 DOUT << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"") 00284 << "): BB#" << BBI.BB->getNumber() << " (" 00285 << ((Kind == ICSimpleFalse) 00286 ? BBI.FalseBB->getNumber() 00287 : BBI.TrueBB->getNumber()) << ") "; 00288 RetVal = IfConvertSimple(BBI, Kind); 00289 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 00290 if (RetVal) { 00291 if (isFalse) NumSimpleFalse++; 00292 else NumSimple++; 00293 } 00294 break; 00295 } 00296 case ICTriangle: 00297 case ICTriangleRev: 00298 case ICTriangleFalse: 00299 case ICTriangleFRev: { 00300 bool isFalse = Kind == ICTriangleFalse; 00301 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev); 00302 if (DisableTriangle && !isFalse && !isRev) break; 00303 if (DisableTriangleR && !isFalse && isRev) break; 00304 if (DisableTriangleF && isFalse && !isRev) break; 00305 if (DisableTriangleFR && isFalse && isRev) break; 00306 DOUT << "Ifcvt (Triangle"; 00307 if (isFalse) 00308 DOUT << " false"; 00309 if (isRev) 00310 DOUT << " rev"; 00311 DOUT << "): BB#" << BBI.BB->getNumber() << " (T:" 00312 << BBI.TrueBB->getNumber() << ",F:" 00313 << BBI.FalseBB->getNumber() << ") "; 00314 RetVal = IfConvertTriangle(BBI, Kind); 00315 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 00316 if (RetVal) { 00317 if (isFalse) { 00318 if (isRev) NumTriangleFRev++; 00319 else NumTriangleFalse++; 00320 } else { 00321 if (isRev) NumTriangleRev++; 00322 else NumTriangle++; 00323 } 00324 } 00325 break; 00326 } 00327 case ICDiamond: { 00328 if (DisableDiamond) break; 00329 DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" 00330 << BBI.TrueBB->getNumber() << ",F:" 00331 << BBI.FalseBB->getNumber() << ") "; 00332 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2); 00333 DOUT << (RetVal ? "succeeded!" : "failed!") << "\n"; 00334 if (RetVal) NumDiamonds++; 00335 break; 00336 } 00337 } 00338 00339 Change |= RetVal; 00340 00341 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev + 00342 NumTriangleFalse + NumTriangleFRev + NumDiamonds; 00343 if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit) 00344 break; 00345 } 00346 00347 if (!Change) 00348 break; 00349 MadeChange |= Change; 00350 } 00351 00352 // Delete tokens in case of early exit. 00353 while (!Tokens.empty()) { 00354 IfcvtToken *Token = Tokens.back(); 00355 Tokens.pop_back(); 00356 delete Token; 00357 } 00358 00359 Tokens.clear(); 00360 Roots.clear(); 00361 BBAnalysis.clear(); 00362 00363 return MadeChange; 00364 } 00365 00366 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given 00367 /// its 'true' successor. 00368 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 00369 MachineBasicBlock *TrueBB) { 00370 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 00371 E = BB->succ_end(); SI != E; ++SI) { 00372 MachineBasicBlock *SuccBB = *SI; 00373 if (SuccBB != TrueBB) 00374 return SuccBB; 00375 } 00376 return NULL; 00377 } 00378 00379 /// ReverseBranchCondition - Reverse the condition of the end of the block 00380 /// branch. Swap block's 'true' and 'false' successors. 00381 bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { 00382 if (!TII->ReverseBranchCondition(BBI.BrCond)) { 00383 TII->RemoveBranch(*BBI.BB); 00384 TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond); 00385 std::swap(BBI.TrueBB, BBI.FalseBB); 00386 return true; 00387 } 00388 return false; 00389 } 00390 00391 /// getNextBlock - Returns the next block in the function blocks ordering. If 00392 /// it is the end, returns NULL. 00393 static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) { 00394 MachineFunction::iterator I = BB; 00395 MachineFunction::iterator E = BB->getParent()->end(); 00396 if (++I == E) 00397 return NULL; 00398 return I; 00399 } 00400 00401 /// ValidSimple - Returns true if the 'true' block (along with its 00402 /// predecessor) forms a valid simple shape for ifcvt. It also returns the 00403 /// number of instructions that the ifcvt would need to duplicate if performed 00404 /// in Dups. 00405 bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const { 00406 Dups = 0; 00407 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) 00408 return false; 00409 00410 if (TrueBBI.IsBrAnalyzable) 00411 return false; 00412 00413 if (TrueBBI.BB->pred_size() > 1) { 00414 if (TrueBBI.CannotBeCopied || 00415 TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit()) 00416 return false; 00417 Dups = TrueBBI.NonPredSize; 00418 } 00419 00420 return true; 00421 } 00422 00423 /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along 00424 /// with their common predecessor) forms a valid triangle shape for ifcvt. 00425 /// If 'FalseBranch' is true, it checks if 'true' block's false branch 00426 /// branches to the false branch rather than the other way around. It also 00427 /// returns the number of instructions that the ifcvt would need to duplicate 00428 /// if performed in 'Dups'. 00429 bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, 00430 bool FalseBranch, unsigned &Dups) const { 00431 Dups = 0; 00432 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) 00433 return false; 00434 00435 if (TrueBBI.BB->pred_size() > 1) { 00436 if (TrueBBI.CannotBeCopied) 00437 return false; 00438 00439 unsigned Size = TrueBBI.NonPredSize; 00440 if (TrueBBI.IsBrAnalyzable) { 00441 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty()) 00442 // Ends with an unconditional branch. It will be removed. 00443 --Size; 00444 else { 00445 MachineBasicBlock *FExit = FalseBranch 00446 ? TrueBBI.TrueBB : TrueBBI.FalseBB; 00447 if (FExit) 00448 // Require a conditional branch 00449 ++Size; 00450 } 00451 } 00452 if (Size > TLI->getIfCvtDupBlockSizeLimit()) 00453 return false; 00454 Dups = Size; 00455 } 00456 00457 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB; 00458 if (!TExit && blockAlwaysFallThrough(TrueBBI)) { 00459 MachineFunction::iterator I = TrueBBI.BB; 00460 if (++I == TrueBBI.BB->getParent()->end()) 00461 return false; 00462 TExit = I; 00463 } 00464 return TExit && TExit == FalseBBI.BB; 00465 } 00466 00467 static 00468 MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB, 00469 const TargetInstrInfo *TII) { 00470 MachineBasicBlock::iterator I = BB->end(); 00471 while (I != BB->begin()) { 00472 --I; 00473 if (!I->getDesc().isBranch()) 00474 break; 00475 } 00476 return I; 00477 } 00478 00479 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along 00480 /// with their common predecessor) forms a valid diamond shape for ifcvt. 00481 bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, 00482 unsigned &Dups1, unsigned &Dups2) const { 00483 Dups1 = Dups2 = 0; 00484 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone || 00485 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone) 00486 return false; 00487 00488 MachineBasicBlock *TT = TrueBBI.TrueBB; 00489 MachineBasicBlock *FT = FalseBBI.TrueBB; 00490 00491 if (!TT && blockAlwaysFallThrough(TrueBBI)) 00492 TT = getNextBlock(TrueBBI.BB); 00493 if (!FT && blockAlwaysFallThrough(FalseBBI)) 00494 FT = getNextBlock(FalseBBI.BB); 00495 if (TT != FT) 00496 return false; 00497 if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable)) 00498 return false; 00499 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) 00500 return false; 00501 00502 // FIXME: Allow true block to have an early exit? 00503 if (TrueBBI.FalseBB || FalseBBI.FalseBB || 00504 (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) 00505 return false; 00506 00507 MachineBasicBlock::iterator TI = TrueBBI.BB->begin(); 00508 MachineBasicBlock::iterator FI = FalseBBI.BB->begin(); 00509 while (TI != TrueBBI.BB->end() && FI != FalseBBI.BB->end()) { 00510 if (!TI->isIdenticalTo(FI)) 00511 break; 00512 ++Dups1; 00513 ++TI; 00514 ++FI; 00515 } 00516 00517 TI = firstNonBranchInst(TrueBBI.BB, TII); 00518 FI = firstNonBranchInst(FalseBBI.BB, TII); 00519 while (TI != TrueBBI.BB->begin() && FI != FalseBBI.BB->begin()) { 00520 if (!TI->isIdenticalTo(FI)) 00521 break; 00522 ++Dups2; 00523 --TI; 00524 --FI; 00525 } 00526 00527 return true; 00528 } 00529 00530 /// ScanInstructions - Scan all the instructions in the block to determine if 00531 /// the block is predicable. In most cases, that means all the instructions 00532 /// in the block are isPredicable(). Also checks if the block contains any 00533 /// instruction which can clobber a predicate (e.g. condition code register). 00534 /// If so, the block is not predicable unless it's the last instruction. 00535 void IfConverter::ScanInstructions(BBInfo &BBI) { 00536 if (BBI.IsDone) 00537 return; 00538 00539 bool AlreadyPredicated = BBI.Predicate.size() > 0; 00540 // First analyze the end of BB branches. 00541 BBI.TrueBB = BBI.FalseBB = NULL; 00542 BBI.BrCond.clear(); 00543 BBI.IsBrAnalyzable = 00544 !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); 00545 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL; 00546 00547 if (BBI.BrCond.size()) { 00548 // No false branch. This BB must end with a conditional branch and a 00549 // fallthrough. 00550 if (!BBI.FalseBB) 00551 BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB); 00552 if (!BBI.FalseBB) { 00553 // Malformed bcc? True and false blocks are the same? 00554 BBI.IsUnpredicable = true; 00555 return; 00556 } 00557 } 00558 00559 // Then scan all the instructions. 00560 BBI.NonPredSize = 0; 00561 BBI.ClobbersPred = false; 00562 for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); 00563 I != E; ++I) { 00564 const TargetInstrDesc &TID = I->getDesc(); 00565 if (TID.isNotDuplicable()) 00566 BBI.CannotBeCopied = true; 00567 00568 bool isPredicated = TII->isPredicated(I); 00569 bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch(); 00570 00571 if (!isCondBr) { 00572 if (!isPredicated) 00573 BBI.NonPredSize++; 00574 else if (!AlreadyPredicated) { 00575 // FIXME: This instruction is already predicated before the 00576 // if-conversion pass. It's probably something like a conditional move. 00577 // Mark this block unpredicable for now. 00578 BBI.IsUnpredicable = true; 00579 return; 00580 } 00581 } 00582 00583 if (BBI.ClobbersPred && !isPredicated) { 00584 // Predicate modification instruction should end the block (except for 00585 // already predicated instructions and end of block branches). 00586 if (isCondBr) { 00587 // A conditional branch is not predicable, but it may be eliminated. 00588 continue; 00589 } 00590 00591 // Predicate may have been modified, the subsequent (currently) 00592 // unpredicated instructions cannot be correctly predicated. 00593 BBI.IsUnpredicable = true; 00594 return; 00595 } 00596 00597 // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are 00598 // still potentially predicable. 00599 std::vector<MachineOperand> PredDefs; 00600 if (TII->DefinesPredicate(I, PredDefs)) 00601 BBI.ClobbersPred = true; 00602 00603 if (!TID.isPredicable()) { 00604 BBI.IsUnpredicable = true; 00605 return; 00606 } 00607 } 00608 } 00609 00610 /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be 00611 /// predicated by the specified predicate. 00612 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, 00613 SmallVectorImpl<MachineOperand> &Pred, 00614 bool isTriangle, bool RevBranch) { 00615 // If the block is dead or unpredicable, then it cannot be predicated. 00616 if (BBI.IsDone || BBI.IsUnpredicable) 00617 return false; 00618 00619 // If it is already predicated, check if its predicate subsumes the new 00620 // predicate. 00621 if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred)) 00622 return false; 00623 00624 if (BBI.BrCond.size()) { 00625 if (!isTriangle) 00626 return false; 00627 00628 // Test predicate subsumption. 00629 SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end()); 00630 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 00631 if (RevBranch) { 00632 if (TII->ReverseBranchCondition(Cond)) 00633 return false; 00634 } 00635 if (TII->ReverseBranchCondition(RevPred) || 00636 !TII->SubsumesPredicate(Cond, RevPred)) 00637 return false; 00638 } 00639 00640 return true; 00641 } 00642 00643 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from 00644 /// the specified block. Record its successors and whether it looks like an 00645 /// if-conversion candidate. 00646 IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, 00647 std::vector<IfcvtToken*> &Tokens) { 00648 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 00649 00650 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) 00651 return BBI; 00652 00653 BBI.BB = BB; 00654 BBI.IsBeingAnalyzed = true; 00655 00656 ScanInstructions(BBI); 00657 00658 // Unanalyzable or ends with fallthrough or unconditional branch. 00659 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) { 00660 BBI.IsBeingAnalyzed = false; 00661 BBI.IsAnalyzed = true; 00662 return BBI; 00663 } 00664 00665 // Do not ifcvt if either path is a back edge to the entry block. 00666 if (BBI.TrueBB == BB || BBI.FalseBB == BB) { 00667 BBI.IsBeingAnalyzed = false; 00668 BBI.IsAnalyzed = true; 00669 return BBI; 00670 } 00671 00672 // Do not ifcvt if true and false fallthrough blocks are the same. 00673 if (!BBI.FalseBB) { 00674 BBI.IsBeingAnalyzed = false; 00675 BBI.IsAnalyzed = true; 00676 return BBI; 00677 } 00678 00679 BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens); 00680 BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens); 00681 00682 if (TrueBBI.IsDone && FalseBBI.IsDone) { 00683 BBI.IsBeingAnalyzed = false; 00684 BBI.IsAnalyzed = true; 00685 return BBI; 00686 } 00687 00688 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); 00689 bool CanRevCond = !TII->ReverseBranchCondition(RevCond); 00690 00691 unsigned Dups = 0; 00692 unsigned Dups2 = 0; 00693 bool TNeedSub = TrueBBI.Predicate.size() > 0; 00694 bool FNeedSub = FalseBBI.Predicate.size() > 0; 00695 bool Enqueued = false; 00696 if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) && 00697 MeetIfcvtSizeLimit(TrueBBI.NonPredSize - (Dups + Dups2)) && 00698 MeetIfcvtSizeLimit(FalseBBI.NonPredSize - (Dups + Dups2)) && 00699 FeasibilityAnalysis(TrueBBI, BBI.BrCond) && 00700 FeasibilityAnalysis(FalseBBI, RevCond)) { 00701 // Diamond: 00702 // EBB 00703 // / \_ 00704 // | | 00705 // TBB FBB 00706 // \ / 00707 // TailBB 00708 // Note TailBB can be empty. 00709 Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups, 00710 Dups2)); 00711 Enqueued = true; 00712 } 00713 00714 if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) && 00715 MeetIfcvtSizeLimit(TrueBBI.NonPredSize) && 00716 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { 00717 // Triangle: 00718 // EBB 00719 // | \_ 00720 // | | 00721 // | TBB 00722 // | / 00723 // FBB 00724 Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups)); 00725 Enqueued = true; 00726 } 00727 00728 if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) && 00729 MeetIfcvtSizeLimit(TrueBBI.NonPredSize) && 00730 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) { 00731 Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups)); 00732 Enqueued = true; 00733 } 00734 00735 if (ValidSimple(TrueBBI, Dups) && 00736 MeetIfcvtSizeLimit(TrueBBI.NonPredSize) && 00737 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { 00738 // Simple (split, no rejoin): 00739 // EBB 00740 // | \_ 00741 // | | 00742 // | TBB---> exit 00743 // | 00744 // FBB 00745 Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups)); 00746 Enqueued = true; 00747 } 00748 00749 if (CanRevCond) { 00750 // Try the other path... 00751 if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) && 00752 MeetIfcvtSizeLimit(FalseBBI.NonPredSize) && 00753 FeasibilityAnalysis(FalseBBI, RevCond, true)) { 00754 Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups)); 00755 Enqueued = true; 00756 } 00757 00758 if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) && 00759 MeetIfcvtSizeLimit(FalseBBI.NonPredSize) && 00760 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { 00761 Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups)); 00762 Enqueued = true; 00763 } 00764 00765 if (ValidSimple(FalseBBI, Dups) && 00766 MeetIfcvtSizeLimit(FalseBBI.NonPredSize) && 00767 FeasibilityAnalysis(FalseBBI, RevCond)) { 00768 Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups)); 00769 Enqueued = true; 00770 } 00771 } 00772 00773 BBI.IsEnqueued = Enqueued; 00774 BBI.IsBeingAnalyzed = false; 00775 BBI.IsAnalyzed = true; 00776 return BBI; 00777 } 00778 00779 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion 00780 /// candidates. It returns true if any CFG restructuring is done to expose more 00781 /// if-conversion opportunities. 00782 bool IfConverter::AnalyzeBlocks(MachineFunction &MF, 00783 std::vector<IfcvtToken*> &Tokens) { 00784 bool Change = false; 00785 std::set<MachineBasicBlock*> Visited; 00786 for (unsigned i = 0, e = Roots.size(); i != e; ++i) { 00787 for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited), 00788 E = idf_ext_end(Roots[i], Visited); I != E; ++I) { 00789 MachineBasicBlock *BB = *I; 00790 AnalyzeBlock(BB, Tokens); 00791 } 00792 } 00793 00794 // Sort to favor more complex ifcvt scheme. 00795 std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp); 00796 00797 return Change; 00798 } 00799 00800 /// canFallThroughTo - Returns true either if ToBB is the next block after BB or 00801 /// that all the intervening blocks are empty (given BB can fall through to its 00802 /// next block). 00803 static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { 00804 MachineFunction::iterator I = BB; 00805 MachineFunction::iterator TI = ToBB; 00806 MachineFunction::iterator E = BB->getParent()->end(); 00807 while (++I != TI) 00808 if (I == E || !I->empty()) 00809 return false; 00810 return true; 00811 } 00812 00813 /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed 00814 /// to determine if it can be if-converted. If predecessor is already enqueued, 00815 /// dequeue it! 00816 void IfConverter::InvalidatePreds(MachineBasicBlock *BB) { 00817 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 00818 E = BB->pred_end(); PI != E; ++PI) { 00819 BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()]; 00820 if (PBBI.IsDone || PBBI.BB == BB) 00821 continue; 00822 PBBI.IsAnalyzed = false; 00823 PBBI.IsEnqueued = false; 00824 } 00825 } 00826 00827 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. 00828 /// 00829 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, 00830 const TargetInstrInfo *TII) { 00831 SmallVector<MachineOperand, 0> NoCond; 00832 TII->InsertBranch(*BB, ToBB, NULL, NoCond); 00833 } 00834 00835 /// RemoveExtraEdges - Remove true / false edges if either / both are no longer 00836 /// successors. 00837 void IfConverter::RemoveExtraEdges(BBInfo &BBI) { 00838 MachineBasicBlock *TBB = NULL, *FBB = NULL; 00839 SmallVector<MachineOperand, 4> Cond; 00840 if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond)) 00841 BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 00842 } 00843 00844 /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. 00845 /// 00846 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { 00847 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 00848 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 00849 BBInfo *CvtBBI = &TrueBBI; 00850 BBInfo *NextBBI = &FalseBBI; 00851 00852 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 00853 if (Kind == ICSimpleFalse) 00854 std::swap(CvtBBI, NextBBI); 00855 00856 if (CvtBBI->IsDone || 00857 (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { 00858 // Something has changed. It's no longer safe to predicate this block. 00859 BBI.IsAnalyzed = false; 00860 CvtBBI->IsAnalyzed = false; 00861 return false; 00862 } 00863 00864 if (Kind == ICSimpleFalse) 00865 if (TII->ReverseBranchCondition(Cond)) 00866 assert(false && "Unable to reverse branch condition!"); 00867 00868 if (CvtBBI->BB->pred_size() > 1) { 00869 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 00870 // Copy instructions in the true block, predicate them, and add them to 00871 // the entry block. 00872 CopyAndPredicateBlock(BBI, *CvtBBI, Cond); 00873 } else { 00874 PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond); 00875 00876 // Merge converted block into entry block. 00877 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 00878 MergeBlocks(BBI, *CvtBBI); 00879 } 00880 00881 bool IterIfcvt = true; 00882 if (!canFallThroughTo(BBI.BB, NextBBI->BB)) { 00883 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 00884 BBI.HasFallThrough = false; 00885 // Now ifcvt'd block will look like this: 00886 // BB: 00887 // ... 00888 // t, f = cmp 00889 // if t op 00890 // b BBf 00891 // 00892 // We cannot further ifcvt this block because the unconditional branch 00893 // will have to be predicated on the new condition, that will not be 00894 // available if cmp executes. 00895 IterIfcvt = false; 00896 } 00897 00898 RemoveExtraEdges(BBI); 00899 00900 // Update block info. BB can be iteratively if-converted. 00901 if (!IterIfcvt) 00902 BBI.IsDone = true; 00903 InvalidatePreds(BBI.BB); 00904 CvtBBI->IsDone = true; 00905 00906 // FIXME: Must maintain LiveIns. 00907 return true; 00908 } 00909 00910 /// IfConvertTriangle - If convert a triangle sub-CFG. 00911 /// 00912 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { 00913 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 00914 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 00915 BBInfo *CvtBBI = &TrueBBI; 00916 BBInfo *NextBBI = &FalseBBI; 00917 00918 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); 00919 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) 00920 std::swap(CvtBBI, NextBBI); 00921 00922 if (CvtBBI->IsDone || 00923 (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { 00924 // Something has changed. It's no longer safe to predicate this block. 00925 BBI.IsAnalyzed = false; 00926 CvtBBI->IsAnalyzed = false; 00927 return false; 00928 } 00929 00930 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) 00931 if (TII->ReverseBranchCondition(Cond)) 00932 assert(false && "Unable to reverse branch condition!"); 00933 00934 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) { 00935 if (ReverseBranchCondition(*CvtBBI)) { 00936 // BB has been changed, modify its predecessors (except for this 00937 // one) so they don't get ifcvt'ed based on bad intel. 00938 for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(), 00939 E = CvtBBI->BB->pred_end(); PI != E; ++PI) { 00940 MachineBasicBlock *PBB = *PI; 00941 if (PBB == BBI.BB) 00942 continue; 00943 BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; 00944 if (PBBI.IsEnqueued) { 00945 PBBI.IsAnalyzed = false; 00946 PBBI.IsEnqueued = false; 00947 } 00948 } 00949 } 00950 } 00951 00952 bool HasEarlyExit = CvtBBI->FalseBB != NULL; 00953 bool DupBB = CvtBBI->BB->pred_size() > 1; 00954 if (DupBB) { 00955 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 00956 // Copy instructions in the true block, predicate them, and add them to 00957 // the entry block. 00958 CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true); 00959 } else { 00960 // Predicate the 'true' block after removing its branch. 00961 CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); 00962 PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond); 00963 00964 // Now merge the entry of the triangle with the true block. 00965 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 00966 MergeBlocks(BBI, *CvtBBI); 00967 } 00968 00969 // If 'true' block has a 'false' successor, add an exit branch to it. 00970 if (HasEarlyExit) { 00971 SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(), 00972 CvtBBI->BrCond.end()); 00973 if (TII->ReverseBranchCondition(RevCond)) 00974 assert(false && "Unable to reverse branch condition!"); 00975 TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond); 00976 BBI.BB->addSuccessor(CvtBBI->FalseBB); 00977 } 00978 00979 // Merge in the 'false' block if the 'false' block has no other 00980 // predecessors. Otherwise, add an unconditional branch to 'false'. 00981 bool FalseBBDead = false; 00982 bool IterIfcvt = true; 00983 bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB); 00984 if (!isFallThrough) { 00985 // Only merge them if the true block does not fallthrough to the false 00986 // block. By not merging them, we make it possible to iteratively 00987 // ifcvt the blocks. 00988 if (!HasEarlyExit && 00989 NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) { 00990 MergeBlocks(BBI, *NextBBI); 00991 FalseBBDead = true; 00992 } else { 00993 InsertUncondBranch(BBI.BB, NextBBI->BB, TII); 00994 BBI.HasFallThrough = false; 00995 } 00996 // Mixed predicated and unpredicated code. This cannot be iteratively 00997 // predicated. 00998 IterIfcvt = false; 00999 } 01000 01001 RemoveExtraEdges(BBI); 01002 01003 // Update block info. BB can be iteratively if-converted. 01004 if (!IterIfcvt) 01005 BBI.IsDone = true; 01006 InvalidatePreds(BBI.BB); 01007 CvtBBI->IsDone = true; 01008 if (FalseBBDead) 01009 NextBBI->IsDone = true; 01010 01011 // FIXME: Must maintain LiveIns. 01012 return true; 01013 } 01014 01015 /// IfConvertDiamond - If convert a diamond sub-CFG. 01016 /// 01017 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, 01018 unsigned NumDups1, unsigned NumDups2) { 01019 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; 01020 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; 01021 MachineBasicBlock *TailBB = TrueBBI.TrueBB; 01022 // True block must fall through or end with an unanalyzable terminator. 01023 if (!TailBB) { 01024 if (blockAlwaysFallThrough(TrueBBI)) 01025 TailBB = FalseBBI.TrueBB; 01026 assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!"); 01027 } 01028 01029 if (TrueBBI.IsDone || FalseBBI.IsDone || 01030 TrueBBI.BB->pred_size() > 1 || 01031 FalseBBI.BB->pred_size() > 1) { 01032 // Something has changed. It's no longer safe to predicate these blocks. 01033 BBI.IsAnalyzed = false; 01034 TrueBBI.IsAnalyzed = false; 01035 FalseBBI.IsAnalyzed = false; 01036 return false; 01037 } 01038 01039 // Merge the 'true' and 'false' blocks by copying the instructions 01040 // from the 'false' block to the 'true' block. That is, unless the true 01041 // block would clobber the predicate, in that case, do the opposite. 01042 BBInfo *BBI1 = &TrueBBI; 01043 BBInfo *BBI2 = &FalseBBI; 01044 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); 01045 if (TII->ReverseBranchCondition(RevCond)) 01046 assert(false && "Unable to reverse branch condition!"); 01047 SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond; 01048 SmallVector<MachineOperand, 4> *Cond2 = &RevCond; 01049 01050 // Figure out the more profitable ordering. 01051 bool DoSwap = false; 01052 if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred) 01053 DoSwap = true; 01054 else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) { 01055 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize) 01056 DoSwap = true; 01057 } 01058 if (DoSwap) { 01059 std::swap(BBI1, BBI2); 01060 std::swap(Cond1, Cond2); 01061 } 01062 01063 // Remove the conditional branch from entry to the blocks. 01064 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 01065 01066 // Remove the duplicated instructions at the beginnings of both paths. 01067 MachineBasicBlock::iterator DI1 = BBI1->BB->begin(); 01068 MachineBasicBlock::iterator DI2 = BBI2->BB->begin(); 01069 BBI1->NonPredSize -= NumDups1; 01070 BBI2->NonPredSize -= NumDups1; 01071 while (NumDups1 != 0) { 01072 ++DI1; 01073 ++DI2; 01074 --NumDups1; 01075 } 01076 BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1); 01077 BBI2->BB->erase(BBI2->BB->begin(), DI2); 01078 01079 // Predicate the 'true' block after removing its branch. 01080 BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB); 01081 DI1 = BBI1->BB->end(); 01082 for (unsigned i = 0; i != NumDups2; ++i) 01083 --DI1; 01084 BBI1->BB->erase(DI1, BBI1->BB->end()); 01085 PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1); 01086 01087 // Predicate the 'false' block. 01088 BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB); 01089 DI2 = BBI2->BB->end(); 01090 while (NumDups2 != 0) { 01091 --DI2; 01092 --NumDups2; 01093 } 01094 PredicateBlock(*BBI2, DI2, *Cond2); 01095 01096 // Merge the true block into the entry of the diamond. 01097 MergeBlocks(BBI, *BBI1); 01098 MergeBlocks(BBI, *BBI2); 01099 01100 // If the if-converted block falls through or unconditionally branches into 01101 // the tail block, and the tail block does not have other predecessors, then 01102 // fold the tail block in as well. Otherwise, unless it falls through to the 01103 // tail, add a unconditional branch to it. 01104 if (TailBB) { 01105 BBInfo TailBBI = BBAnalysis[TailBB->getNumber()]; 01106 if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) { 01107 BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); 01108 MergeBlocks(BBI, TailBBI); 01109 TailBBI.IsDone = true; 01110 } else { 01111 InsertUncondBranch(BBI.BB, TailBB, TII); 01112 BBI.HasFallThrough = false; 01113 } 01114 } 01115 01116 RemoveExtraEdges(BBI); 01117 01118 // Update block info. 01119 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true; 01120 InvalidatePreds(BBI.BB); 01121 01122 // FIXME: Must maintain LiveIns. 01123 return true; 01124 } 01125 01126 /// PredicateBlock - Predicate instructions from the start of the block to the 01127 /// specified end with the specified condition. 01128 void IfConverter::PredicateBlock(BBInfo &BBI, 01129 MachineBasicBlock::iterator E, 01130 SmallVectorImpl<MachineOperand> &Cond) { 01131 for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) { 01132 if (TII->isPredicated(I)) 01133 continue; 01134 if (!TII->PredicateInstruction(I, Cond)) { 01135 #ifndef NDEBUG 01136 cerr << "Unable to predicate " << *I << "!\n"; 01137 #endif 01138 llvm_unreachable(0); 01139 } 01140 } 01141 01142 std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate)); 01143 01144 BBI.IsAnalyzed = false; 01145 BBI.NonPredSize = 0; 01146 01147 NumIfConvBBs++; 01148 } 01149 01150 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to 01151 /// the destination block. Skip end of block branches if IgnoreBr is true. 01152 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, 01153 SmallVectorImpl<MachineOperand> &Cond, 01154 bool IgnoreBr) { 01155 MachineFunction &MF = *ToBBI.BB->getParent(); 01156 01157 for (MachineBasicBlock::iterator I = FromBBI.BB->begin(), 01158 E = FromBBI.BB->end(); I != E; ++I) { 01159 const TargetInstrDesc &TID = I->getDesc(); 01160 bool isPredicated = TII->isPredicated(I); 01161 // Do not copy the end of the block branches. 01162 if (IgnoreBr && !isPredicated && TID.isBranch()) 01163 break; 01164 01165 MachineInstr *MI = MF.CloneMachineInstr(I); 01166 ToBBI.BB->insert(ToBBI.BB->end(), MI); 01167 ToBBI.NonPredSize++; 01168 01169 if (!isPredicated) 01170 if (!TII->PredicateInstruction(MI, Cond)) { 01171 #ifndef NDEBUG 01172 cerr << "Unable to predicate " << *I << "!\n"; 01173 #endif 01174 llvm_unreachable(0); 01175 } 01176 } 01177 01178 std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), 01179 FromBBI.BB->succ_end()); 01180 MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); 01181 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; 01182 01183 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 01184 MachineBasicBlock *Succ = Succs[i]; 01185 // Fallthrough edge can't be transferred. 01186 if (Succ == FallThrough) 01187 continue; 01188 ToBBI.BB->addSuccessor(Succ); 01189 } 01190 01191 std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), 01192 std::back_inserter(ToBBI.Predicate)); 01193 std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate)); 01194 01195 ToBBI.ClobbersPred |= FromBBI.ClobbersPred; 01196 ToBBI.IsAnalyzed = false; 01197 01198 NumDupBBs++; 01199 } 01200 01201 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB. 01202 /// 01203 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) { 01204 ToBBI.BB->splice(ToBBI.BB->end(), 01205 FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); 01206 01207 // Redirect all branches to FromBB to ToBB. 01208 std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(), 01209 FromBBI.BB->pred_end()); 01210 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 01211 MachineBasicBlock *Pred = Preds[i]; 01212 if (Pred == ToBBI.BB) 01213 continue; 01214 Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB); 01215 } 01216 01217 std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), 01218 FromBBI.BB->succ_end()); 01219 MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); 01220 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL; 01221 01222 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 01223 MachineBasicBlock *Succ = Succs[i]; 01224 // Fallthrough edge can't be transferred. 01225 if (Succ == FallThrough) 01226 continue; 01227 FromBBI.BB->removeSuccessor(Succ); 01228 ToBBI.BB->addSuccessor(Succ); 01229 } 01230 01231 // Now FromBBI always falls through to the next block! 01232 if (NBB && !FromBBI.BB->isSuccessor(NBB)) 01233 FromBBI.BB->addSuccessor(NBB); 01234 01235 std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), 01236 std::back_inserter(ToBBI.Predicate)); 01237 FromBBI.Predicate.clear(); 01238 01239 ToBBI.NonPredSize += FromBBI.NonPredSize; 01240 FromBBI.NonPredSize = 0; 01241 01242 ToBBI.ClobbersPred |= FromBBI.ClobbersPred; 01243 ToBBI.HasFallThrough = FromBBI.HasFallThrough; 01244 ToBBI.IsAnalyzed = false; 01245 FromBBI.IsAnalyzed = false; 01246 }