Home | History | Annotate | Line # | Download | only in ARM 
      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