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; 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 }; 61 char AArch64CompressJumpTables::ID = 0; 62 } 63 64 INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE, 65 "AArch64 compress jump tables pass", false, false) 66 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 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(1)) 83 AlignedOffset = Offset; 84 else 85 AlignedOffset = alignTo(Offset, Alignment); 86 BlockInfo[MBB.getNumber()] = AlignedOffset; 87 Offset = AlignedOffset + computeBlockSize(MBB); 88 } 89 } 90 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 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 167 FunctionPass *llvm::createAArch64CompressJumpTablesPass() { 168 return new AArch64CompressJumpTables(); 169 } 170