LLVM 17.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"
24#include "llvm/Support/Debug.h"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "aarch64-jump-tables"
29
30STATISTIC(NumJT8, "Number of jump-tables with 1-byte entries");
31STATISTIC(NumJT16, "Number of jump-tables with 2-byte entries");
32STATISTIC(NumJT32, "Number of jump-tables with 4-byte entries");
33
34namespace {
35class AArch64CompressJumpTables : public MachineFunctionPass {
36 const TargetInstrInfo *TII;
38 SmallVector<int, 8> BlockInfo;
39
40 /// Returns the size in instructions of the block \p MBB, or std::nullopt if
41 /// we couldn't get a safe upper bound.
42 std::optional<int> computeBlockSize(MachineBasicBlock &MBB);
43
44 /// Gather information about the function, returns false if we can't perform
45 /// this optimization for some reason.
46 bool scanFunction();
47
48 bool compressJumpTable(MachineInstr &MI, int Offset);
49
50public:
51 static char ID;
52 AArch64CompressJumpTables() : MachineFunctionPass(ID) {
54 }
55
56 bool runOnMachineFunction(MachineFunction &MF) override;
57
60 MachineFunctionProperties::Property::NoVRegs);
61 }
62 StringRef getPassName() const override {
63 return "AArch64 Compress Jump Tables";
64 }
65};
66char AArch64CompressJumpTables::ID = 0;
67} // namespace
68
69INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
70 "AArch64 compress jump tables pass", false, false)
71
72std::optional<int>
73AArch64CompressJumpTables::computeBlockSize(MachineBasicBlock &MBB) {
74 int Size = 0;
75 for (const MachineInstr &MI : MBB) {
76 // Inline asm may contain some directives like .bytes which we don't
77 // currently have the ability to parse accurately. To be safe, just avoid
78 // computing a size and bail out.
79 if (MI.getOpcode() == AArch64::INLINEASM ||
80 MI.getOpcode() == AArch64::INLINEASM_BR)
81 return std::nullopt;
82 Size += TII->getInstSizeInBytes(MI);
83 }
84 return Size;
85}
86
87bool AArch64CompressJumpTables::scanFunction() {
88 BlockInfo.clear();
89 BlockInfo.resize(MF->getNumBlockIDs());
90
91 unsigned Offset = 0;
92 for (MachineBasicBlock &MBB : *MF) {
93 const Align Alignment = MBB.getAlignment();
94 unsigned AlignedOffset;
95 if (Alignment == Align(1))
96 AlignedOffset = Offset;
97 else
98 AlignedOffset = alignTo(Offset, Alignment);
99 BlockInfo[MBB.getNumber()] = AlignedOffset;
100 auto BlockSize = computeBlockSize(MBB);
101 if (!BlockSize)
102 return false;
103 Offset = AlignedOffset + *BlockSize;
104 }
105 return true;
106}
107
108bool AArch64CompressJumpTables::compressJumpTable(MachineInstr &MI,
109 int Offset) {
110 if (MI.getOpcode() != AArch64::JumpTableDest32)
111 return false;
112
113 int JTIdx = MI.getOperand(4).getIndex();
114 auto &JTInfo = *MF->getJumpTableInfo();
115 const MachineJumpTableEntry &JT = JTInfo.getJumpTables()[JTIdx];
116
117 // The jump-table might have been optimized away.
118 if (JT.MBBs.empty())
119 return false;
120
121 int MaxOffset = std::numeric_limits<int>::min(),
122 MinOffset = std::numeric_limits<int>::max();
123 MachineBasicBlock *MinBlock = nullptr;
124 for (auto *Block : JT.MBBs) {
125 int BlockOffset = BlockInfo[Block->getNumber()];
126 assert(BlockOffset % 4 == 0 && "misaligned basic block");
127
128 MaxOffset = std::max(MaxOffset, BlockOffset);
129 if (BlockOffset <= MinOffset) {
130 MinOffset = BlockOffset;
131 MinBlock = Block;
132 }
133 }
134 assert(MinBlock && "Failed to find minimum offset block");
135
136 // The ADR instruction needed to calculate the address of the first reachable
137 // basic block can address +/-1MB.
138 if (!isInt<21>(MinOffset - Offset)) {
139 ++NumJT32;
140 return false;
141 }
142
143 int Span = MaxOffset - MinOffset;
144 auto *AFI = MF->getInfo<AArch64FunctionInfo>();
145 if (isUInt<8>(Span / 4)) {
146 AFI->setJumpTableEntryInfo(JTIdx, 1, MinBlock->getSymbol());
147 MI.setDesc(TII->get(AArch64::JumpTableDest8));
148 ++NumJT8;
149 return true;
150 }
151 if (isUInt<16>(Span / 4)) {
152 AFI->setJumpTableEntryInfo(JTIdx, 2, MinBlock->getSymbol());
153 MI.setDesc(TII->get(AArch64::JumpTableDest16));
154 ++NumJT16;
155 return true;
156 }
157
158 ++NumJT32;
159 return false;
160}
161
162bool AArch64CompressJumpTables::runOnMachineFunction(MachineFunction &MFIn) {
163 bool Changed = false;
164 MF = &MFIn;
165
166 const auto &ST = MF->getSubtarget<AArch64Subtarget>();
167 TII = ST.getInstrInfo();
168
169 if (ST.force32BitJumpTables() && !MF->getFunction().hasMinSize())
170 return false;
171
172 if (!scanFunction())
173 return false;
174
175 for (MachineBasicBlock &MBB : *MF) {
176 int Offset = BlockInfo[MBB.getNumber()];
177 for (MachineInstr &MI : MBB) {
178 Changed |= compressJumpTable(MI, Offset);
179 Offset += TII->getInstSizeInBytes(MI);
180 }
181 }
182
183 return Changed;
184}
185
187 return new AArch64CompressJumpTables();
188}
#define DEBUG_TYPE
MachineBasicBlock & MBB
uint64_t Size
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static const int BlockSize
Definition: TarWriter.cpp:33
AArch64FunctionInfo - This class is derived from MachineFunctionInfo and contains private AArch64-spe...
void setJumpTableEntryInfo(int Idx, unsigned Size, MCSymbol *PCRelSym)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Align getAlignment() const
Return alignment of the basic block.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:68
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
void resize(size_type N)
Definition: SmallVector.h:642
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
FunctionPass * createAArch64CompressJumpTablesPass()
void initializeAArch64CompressJumpTablesPass(PassRegistry &)
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
Definition: BitVector.h:851
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
MachineJumpTableEntry - One jump table in the jump table info.