LLVM  9.0.0svn
AArch64CompressJumpTables.cpp
Go to the documentation of this file.
1 //==-- AArch64CompressJumpTables.cpp - Compress jump tables for AArch64 --====//
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 // This pass looks at the basic blocks each jump-table refers to and works out
8 // whether they can be emitted in a compressed form (with 8 or 16-bit
9 // entries). If so, it changes the opcode and flags them in the associated
10 // AArch64FunctionInfo.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "AArch64.h"
16 #include "AArch64Subtarget.h"
17 #include "llvm/ADT/Statistic.h"
22 #include "llvm/MC/MCContext.h"
23 #include "llvm/Support/Debug.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "aarch64-jump-tables"
28 
29 STATISTIC(NumJT8, "Number of jump-tables with 1-byte entries");
30 STATISTIC(NumJT16, "Number of jump-tables with 2-byte entries");
31 STATISTIC(NumJT32, "Number of jump-tables with 4-byte entries");
32 
33 namespace {
34 class AArch64CompressJumpTables : public MachineFunctionPass {
35  const TargetInstrInfo *TII;
36  MachineFunction *MF;
37  SmallVector<int, 8> BlockInfo;
38 
40  void scanFunction();
41 
42  bool compressJumpTable(MachineInstr &MI, int Offset);
43 
44 public:
45  static char ID;
46  AArch64CompressJumpTables() : MachineFunctionPass(ID) {
48  }
49 
50  bool runOnMachineFunction(MachineFunction &MF) override;
51 
52  MachineFunctionProperties getRequiredProperties() const override {
55  }
56  StringRef getPassName() const override {
57  return "AArch64 Compress Jump Tables";
58  }
59 };
61 }
62 
63 INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
64  "AArch64 compress jump tables pass", false, false)
65 
66 int AArch64CompressJumpTables::computeBlockSize(MachineBasicBlock &MBB) {
67  int Size = 0;
68  for (const MachineInstr &MI : MBB)
69  Size += TII->getInstSizeInBytes(MI);
70  return Size;
71 }
72 
73 void AArch64CompressJumpTables::scanFunction() {
74  BlockInfo.clear();
75  BlockInfo.resize(MF->getNumBlockIDs());
76 
77  int Offset = 0;
78  for (MachineBasicBlock &MBB : *MF) {
79  BlockInfo[MBB.getNumber()] = Offset;
80  Offset += computeBlockSize(MBB);
81  }
82 }
83 
84 bool AArch64CompressJumpTables::compressJumpTable(MachineInstr &MI,
85  int Offset) {
86  if (MI.getOpcode() != AArch64::JumpTableDest32)
87  return false;
88 
89  int JTIdx = MI.getOperand(4).getIndex();
90  auto &JTInfo = *MF->getJumpTableInfo();
91  const MachineJumpTableEntry &JT = JTInfo.getJumpTables()[JTIdx];
92 
93  // The jump-table might have been optimized away.
94  if (JT.MBBs.empty())
95  return false;
96 
97  int MaxOffset = std::numeric_limits<int>::min(),
98  MinOffset = std::numeric_limits<int>::max();
99  MachineBasicBlock *MinBlock = nullptr;
100  for (auto Block : JT.MBBs) {
101  int BlockOffset = BlockInfo[Block->getNumber()];
102  assert(BlockOffset % 4 == 0 && "misaligned basic block");
103 
104  MaxOffset = std::max(MaxOffset, BlockOffset);
105  if (BlockOffset <= MinOffset) {
106  MinOffset = BlockOffset;
107  MinBlock = Block;
108  }
109  }
110 
111  // The ADR instruction needed to calculate the address of the first reachable
112  // basic block can address +/-1MB.
113  if (!isInt<21>(MinOffset - Offset)) {
114  ++NumJT32;
115  return false;
116  }
117 
118  int Span = MaxOffset - MinOffset;
119  auto AFI = MF->getInfo<AArch64FunctionInfo>();
120  if (isUInt<8>(Span / 4)) {
121  AFI->setJumpTableEntryInfo(JTIdx, 1, MinBlock->getSymbol());
122  MI.setDesc(TII->get(AArch64::JumpTableDest8));
123  ++NumJT8;
124  return true;
125  } else if (isUInt<16>(Span / 4)) {
126  AFI->setJumpTableEntryInfo(JTIdx, 2, MinBlock->getSymbol());
127  MI.setDesc(TII->get(AArch64::JumpTableDest16));
128  ++NumJT16;
129  return true;
130  }
131 
132  ++NumJT32;
133  return false;
134 }
135 
136 bool AArch64CompressJumpTables::runOnMachineFunction(MachineFunction &MFIn) {
137  bool Changed = false;
138  MF = &MFIn;
139 
140  const auto &ST = MF->getSubtarget<AArch64Subtarget>();
141  TII = ST.getInstrInfo();
142 
143  if (ST.force32BitJumpTables() && !MF->getFunction().optForMinSize())
144  return false;
145 
146  scanFunction();
147 
148  for (MachineBasicBlock &MBB : *MF) {
149  int Offset = BlockInfo[MBB.getNumber()];
150  for (MachineInstr &MI : MBB) {
151  Changed |= compressJumpTable(MI, Offset);
152  Offset += TII->getInstSizeInBytes(MI);
153  }
154  }
155 
156  return Changed;
157 }
158 
160  return new AArch64CompressJumpTables();
161 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AArch64FunctionInfo - This class is derived from MachineFunctionInfo and contains private AArch64-spe...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
#define DEBUG_TYPE
STATISTIC(NumFunctions, "Total number of functions")
void computeBlockSize(MachineFunction *MF, MachineBasicBlock *MBB, BasicBlockInfo &BBI)
virtual unsigned getInstSizeInBytes(const MachineInstr &MI) const
Returns the size in bytes of the specified MachineInstr, or ~0U when this function is not implemented...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
TargetInstrInfo - Interface to description of machine instruction set.
constexpr bool isUInt< 8 >(uint64_t x)
Definition: MathExtras.h:342
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void setJumpTableEntryInfo(int Idx, unsigned Size, MCSymbol *PCRelSym)
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
std::vector< MachineBasicBlock * > MBBs
MBBs - The vector of basic blocks from which to create the jump table.
INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE, "AArch64 compress jump tables pass", false, false) int AArch64CompressJumpTables
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
MachineJumpTableEntry - One jump table in the jump table info.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
bool optForMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:594
uint32_t Size
Definition: Profile.cpp:46
constexpr bool isUInt< 16 >(uint64_t x)
Definition: MathExtras.h:345
void initializeAArch64CompressJumpTablesPass(PassRegistry &)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
Properties which a MachineFunction may have at a given point in time.
FunctionPass * createAArch64CompressJumpTablesPass()
void resize(size_type N)
Definition: SmallVector.h:344