LLVM  8.0.0svn
AArch64CompressJumpTables.cpp
Go to the documentation of this file.
1 //==-- AArch64CompressJumpTables.cpp - Compress jump tables for AArch64 --====//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 // This pass looks at the basic blocks each jump-table refers to and works out
9 // whether they can be emitted in a compressed form (with 8 or 16-bit
10 // entries). If so, it changes the opcode and flags them in the associated
11 // AArch64FunctionInfo.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "AArch64.h"
17 #include "AArch64Subtarget.h"
18 #include "llvm/ADT/Statistic.h"
23 #include "llvm/MC/MCContext.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 
41  void scanFunction();
42 
43  bool compressJumpTable(MachineInstr &MI, int Offset);
44 
45 public:
46  static char ID;
47  AArch64CompressJumpTables() : MachineFunctionPass(ID) {
49  }
50 
51  bool runOnMachineFunction(MachineFunction &MF) override;
52 
53  MachineFunctionProperties getRequiredProperties() const override {
56  }
57  StringRef getPassName() const override {
58  return "AArch64 Compress Jump Tables";
59  }
60 };
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  int Offset = 0;
79  for (MachineBasicBlock &MBB : *MF) {
80  BlockInfo[MBB.getNumber()] = Offset;
81  Offset += computeBlockSize(MBB);
82  }
83 }
84 
85 bool AArch64CompressJumpTables::compressJumpTable(MachineInstr &MI,
86  int Offset) {
87  if (MI.getOpcode() != AArch64::JumpTableDest32)
88  return false;
89 
90  int JTIdx = MI.getOperand(4).getIndex();
91  auto &JTInfo = *MF->getJumpTableInfo();
92  const MachineJumpTableEntry &JT = JTInfo.getJumpTables()[JTIdx];
93 
94  // The jump-table might have been optimized away.
95  if (JT.MBBs.empty())
96  return false;
97 
98  int MaxOffset = std::numeric_limits<int>::min(),
99  MinOffset = std::numeric_limits<int>::max();
100  MachineBasicBlock *MinBlock = nullptr;
101  for (auto Block : JT.MBBs) {
102  int BlockOffset = BlockInfo[Block->getNumber()];
103  assert(BlockOffset % 4 == 0 && "misaligned basic block");
104 
105  MaxOffset = std::max(MaxOffset, BlockOffset);
106  if (BlockOffset <= MinOffset) {
107  MinOffset = BlockOffset;
108  MinBlock = Block;
109  }
110  }
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().optForMinSize())
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 
161  return new AArch64CompressJumpTables();
162 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AArch64FunctionInfo - This class is derived from MachineFunctionInfo and contains private AArch64-spe...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:24
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
#define DEBUG_TYPE
STATISTIC(NumFunctions, "Total number of functions")
void computeBlockSize(MachineFunction *MF, MachineBasicBlock *MBB, BasicBlockInfo &BBI)
virtual unsigned getInstSizeInBytes(const MachineInstr &MI) const
Returns the size in bytes of the specified MachineInstr, or ~0U when this function is not implemented...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
TargetInstrInfo - Interface to description of machine instruction set.
constexpr bool isUInt< 8 >(uint64_t x)
Definition: MathExtras.h:343
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void setJumpTableEntryInfo(int Idx, unsigned Size, MCSymbol *PCRelSym)
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
std::vector< MachineBasicBlock * > MBBs
MBBs - The vector of basic blocks from which to create the jump table.
INITIALIZE_PASS(AArch64CompressJumpTables, DEBUG_TYPE, "AArch64 compress jump tables pass", false, false) int AArch64CompressJumpTables
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
MachineJumpTableEntry - One jump table in the jump table info.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
bool optForMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:595
uint32_t Size
Definition: Profile.cpp:47
constexpr bool isUInt< 16 >(uint64_t x)
Definition: MathExtras.h:346
void initializeAArch64CompressJumpTablesPass(PassRegistry &)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
Properties which a MachineFunction may have at a given point in time.
FunctionPass * createAArch64CompressJumpTablesPass()
void resize(size_type N)
Definition: SmallVector.h:351