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