IfConversion.cpp revision c5d05ef35780bf822765c5a3e2c13201450591ba
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 "ifconversion" 15#include "llvm/CodeGen/Passes.h" 16#include "llvm/CodeGen/MachineModuleInfo.h" 17#include "llvm/CodeGen/MachineFunctionPass.h" 18#include "llvm/Target/TargetInstrInfo.h" 19#include "llvm/Target/TargetMachine.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/ADT/Statistic.h" 22using namespace llvm; 23 24STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); 25 26namespace { 27 class IfConverter : public MachineFunctionPass { 28 enum BBICKind { 29 ICInvalid, // BB data invalid. 30 ICNotClassfied, // BB data valid, but not classified. 31 ICTriangle, // BB is part of a triangle sub-CFG. 32 ICDiamond, // BB is part of a diamond sub-CFG. 33 ICTriangleEntry, // BB is entry of a triangle sub-CFG. 34 ICDiamondEntry // BB is entry of a diamond sub-CFG. 35 }; 36 37 /// BBInfo - One per MachineBasicBlock, this is used to cache the result 38 /// if-conversion feasibility analysis. This includes results from 39 /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its 40 /// classification, and common merge block of its successors (if it's a 41 /// diamond shape). 42 struct BBInfo { 43 BBICKind Kind; 44 MachineBasicBlock *EBB; 45 MachineBasicBlock *TBB; 46 MachineBasicBlock *FBB; 47 MachineBasicBlock *CMBB; 48 std::vector<MachineOperand> Cond; 49 BBInfo() : Kind(ICInvalid), EBB(0), TBB(0), FBB(0), CMBB(0) {} 50 }; 51 52 /// BBAnalysis - Results of if-conversion feasibility analysis indexed by 53 /// basic block number. 54 std::vector<BBInfo> BBAnalysis; 55 56 const TargetInstrInfo *TII; 57 bool MadeChange; 58 public: 59 static char ID; 60 IfConverter() : MachineFunctionPass((intptr_t)&ID) {} 61 62 virtual bool runOnMachineFunction(MachineFunction &MF); 63 virtual const char *getPassName() const { return "If converter"; } 64 65 private: 66 void AnalyzeBlock(MachineBasicBlock *BB); 67 void InitialFunctionAnalysis(MachineFunction &MF, 68 std::vector<int> &Candidates); 69 bool IfConvertDiamond(BBInfo &BBI); 70 bool IfConvertTriangle(BBInfo &BBI); 71 bool isBlockPredicatable(MachineBasicBlock *BB, 72 bool IgnoreTerm = false) const; 73 void PredicateBlock(MachineBasicBlock *BB, 74 std::vector<MachineOperand> &Cond, 75 bool IgnoreTerm = false); 76 void MergeBlocks(MachineBasicBlock *TBB, MachineBasicBlock *FBB); 77 }; 78 char IfConverter::ID = 0; 79} 80 81FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } 82 83bool IfConverter::runOnMachineFunction(MachineFunction &MF) { 84 TII = MF.getTarget().getInstrInfo(); 85 if (!TII) return false; 86 87 MadeChange = false; 88 89 MF.RenumberBlocks(); 90 unsigned NumBBs = MF.getNumBlockIDs(); 91 BBAnalysis.resize(NumBBs); 92 93 std::vector<int> Candidates; 94 // Do an intial analysis for each basic block and finding all the potential 95 // candidates to perform if-convesion. 96 InitialFunctionAnalysis(MF, Candidates); 97 98 for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 99 BBInfo &BBI = BBAnalysis[i]; 100 switch (BBI.Kind) { 101 default: assert(false && "Unexpected!"); 102 break; 103 case ICTriangleEntry: 104 MadeChange |= IfConvertTriangle(BBI); 105 break; 106 case ICDiamondEntry: 107 MadeChange |= IfConvertDiamond(BBI); 108 break; 109 } 110 } 111 return MadeChange; 112} 113 114static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 115 MachineBasicBlock *TBB) { 116 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 117 E = BB->succ_end(); SI != E; ++SI) { 118 MachineBasicBlock *SuccBB = *SI; 119 if (SuccBB != TBB) 120 return SuccBB; 121 } 122 return NULL; 123} 124 125void IfConverter::AnalyzeBlock(MachineBasicBlock *BB) { 126 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 127 128 if (BBI.Kind != ICInvalid) 129 return; // Always analyzed. 130 BBI.EBB = BB; 131 132 // Look for 'root' of a simple (non-nested) triangle or diamond. 133 BBI.Kind = ICNotClassfied; 134 if (TII->AnalyzeBranch(*BB, BBI.TBB, BBI.FBB, BBI.Cond) 135 || !BBI.TBB || BBI.Cond.size() == 0) 136 return; 137 AnalyzeBlock(BBI.TBB); 138 BBInfo &TBBI = BBAnalysis[BBI.TBB->getNumber()]; 139 if (TBBI.Kind != ICNotClassfied) 140 return; 141 142 if (!BBI.FBB) 143 BBI.FBB = findFalseBlock(BB, BBI.TBB); 144 assert(BBI.FBB && "Expected to find the fallthrough block!"); 145 146 AnalyzeBlock(BBI.FBB); 147 BBInfo &FBBI = BBAnalysis[BBI.FBB->getNumber()]; 148 if (FBBI.Kind != ICNotClassfied) 149 return; 150 151 // TODO: Only handle very simple cases for now. 152 if (TBBI.FBB || FBBI.FBB || TBBI.Cond.size() > 1 || FBBI.Cond.size() > 1) 153 return; 154 155 if (TBBI.TBB && TBBI.TBB == BBI.FBB) { 156 // Triangle: 157 // EBB 158 // | \_ 159 // | | 160 // | TBB 161 // | / 162 // FBB 163 BBI.Kind = ICTriangleEntry; 164 TBBI.Kind = FBBI.Kind = ICTriangle; 165 } else if (TBBI.TBB == FBBI.TBB) { 166 // Diamond: 167 // EBB 168 // / \_ 169 // | | 170 // TBB FBB 171 // \ / 172 // MBB 173 // Note MBB can be empty in case both TBB and FBB are return blocks. 174 BBI.Kind = ICDiamondEntry; 175 TBBI.Kind = FBBI.Kind = ICDiamond; 176 BBI.CMBB = TBBI.TBB; 177 } 178 return; 179} 180 181void IfConverter::InitialFunctionAnalysis(MachineFunction &MF, 182 std::vector<int> &Candidates) { 183 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 184 MachineBasicBlock *BB = I; 185 AnalyzeBlock(BB); 186 BBInfo &BBI = BBAnalysis[BB->getNumber()]; 187 if (BBI.Kind == ICTriangleEntry || BBI.Kind == ICDiamondEntry) 188 Candidates.push_back(BB->getNumber()); 189 } 190} 191 192bool IfConverter::IfConvertTriangle(BBInfo &BBI) { 193 if (isBlockPredicatable(BBI.TBB, true)) { 194 // Predicate the 'true' block after removing its branch. 195 TII->RemoveBranch(*BBI.TBB); 196 PredicateBlock(BBI.TBB, BBI.Cond); 197 198 // Join the 'true' and 'false' blocks by copying the instructions 199 // from the 'false' block to the 'true' block. 200 MergeBlocks(BBI.TBB, BBI.FBB); 201 202 // Adjust entry block, it should have but a single unconditional 203 // branch. 204 BBI.EBB->removeSuccessor(BBI.FBB); 205 TII->RemoveBranch(*BBI.EBB); 206 std::vector<MachineOperand> NoCond; 207 TII->InsertBranch(*BBI.EBB, BBI.TBB, NULL, NoCond); 208 209 // FIXME: Must maintain LiveIns. 210 NumIfConvBBs++; 211 return true; 212 } 213 return false; 214} 215 216bool IfConverter::IfConvertDiamond(BBInfo &BBI) { 217 if (isBlockPredicatable(BBI.TBB, true) && 218 isBlockPredicatable(BBI.FBB, true)) { 219 std::vector<MachineInstr*> Dups; 220 if (!BBI.CMBB) { 221 // No common merge block. Check if the terminators (e.g. return) are 222 // the same or predicatable. 223 MachineBasicBlock::iterator TT = BBI.TBB->getFirstTerminator(); 224 MachineBasicBlock::iterator FT = BBI.FBB->getFirstTerminator(); 225 while (TT != BBI.TBB->end() && FT != BBI.FBB->end()) { 226 if (TT->isIdenticalTo(FT)) 227 Dups.push_back(TT); // Will erase these later. 228 else if (!TII->isPredicatable(TT) && !TII->isPredicatable(FT)) 229 return false; // Can't if-convert. Abort! 230 ++TT; 231 ++FT; 232 } 233 234 while (TT != BBI.TBB->end()) 235 if (!TII->isPredicatable(TT)) 236 return false; // Can't if-convert. Abort! 237 while (FT != BBI.FBB->end()) 238 if (!TII->isPredicatable(FT)) 239 return false; // Can't if-convert. Abort! 240 } 241 242 // Remove the duplicated instructions from the 'true' block. 243 for (unsigned i = 0, e = Dups.size(); i != e; ++i) 244 Dups[i]->eraseFromParent(); 245 246 // Predicate the 'true' block after removing its branch. 247 TII->RemoveBranch(*BBI.TBB); 248 PredicateBlock(BBI.TBB, BBI.Cond); 249 250 // Predicate the 'false' block. 251 std::vector<MachineOperand> NewCond(BBI.Cond); 252 TII->ReverseBranchCondition(NewCond); 253 PredicateBlock(BBI.FBB, NewCond, true); 254 255 // Join the 'true' and 'false' blocks by copying the instructions 256 // from the 'false' block to the 'true' block. 257 MergeBlocks(BBI.TBB, BBI.FBB); 258 259 // Adjust entry block, it should have but a single unconditional 260 // branch . 261 BBI.EBB->removeSuccessor(BBI.FBB); 262 TII->RemoveBranch(*BBI.EBB); 263 std::vector<MachineOperand> NoCond; 264 TII->InsertBranch(*BBI.EBB, BBI.TBB, NULL, NoCond); 265 266 // FIXME: Must maintain LiveIns. 267 NumIfConvBBs += 2; 268 return true; 269 } 270 return false; 271} 272 273/// isBlockPredicatable - Returns true if the block is predicatable. In most 274/// cases, that means all the instructions in the block has M_PREDICATED flag. 275/// If IgnoreTerm is true, assume all the terminator instructions can be 276/// converted or deleted. 277bool IfConverter::isBlockPredicatable(MachineBasicBlock *BB, 278 bool IgnoreTerm) const { 279 for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 280 I != E; ++I) { 281 if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode())) 282 continue; 283 if (!TII->isPredicatable(I)) 284 return false; 285 } 286 return true; 287} 288 289/// PredicateBlock - Predicate every instruction in the block with the specified 290/// condition. If IgnoreTerm is true, skip over all terminator instructions. 291void IfConverter::PredicateBlock(MachineBasicBlock *BB, 292 std::vector<MachineOperand> &Cond, 293 bool IgnoreTerm) { 294 for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 295 I != E; ++I) { 296 if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode())) 297 continue; 298 TII->PredicateInstruction(&*I, Cond); 299 } 300} 301 302/// MergeBlocks - Move all instructions from FBB to the end of TBB. 303/// 304void IfConverter::MergeBlocks(MachineBasicBlock *TBB, MachineBasicBlock *FBB) { 305 TBB->splice(TBB->end(), FBB, FBB->begin(), FBB->end()); 306} 307