[SystemZ] Add long branch pass

Before this change, the SystemZ backend would use BRCL for all branches
and only consider shortening them to BRC when generating an object file.
E.g. a branch on equal would use the JGE alias of BRCL in assembly output,
but might be shortened to the JE alias of BRC in ELF output.  This was
a useful first step, but it had two problems:

(1) The z assembler isn't traditionally supposed to perform branch shortening
    or branch relaxation.  We followed this rule by not relaxing branches
    in assembler input, but that meant that generating assembly code and
    then assembling it would not produce the same result as going directly
    to object code; the former would give long branches everywhere, whereas
    the latter would use short branches where possible.

(2) Other useful branches, like COMPARE AND BRANCH, do not have long forms.
    We would need to do something else before supporting them.

    (Although COMPARE AND BRANCH does not change the condition codes,
    the plan is to model COMPARE AND BRANCH as a CC-clobbering instruction
    during codegen, so that we can safely lower it to a separate compare
    and long branch where necessary.  This is not a valid transformation
    for the assembler proper to make.)

This patch therefore moves branch relaxation to a pre-emit pass.
For now, calls are still shortened from BRASL to BRAS by the assembler,
although this too is not really the traditional behaviour.

The first test takes about 1.5s to run, and there are likely to be
more tests in this vein once further branch types are added.  The feeling
on IRC was that 1.5s is a bit much for a single test, so I've restricted
it to SystemZ hosts for now.

The patch exposes (and fixes) some typos in the main CodeGen/SystemZ tests.
A later patch will remove the {{g}}s from that directory.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182274 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 357 insertions, 0 deletions

