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 struct BasicBlockInfo;
25 using BBInfoVector = SmallVectorImpl<BasicBlockInfo>;
26 
27 /// UnknownPadding - Return the worst case padding that could result from
28 /// unknown offset bits.  This does not include alignment padding caused by
29 /// known offset bits.
30 ///
31 /// @param Alignment alignment
32 /// @param KnownBits Number of known low offset bits.
33 inline unsigned UnknownPadding(Align Alignment, unsigned KnownBits) {
34   if (KnownBits < Log2(Alignment))
35     return Alignment.value() - (1ull << KnownBits);
36   return 0;
37 }
38 
39 /// BasicBlockInfo - Information about the offset and size of a single
40 /// basic block.
41 struct BasicBlockInfo {
42   /// Offset - Distance from the beginning of the function to the beginning
43   /// of this basic block.
44   ///
45   /// Offsets are computed assuming worst case padding before an aligned
46   /// block. This means that subtracting basic block offsets always gives a
47   /// conservative estimate of the real distance which may be smaller.
48   ///
49   /// Because worst case padding is used, the computed offset of an aligned
50   /// block may not actually be aligned.
51   unsigned Offset = 0;
52 
53   /// Size - Size of the basic block in bytes.  If the block contains
54   /// inline assembly, this is a worst case estimate.
55   ///
56   /// The size does not include any alignment padding whether from the
57   /// beginning of the block, or from an aligned jump table at the end.
58   unsigned Size = 0;
59 
60   /// KnownBits - The number of low bits in Offset that are known to be
61   /// exact.  The remaining bits of Offset are an upper bound.
62   uint8_t KnownBits = 0;
63 
64   /// Unalign - When non-zero, the block contains instructions (inline asm)
65   /// of unknown size.  The real size may be smaller than Size bytes by a
66   /// multiple of 1 << Unalign.
67   uint8_t Unalign = 0;
68 
69   /// PostAlign - When > 1, the block terminator contains a .align
70   /// directive, so the end of the block is aligned to PostAlign bytes.
71   Align PostAlign;
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.
78   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 Align is
88   /// specified, return the offset the successor block will get if it has
89   /// this alignment.
90   unsigned postOffset(Align Alignment = Align(1)) const {
91     unsigned PO = Offset + Size;
92     const Align PA = std::max(PostAlign, Alignment);
93     if (PA == Align(1))
94       return PO;
95     // Add alignment padding from the terminator.
96     return PO + UnknownPadding(PA, 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(Align Align = llvm::Align(1)) const {
105     return std::max(Log2(std::max(PostAlign, Align)), internalKnownBits());
106   }
107 };
108 
109 class ARMBasicBlockUtils {
110 
111 private:
112   MachineFunction &MF;
113   bool isThumb = false;
114   const ARMBaseInstrInfo *TII = nullptr;
115   SmallVector<BasicBlockInfo, 8> BBInfo;
116 
117 public:
118   ARMBasicBlockUtils(MachineFunction &MF) : MF(MF) {
119     TII =
120       static_cast<const ARMBaseInstrInfo*>(MF.getSubtarget().getInstrInfo());
121     isThumb = MF.getInfo<ARMFunctionInfo>()->isThumbFunction();
122   }
123 
124   void computeAllBlockSizes() {
125     BBInfo.resize(MF.getNumBlockIDs());
126     for (MachineBasicBlock &MBB : MF)
127       computeBlockSize(&MBB);
128   }
129 
130   void computeBlockSize(MachineBasicBlock *MBB);
131 
132   unsigned getOffsetOf(MachineInstr *MI) const;
133 
134   unsigned getOffsetOf(MachineBasicBlock *MBB) const {
135     return BBInfo[MBB->getNumber()].Offset;
136   }
137 
138   void adjustBBOffsetsAfter(MachineBasicBlock *MBB);
139 
140   void adjustBBSize(MachineBasicBlock *MBB, int Size) {
141     BBInfo[MBB->getNumber()].Size += Size;
142   }
143 
144   bool isBBInRange(MachineInstr *MI, MachineBasicBlock *DestBB,
145                    unsigned MaxDisp) const;
146 
147   void insert(unsigned BBNum, BasicBlockInfo BBI) {
148     BBInfo.insert(BBInfo.begin() + BBNum, BBI);
149   }
150 
151   void clear() { BBInfo.clear(); }
152 
153   BBInfoVector &getBBInfo() { return BBInfo; }
154 
155 };
156 
157 } // end namespace llvm
158 
159 #endif // LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
160