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