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::None()) const { 91 unsigned PO = Offset + Size; 92 const Align PA = std::max(PostAlign, Alignment); 93 if (PA == Align::None()) 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 = Align::None()) 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