diff --git a/lib/Target/SystemZ/SystemZLongBranch.cpp b/lib/Target/SystemZ/SystemZLongBranch.cpp
new file mode 100644
index 0000000000..d9d1c7ea69
--- /dev/null
+++ b/lib/Target/SystemZ/SystemZLongBranch.cpp
@@ -0,0 +1,357 @@
+//===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass makes sure that all branches are in range.  There are several ways
+// in which this could be done.  One aggressive approach is to assume that all
+// branches are in range and successively replace those that turn out not
+// to be in range with a longer form (branch relaxation).  A simple
+// implementation is to continually walk through the function relaxing
+// branches until no more changes are needed and a fixed point is reached.
+// However, in the pathological worst case, this implementation is
+// quadratic in the number of blocks; relaxing branch N can make branch N-1
+// go out of range, which in turn can make branch N-2 go out of range,
+// and so on.
+//
+// An alternative approach is to assume that all branches must be
+// converted to their long forms, then reinstate the short forms of
+// branches that, even under this pessimistic assumption, turn out to be
+// in range (branch shortening).  This too can be implemented as a function
+// walk that is repeated until a fixed point is reached.  In general,
+// the result of shortening is not as good as that of relaxation, and
+// shortening is also quadratic in the worst case; shortening branch N
+// can bring branch N-1 in range of the short form, which in turn can do
+// the same for branch N-2, and so on.  The main advantage of shortening
+// is that each walk through the function produces valid code, so it is
+// possible to stop at any point after the first walk.  The quadraticness
+// could therefore be handled with a maximum pass count, although the
+// question then becomes: what maximum count should be used?
+//
+// On SystemZ, long branches are only needed for functions bigger than 64k,
+// which are relatively rare to begin with, and the long branch sequences
+// are actually relatively cheap.  It therefore doesn't seem worth spending
+// much compilation time on the problem.  Instead, the approach we take is:
+//
+// (1) Check whether all branches can be short (the usual case).  Exit the
+//     pass if so.
+// (2) If one branch needs to be long, work out the address that each block
+//     would have if all branches need to be long, as for shortening above.
+// (3) Relax any branch that is out of range according to this pessimistic
+//     assumption.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "systemz-long-branch"
+
+#include "SystemZTargetMachine.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+using namespace llvm;
+
+STATISTIC(LongBranches, "Number of long branches.");
+
+namespace {
+  typedef MachineBasicBlock::iterator Iter;
+
+  // Represents positional information about a basic block.
+  struct MBBInfo {
+    // The address that we currently assume the block has, relative to
+    // the start of the function.  This is designed so that taking the
+    // difference between two addresses gives a conservative upper bound
+    // on the distance between them.
+    uint64_t Address;
+
+    // The size of the block in bytes, excluding terminators.
+    // This value never changes.
+    uint64_t Size;
+
+    // The minimum alignment of the block, as a log2 value.
+    // This value never changes.
+    unsigned Alignment;
+
+    // The number of terminators in this block.  This value never changes.
+    unsigned NumTerminators;
+
+    MBBInfo()
+      : Address(0), Size(0), Alignment(0), NumTerminators(0) {} 
+  };
+
+  // Represents the state of a block terminator.
+  struct TerminatorInfo {
+    // If this terminator is a relaxable branch, this points to the branch
+    // instruction, otherwise it is null.
+    MachineInstr *Branch;
+
+    // The current address of the terminator, in the same form as
+    // for BlockInfo.
+    uint64_t Address;
+
+    // The current size of the terminator in bytes.
+    uint64_t Size;
+
+    // If Branch is nonnull, this is the number of the target block,
+    // otherwise it is unused.
+    unsigned TargetBlock;
+
+    // If Branch is nonnull, this is the length of the longest relaxed form,
+    // otherwise it is zero.
+    unsigned ExtraRelaxSize;
+
+    TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {}
+  };
+
+  // Used to keep track of the current position while iterating over the blocks.
+  struct BlockPosition {
+    // The offset from the start of the function, in the same form
+    // as BlockInfo.
+    uint64_t Address;
+
+    // The number of low bits in Address that are known to be the same
+    // as the runtime address.
+    unsigned KnownBits;
+
+    BlockPosition(unsigned InitialAlignment)
+      : Address(0), KnownBits(InitialAlignment) {}
+  };
+
+  class SystemZLongBranch : public MachineFunctionPass {
+  public:
+    static char ID;
+    SystemZLongBranch(const SystemZTargetMachine &tm)
+      : MachineFunctionPass(ID),
+        TII(static_cast<const SystemZInstrInfo *>(tm.getInstrInfo())) {}
+
+    virtual const char *getPassName() const {
+      return "SystemZ Long Branch";
+    }
+
+    bool runOnMachineFunction(MachineFunction &F);
+
+  private:
+    void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
+    void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
+                        bool AssumeRelaxed);
+    TerminatorInfo describeTerminator(MachineInstr *MI);
+    uint64_t initMBBInfo();
+    bool mustRelaxBranch(const TerminatorInfo &Terminator);
+    bool mustRelaxABranch();
+    void setWorstCaseAddresses();
+    void relaxBranch(TerminatorInfo &Terminator);
+    void relaxBranches();
+
+    const SystemZInstrInfo *TII;
+    MachineFunction *MF;
+    SmallVector<MBBInfo, 16> MBBs;
+    SmallVector<TerminatorInfo, 16> Terminators;
+  };
+
+  char SystemZLongBranch::ID = 0;
+
+  const uint64_t MaxBackwardRange = 0x10000;
+  const uint64_t MaxForwardRange = 0xfffe;
+} // end of anonymous namespace
+
+FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
+  return new SystemZLongBranch(TM);
+}
+
+// Position describes the state immediately before Block.  Update Block
+// accordingly and move Position to the end of the block's non-terminator
+// instructions.
+void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
+                                           MBBInfo &Block) {
+  if (Block.Alignment > Position.KnownBits) {
+    // When calculating the address of Block, we need to conservatively
+    // assume that Block had the worst possible misalignment.
+    Position.Address += ((uint64_t(1) << Block.Alignment) -
+                         (uint64_t(1) << Position.KnownBits));
+    Position.KnownBits = Block.Alignment;
+  }
+
+  // Align the addresses.
+  uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
+  Position.Address = (Position.Address + AlignMask) & ~AlignMask;
+
+  // Record the block's position.
+  Block.Address = Position.Address;
+
+  // Move past the non-terminators in the block.
+  Position.Address += Block.Size;
+}
+
+// Position describes the state immediately before Terminator.
+// Update Terminator accordingly and move Position past it.
+// Assume that Terminator will be relaxed if AssumeRelaxed.
+void SystemZLongBranch::skipTerminator(BlockPosition &Position,
+                                       TerminatorInfo &Terminator,
+                                       bool AssumeRelaxed) {
+  Terminator.Address = Position.Address;
+  Position.Address += Terminator.Size;
+  if (AssumeRelaxed)
+    Position.Address += Terminator.ExtraRelaxSize;
+}
+
+// Return a description of terminator instruction MI.
+TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
+  TerminatorInfo Terminator;
+  Terminator.Size = TII->getInstSizeInBytes(MI);
+  if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
+    Terminator.Branch = MI;
+    switch (MI->getOpcode()) {
+    case SystemZ::J:
+      // Relaxes to JG, which is 2 bytes longer.
+      Terminator.TargetBlock = MI->getOperand(0).getMBB()->getNumber();
+      Terminator.ExtraRelaxSize = 2;
+      break;
+    case SystemZ::BRC:
+      // Relaxes to BRCL, which is 2 bytes longer.  Operand 0 is the
+      // condition code mask.
+      Terminator.TargetBlock = MI->getOperand(1).getMBB()->getNumber();
+      Terminator.ExtraRelaxSize = 2;
+      break;
+    default:
+      llvm_unreachable("Unrecognized branch instruction");
+    }
+  }
+  return Terminator;
+}
+
+// Fill MBBs and Terminators, setting the addresses on the assumption
+// that no branches need relaxation.  Return the size of the function under
+// this assumption.
+uint64_t SystemZLongBranch::initMBBInfo() {
+  MF->RenumberBlocks();
+  unsigned NumBlocks = MF->size();
+
+  MBBs.clear();
+  MBBs.resize(NumBlocks);
+
+  Terminators.clear();
+  Terminators.reserve(NumBlocks);
+
+  BlockPosition Position(MF->getAlignment());
+  for (unsigned I = 0; I < NumBlocks; ++I) {
+    MachineBasicBlock *MBB = MF->getBlockNumbered(I);
+    MBBInfo &Block = MBBs[I];
+
+    // Record the alignment, for quick access.
+    Block.Alignment = MBB->getAlignment();
+
+    // Calculate the size of the fixed part of the block.
+    MachineBasicBlock::iterator MI = MBB->begin();
+    MachineBasicBlock::iterator End = MBB->end();
+    while (MI != End && !MI->isTerminator()) {
+      Block.Size += TII->getInstSizeInBytes(MI);
+      ++MI;
+    }
+    skipNonTerminators(Position, Block);
+
+    // Add the terminators.
+    while (MI != End) {
+      if (!MI->isDebugValue()) {
+        assert(MI->isTerminator() && "Terminator followed by non-terminator");
+        Terminators.push_back(describeTerminator(MI));
+        skipTerminator(Position, Terminators.back(), false);
+        ++Block.NumTerminators;
+      }
+      ++MI;
+    }
+  }
+
+  return Position.Address;
+}
+
+// Return true if, under current assumptions, Terminator needs to be relaxed.
+bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator) {
+  if (!Terminator.Branch)
+    return false;
+
+  const MBBInfo &Target = MBBs[Terminator.TargetBlock];
+  if (Target.Address < Terminator.Address) {
+    if (Terminator.Address - Target.Address <= MaxBackwardRange)
+      return false;
+  } else {
+    if (Target.Address - Terminator.Address <= MaxForwardRange)
+      return false;
+  }
+
+  return true;
+}
+
+// Return true if, under current assumptions, any terminator needs
+// to be relaxed.
+bool SystemZLongBranch::mustRelaxABranch() {
+  for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(),
+         TE = Terminators.end(); TI != TE; ++TI)
+    if (mustRelaxBranch(*TI))
+      return true;
+  return false;
+}
+
+// Set the address of each block on the assumption that all branches
+// must be long.
+void SystemZLongBranch::setWorstCaseAddresses() {
+  SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
+  BlockPosition Position(MF->getAlignment());
+  for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end();
+       BI != BE; ++BI) {
+    skipNonTerminators(Position, *BI);
+    for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
+      skipTerminator(Position, *TI, true);
+      ++TI;
+    }
+  }
+}
+
+// Relax the branch described by Terminator.
+void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
+  MachineInstr *Branch = Terminator.Branch;
+  switch (Branch->getOpcode()) {
+    case SystemZ::J:
+      Branch->setDesc(TII->get(SystemZ::JG));
+      break;
+    case SystemZ::BRC:
+      Branch->setDesc(TII->get(SystemZ::BRCL));
+      break;
+    default:
+      llvm_unreachable("Unrecognized branch");
+    }
+
+  Terminator.Size += Terminator.ExtraRelaxSize;
+  Terminator.ExtraRelaxSize = 0;
+  Terminator.Branch = 0;
+
+  ++LongBranches;
+}
+
+// Relax any branches that need to be relaxed, under current assumptions.
+void SystemZLongBranch::relaxBranches() {
+  for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(),
+         TE = Terminators.end(); TI != TE; ++TI)
+    if (mustRelaxBranch(*TI))
+      relaxBranch(*TI);
+}
+
+bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
+  MF = &F;
+  uint64_t Size = initMBBInfo();
+  if (Size <= MaxForwardRange || !mustRelaxABranch())
+    return false;
+
+  setWorstCaseAddresses();
+  relaxBranches();
+  return true;
+}