lib/CodeGen/IfConversion.cpp

   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/TargetLowering.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/ADT/Statistic.h"
  23 using namespace llvm;
  24
  25 STATISTIC(NumIfConvBBs, "Number of if-converted blocks");
  26
  27 namespace {
  28   class IfConverter : public MachineFunctionPass {
  29     enum BBICKind {
  30       ICInvalid,       // BB data invalid.
  31       ICNotClassfied,  // BB data valid, but not classified.
  32       ICTriangle,      // BB is part of a triangle sub-CFG.
  33       ICDiamond,       // BB is part of a diamond sub-CFG.
  34       ICTriangleEntry, // BB is entry of a triangle sub-CFG.
  35       ICDiamondEntry   // BB is entry of a diamond sub-CFG.
  36     };
  37
  38     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
  39     /// if-conversion feasibility analysis. This includes results from
  40     /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
  41     /// classification, and common tail block of its successors (if it's a
  42     /// diamond shape).
  43     struct BBInfo {
  44       BBICKind Kind;
  45       MachineBasicBlock *BB;
  46       MachineBasicBlock *TrueBB;
  47       MachineBasicBlock *FalseBB;
  48       MachineBasicBlock *TailBB;
  49       std::vector<MachineOperand> Cond;
  50       unsigned Size;
  51       BBInfo() : Kind(ICInvalid), BB(0), TrueBB(0), FalseBB(0), TailBB(0), Size(0) {}
  52     };
  53
  54     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
  55     /// basic block number.
  56     std::vector<BBInfo> BBAnalysis;
  57
  58     const TargetLowering *TLI;
  59     const TargetInstrInfo *TII;
  60     bool MadeChange;
  61   public:
  62     static char ID;
  63     IfConverter() : MachineFunctionPass((intptr_t)&ID) {}
  64
  65     virtual bool runOnMachineFunction(MachineFunction &MF);
  66     virtual const char *getPassName() const { return "If converter"; }
  67
  68   private:
  69     void AnalyzeBlock(MachineBasicBlock *BB);
  70     void InitialFunctionAnalysis(MachineFunction &MF,
  71                                  std::vector<int> &Candidates);
  72     bool IfConvertDiamond(BBInfo &BBI);
  73     bool IfConvertTriangle(BBInfo &BBI);
  74     bool isBlockPredicable(MachineBasicBlock *BB) const;
  75     void PredicateBlock(MachineBasicBlock *BB,
  76                         std::vector<MachineOperand> &Cond,
  77                         bool IgnoreTerm = false);
  78     void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI);
  79   };
  80   char IfConverter::ID = 0;
  81 }
  82
  83 FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
  84
  85 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
  86   TLI = MF.getTarget().getTargetLowering();
  87   TII = MF.getTarget().getInstrInfo();
  88   if (!TII) return false;
  89
  90   MF.RenumberBlocks();
  91   unsigned NumBBs = MF.getNumBlockIDs();
  92   BBAnalysis.resize(NumBBs);
  93
  94   std::vector<int> Candidates;
  95   // Do an intial analysis for each basic block and finding all the potential
  96   // candidates to perform if-convesion.
  97   InitialFunctionAnalysis(MF, Candidates);
  98
  99   MadeChange = false;
 100   for (unsigned i = 0, e = Candidates.size(); i != e; ++i) {
 101     BBInfo &BBI = BBAnalysis[Candidates[i]];
 102     switch (BBI.Kind) {
 103     default: assert(false && "Unexpected!");
 104       break;
 105     case ICTriangleEntry:
 106       MadeChange |= IfConvertTriangle(BBI);
 107       break;
 108     case ICDiamondEntry:
 109       MadeChange |= IfConvertDiamond(BBI);
 110       break;
 111     }
 112   }
 113
 114   BBAnalysis.clear();
 115
 116   return MadeChange;
 117 }
 118
 119 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
 120                                          MachineBasicBlock *TrueBB) {
 121   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 122          E = BB->succ_end(); SI != E; ++SI) {
 123     MachineBasicBlock *SuccBB = *SI;
 124     if (SuccBB != TrueBB)
 125       return SuccBB;
 126   }
 127   return NULL;
 128 }
 129
 130 void IfConverter::AnalyzeBlock(MachineBasicBlock *BB) {
 131   BBInfo &BBI = BBAnalysis[BB->getNumber()];
 132
 133   if (BBI.Kind != ICInvalid)
 134     return;  // Always analyzed.
 135   BBI.BB = BB;
 136   BBI.Size = std::distance(BB->begin(), BB->end());
 137
 138   // Look for 'root' of a simple (non-nested) triangle or diamond.
 139   BBI.Kind = ICNotClassfied;
 140   if (TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB, BBI.Cond)
 141       || !BBI.TrueBB || BBI.Cond.size() == 0)
 142     return;
 143
 144   // Not a candidate if 'true' block has another predecessor.
 145   // FIXME: Use or'd predicate or predicated cmp.
 146   if (BBI.TrueBB->pred_size() > 1)
 147     return;
 148
 149   // Not a candidate if 'true' block is going to be if-converted.
 150   AnalyzeBlock(BBI.TrueBB);
 151   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 152   if (TrueBBI.Kind != ICNotClassfied)
 153     return;
 154
 155   // TODO: Only handle very simple cases for now.
 156   if (TrueBBI.FalseBB || TrueBBI.Cond.size())
 157     return;
 158
 159   // No false branch. This BB must end with a conditional branch and a
 160   // fallthrough.
 161   if (!BBI.FalseBB)
 162     BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB);
 163   assert(BBI.FalseBB && "Expected to find the fallthrough block!");
 164
 165   // Not a candidate if 'false' block has another predecessor.
 166   // FIXME: Invert condition and swap 'true' / 'false' blocks?
 167   if (BBI.FalseBB->pred_size() > 1)
 168     return;
 169
 170   // Not a candidate if 'false' block is going to be if-converted.
 171   AnalyzeBlock(BBI.FalseBB);
 172   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 173   if (FalseBBI.Kind != ICNotClassfied)
 174     return;
 175
 176   // TODO: Only handle very simple cases for now.
 177   if (FalseBBI.FalseBB || FalseBBI.Cond.size())
 178     return;
 179
 180   if (TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB) {
 181     // Triangle:
 182     //   EBB
 183     //   | \_
 184     //   |  |
 185     //   | TBB
 186     //   |  /
 187     //   FBB
 188     BBI.Kind = ICTriangleEntry;
 189     TrueBBI.Kind = FalseBBI.Kind = ICTriangle;
 190   } else if (TrueBBI.TrueBB == FalseBBI.TrueBB) {
 191     // Diamond:
 192     //   EBB
 193     //   / \_
 194     //  |   |
 195     // TBB FBB
 196     //   \ /
 197     //  TailBB
 198     // Note MBB can be empty in case both TBB and FBB are return blocks.
 199     BBI.Kind = ICDiamondEntry;
 200     TrueBBI.Kind = FalseBBI.Kind = ICDiamond;
 201     BBI.TailBB = TrueBBI.TrueBB;
 202   }
 203   return;
 204 }
 205
 206 /// InitialFunctionAnalysis - Analyze all blocks and find entries for all
 207 /// if-conversion candidates.
 208 void IfConverter::InitialFunctionAnalysis(MachineFunction &MF,
 209                                           std::vector<int> &Candidates) {
 210   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 211     MachineBasicBlock *BB = I;
 212     AnalyzeBlock(BB);
 213     BBInfo &BBI = BBAnalysis[BB->getNumber()];
 214     if (BBI.Kind == ICTriangleEntry || BBI.Kind == ICDiamondEntry)
 215       Candidates.push_back(BB->getNumber());
 216   }
 217 }
 218
 219 /// TransferPreds - Transfer all the predecessors of FromBB to ToBB.
 220 ///
 221 static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
 222    std::vector<MachineBasicBlock*> Preds(FromBB->pred_begin(),
 223                                          FromBB->pred_end());
 224     for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 225       MachineBasicBlock *Pred = Preds[i];
 226       Pred->removeSuccessor(FromBB);
 227       if (!Pred->isSuccessor(ToBB))
 228         Pred->addSuccessor(ToBB);
 229     }
 230 }
 231
 232 /// TransferSuccs - Transfer all the successors of FromBB to ToBB.
 233 ///
 234 static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
 235    std::vector<MachineBasicBlock*> Succs(FromBB->succ_begin(),
 236                                          FromBB->succ_end());
 237     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
 238       MachineBasicBlock *Succ = Succs[i];
 239       FromBB->removeSuccessor(Succ);
 240       if (!ToBB->isSuccessor(Succ))
 241         ToBB->addSuccessor(Succ);
 242     }
 243 }
 244
 245 /// IfConvertTriangle - If convert a triangle sub-CFG.
 246 ///
 247 bool IfConverter::IfConvertTriangle(BBInfo &BBI) {
 248   if (isBlockPredicable(BBI.TrueBB)) {
 249     BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 250     BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 251
 252     // Predicate the 'true' block after removing its branch.
 253     TrueBBI.Size -= TII->RemoveBranch(*BBI.TrueBB);
 254     PredicateBlock(BBI.TrueBB, BBI.Cond);
 255
 256     // Join the 'true' and 'false' blocks by copying the instructions
 257     // from the 'false' block to the 'true' block.
 258     BBI.TrueBB->removeSuccessor(BBI.FalseBB);
 259     MergeBlocks(TrueBBI, FalseBBI);
 260
 261     // Now merge the entry of the triangle with the true block.
 262     BBI.Size -= TII->RemoveBranch(*BBI.BB);
 263     MergeBlocks(BBI, TrueBBI);
 264
 265     // Update block info.
 266     TrueBBI.Kind = ICInvalid;
 267     FalseBBI.Kind = ICInvalid;
 268
 269     // FIXME: Must maintain LiveIns.
 270     NumIfConvBBs++;
 271     return true;
 272   }
 273   return false;
 274 }
 275
 276 /// IfConvertDiamond - If convert a diamond sub-CFG.
 277 ///
 278 bool IfConverter::IfConvertDiamond(BBInfo &BBI) {
 279   if (isBlockPredicable(BBI.TrueBB) && isBlockPredicable(BBI.FalseBB)) {
 280     std::vector<MachineInstr*> Dups;
 281     if (!BBI.TailBB) {
 282       // No common merge block. Check if the terminators (e.g. return) are
 283       // the same or predicable.
 284       MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator();
 285       MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator();
 286       while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) {
 287         if (TT->isIdenticalTo(FT))
 288           Dups.push_back(TT);  // Will erase these later.
 289         else if (!TT->isPredicable() && !FT->isPredicable())
 290           return false; // Can't if-convert. Abort!
 291         ++TT;
 292         ++FT;
 293       }
 294       // One of the two pathes have more terminators, make sure they are all
 295       // predicable.
 296       while (TT != BBI.TrueBB->end())
 297         if (!TT->isPredicable())
 298           return false; // Can't if-convert. Abort!
 299       while (FT != BBI.FalseBB->end())
 300         if (!FT->isPredicable())
 301           return false; // Can't if-convert. Abort!
 302     }
 303
 304     BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 305     BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 306
 307     // Remove the duplicated instructions from the 'true' block.
 308     for (unsigned i = 0, e = Dups.size(); i != e; ++i) {
 309       Dups[i]->eraseFromParent();
 310       --TrueBBI.Size;
 311     }
 312
 313     // Predicate the 'true' block after removing its branch.
 314     TrueBBI.Size -= TII->RemoveBranch(*BBI.TrueBB);
 315     PredicateBlock(BBI.TrueBB, BBI.Cond);
 316
 317     // Either the 'true' block fallthrough to another block or it ends with a
 318     // return. If it's the former, add a conditional branch to its successor.
 319     if (!TrueBBI.TrueBB)
 320       TII->InsertBranch(*BBI.TrueBB, *BBI.TrueBB->succ_begin(), NULL, BBI.Cond);
 321
 322     // Predicate the 'false' block.
 323     std::vector<MachineOperand> NewCond(BBI.Cond);
 324     TII->ReverseBranchCondition(NewCond);
 325     PredicateBlock(BBI.FalseBB, NewCond, true);
 326
 327     // Either the 'false' block fallthrough to another block or it ends with a
 328     // return. If it's the former, add a conditional branch to its successor.
 329     if (!FalseBBI.TrueBB)
 330       TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL,NewCond);
 331
 332     // Merge the 'true' and 'false' blocks by copying the instructions
 333     // from the 'false' block to the 'true' block.
 334     MergeBlocks(TrueBBI, FalseBBI);
 335
 336     // Remove the conditional branch from entry to the blocks.
 337     BBI.Size -= TII->RemoveBranch(*BBI.BB);
 338
 339     // Merge the combined block into the entry of the diamond if the entry
 340     // block is the only predecessor. Otherwise, insert an unconditional
 341     // branch.
 342     BBInfo *CvtBBI = &TrueBBI;
 343     if (BBI.TrueBB->pred_size() == 1) {
 344       BBI.BB->removeSuccessor(BBI.TrueBB);
 345       MergeBlocks(BBI, TrueBBI);
 346       CvtBBI = &BBI;
 347     } else {
 348       std::vector<MachineOperand> NoCond;
 349       TII->InsertBranch(*BBI.BB, BBI.TrueBB, NULL, NoCond);
 350     }
 351
 352     // If the if-converted block fallthrough into the tail block, then
 353     // fold the tail block in as well.
 354     if (BBI.TailBB && CvtBBI->BB->succ_size() == 1) {
 355       CvtBBI->Size -= TII->RemoveBranch(*CvtBBI->BB);
 356       CvtBBI->BB->removeSuccessor(BBI.TailBB);
 357       BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()];
 358       MergeBlocks(*CvtBBI, TailBBI);
 359       TailBBI.Kind = ICInvalid;
 360     }
 361
 362     // Update block info.
 363     TrueBBI.Kind = ICInvalid;
 364     FalseBBI.Kind = ICInvalid;
 365
 366     // FIXME: Must maintain LiveIns.
 367     NumIfConvBBs += 2;
 368     return true;
 369   }
 370   return false;
 371 }
 372
 373 /// isBlockPredicable - Returns true if the block is predicable. In most
 374 /// cases, that means all the instructions in the block has M_PREDICABLE flag.
 375 /// It assume all the terminator instructions can be converted or deleted.
 376 bool IfConverter::isBlockPredicable(MachineBasicBlock *BB) const {
 377   const BBInfo &BBI = BBAnalysis[BB->getNumber()];
 378   if (BBI.Size == 0 || BBI.Size > TLI->getIfCvtBlockSizeLimit())
 379     return false;
 380
 381   for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
 382        I != E; ++I) {
 383     if (TII->isTerminatorInstr(I->getOpcode()))
 384       continue;
 385     if (!I->isPredicable())
 386       return false;
 387   }
 388   return true;
 389 }
 390
 391 /// PredicateBlock - Predicate every instruction in the block with the specified
 392 /// condition. If IgnoreTerm is true, skip over all terminator instructions.
 393 void IfConverter::PredicateBlock(MachineBasicBlock *BB,
 394                                  std::vector<MachineOperand> &Cond,
 395                                  bool IgnoreTerm) {
 396   for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
 397        I != E; ++I) {
 398     if (IgnoreTerm && TII->isTerminatorInstr(I->getOpcode()))
 399       continue;
 400     if (!TII->PredicateInstruction(&*I, Cond)) {
 401       cerr << "Unable to predication " << *I << "!\n";
 402       abort();
 403     }
 404   }
 405 }
 406
 407 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
 408 ///
 409 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
 410   ToBBI.BB->splice(ToBBI.BB->end(),
 411                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
 412   TransferPreds(ToBBI.BB, FromBBI.BB);
 413   TransferSuccs(ToBBI.BB, FromBBI.BB);
 414   ToBBI.Size += FromBBI.Size;
 415   FromBBI.Size = 0;
 416 }