1//===- HexagonCFGOptimizer.cpp - CFG optimizations ------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Hexagon.h"
10#include "MCTargetDesc/HexagonMCTargetDesc.h"
11#include "llvm/CodeGen/MachineBasicBlock.h"
12#include "llvm/CodeGen/MachineFunction.h"
13#include "llvm/CodeGen/MachineFunctionPass.h"
14#include "llvm/CodeGen/MachineInstr.h"
15#include "llvm/CodeGen/MachineOperand.h"
16#include "llvm/CodeGen/TargetInstrInfo.h"
17#include "llvm/CodeGen/TargetSubtargetInfo.h"
18#include "llvm/Pass.h"
19#include "llvm/Support/ErrorHandling.h"
20#include <cassert>
21#include <vector>
22
23using namespace llvm;
24
25#define DEBUG_TYPE "hexagon_cfg"
26
27namespace {
28
29class HexagonCFGOptimizer : public MachineFunctionPass {
30private:
31 void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
32 bool isOnFallThroughPath(MachineBasicBlock *MBB);
33
34public:
35 static char ID;
36
37 HexagonCFGOptimizer() : MachineFunctionPass(ID) {}
38
39 StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
40 bool runOnMachineFunction(MachineFunction &Fn) override;
41
42 MachineFunctionProperties getRequiredProperties() const override {
43 return MachineFunctionProperties().setNoVRegs();
44 }
45};
46
47} // end anonymous namespace
48
49char HexagonCFGOptimizer::ID = 0;
50
51static bool IsConditionalBranch(int Opc) {
52 switch (Opc) {
53 case Hexagon::J2_jumpt:
54 case Hexagon::J2_jumptpt:
55 case Hexagon::J2_jumpf:
56 case Hexagon::J2_jumpfpt:
57 case Hexagon::J2_jumptnew:
58 case Hexagon::J2_jumpfnew:
59 case Hexagon::J2_jumptnewpt:
60 case Hexagon::J2_jumpfnewpt:
61 return true;
62 }
63 return false;
64}
65
66static bool IsUnconditionalJump(int Opc) {
67 return (Opc == Hexagon::J2_jump);
68}
69
70void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
71 MachineInstr &MI, 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 case Hexagon::J2_jumpf:
80 NewOpcode = Hexagon::J2_jumpt;
81 break;
82 case Hexagon::J2_jumptnewpt:
83 NewOpcode = Hexagon::J2_jumpfnewpt;
84 break;
85 case Hexagon::J2_jumpfnewpt:
86 NewOpcode = Hexagon::J2_jumptnewpt;
87 break;
88 default:
89 llvm_unreachable("Cannot handle this case");
90 }
91
92 MI.setDesc(TII->get(Opcode: NewOpcode));
93 MI.getOperand(i: 1).setMBB(NewTarget);
94}
95
96bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
97 if (MBB->canFallThrough())
98 return true;
99 for (MachineBasicBlock *PB : MBB->predecessors())
100 if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())
101 return true;
102 return false;
103}
104
105bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
106 if (skipFunction(F: Fn.getFunction()))
107 return false;
108
109 // Loop over all of the basic blocks.
110 for (MachineBasicBlock &MBB : Fn) {
111 // Traverse the basic block.
112 MachineBasicBlock::iterator MII = MBB.getFirstTerminator();
113 if (MII != MBB.end()) {
114 MachineInstr &MI = *MII;
115 int Opc = MI.getOpcode();
116 if (IsConditionalBranch(Opc)) {
117 // (Case 1) Transform the code if the following condition occurs:
118 // BB1: if (p0) jump BB3
119 // ...falls-through to BB2 ...
120 // BB2: jump BB4
121 // ...next block in layout is BB3...
122 // BB3: ...
123 //
124 // Transform this to:
125 // BB1: if (!p0) jump BB4
126 // Remove BB2
127 // BB3: ...
128 //
129 // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
130 // BB1: if (p0) jump BB3
131 // ...falls-through to BB2 ...
132 // BB2: jump BB4
133 // ...other basic blocks ...
134 // BB4:
135 // ...not a fall-thru
136 // BB3: ...
137 // jump BB4
138 //
139 // Transform this to:
140 // BB1: if (!p0) jump BB4
141 // Remove BB2
142 // BB3: ...
143 // BB4: ...
144 unsigned NumSuccs = MBB.succ_size();
145 MachineBasicBlock::succ_iterator SI = MBB.succ_begin();
146 MachineBasicBlock* FirstSucc = *SI;
147 MachineBasicBlock* SecondSucc = *(++SI);
148 MachineBasicBlock* LayoutSucc = nullptr;
149 MachineBasicBlock* JumpAroundTarget = nullptr;
150
151 if (MBB.isLayoutSuccessor(MBB: FirstSucc)) {
152 LayoutSucc = FirstSucc;
153 JumpAroundTarget = SecondSucc;
154 } else if (MBB.isLayoutSuccessor(MBB: SecondSucc)) {
155 LayoutSucc = SecondSucc;
156 JumpAroundTarget = FirstSucc;
157 } else {
158 // Odd case...cannot handle.
159 }
160
161 // The target of the unconditional branch must be JumpAroundTarget.
162 // TODO: If not, we should not invert the unconditional branch.
163 MachineBasicBlock* CondBranchTarget = nullptr;
164 if (MI.getOpcode() == Hexagon::J2_jumpt ||
165 MI.getOpcode() == Hexagon::J2_jumpf) {
166 CondBranchTarget = MI.getOperand(i: 1).getMBB();
167 }
168
169 if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
170 continue;
171 }
172
173 if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
174 // Ensure that BB2 has one instruction -- an unconditional jump.
175 if ((LayoutSucc->size() == 1) &&
176 IsUnconditionalJump(Opc: LayoutSucc->front().getOpcode())) {
177 assert(JumpAroundTarget && "jump target is needed to process second basic block");
178 MachineBasicBlock* UncondTarget =
179 LayoutSucc->front().getOperand(i: 0).getMBB();
180 // Check if the layout successor of BB2 is BB3.
181 bool case1 = LayoutSucc->isLayoutSuccessor(MBB: JumpAroundTarget);
182 bool case2 = JumpAroundTarget->isSuccessor(MBB: UncondTarget) &&
183 !JumpAroundTarget->empty() &&
184 IsUnconditionalJump(Opc: JumpAroundTarget->back().getOpcode()) &&
185 JumpAroundTarget->pred_size() == 1 &&
186 JumpAroundTarget->succ_size() == 1;
187
188 if (case1 || case2) {
189 InvertAndChangeJumpTarget(MI, NewTarget: UncondTarget);
190 MBB.replaceSuccessor(Old: JumpAroundTarget, New: UncondTarget);
191
192 // Remove the unconditional branch in LayoutSucc.
193 LayoutSucc->erase(I: LayoutSucc->begin());
194 LayoutSucc->replaceSuccessor(Old: UncondTarget, New: 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(NewBefore: LayoutSucc);
200 // only move a block if it doesn't have a fall-thru. otherwise
201 // the CFG will be incorrect.
202 if (!isOnFallThroughPath(MBB: UncondTarget))
203 UncondTarget->moveAfter(NewBefore: JumpAroundTarget);
204 }
205
206 // Correct live-in information. Is used by post-RA scheduler
207 // The live-in to LayoutSucc is now all values live-in to
208 // JumpAroundTarget.
209 std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
210 LayoutSucc->livein_begin(), LayoutSucc->livein_end());
211 std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
212 JumpAroundTarget->livein_begin(),
213 JumpAroundTarget->livein_end());
214 for (const auto &OrigLI : OrigLiveIn)
215 LayoutSucc->removeLiveIn(Reg: OrigLI.PhysReg);
216 for (const auto &NewLI : NewLiveIn)
217 LayoutSucc->addLiveIn(RegMaskPair: NewLI);
218 }
219 }
220 }
221 }
222 }
223 }
224 return true;
225}
226
227//===----------------------------------------------------------------------===//
228// Public Constructor Functions
229//===----------------------------------------------------------------------===//
230
231INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
232 false, false)
233
234FunctionPass *llvm::createHexagonCFGOptimizer() {
235 return new HexagonCFGOptimizer();
236}
237