1 //===-- ARMBasicBlockInfo.h - Basic Block Information -----------*- C++ -*-===//
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 //===----------------------------------------------------------------------===//
8 //
9 // Utility functions and data structure for computing block size.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #ifndef LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
14 #define LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
15
16 #include "ARMBaseInstrInfo.h"
17 #include "ARMMachineFunctionInfo.h"
18 #include "llvm/Support/MathExtras.h"
19 #include <algorithm>
20 #include <cstdint>
21
22 namespace llvm {
23
24 using BBInfoVector = SmallVectorImpl<BasicBlockInfo>;
25
26 /// UnknownPadding - Return the worst case padding that could result from
27 /// unknown offset bits. This does not include alignment padding caused by
28 /// known offset bits.
29 ///
30 /// @param LogAlign log2(alignment)
31 /// @param KnownBits Number of known low offset bits.
UnknownPadding(unsigned LogAlign,unsigned KnownBits)32 inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
33 if (KnownBits < LogAlign)
34 return (1u << LogAlign) - (1u << KnownBits);
35 return 0;
36 }
37
38 /// BasicBlockInfo - Information about the offset and size of a single
39 /// basic block.
40 struct BasicBlockInfo {
41 /// Offset - Distance from the beginning of the function to the beginning
42 /// of this basic block.
43 ///
44 /// Offsets are computed assuming worst case padding before an aligned
45 /// block. This means that subtracting basic block offsets always gives a
46 /// conservative estimate of the real distance which may be smaller.
47 ///
48 /// Because worst case padding is used, the computed offset of an aligned
49 /// block may not actually be aligned.
50 unsigned Offset = 0;
51
52 /// Size - Size of the basic block in bytes. If the block contains
53 /// inline assembly, this is a worst case estimate.
54 ///
55 /// The size does not include any alignment padding whether from the
56 /// beginning of the block, or from an aligned jump table at the end.
57 unsigned Size = 0;
58
59 /// KnownBits - The number of low bits in Offset that are known to be
60 /// exact. The remaining bits of Offset are an upper bound.
61 uint8_t KnownBits = 0;
62
63 /// Unalign - When non-zero, the block contains instructions (inline asm)
64 /// of unknown size. The real size may be smaller than Size bytes by a
65 /// multiple of 1 << Unalign.
66 uint8_t Unalign = 0;
67
68 /// PostAlign - When non-zero, the block terminator contains a .align
69 /// directive, so the end of the block is aligned to 1 << PostAlign
70 /// bytes.
71 uint8_t PostAlign = 0;
72
73 BasicBlockInfo() = default;
74
75 /// Compute the number of known offset bits internally to this block.
76 /// This number should be used to predict worst case padding when
77 /// splitting the block.
internalKnownBitsBasicBlockInfo78 unsigned internalKnownBits() const {
79 unsigned Bits = Unalign ? Unalign : KnownBits;
80 // If the block size isn't a multiple of the known bits, assume the
81 // worst case padding.
82 if (Size & ((1u << Bits) - 1))
83 Bits = countTrailingZeros(Size);
84 return Bits;
85 }
86
87 /// Compute the offset immediately following this block. If LogAlign is
88 /// specified, return the offset the successor block will get if it has
89 /// this alignment.
90 unsigned postOffset(unsigned LogAlign = 0) const {
91 unsigned PO = Offset + Size;
92 unsigned LA = std::max(unsigned(PostAlign), LogAlign);
93 if (!LA)
94 return PO;
95 // Add alignment padding from the terminator.
96 return PO + UnknownPadding(LA, internalKnownBits());
97 }
98
99 /// Compute the number of known low bits of postOffset. If this block
100 /// contains inline asm, the number of known bits drops to the
101 /// instruction alignment. An aligned terminator may increase the number
102 /// of know bits.
103 /// If LogAlign is given, also consider the alignment of the next block.
104 unsigned postKnownBits(unsigned LogAlign = 0) const {
105 return std::max(std::max(unsigned(PostAlign), LogAlign),
106 internalKnownBits());
107 }
108 };
109
110 class ARMBasicBlockUtils {
111
112 private:
113 MachineFunction &MF;
114 bool isThumb = false;
115 const ARMBaseInstrInfo *TII = nullptr;
116 SmallVector<BasicBlockInfo, 8> BBInfo;
117
118 public:
ARMBasicBlockUtils(MachineFunction & MF)119 ARMBasicBlockUtils(MachineFunction &MF) : MF(MF) {
120 TII =
121 static_cast<const ARMBaseInstrInfo*>(MF.getSubtarget().getInstrInfo());
122 isThumb = MF.getInfo<ARMFunctionInfo>()->isThumbFunction();
123 }
124
computeAllBlockSizes()125 void computeAllBlockSizes() {
126 BBInfo.resize(MF.getNumBlockIDs());
127 for (MachineBasicBlock &MBB : MF)
128 computeBlockSize(&MBB);
129 }
130
131 void computeBlockSize(MachineBasicBlock *MBB);
132
133 unsigned getOffsetOf(MachineInstr *MI) const;
134
getOffsetOf(MachineBasicBlock * MBB)135 unsigned getOffsetOf(MachineBasicBlock *MBB) const {
136 return BBInfo[MBB->getNumber()].Offset;
137 }
138
139 void adjustBBOffsetsAfter(MachineBasicBlock *MBB);
140
adjustBBSize(MachineBasicBlock * MBB,int Size)141 void adjustBBSize(MachineBasicBlock *MBB, int Size) {
142 BBInfo[MBB->getNumber()].Size += Size;
143 }
144
145 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *DestBB,
146 unsigned MaxDisp) const;
147
insert(unsigned BBNum,BasicBlockInfo BBI)148 void insert(unsigned BBNum, BasicBlockInfo BBI) {
149 BBInfo.insert(BBInfo.begin() + BBNum, BBI);
150 }
151
clear()152 void clear() { BBInfo.clear(); }
153
getBBInfo()154 BBInfoVector &getBBInfo() { return BBInfo; }
155
156 };
157
158 } // end namespace llvm
159
160 #endif // LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
161