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