blob: 2328a8b4deb8248201b16f36298e64d61d2ec927 [file] [log] [blame]
//==-- AArch64CompressJumpTables.cpp - Compress jump tables for AArch64 --====//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
// This pass looks at the basic blocks each jump-table refers to and works out
// whether they can be emitted in a compressed form (with 8 or 16-bit
// entries). If so, it changes the opcode and flags them in the associated
// AArch64FunctionInfo.
//
//===----------------------------------------------------------------------===//
#include "AArch64.h"
#include "AArch64MachineFunctionInfo.h"
#include "AArch64Subtarget.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/MC/MCContext.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/Debug.h"
using namespace llvm;
#define DEBUG_TYPE "aarch64-jump-tables"
STATISTIC(NumJT8, "Number of jump-tables with 1-byte entries");
STATISTIC(NumJT16, "Number of jump-tables with 2-byte entries");
STATISTIC(NumJT32, "Number of jump-tables with 4-byte entries");
namespace {
class AArch64CompressJumpTables : public MachineFunctionPass {
const TargetInstrInfo *TII;
MachineFunction *MF;
SmallVector<int, 8> BlockInfo;
/// Returns the size in instructions of the block \p MBB, or None if we
/// couldn't get a safe upper bound.
Optional<int> computeBlockSize(MachineBasicBlock &MBB);
/// Gather information about the function, returns false if we can't perform
/// this optimization for some reason.
bool scanFunction();
bool compressJumpTable(MachineInstr &MI, int Offset);
public:
static char ID;
AArch64CompressJumpTables() : MachineFunctionPass(ID) {
initializeAArch64CompressJumpTablesPass(*PassRegistry::getPassRegistry());
}
bool runOnMachineFunction(MachineFunction &MF) override;
MachineFunctionProperties getRequiredProperties() const override {
return MachineFunctionProperties().set(
MachineFunctionProperties::Property::NoVRegs);
}
StringRef getPassName() const override {
return "AArch64 Compress Jump Tables";
}
};
char AArch64CompressJumpTables::ID = 0;
} // namespace
INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE,
"AArch64 compress jump tables pass", false, false)
Optional<int>
AArch64CompressJumpTables::computeBlockSize(MachineBasicBlock &MBB) {
int Size = 0;
for (const MachineInstr &MI : MBB) {
// Inline asm may contain some directives like .bytes which we don't
// currently have the ability to parse accurately. To be safe, just avoid
// computing a size and bail out.
if (MI.getOpcode() == AArch64::INLINEASM ||
MI.getOpcode() == AArch64::INLINEASM_BR)
return None;
Size += TII->getInstSizeInBytes(MI);
}
return Size;
}
bool AArch64CompressJumpTables::scanFunction() {
BlockInfo.clear();
BlockInfo.resize(MF->getNumBlockIDs());
unsigned Offset = 0;
for (MachineBasicBlock &MBB : *MF) {
const Align Alignment = MBB.getAlignment();
unsigned AlignedOffset;
if (Alignment == Align(1))
AlignedOffset = Offset;
else
AlignedOffset = alignTo(Offset, Alignment);
BlockInfo[MBB.getNumber()] = AlignedOffset;
auto BlockSize = computeBlockSize(MBB);
if (!BlockSize)
return false;
Offset = AlignedOffset + *BlockSize;
}
return true;
}
bool AArch64CompressJumpTables::compressJumpTable(MachineInstr &MI,
int Offset) {
if (MI.getOpcode() != AArch64::JumpTableDest32)
return false;
int JTIdx = MI.getOperand(4).getIndex();
auto &JTInfo = *MF->getJumpTableInfo();
const MachineJumpTableEntry &JT = JTInfo.getJumpTables()[JTIdx];
// The jump-table might have been optimized away.
if (JT.MBBs.empty())
return false;
int MaxOffset = std::numeric_limits<int>::min(),
MinOffset = std::numeric_limits<int>::max();
MachineBasicBlock *MinBlock = nullptr;
for (auto *Block : JT.MBBs) {
int BlockOffset = BlockInfo[Block->getNumber()];
assert(BlockOffset % 4 == 0 && "misaligned basic block");
MaxOffset = std::max(MaxOffset, BlockOffset);
if (BlockOffset <= MinOffset) {
MinOffset = BlockOffset;
MinBlock = Block;
}
}
assert(MinBlock && "Failed to find minimum offset block");
// The ADR instruction needed to calculate the address of the first reachable
// basic block can address +/-1MB.
if (!isInt<21>(MinOffset - Offset)) {
++NumJT32;
return false;
}
int Span = MaxOffset - MinOffset;
auto *AFI = MF->getInfo<AArch64FunctionInfo>();
if (isUInt<8>(Span / 4)) {
AFI->setJumpTableEntryInfo(JTIdx, 1, MinBlock->getSymbol());
MI.setDesc(TII->get(AArch64::JumpTableDest8));
++NumJT8;
return true;
}
if (isUInt<16>(Span / 4)) {
AFI->setJumpTableEntryInfo(JTIdx, 2, MinBlock->getSymbol());
MI.setDesc(TII->get(AArch64::JumpTableDest16));
++NumJT16;
return true;
}
++NumJT32;
return false;
}
bool AArch64CompressJumpTables::runOnMachineFunction(MachineFunction &MFIn) {
bool Changed = false;
MF = &MFIn;
const auto &ST = MF->getSubtarget<AArch64Subtarget>();
TII = ST.getInstrInfo();
if (ST.force32BitJumpTables() && !MF->getFunction().hasMinSize())
return false;
if (!scanFunction())
return false;
for (MachineBasicBlock &MBB : *MF) {
int Offset = BlockInfo[MBB.getNumber()];
for (MachineInstr &MI : MBB) {
Changed |= compressJumpTable(MI, Offset);
Offset += TII->getInstSizeInBytes(MI);
}
}
return Changed;
}
FunctionPass *llvm::createAArch64CompressJumpTablesPass() {
return new AArch64CompressJumpTables();
}