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