lib/Target/AArch64/AArch64CompressJumpTables.cpp

   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/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) {
  47     initializeAArch64CompressJumpTablesPass(*PassRegistry::getPassRegistry());
  48   }
  49
  50   bool runOnMachineFunction(MachineFunction &MF) override;
  51
  52   MachineFunctionProperties getRequiredProperties() const override {
  53     return MachineFunctionProperties().set(
  54         MachineFunctionProperties::Property::NoVRegs);
  55   }
  56   StringRef getPassName() const override {
  57     return "AArch64 Compress Jump Tables";
  58   }
  59 };
  60 char AArch64CompressJumpTables::ID = 0;
  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
 160 FunctionPass *llvm::createAArch64CompressJumpTablesPass() {
 161   return new AArch64CompressJumpTables();
 162 }