LLVM  10.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 
39  int computeBlockSize(MachineBasicBlock &MBB);
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  assert(MinBlock && "Failed to find minimum offset block");
111 
112  // The ADR instruction needed to calculate the address of the first reachable
113  // basic block can address +/-1MB.
114  if (!isInt<21>(MinOffset - Offset)) {
115  ++NumJT32;
116  return false;
117  }
118 
119  int Span = MaxOffset - MinOffset;
120  auto AFI = MF->getInfo<AArch64FunctionInfo>();
121  if (isUInt<8>(Span / 4)) {
122  AFI->setJumpTableEntryInfo(JTIdx, 1, MinBlock->getSymbol());
123  MI.setDesc(TII->get(AArch64::JumpTableDest8));
124  ++NumJT8;
125  return true;
126  } else if (isUInt<16>(Span / 4)) {
127  AFI->setJumpTableEntryInfo(JTIdx, 2, MinBlock->getSymbol());
128  MI.setDesc(TII->get(AArch64::JumpTableDest16));
129  ++NumJT16;
130  return true;
131  }
132 
133  ++NumJT32;
134  return false;
135 }
136 
137 bool AArch64CompressJumpTables::runOnMachineFunction(MachineFunction &MFIn) {
138  bool Changed = false;
139  MF = &MFIn;
140 
141  const auto &ST = MF->getSubtarget<AArch64Subtarget>();
142  TII = ST.getInstrInfo();
143 
144  if (ST.force32BitJumpTables() && !MF->getFunction().hasMinSize())
145  return false;
146 
147  scanFunction();
148 
149  for (MachineBasicBlock &MBB : *MF) {
150  int Offset = BlockInfo[MBB.getNumber()];
151  for (MachineInstr &MI : MBB) {
152  Changed |= compressJumpTable(MI, Offset);
153  Offset += TII->getInstSizeInBytes(MI);
154  }
155  }
156 
157  return Changed;
158 }
159 
161  return new AArch64CompressJumpTables();
162 }
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...
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")
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:411
TargetInstrInfo - Interface to description of machine instruction set.
constexpr bool isUInt< 8 >(uint64_t x)
Definition: MathExtras.h:379
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...
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:336
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:64
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 hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:619
uint32_t Size
Definition: Profile.cpp:46
constexpr bool isUInt< 16 >(uint64_t x)
Definition: MathExtras.h:382
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:416
Properties which a MachineFunction may have at a given point in time.
FunctionPass * createAArch64CompressJumpTablesPass()
void resize(size_type N)
Definition: SmallVector.h:344