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"
15 #include "AArch64MachineFunctionInfo.h"
16 #include "AArch64Subtarget.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineJumpTableInfo.h"
20 #include "llvm/CodeGen/TargetInstrInfo.h"
21 #include "llvm/CodeGen/TargetSubtargetInfo.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;
AArch64CompressJumpTables()47 AArch64CompressJumpTables() : MachineFunctionPass(ID) {
48 initializeAArch64CompressJumpTablesPass(*PassRegistry::getPassRegistry());
49 }
50
51 bool runOnMachineFunction(MachineFunction &MF) override;
52
getRequiredProperties() const53 MachineFunctionProperties getRequiredProperties() const override {
54 return MachineFunctionProperties().set(
55 MachineFunctionProperties::Property::NoVRegs);
56 }
getPassName() const57 StringRef getPassName() const override {
58 return "AArch64 Compress Jump Tables";
59 }
60 };
61 char AArch64CompressJumpTables::ID = 0;
62 }
63
64 INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
65 "AArch64 compress jump tables pass", false, false)
66
computeBlockSize(MachineBasicBlock & MBB)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
scanFunction()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::None())
83 AlignedOffset = Offset;
84 else
85 AlignedOffset = alignTo(Offset, Alignment);
86 BlockInfo[MBB.getNumber()] = AlignedOffset;
87 Offset = AlignedOffset + computeBlockSize(MBB);
88 }
89 }
90
compressJumpTable(MachineInstr & MI,int Offset)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
runOnMachineFunction(MachineFunction & MFIn)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
createAArch64CompressJumpTablesPass()167 FunctionPass *llvm::createAArch64CompressJumpTablesPass() {
168 return new AArch64CompressJumpTables();
169 }
170