LLVM 19.0.0git
HexagonCFGOptimizer.cpp
Go to the documentation of this file.
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"
19#include "llvm/Pass.h"
21#include <cassert>
22#include <vector>
23
24using namespace llvm;
25
26#define DEBUG_TYPE "hexagon_cfg"
27
28namespace llvm {
29
32
33} // end namespace llvm
34
35namespace {
36
37class HexagonCFGOptimizer : public MachineFunctionPass {
38private:
39 void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
40 bool isOnFallThroughPath(MachineBasicBlock *MBB);
41
42public:
43 static char ID;
44
45 HexagonCFGOptimizer() : MachineFunctionPass(ID) {
47 }
48
49 StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
50 bool runOnMachineFunction(MachineFunction &Fn) override;
51
54 MachineFunctionProperties::Property::NoVRegs);
55 }
56};
57
58} // end anonymous namespace
59
60char HexagonCFGOptimizer::ID = 0;
61
62static bool IsConditionalBranch(int Opc) {
63 switch (Opc) {
64 case Hexagon::J2_jumpt:
65 case Hexagon::J2_jumptpt:
66 case Hexagon::J2_jumpf:
67 case Hexagon::J2_jumpfpt:
68 case Hexagon::J2_jumptnew:
69 case Hexagon::J2_jumpfnew:
70 case Hexagon::J2_jumptnewpt:
71 case Hexagon::J2_jumpfnewpt:
72 return true;
73 }
74 return false;
75}
76
77static bool IsUnconditionalJump(int Opc) {
78 return (Opc == Hexagon::J2_jump);
79}
80
81void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
82 MachineInstr &MI, MachineBasicBlock *NewTarget) {
83 const TargetInstrInfo *TII =
84 MI.getParent()->getParent()->getSubtarget().getInstrInfo();
85 int NewOpcode = 0;
86 switch (MI.getOpcode()) {
87 case Hexagon::J2_jumpt:
88 NewOpcode = Hexagon::J2_jumpf;
89 break;
90 case Hexagon::J2_jumpf:
91 NewOpcode = Hexagon::J2_jumpt;
92 break;
93 case Hexagon::J2_jumptnewpt:
94 NewOpcode = Hexagon::J2_jumpfnewpt;
95 break;
96 case Hexagon::J2_jumpfnewpt:
97 NewOpcode = Hexagon::J2_jumptnewpt;
98 break;
99 default:
100 llvm_unreachable("Cannot handle this case");
101 }
102
103 MI.setDesc(TII->get(NewOpcode));
104 MI.getOperand(1).setMBB(NewTarget);
105}
106
107bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
108 if (MBB->canFallThrough())
109 return true;
111 if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())
112 return true;
113 return false;
114}
115
116bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
117 if (skipFunction(Fn.getFunction()))
118 return false;
119
120 // Loop over all of the basic blocks.
121 for (MachineBasicBlock &MBB : Fn) {
122 // Traverse the basic block.
124 if (MII != MBB.end()) {
125 MachineInstr &MI = *MII;
126 int Opc = MI.getOpcode();
127 if (IsConditionalBranch(Opc)) {
128 // (Case 1) Transform the code if the following condition occurs:
129 // BB1: if (p0) jump BB3
130 // ...falls-through to BB2 ...
131 // BB2: jump BB4
132 // ...next block in layout is BB3...
133 // BB3: ...
134 //
135 // Transform this to:
136 // BB1: if (!p0) jump BB4
137 // Remove BB2
138 // BB3: ...
139 //
140 // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
141 // BB1: if (p0) jump BB3
142 // ...falls-through to BB2 ...
143 // BB2: jump BB4
144 // ...other basic blocks ...
145 // BB4:
146 // ...not a fall-thru
147 // BB3: ...
148 // jump BB4
149 //
150 // Transform this to:
151 // BB1: if (!p0) jump BB4
152 // Remove BB2
153 // BB3: ...
154 // BB4: ...
155 unsigned NumSuccs = MBB.succ_size();
157 MachineBasicBlock* FirstSucc = *SI;
158 MachineBasicBlock* SecondSucc = *(++SI);
159 MachineBasicBlock* LayoutSucc = nullptr;
160 MachineBasicBlock* JumpAroundTarget = nullptr;
161
162 if (MBB.isLayoutSuccessor(FirstSucc)) {
163 LayoutSucc = FirstSucc;
164 JumpAroundTarget = SecondSucc;
165 } else if (MBB.isLayoutSuccessor(SecondSucc)) {
166 LayoutSucc = SecondSucc;
167 JumpAroundTarget = FirstSucc;
168 } else {
169 // Odd case...cannot handle.
170 }
171
172 // The target of the unconditional branch must be JumpAroundTarget.
173 // TODO: If not, we should not invert the unconditional branch.
174 MachineBasicBlock* CondBranchTarget = nullptr;
175 if (MI.getOpcode() == Hexagon::J2_jumpt ||
176 MI.getOpcode() == Hexagon::J2_jumpf) {
177 CondBranchTarget = MI.getOperand(1).getMBB();
178 }
179
180 if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
181 continue;
182 }
183
184 if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
185 // Ensure that BB2 has one instruction -- an unconditional jump.
186 if ((LayoutSucc->size() == 1) &&
187 IsUnconditionalJump(LayoutSucc->front().getOpcode())) {
188 assert(JumpAroundTarget && "jump target is needed to process second basic block");
189 MachineBasicBlock* UncondTarget =
190 LayoutSucc->front().getOperand(0).getMBB();
191 // Check if the layout successor of BB2 is BB3.
192 bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
193 bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
194 !JumpAroundTarget->empty() &&
195 IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
196 JumpAroundTarget->pred_size() == 1 &&
197 JumpAroundTarget->succ_size() == 1;
198
199 if (case1 || case2) {
200 InvertAndChangeJumpTarget(MI, UncondTarget);
201 MBB.replaceSuccessor(JumpAroundTarget, UncondTarget);
202
203 // Remove the unconditional branch in LayoutSucc.
204 LayoutSucc->erase(LayoutSucc->begin());
205 LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);
206
207 // This code performs the conversion for case 2, which moves
208 // the block to the fall-thru case (BB3 in the code above).
209 if (case2 && !case1) {
210 JumpAroundTarget->moveAfter(LayoutSucc);
211 // only move a block if it doesn't have a fall-thru. otherwise
212 // the CFG will be incorrect.
213 if (!isOnFallThroughPath(UncondTarget))
214 UncondTarget->moveAfter(JumpAroundTarget);
215 }
216
217 // Correct live-in information. Is used by post-RA scheduler
218 // The live-in to LayoutSucc is now all values live-in to
219 // JumpAroundTarget.
220 std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
221 LayoutSucc->livein_begin(), LayoutSucc->livein_end());
222 std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
223 JumpAroundTarget->livein_begin(),
224 JumpAroundTarget->livein_end());
225 for (const auto &OrigLI : OrigLiveIn)
226 LayoutSucc->removeLiveIn(OrigLI.PhysReg);
227 for (const auto &NewLI : NewLiveIn)
228 LayoutSucc->addLiveIn(NewLI);
229 }
230 }
231 }
232 }
233 }
234 }
235 return true;
236}
237
238//===----------------------------------------------------------------------===//
239// Public Constructor Functions
240//===----------------------------------------------------------------------===//
241
242INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
243 false, false)
244
246 return new HexagonCFGOptimizer();
247}
MachineBasicBlock & MBB
static bool IsConditionalBranch(int Opc)
static bool IsUnconditionalJump(int Opc)
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
unsigned pred_size() const
livein_iterator livein_end() const
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
livein_iterator livein_begin() const
unsigned succ_size() const
std::vector< MachineBasicBlock * >::iterator succ_iterator
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
iterator_range< pred_iterator > predecessors()
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
void moveAfter(MachineBasicBlock *NewBefore)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:546
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:556
MachineBasicBlock * getMBB() const
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createHexagonCFGOptimizer()
void initializeHexagonCFGOptimizerPass(PassRegistry &)