LLVM  12.0.0git
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/Alignment.h"
24 #include "llvm/Support/Debug.h"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "aarch64-jump-tables"
29 
30 STATISTIC(NumJT8, "Number of jump-tables with 1-byte entries");
31 STATISTIC(NumJT16, "Number of jump-tables with 2-byte entries");
32 STATISTIC(NumJT32, "Number of jump-tables with 4-byte entries");
33 
34 namespace {
35 class AArch64CompressJumpTables : public MachineFunctionPass {
36  const TargetInstrInfo *TII;
37  MachineFunction *MF;
38  SmallVector<int, 8> BlockInfo;
39 
40  int computeBlockSize(MachineBasicBlock &MBB);
41  void scanFunction();
42 
43  bool compressJumpTable(MachineInstr &MI, int Offset);
44 
45 public:
46  static char ID;
47  AArch64CompressJumpTables() : MachineFunctionPass(ID) {
49  }
50 
51  bool runOnMachineFunction(MachineFunction &MF) override;
52 
53  MachineFunctionProperties getRequiredProperties() const override {
56  }
57  StringRef getPassName() const override {
58  return "AArch64 Compress Jump Tables";
59  }
60 };
62 }
63 
64 INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
65  "AArch64 compress jump tables pass", false, false)
66 
67 int AArch64CompressJumpTables::computeBlockSize(MachineBasicBlock &MBB) {
68  int Size = 0;
69  for (const MachineInstr &MI : MBB)
70  Size += TII->getInstSizeInBytes(MI);
71  return Size;
72 }
73 
74 void AArch64CompressJumpTables::scanFunction() {
75  BlockInfo.clear();
76  BlockInfo.resize(MF->getNumBlockIDs());
77 
78  unsigned Offset = 0;
79  for (MachineBasicBlock &MBB : *MF) {
80  const Align Alignment = MBB.getAlignment();
81  unsigned AlignedOffset;
82  if (Alignment == Align(1))
83  AlignedOffset = Offset;
84  else
85  AlignedOffset = alignTo(Offset, Alignment);
86  BlockInfo[MBB.getNumber()] = AlignedOffset;
87  Offset = AlignedOffset + computeBlockSize(MBB);
88  }
89 }
90 
91 bool AArch64CompressJumpTables::compressJumpTable(MachineInstr &MI,
92  int Offset) {
93  if (MI.getOpcode() != AArch64::JumpTableDest32)
94  return false;
95 
96  int JTIdx = MI.getOperand(4).getIndex();
97  auto &JTInfo = *MF->getJumpTableInfo();
98  const MachineJumpTableEntry &JT = JTInfo.getJumpTables()[JTIdx];
99 
100  // The jump-table might have been optimized away.
101  if (JT.MBBs.empty())
102  return false;
103 
104  int MaxOffset = std::numeric_limits<int>::min(),
105  MinOffset = std::numeric_limits<int>::max();
106  MachineBasicBlock *MinBlock = nullptr;
107  for (auto Block : JT.MBBs) {
108  int BlockOffset = BlockInfo[Block->getNumber()];
109  assert(BlockOffset % 4 == 0 && "misaligned basic block");
110 
111  MaxOffset = std::max(MaxOffset, BlockOffset);
112  if (BlockOffset <= MinOffset) {
113  MinOffset = BlockOffset;
114  MinBlock = Block;
115  }
116  }
117  assert(MinBlock && "Failed to find minimum offset block");
118 
119  // The ADR instruction needed to calculate the address of the first reachable
120  // basic block can address +/-1MB.
121  if (!isInt<21>(MinOffset - Offset)) {
122  ++NumJT32;
123  return false;
124  }
125 
126  int Span = MaxOffset - MinOffset;
127  auto AFI = MF->getInfo<AArch64FunctionInfo>();
128  if (isUInt<8>(Span / 4)) {
129  AFI->setJumpTableEntryInfo(JTIdx, 1, MinBlock->getSymbol());
130  MI.setDesc(TII->get(AArch64::JumpTableDest8));
131  ++NumJT8;
132  return true;
133  } else if (isUInt<16>(Span / 4)) {
134  AFI->setJumpTableEntryInfo(JTIdx, 2, MinBlock->getSymbol());
135  MI.setDesc(TII->get(AArch64::JumpTableDest16));
136  ++NumJT16;
137  return true;
138  }
139 
140  ++NumJT32;
141  return false;
142 }
143 
144 bool AArch64CompressJumpTables::runOnMachineFunction(MachineFunction &MFIn) {
145  bool Changed = false;
146  MF = &MFIn;
147 
148  const auto &ST = MF->getSubtarget<AArch64Subtarget>();
149  TII = ST.getInstrInfo();
150 
151  if (ST.force32BitJumpTables() && !MF->getFunction().hasMinSize())
152  return false;
153 
154  scanFunction();
155 
156  for (MachineBasicBlock &MBB : *MF) {
157  int Offset = BlockInfo[MBB.getNumber()];
158  for (MachineInstr &MI : MBB) {
159  Changed |= compressJumpTable(MI, Offset);
160  Offset += TII->getInstSizeInBytes(MI);
161  }
162  }
163 
164  return Changed;
165 }
166 
168  return new AArch64CompressJumpTables();
169 }
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
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")
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineBasicBlock & MBB
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:456
Align getAlignment() const
Return alignment of the basic block.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
TargetInstrInfo - Interface to description of machine instruction set.
constexpr bool isUInt< 8 >(uint64_t x)
Definition: MathExtras.h:406
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void setJumpTableEntryInfo(int Idx, unsigned Size, MCSymbol *PCRelSym)
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:305
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.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
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:350
MachineJumpTableEntry - One jump table in the jump table info.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:62
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:158
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:62
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:644
uint32_t Size
Definition: Profile.cpp:46
constexpr bool isUInt< 16 >(uint64_t x)
Definition: MathExtras.h:409
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:57
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
Properties which a MachineFunction may have at a given point in time.
FunctionPass * createAArch64CompressJumpTablesPass()
void resize(size_type N)
Definition: SmallVector.h:390