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 } 163