LLVM  13.0.0git
ARMBlockPlacement.cpp
Go to the documentation of this file.
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"
22 
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "arm-block-placement"
26 #define DEBUG_PREFIX "ARM Block Placement: "
27 
28 namespace llvm {
30 private:
31  const ARMBaseInstrInfo *TII;
32  std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
33  MachineLoopInfo *MLI = nullptr;
34 
35 public:
36  static char ID;
38 
39  bool runOnMachineFunction(MachineFunction &MF) override;
42  bool fixBackwardsWLS(MachineLoop *ML);
44 
45  void getAnalysisUsage(AnalysisUsage &AU) const override {
46  AU.setPreservesCFG();
49  }
50 };
51 
52 } // namespace llvm
53 
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 
63 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
64  for (auto &Terminator : MBB->terminators()) {
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.
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.
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()) {
123  continue;
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
145  bool Changed = false;
146  for (auto *InnerML : *ML)
147  Changed |= processPostOrderLoops(InnerML);
148  return Changed | fixBackwardsWLS(ML);
149 }
150 
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 
174  MachineBasicBlock *Other) {
175  return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
176 }
177 
178 // Moves a BasicBlock before another, without changing the control flow
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);
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 }
ARMSubtarget.h
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:316
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:250
llvm::ARMBlockPlacement::fixBackwardsWLS
bool fixBackwardsWLS(MachineLoop *ML)
Checks if loop has a backwards branching WLS, and if possible, fixes it.
Definition: ARMBlockPlacement.cpp:91
llvm::ARMSubtarget
Definition: ARMSubtarget.h:46
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:195
llvm::FunctionPass::skipFunction
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:163
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::ARMBlockPlacement::processPostOrderLoops
bool processPostOrderLoops(MachineLoop *ML)
Updates ordering (of WLS BB and their loopExits) in inner loops first Returns true if any change was ...
Definition: ARMBlockPlacement.cpp:144
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:288
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::ARMBlockPlacement
Definition: ARMBlockPlacement.cpp:29
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:328
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:816
MachineLoopInfo.h
llvm::MachineInstrBuilder::addMBB
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:146
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:908
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
MVETailPredUtils.h
llvm::ARMBlockPlacement::ARMBlockPlacement
ARMBlockPlacement()
Definition: ARMBlockPlacement.cpp:37
llvm::createARMBlockPlacementPass
FunctionPass * createARMBlockPlacementPass()
Definition: ARMBlockPlacement.cpp:54
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:622
llvm::ARMBlockPlacement::ID
static char ID
Definition: ARMBlockPlacement.cpp:36
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
findWLS
static MachineInstr * findWLS(MachineLoop *ML)
Find WhileLoopStart in the loop predecessor BB or otherwise in its only predecessor.
Definition: ARMBlockPlacement.cpp:73
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::ARMBlockPlacement::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: ARMBlockPlacement.cpp:45
llvm::ARMBaseInstrInfo
Definition: ARMBaseInstrInfo.h:37
MachineFunctionPass.h
llvm::ARMBlockPlacement::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: ARMBlockPlacement.cpp:151
INITIALIZE_PASS
INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false, false) static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB)
Definition: ARMBlockPlacement.cpp:60
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:541
llvm::ilist_node_with_parent::getPrevNode
NodeTy * getPrevNode()
Definition: ilist_node.h:274
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ARMBaseInstrInfo.h
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
ARM.h
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::MachineBasicBlock::getFullName
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
Definition: MachineBasicBlock.cpp:322
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::isWhileLoopStart
static bool isWhileLoopStart(const MachineInstr &MI)
Definition: MVETailPredUtils.h:76
ARMBasicBlockInfo.h
llvm::getWhileLoopStartTargetBB
MachineBasicBlock * getWhileLoopStartTargetBB(const MachineInstr &MI)
Definition: MVETailPredUtils.h:87
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
llvm::MachineInstrBuilder::getInstr
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
Definition: MachineInstrBuilder.h:89
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:588
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ARMBlockPlacement.cpp:25
llvm::ARMBlockPlacement::blockIsBefore
bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other)
Definition: ARMBlockPlacement.cpp:173
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::ARMBlockPlacement::moveBasicBlock
void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before)
Definition: ARMBlockPlacement.cpp:179
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
DEBUG_PREFIX
#define DEBUG_PREFIX
Definition: ARMBlockPlacement.cpp:26
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:155
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:314
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:294
llvm::ARMBasicBlockUtils
Definition: ARMBasicBlockInfo.h:109
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172