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