lib/Target/ARM/ARMBasicBlockInfo.h

   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