lib/Target/Hexagon/HexagonCFGOptimizer.cpp

   1 //===-- HexagonCFGOptimizer.cpp - CFG optimizations -----------------------===//
   2 //                     The LLVM Compiler Infrastructure
   3 //
   4 // This file is distributed under the University of Illinois Open Source
   5 // License. See LICENSE.TXT for details.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #define DEBUG_TYPE "hexagon_cfg"
  10 #include "Hexagon.h"
  11 #include "HexagonMachineFunctionInfo.h"
  12 #include "HexagonSubtarget.h"
  13 #include "HexagonTargetMachine.h"
  14 #include "llvm/CodeGen/MachineDominators.h"
  15 #include "llvm/CodeGen/MachineFunctionPass.h"
  16 #include "llvm/CodeGen/MachineInstrBuilder.h"
  17 #include "llvm/CodeGen/MachineLoopInfo.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/MathExtras.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26
  27 using namespace llvm;
  28
  29 namespace llvm {
  30   void initializeHexagonCFGOptimizerPass(PassRegistry&);
  31 }
  32
  33
  34 namespace {
  35
  36 class HexagonCFGOptimizer : public MachineFunctionPass {
  37
  38 private:
  39   const HexagonTargetMachine& QTM;
  40   const HexagonSubtarget &QST;
  41
  42   void InvertAndChangeJumpTarget(MachineInstr*, MachineBasicBlock*);
  43
  44  public:
  45   static char ID;
  46   HexagonCFGOptimizer(const HexagonTargetMachine& TM)
  47     : MachineFunctionPass(ID), QTM(TM), QST(*TM.getSubtargetImpl()) {
  48     initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry());
  49   }
  50
  51   const char *getPassName() const {
  52     return "Hexagon CFG Optimizer";
  53   }
  54   bool runOnMachineFunction(MachineFunction &Fn);
  55 };
  56
  57
  58 char HexagonCFGOptimizer::ID = 0;
  59
  60 static bool IsConditionalBranch(int Opc) {
  61   return (Opc == Hexagon::JMP_t) || (Opc == Hexagon::JMP_f)
  62     || (Opc == Hexagon::JMP_tnew_t) || (Opc == Hexagon::JMP_fnew_t);
  63 }
  64
  65
  66 static bool IsUnconditionalJump(int Opc) {
  67   return (Opc == Hexagon::JMP);
  68 }
  69
  70
  71 void
  72 HexagonCFGOptimizer::InvertAndChangeJumpTarget(MachineInstr* MI,
  73                                                MachineBasicBlock* NewTarget) {
  74   const HexagonInstrInfo *QII = QTM.getInstrInfo();
  75   int NewOpcode = 0;
  76   switch(MI->getOpcode()) {
  77   case Hexagon::JMP_t:
  78     NewOpcode = Hexagon::JMP_f;
  79     break;
  80
  81   case Hexagon::JMP_f:
  82     NewOpcode = Hexagon::JMP_t;
  83     break;
  84
  85   case Hexagon::JMP_tnew_t:
  86     NewOpcode = Hexagon::JMP_fnew_t;
  87     break;
  88
  89   case Hexagon::JMP_fnew_t:
  90     NewOpcode = Hexagon::JMP_tnew_t;
  91     break;
  92
  93   default:
  94     llvm_unreachable("Cannot handle this case");
  95   }
  96
  97   MI->setDesc(QII->get(NewOpcode));
  98   MI->getOperand(1).setMBB(NewTarget);
  99 }
 100
 101
 102 bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
 103
 104   // Loop over all of the basic blocks.
 105   for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end();
 106        MBBb != MBBe; ++MBBb) {
 107     MachineBasicBlock* MBB = MBBb;
 108
 109     // Traverse the basic block.
 110     MachineBasicBlock::iterator MII = MBB->getFirstTerminator();
 111     if (MII != MBB->end()) {
 112       MachineInstr *MI = MII;
 113       int Opc = MI->getOpcode();
 114       if (IsConditionalBranch(Opc)) {
 115
 116         //
 117         // (Case 1) Transform the code if the following condition occurs:
 118         //   BB1: if (p0) jump BB3
 119         //   ...falls-through to BB2 ...
 120         //   BB2: jump BB4
 121         //   ...next block in layout is BB3...
 122         //   BB3: ...
 123         //
 124         //  Transform this to:
 125         //  BB1: if (!p0) jump BB4
 126         //  Remove BB2
 127         //  BB3: ...
 128         //
 129         // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
 130         //   BB1: if (p0) jump BB3
 131         //   ...falls-through to BB2 ...
 132         //   BB2: jump BB4
 133         //   ...other basic blocks ...
 134         //   BB4:
 135         //   ...not a fall-thru
 136         //   BB3: ...
 137         //     jump BB4
 138         //
 139         // Transform this to:
 140         //   BB1: if (!p0) jump BB4
 141         //   Remove BB2
 142         //   BB3: ...
 143         //   BB4: ...
 144         //
 145         unsigned NumSuccs = MBB->succ_size();
 146         MachineBasicBlock::succ_iterator SI = MBB->succ_begin();
 147         MachineBasicBlock* FirstSucc = *SI;
 148         MachineBasicBlock* SecondSucc = *(++SI);
 149         MachineBasicBlock* LayoutSucc = NULL;
 150         MachineBasicBlock* JumpAroundTarget = NULL;
 151
 152         if (MBB->isLayoutSuccessor(FirstSucc)) {
 153           LayoutSucc = FirstSucc;
 154           JumpAroundTarget = SecondSucc;
 155         } else if (MBB->isLayoutSuccessor(SecondSucc)) {
 156           LayoutSucc = SecondSucc;
 157           JumpAroundTarget = FirstSucc;
 158         } else {
 159           // Odd case...cannot handle.
 160         }
 161
 162         // The target of the unconditional branch must be JumpAroundTarget.
 163         // TODO: If not, we should not invert the unconditional branch.
 164         MachineBasicBlock* CondBranchTarget = NULL;
 165         if ((MI->getOpcode() == Hexagon::JMP_t) ||
 166             (MI->getOpcode() == Hexagon::JMP_f)) {
 167           CondBranchTarget = MI->getOperand(1).getMBB();
 168         }
 169
 170         if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
 171           continue;
 172         }
 173
 174         if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
 175
 176           // Ensure that BB2 has one instruction -- an unconditional jump.
 177           if ((LayoutSucc->size() == 1) &&
 178               IsUnconditionalJump(LayoutSucc->front().getOpcode())) {
 179             MachineBasicBlock* UncondTarget =
 180               LayoutSucc->front().getOperand(0).getMBB();
 181             // Check if the layout successor of BB2 is BB3.
 182             bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
 183             bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
 184               JumpAroundTarget->size() >= 1 &&
 185               IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
 186               JumpAroundTarget->pred_size() == 1 &&
 187               JumpAroundTarget->succ_size() == 1;
 188
 189             if (case1 || case2) {
 190               InvertAndChangeJumpTarget(MI, UncondTarget);
 191               MBB->removeSuccessor(JumpAroundTarget);
 192               MBB->addSuccessor(UncondTarget);
 193
 194               // Remove the unconditional branch in LayoutSucc.
 195               LayoutSucc->erase(LayoutSucc->begin());
 196               LayoutSucc->removeSuccessor(UncondTarget);
 197               LayoutSucc->addSuccessor(JumpAroundTarget);
 198
 199               // This code performs the conversion for case 2, which moves
 200               // the block to the fall-thru case (BB3 in the code above).
 201               if (case2 && !case1) {
 202                 JumpAroundTarget->moveAfter(LayoutSucc);
 203                 // only move a block if it doesn't have a fall-thru. otherwise
 204                 // the CFG will be incorrect.
 205                 if (!UncondTarget->canFallThrough()) {
 206                   UncondTarget->moveAfter(JumpAroundTarget);
 207                 }
 208               }
 209
 210               //
 211               // Correct live-in information. Is used by post-RA scheduler
 212               // The live-in to LayoutSucc is now all values live-in to
 213               // JumpAroundTarget.
 214               //
 215               std::vector<unsigned> OrigLiveIn(LayoutSucc->livein_begin(),
 216                                                LayoutSucc->livein_end());
 217               std::vector<unsigned> NewLiveIn(JumpAroundTarget->livein_begin(),
 218                                               JumpAroundTarget->livein_end());
 219               for (unsigned i = 0; i < OrigLiveIn.size(); ++i) {
 220                 LayoutSucc->removeLiveIn(OrigLiveIn[i]);
 221               }
 222               for (unsigned i = 0; i < NewLiveIn.size(); ++i) {
 223                 LayoutSucc->addLiveIn(NewLiveIn[i]);
 224               }
 225             }
 226           }
 227         }
 228       }
 229     }
 230   }
 231   return true;
 232 }
 233 }
 234
 235
 236 //===----------------------------------------------------------------------===//
 237 //                         Public Constructor Functions
 238 //===----------------------------------------------------------------------===//
 239
 240 static void initializePassOnce(PassRegistry &Registry) {
 241   PassInfo *PI = new PassInfo("Hexagon CFG Optimizer", "hexagon-cfg",
 242                               &HexagonCFGOptimizer::ID, 0, false, false);
 243   Registry.registerPass(*PI, true);
 244 }
 245
 246 void llvm::initializeHexagonCFGOptimizerPass(PassRegistry &Registry) {
 247   CALL_ONCE_INITIALIZATION(initializePassOnce)
 248 }
 249
 250 FunctionPass *llvm::createHexagonCFGOptimizer(const HexagonTargetMachine &TM) {
 251   return new HexagonCFGOptimizer(TM);
 252 }