AArch64CompressJumpTables.cpp revision 360784 
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
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;
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
45public:
46  static char ID;
47  AArch64CompressJumpTables() : MachineFunctionPass(ID) {
48    initializeAArch64CompressJumpTablesPass(*PassRegistry::getPassRegistry());
49  }
50
51  bool runOnMachineFunction(MachineFunction &MF) override;
52
53  MachineFunctionProperties getRequiredProperties() const override {
54    return MachineFunctionProperties().set(
55        MachineFunctionProperties::Property::NoVRegs);
56  }
57  StringRef getPassName() const override {
58    return "AArch64 Compress Jump Tables";
59  }
60};
61char AArch64CompressJumpTables::ID = 0;
62}
63
64INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
65                "AArch64 compress jump tables pass", false, false)
66
67int AArch64CompressJumpTables::computeBlockSize(MachineBasicBlock &MBB) {
68  int Size = 0;
69  for (const MachineInstr &MI : MBB)
70    Size += TII->getInstSizeInBytes(MI);
71  return Size;
72}
73
74void 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
91bool 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
144bool 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
167FunctionPass *llvm::createAArch64CompressJumpTablesPass() {
168  return new AArch64CompressJumpTables();
169}
170