path: root/lib/Target/AArch64/AArch64BranchFixupPass.cpp

//===-- AArch64BranchFixupPass.cpp - AArch64 branch fixup -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that fixes AArch64 branches which have ended up out
// of range for their immediate operands.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "aarch64-branch-fixup"
#include "AArch64.h"
#include "AArch64InstrInfo.h"
#include "Utils/AArch64BaseInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;

STATISTIC(NumSplit,      "Number of uncond branches inserted");
STATISTIC(NumCBrFixed,   "Number of cond branches fixed");

/// Return the worst case padding that could result from unknown offset bits.
/// This does not include alignment padding caused by known offset bits.
///
/// @param LogAlign log2(alignment)
/// @param KnownBits Number of known low offset bits.
static inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
  if (KnownBits < LogAlign)
    return (1u << LogAlign) - (1u << KnownBits);
  return 0;
}

namespace {
  /// Due to limited PC-relative displacements, conditional branches to distant
  /// blocks may need converting into an unconditional equivalent. For example:
  ///     tbz w1, #0, far_away
  /// becomes
  ///     tbnz w1, #0, skip
  ///     b far_away
  ///   skip:
  class AArch64BranchFixup : public MachineFunctionPass {
    /// Information about the offset and size of a single basic block.
    struct BasicBlockInfo {
      /// Distance from the beginning of the function to the beginning of this
      /// basic block.
      ///
      /// Offsets are computed assuming worst case padding before an aligned
      /// block. This means that subtracting basic block offsets always gives a
      /// conservative estimate of the real distance which may be smaller.
      ///
      /// Because worst case padding is used, the computed offset of an aligned
      /// block may not actually be aligned.
      unsigned Offset;

      /// Size of the basic block in bytes.  If the block contains inline
      /// assembly, this is a worst case estimate.
      ///
      /// The size does not include any alignment padding whether from the
      /// beginning of the block, or from an aligned jump table at the end.
      unsigned Size;

      /// The number of low bits in Offset that are known to be exact.  The
      /// remaining bits of Offset are an upper bound.
      uint8_t KnownBits;

      /// When non-zero, the block contains instructions (inline asm) of unknown
      /// size.  The real size may be smaller than Size bytes by a multiple of 1
      /// << Unalign.
      uint8_t Unalign;

      BasicBlockInfo() : Offset(0), Size(0), KnownBits(0), Unalign(0) {}

      /// Compute the number of known offset bits internally to this block.
      /// This number should be used to predict worst case padding when
      /// splitting the block.
      unsigned internalKnownBits() const {
        unsigned Bits = Unalign ? Unalign : KnownBits;
        // If the block size isn't a multiple of the known bits, assume the
        // worst case padding.
        if (Size & ((1u << Bits) - 1))
          Bits = CountTrailingZeros_32(Size);
        return Bits;
      }

      /// Compute the offset immediately following this block.  If LogAlign is
      /// specified, return the offset the successor block will get if it has
      /// this alignment.
      unsigned postOffset(unsigned LogAlign = 0) const {
        unsigned PO = Offset + Size;
        if (!LogAlign)
          return PO;
        // Add alignment padding from the terminator.
        return PO + UnknownPadding(LogAlign, internalKnownBits());
      }

      /// Compute the number of known low bits of postOffset.  If this block
      /// contains inline asm, the number of known bits drops to the
      /// instruction alignment.  An aligned terminator may increase the number
      /// of know bits.
      /// If LogAlign is given, also consider the alignment of the next block.
      unsigned postKnownBits(unsigned LogAlign = 0) const {
        return std::max(LogAlign, internalKnownBits());
      }
    };

    std::vector<BasicBlockInfo> BBInfo;

    /// One per immediate branch, keeping the machine instruction pointer,
    /// conditional or unconditional, the max displacement, and (if IsCond is
    /// true) the corresponding inverted branch opcode.
    struct ImmBranch {
      MachineInstr *MI;
      unsigned OffsetBits : 31;
      bool IsCond : 1;
      ImmBranch(MachineInstr *mi, unsigned offsetbits, bool cond)
        : MI(mi), OffsetBits(offsetbits), IsCond(cond) {}
    };

    /// Keep track of all the immediate branch instructions.
    ///
    std::vector<ImmBranch> ImmBranches;

    MachineFunction *MF;
    const AArch64InstrInfo *TII;
  public:
    static char ID;
    AArch64BranchFixup() : MachineFunctionPass(ID) {}

    virtual bool runOnMachineFunction(MachineFunction &MF);

    virtual const char *getPassName() const {
      return "AArch64 branch fixup pass";
    }

  private:
    void initializeFunctionInfo();
    MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
    void adjustBBOffsetsAfter(MachineBasicBlock *BB);
    bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB,
                     unsigned OffsetBits);
    bool fixupImmediateBr(ImmBranch &Br);
    bool fixupConditionalBr(ImmBranch &Br);

    void computeBlockSize(MachineBasicBlock *MBB);
    unsigned getOffsetOf(MachineInstr *MI) const;
    void dumpBBs();
    void verify();
  };
  char AArch64BranchFixup::ID = 0;
}

/// check BBOffsets
void AArch64BranchFixup::verify() {
#ifndef NDEBUG
  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
       MBBI != E; ++MBBI) {
    MachineBasicBlock *MBB = MBBI;
    unsigned MBBId = MBB->getNumber();
    assert(!MBBId || BBInfo[MBBId - 1].postOffset() <= BBInfo[MBBId].Offset);
  }
#endif
}

/// print block size and offset information - debugging
void AArch64BranchFixup::dumpBBs() {
  DEBUG({
    for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
      const BasicBlockInfo &BBI = BBInfo[J];
      dbgs() << format("%08x BB#%u\t", BBI.Offset, J)
             << " kb=" << unsigned(BBI.KnownBits)
             << " ua=" << unsigned(BBI.Unalign)
             << format(" size=%#x\n", BBInfo[J].Size);
    }
  });
}

/// Returns an instance of the branch fixup pass.
FunctionPass *llvm::createAArch64BranchFixupPass() {
  return new AArch64BranchFixup();
}

bool AArch64BranchFixup::runOnMachineFunction(MachineFunction &mf) {
  MF = &mf;
  DEBUG(dbgs() << "***** AArch64BranchFixup ******");
  TII = (const AArch64InstrInfo*)MF->getTarget().getInstrInfo();

  // This pass invalidates liveness information when it splits basic blocks.
  MF->getRegInfo().invalidateLiveness();

  // Renumber all of the machine basic blocks in the function, guaranteeing that
  // the numbers agree with the position of the block in the function.
  MF->RenumberBlocks();

  // Do the initial scan of the function, building up information about the
  // sizes of each block and location of each immediate branch.
  initializeFunctionInfo();

  // Iteratively fix up branches until there is no change.
  unsigned NoBRIters = 0;
  bool MadeChange = false;
  while (true) {
    DEBUG(dbgs() << "Beginning iteration #" << NoBRIters << '\n');
    bool BRChange = false;
    for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
      BRChange |= fixupImmediateBr(ImmBranches[i]);
    if (BRChange && ++NoBRIters > 30)
      report_fatal_error("Branch Fix Up pass failed to converge!");
    DEBUG(dumpBBs());

    if (!BRChange)
      break;
    MadeChange = true;
  }

  // After a while, this might be made debug-only, but it is not expensive.