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  FunctionPass *createHexagonCFGOptimizer();
32  void initializeHexagonCFGOptimizerPass(PassRegistry&);
33}
34
35
36namespace {
37
38class HexagonCFGOptimizer : public MachineFunctionPass {
39
40private:
41  void InvertAndChangeJumpTarget(MachineInstr*, MachineBasicBlock*);
42
43 public:
44  static char ID;
45  HexagonCFGOptimizer() : MachineFunctionPass(ID) {
46    initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry());
47  }
48
49  const char *getPassName() const override {
50    return "Hexagon CFG Optimizer";
51  }
52  bool runOnMachineFunction(MachineFunction &Fn) override;
53};
54
55
56char HexagonCFGOptimizer::ID = 0;
57
58static bool IsConditionalBranch(int Opc) {
59  return (Opc == Hexagon::J2_jumpt) || (Opc == Hexagon::J2_jumpf)
60    || (Opc == Hexagon::J2_jumptnewpt) || (Opc == Hexagon::J2_jumpfnewpt);
61}
62
63
64static bool IsUnconditionalJump(int Opc) {
65  return (Opc == Hexagon::J2_jump);
66}
67
68
69void
70HexagonCFGOptimizer::InvertAndChangeJumpTarget(MachineInstr* MI,
71                                               MachineBasicBlock* NewTarget) {
72  const TargetInstrInfo *TII =
73      MI->getParent()->getParent()->getSubtarget().getInstrInfo();
74  int NewOpcode = 0;
75  switch(MI->getOpcode()) {
76  case Hexagon::J2_jumpt:
77    NewOpcode = Hexagon::J2_jumpf;
78    break;
79
80  case Hexagon::J2_jumpf:
81    NewOpcode = Hexagon::J2_jumpt;
82    break;
83
84  case Hexagon::J2_jumptnewpt:
85    NewOpcode = Hexagon::J2_jumpfnewpt;
86    break;
87
88  case Hexagon::J2_jumpfnewpt:
89    NewOpcode = Hexagon::J2_jumptnewpt;
90    break;
91
92  default:
93    llvm_unreachable("Cannot handle this case");
94  }
95
96  MI->setDesc(TII->get(NewOpcode));
97  MI->getOperand(1).setMBB(NewTarget);
98}
99
100
101bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
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 = nullptr;
148        MachineBasicBlock* JumpAroundTarget = nullptr;
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 = nullptr;
163        if ((MI->getOpcode() == Hexagon::J2_jumpt) ||
164            (MI->getOpcode() == Hexagon::J2_jumpf)) {
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->replaceSuccessor(JumpAroundTarget, UncondTarget);
190
191              // Remove the unconditional branch in LayoutSucc.
192              LayoutSucc->erase(LayoutSucc->begin());
193              LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);
194
195              // This code performs the conversion for case 2, which moves
196              // the block to the fall-thru case (BB3 in the code above).
197              if (case2 && !case1) {
198                JumpAroundTarget->moveAfter(LayoutSucc);
199                // only move a block if it doesn't have a fall-thru. otherwise
200                // the CFG will be incorrect.
201                if (!UncondTarget->canFallThrough()) {
202                  UncondTarget->moveAfter(JumpAroundTarget);
203                }
204              }
205
206              //
207              // Correct live-in information. Is used by post-RA scheduler
208              // The live-in to LayoutSucc is now all values live-in to
209              // JumpAroundTarget.
210              //
211              std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
212                  LayoutSucc->livein_begin(), LayoutSucc->livein_end());
213              std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
214                  JumpAroundTarget->livein_begin(),
215                  JumpAroundTarget->livein_end());
216              for (const auto &OrigLI : OrigLiveIn)
217                LayoutSucc->removeLiveIn(OrigLI.PhysReg);
218              for (const auto &NewLI : NewLiveIn)
219                LayoutSucc->addLiveIn(NewLI);
220            }
221          }
222        }
223      }
224    }
225  }
226  return true;
227}
228}
229
230
231//===----------------------------------------------------------------------===//
232//                         Public Constructor Functions
233//===----------------------------------------------------------------------===//
234
235static void initializePassOnce(PassRegistry &Registry) {
236  PassInfo *PI = new PassInfo("Hexagon CFG Optimizer", "hexagon-cfg",
237                              &HexagonCFGOptimizer::ID, nullptr, false, false);
238  Registry.registerPass(*PI, true);
239}
240
241void llvm::initializeHexagonCFGOptimizerPass(PassRegistry &Registry) {
242  CALL_ONCE_INITIALIZATION(initializePassOnce)
243}
244
245FunctionPass *llvm::createHexagonCFGOptimizer() {
246  return new HexagonCFGOptimizer();
247}
248