1 //===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===//
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 // This pass re-arranges machine basic blocks to suit target requirements.
10 // Currently it only moves blocks to fix backwards WLS branches.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ARM.h"
15 #include "ARMBaseInstrInfo.h"
16 #include "ARMBasicBlockInfo.h"
17 #include "ARMSubtarget.h"
18 #include "MVETailPredUtils.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineLoopInfo.h"
22
23 using namespace llvm;
24
25 #define DEBUG_TYPE "arm-block-placement"
26 #define DEBUG_PREFIX "ARM Block Placement: "
27
28 namespace llvm {
29 class ARMBlockPlacement : public MachineFunctionPass {
30 private:
31 const ARMBaseInstrInfo *TII;
32 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
33 MachineLoopInfo *MLI = nullptr;
34
35 public:
36 static char ID;
ARMBlockPlacement()37 ARMBlockPlacement() : MachineFunctionPass(ID) {}
38
39 bool runOnMachineFunction(MachineFunction &MF) override;
40 void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before);
41 bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
42 bool fixBackwardsWLS(MachineLoop *ML);
43 bool processPostOrderLoops(MachineLoop *ML);
44
getAnalysisUsage(AnalysisUsage & AU) const45 void getAnalysisUsage(AnalysisUsage &AU) const override {
46 AU.setPreservesCFG();
47 AU.addRequired<MachineLoopInfo>();
48 MachineFunctionPass::getAnalysisUsage(AU);
49 }
50 };
51
52 } // namespace llvm
53
createARMBlockPlacementPass()54 FunctionPass *llvm::createARMBlockPlacementPass() {
55 return new ARMBlockPlacement();
56 }
57
58 char ARMBlockPlacement::ID = 0;
59
60 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
61 false)
62
findWLSInBlock(MachineBasicBlock * MBB)63 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
64 for (auto &Terminator : MBB->terminators()) {
65 if (isWhileLoopStart(Terminator))
66 return &Terminator;
67 }
68 return nullptr;
69 }
70
71 /// Find WhileLoopStart in the loop predecessor BB or otherwise in its only
72 /// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair.
findWLS(MachineLoop * ML)73 static MachineInstr *findWLS(MachineLoop *ML) {
74 MachineBasicBlock *Predecessor = ML->getLoopPredecessor();
75 if (!Predecessor)
76 return nullptr;
77 MachineInstr *WlsInstr = findWLSInBlock(Predecessor);
78 if (WlsInstr)
79 return WlsInstr;
80 if (Predecessor->pred_size() == 1)
81 return findWLSInBlock(*Predecessor->pred_begin());
82 return nullptr;
83 }
84
85 /// Checks if loop has a backwards branching WLS, and if possible, fixes it.
86 /// This requires checking the predecessor (ie. preheader or it's predecessor)
87 /// for a WLS and if its loopExit/target is before it.
88 /// If moving the predecessor won't convert a WLS (to the predecessor) from
89 /// a forward to a backward branching WLS, then move the predecessor block
90 /// to before the loopExit/target.
fixBackwardsWLS(MachineLoop * ML)91 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) {
92 MachineInstr *WlsInstr = findWLS(ML);
93 if (!WlsInstr)
94 return false;
95
96 MachineBasicBlock *Predecessor = WlsInstr->getParent();
97 MachineBasicBlock *LoopExit = getWhileLoopStartTargetBB(*WlsInstr);
98
99 // We don't want to move Preheader to before the function's entry block.
100 if (!LoopExit->getPrevNode())
101 return false;
102 if (blockIsBefore(Predecessor, LoopExit))
103 return false;
104 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
105 << Predecessor->getFullName() << " to "
106 << LoopExit->getFullName() << "\n");
107
108 // Make sure no forward branching WLSs to the Predecessor become backwards
109 // branching. An example loop structure where the Predecessor can't be moved,
110 // since bb2's WLS will become forwards once bb3 is moved before/above bb1.
111 //
112 // bb1: - LoopExit
113 // bb2:
114 // WLS bb3
115 // bb3: - Predecessor
116 // WLS bb1
117 // bb4: - Header
118 for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
119 ++It) {
120 MachineBasicBlock *MBB = &*It;
121 for (auto &Terminator : MBB->terminators()) {
122 if (!isWhileLoopStart(Terminator))
123 continue;
124 MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator);
125 // TODO: Analyse the blocks to make a decision if it would be worth
126 // moving Preheader even if we'd introduce a backwards WLS
127 if (WLSTarget == Predecessor) {
128 LLVM_DEBUG(
129 dbgs() << DEBUG_PREFIX
130 << "Can't move Predecessor"
131 "block as it would convert a WLS from forward to a "
132 "backwards branching WLS\n");
133 return false;
134 }
135 }
136 }
137
138 moveBasicBlock(Predecessor, LoopExit);
139 return true;
140 }
141
142 /// Updates ordering (of WLS BB and their loopExits) in inner loops first
143 /// Returns true if any change was made in any of the loops
processPostOrderLoops(MachineLoop * ML)144 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
145 bool Changed = false;
146 for (auto *InnerML : *ML)
147 Changed |= processPostOrderLoops(InnerML);
148 return Changed | fixBackwardsWLS(ML);
149 }
150
runOnMachineFunction(MachineFunction & MF)151 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
152 if (skipFunction(MF.getFunction()))
153 return false;
154 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
155 if (!ST.hasLOB())
156 return false;
157 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
158 MLI = &getAnalysis<MachineLoopInfo>();
159 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
160 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
161 MF.RenumberBlocks();
162 BBUtils->computeAllBlockSizes();
163 BBUtils->adjustBBOffsetsAfter(&MF.front());
164 bool Changed = false;
165
166 // Find loops with a backwards branching WLS and fix if possible.
167 for (auto *ML : *MLI)
168 Changed |= processPostOrderLoops(ML);
169
170 return Changed;
171 }
172
blockIsBefore(MachineBasicBlock * BB,MachineBasicBlock * Other)173 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
174 MachineBasicBlock *Other) {
175 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
176 }
177
178 // Moves a BasicBlock before another, without changing the control flow
moveBasicBlock(MachineBasicBlock * BB,MachineBasicBlock * Before)179 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
180 MachineBasicBlock *Before) {
181 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before "
182 << Before->getName() << "\n");
183 MachineBasicBlock *BBPrevious = BB->getPrevNode();
184 assert(BBPrevious && "Cannot move the function entry basic block");
185 MachineBasicBlock *BBNext = BB->getNextNode();
186
187 MachineBasicBlock *BeforePrev = Before->getPrevNode();
188 assert(BeforePrev &&
189 "Cannot move the given block to before the function entry block");
190 MachineFunction *F = BB->getParent();
191 BB->moveBefore(Before);
192
193 // Since only the blocks are to be moved around (but the control flow must
194 // not change), if there were any fall-throughs (to/from adjacent blocks),
195 // replace with unconditional branch to the fall through block.
196 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
197 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
198 << From->getName() << " to " << To->getName() << "\n");
199 assert(From->isSuccessor(To) &&
200 "'To' is expected to be a successor of 'From'");
201 MachineInstr &Terminator = *(--From->terminators().end());
202 if (!Terminator.isUnconditionalBranch()) {
203 // The BB doesn't have an unconditional branch so it relied on
204 // fall-through. Fix by adding an unconditional branch to the moved BB.
205 MachineInstrBuilder MIB =
206 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
207 MIB.addMBB(To);
208 MIB.addImm(ARMCC::CondCodes::AL);
209 MIB.addReg(ARM::NoRegister);
210 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
211 << From->getName() << " to " << To->getName() << ": "
212 << *MIB.getInstr());
213 }
214 };
215
216 // Fix fall-through to the moved BB from the one that used to be before it.
217 if (BBPrevious->isSuccessor(BB))
218 FixFallthrough(BBPrevious, BB);
219 // Fix fall through from the destination BB to the one that used to before it.
220 if (BeforePrev->isSuccessor(Before))
221 FixFallthrough(BeforePrev, Before);
222 // Fix fall through from the moved BB to the one that used to follow.
223 if (BBNext && BB->isSuccessor(BBNext))
224 FixFallthrough(BB, BBNext);
225
226 F->RenumberBlocks();
227 BBUtils->computeAllBlockSizes();
228 BBUtils->adjustBBOffsetsAfter(&F->front());
229 }
230