AArch64: Move remaining target specific BranchRelaxation bits to TII

[t.p.northover]

lib/Target/AArch64/AArch64InstrInfo.cpp

131–132

This doesn't look right to me. I see that it's coming from a "return -1" but unconditional branches don't have unlimited range. They've got 26-bit signed range.

lib/Target/AArch64/AArch64InstrInfo.h

204–207

Could these APIs be expressed in terms of InsertBranch? At the moment it seems like we're crafting a parallel set of special-purpose branch-mangling functions but instead we could add something like

SmallVectorImpl<MachineOperand> getUnconditionalCond();
SmallVectorImpl<MachineOperand> getInvertedCond(SmallVectorImpl<MachineOperand> &Cond);

(feel free to bikeshed the interface, I'm not attached) and then these 3 become fairly simple wrappers around the existing functionality.

[arsenm]

lib/Target/AArch64/AArch64InstrInfo.cpp

131–132

The current code assumes they don't need to be relaxed, so I just assumed infinite range. I have another patch which adds support for expanding unconditional branches

lib/Target/AArch64/AArch64InstrInfo.h

204–207

I don't think it's quite the same. I thought about trying to use the existing family of analyzeBranch functions, but I think they have a different purpose. A better name would be something like analyzeBlockBranches. I hadn't thougt about trying to produce the cond vector from some other means.

The important features this one has are supporting inserting an additional branch block, passing the branch offset and returning the change in code size. I also may eventually want to introduce the ability to add even more blocks during he unconditional expansion, so at that point I don't think it has much in common with the existing InsertBranch, which just inserts a simple assumed legal branch. I suppose I could change the caller of this for conditional branches to use that instead of using 0 to assume a legal offset

[t.p.northover]

lib/Target/AArch64/AArch64InstrInfo.h

204–207

I don't think it's quite the same. I thought about trying to use the existing family of analyzeBranch functions, but I think they have a different purpose. A better name would be something like analyzeBlockBranches.

Sure, but these new functions are actually being used in a very similar way already.

• The setDestBlock/insertInvertedBranch pair is essentially an insertBranch with inverted condition and the specified blocks.
• insertInverted/insertUnconditional ditto.
• The lone insertUnconditional (patching a fallthrough) is just an InsertBranch with only one BB.

The important features this one has are supporting inserting an additional branch block

Not sure I follow this one. Are you planning to make the TargetInstrInfo do part of the relaxation (creating BBs if the unconditional branch is out of range)? That sounds like the wrong place if so.

passing the branch offset

I take it this is going to be used for AMDGPU? It seems unused here, and I can't quite see the implications.

and returning the change in code size.

That is unfortunate. It still seems like it'd be better to extend the InsertBranch interface rather than duplicate it though. Simplest would be returning an std::pair<unsigned, unsigned>, or perhaps adding a helper to convert from NumInstructions to a size.

[t.p.northover]

BTW, I should say that I love the idea of the pass becoming generic in general! It's got to be a really commonly useful bit of functionality.

[arsenm]

lib/Target/AArch64/AArch64InstrInfo.h

204–207

I posted D23373 which uses these. The point is unconditional branches need to be expanded, which requires knowing the offsets. The pass now inserts the new block. I have another problem to solve someday which will involve inserting more blocks for weird spilling cases, but I'm not sure how that should work quite yet.

[t.p.northover]

Sorry I dropped this last week. It doesn't seem unreasonable to add KnownOffset arguments to InsertBranch's interface, and the return value really doesn't seem like a blocker to using InsertBranch.

In fact, I've just noticed that ReverseBranchCondition already exists. So I think all that'd be needed is the getUnconditionalCondition.

Would you like me to put together an alternative patch, and we can see if it'll fit your needs too?

[arsenm]

In D23269#516875, @t.p.northover wrote:

Sorry I dropped this last week. It doesn't seem unreasonable to add KnownOffset arguments to InsertBranch's interface, and the return value really doesn't seem like a blocker to using InsertBranch.

In fact, I've just noticed that ReverseBranchCondition already exists. So I think all that'd be needed is the getUnconditionalCondition.

Would you like me to put together an alternative patch, and we can see if it'll fit your needs too?

I think it might be just a question of naming. I think it would make sense to use InsertBranch when expanding unconditional branches. The main use for insertUnconditionalBranch (at least for my purposes) is insertIndirectBranch. I can switch the branch insertion for expanding conditional branches to use the regular InsertBranch, and rename it for expanding unconditionals.

[t.p.northover]

I think it might be just a question of naming.

For me it's the code duplication, though I think we might be in agreement now and just looking at it from different angles. AArch64BranchRelaxation contains quite a bit of code basically copy/pasted from AArch64InstrInfo.cpp just because the Analyze/Insert/Remove branch interface wasn't quite right. This looks even sillier when both instances are in InstrInfo with subtly different semantics.

Adding a convenience insertUnconditionalBranch function (and even insertInvertedConditionBranch) seems reasonable, but one way or the other delegation with InsertBranch should be involved.

Anyway, a very preliminary and largely untested outline of what I have in mind is at https://github.com/TNorthover/llvm/tree/branch-relax (making use of a possibly buggy version of D23379 so we can analyze everything). The diff is +57/-174 at the moment. It seems like we'd just have to make InsertBranch return the bytes as well (if not for IfConversion we could do a straight swap) and accept optional KnownOffset args and it could do everything you need.

[arsenm]

In D23269#517159, @t.p.northover wrote:

I think it might be just a question of naming.

For me it's the code duplication, though I think we might be in agreement now and just looking at it from different angles. AArch64BranchRelaxation contains quite a bit of code basically copy/pasted from AArch64InstrInfo.cpp just because the Analyze/Insert/Remove branch interface wasn't quite right. This looks even sillier when both instances are in InstrInfo with subtly different semantics.

Adding a convenience insertUnconditionalBranch function (and even insertInvertedConditionBranch) seems reasonable, but one way or the other delegation with InsertBranch should be involved.

Anyway, a very preliminary and largely untested outline of what I have in mind is at https://github.com/TNorthover/llvm/tree/branch-relax (making use of a possibly buggy version of D23379 so we can analyze everything). The diff is +57/-174 at the moment. It seems like we'd just have to make InsertBranch return the bytes as well (if not for IfConversion we could do a straight swap) and accept optional KnownOffset args and it could do everything you need.

We could get away with it returning the number of instructions to get the size by calling getInstSizeInBytes on them (though I always thought the return the number of instructions API was weird). Your patch untangles the weird mess with NeedSplit trying to skip analyzeBranch which I was hoping to fix later, so overall I think your patch makes sense. The API changes I really need make more sense in the context of inserting an indirect branch, so I think keeping those bits as a new function separate from InsertBranch still makes sense rather than cluttering up all of the other uses

[arsenm]

Update for trunk

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[SjoerdMeijer]

This looks reasonable to me. In fact, we have been discussing this before in D23067, which was also supposed to add hook isBranchOffsetInRange. I had to park this work (hope to pick it up), but anyway, they are more than useful hooks to have and the implementation here makes sense to me.

[arsenm]

r283458

include/llvm/Target/TargetInstrInfo.h

public:
   /// By default, this is only true when the two instructions
   /// are deemed identical except for defs. If this function is called when the
   /// IR is still in SSA form, the caller can pass the MachineRegisterInfo for
   /// aggressive checks.
   virtual bool produceSameValue(const MachineInstr &MI0,
                                 const MachineInstr &MI1,
                                 const MachineRegisterInfo *MRI = nullptr) const;
 
+  /// \returns true if a branch from an instruction with opcode \p BranchOpc
+  ///  bytes is capable of jumping to a position \p BrOffset bytes away.
+  virtual bool isBranchOffsetInRange(unsigned BranchOpc,
+                                     int64_t BrOffset) const {
+    llvm_unreachable("target did not implement");
+  }
+
+  /// \returns The block that branch instruction \p MI jumps to.
+  virtual MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const {
+    llvm_unreachable("target did not implement");
+  }
+
   /// Analyze the branching code at the end of MBB, returning
   /// true if it cannot be understood (e.g. it's a switch dispatch or isn't
   /// implemented for a target).  Upon success, this returns false and returns
   /// with the following information in various cases:
   ///
   /// 1. If this block ends with no branches (it just falls through to its succ)
   ///    just return false, leaving TBB/FBB null.
   /// 2. If this block ends with only an unconditional branch, it sets TBB to be

lib/Target/AArch64/AArch64BranchRelaxation.cpp

 //===-- AArch64BranchRelaxation.cpp - AArch64 branch relaxation -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AArch64.h"
 #include "AArch64InstrInfo.h"
 #include "AArch64MachineFunctionInfo.h"
 #include "AArch64Subtarget.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "aarch64-branch-relax"
 
AArch64BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI) {
 
   return NewBB;
 }
 
 /// isBlockInRange - Returns true if the distance between specific MI and
 /// specific BB can fit in MI's displacement field.
 bool AArch64BranchRelaxation::isBlockInRange(
   const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
-  unsigned BrOffset = getInstrOffset(MI);
-  unsigned DestOffset = BlockInfo[DestBB.getNumber()].Offset;
+  int64_t BrOffset = getInstrOffset(MI);
+  int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
 
-  if (TII->isBranchInRange(MI.getOpcode(), BrOffset, DestOffset))
+  if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
     return true;
 
   DEBUG(
     dbgs() << "Out of range branch to destination BB#" << DestBB.getNumber()
            << " from BB#" << MI.getParent()->getNumber()
            << " to " << DestOffset
-           << " offset " << static_cast<int>(DestOffset - BrOffset)
+           << " offset " << DestOffset - BrOffset
            << '\t' << MI
   );
 
   return false;
 }
 
-static MachineBasicBlock *getDestBlock(const MachineInstr &MI) {
-  switch (MI.getOpcode()) {
-  default:
-    llvm_unreachable("unexpected opcode!");
-  case AArch64::B:
-    return MI.getOperand(0).getMBB();
-  case AArch64::TBZW:
-  case AArch64::TBNZW:
-  case AArch64::TBZX:
-  case AArch64::TBNZX:
-    return MI.getOperand(2).getMBB();
-  case AArch64::CBZW:
-  case AArch64::CBNZW:
-  case AArch64::CBZX:
-  case AArch64::CBNZX:
-  case AArch64::Bcc:
-    return MI.getOperand(1).getMBB();
-  }
-}
-
 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
 /// too far away to fit in its displacement field. It is converted to an inverse
 /// conditional branch + an unconditional branch to the destination.
 bool AArch64BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
   DebugLoc DL = MI.getDebugLoc();
   MachineBasicBlock *MBB = MI.getParent();
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
 
     MachineBasicBlock::iterator Next;
     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
          J != MBB.end(); J = Next) {
       Next = std::next(J);
       MachineInstr &MI = *J;
 
       if (MI.isConditionalBranch()) {
-        MachineBasicBlock *DestBB = getDestBlock(MI);
+        MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
         if (!isBlockInRange(MI, *DestBB)) {
           if (Next != MBB.end() && Next->isConditionalBranch()) {
             // If there are multiple conditional branches, this isn't an
             // analyzable block. Split later terminators into a new block so
             // each one will be analyzable.
 
             MachineBasicBlock *NewBB = splitBlockBeforeInstr(*Next);
             NewBB->transferSuccessors(&MBB);

lib/Target/AArch64/AArch64InstrInfo.h

public:
   using TargetInstrInfo::foldMemoryOperandImpl;
   MachineInstr *
   foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                         ArrayRef<unsigned> Ops,
                         MachineBasicBlock::iterator InsertPt, int FrameIndex,
                         LiveIntervals *LIS = nullptr) const override;
 
   /// \returns true if a branch from an instruction with opcode \p BranchOpc
-  /// located at \p BrOffset bytes is capable of jumping to a position at \p
-  /// DestOffset.
-  bool isBranchInRange(unsigned BranchOpc, uint64_t BrOffset,
-                       uint64_t DestOffset) const;
+  ///  bytes is capable of jumping to a position \p BrOffset bytes away.
+  bool isBranchOffsetInRange(unsigned BranchOpc,
+                             int64_t BrOffset) const override;
+
+  MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
 
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify = false) const override;
   unsigned removeBranch(MachineBasicBlock &MBB,
                         int *BytesRemoved = nullptr) const override;
   unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                         MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                         const DebugLoc &DL,
                         int *BytesAdded = nullptr) const override;
   bool
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
   bool canInsertSelect(const MachineBasicBlock &, ArrayRef<MachineOperand> Cond,
                        unsigned, unsigned, int &, int &, int &) const override;
   void insertSelect(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                     const DebugLoc &DL, unsigned DstReg,
                     ArrayRef<MachineOperand> Cond, unsigned TrueReg,
                     unsigned FalseReg) const override;
   void getNoopForMachoTarget(MCInst &NopInst) const override;
 
   /// analyzeCompare - For a comparison instruction, return the source registers
   /// in SrcReg and SrcReg2, and the value it compares against in CmpValue.
   /// Return true if the comparison instruction can be analyzed.
   bool analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
                       unsigned &SrcReg2, int &CmpMask,
                       int &CmpValue) const override;
   /// optimizeCompareInstr - Convert the instruction supplying the argument to
   /// the comparison into one that sets the zero bit in the flags register.
   bool optimizeCompareInstr(MachineInstr &CmpInstr, unsigned SrcReg,
                             unsigned SrcReg2, int CmpMask, int CmpValue,
                             const MachineRegisterInfo *MRI) const override;
   bool optimizeCondBranch(MachineInstr &MI) const override;
 

lib/Target/AArch64/AArch64InstrInfo.cpp

case AArch64::TBNZX:
     Cond.push_back(LastInst->getOperand(1));
   }
 }
 
 static unsigned getBranchDisplacementBits(unsigned Opc) {
   switch (Opc) {
   default:
     llvm_unreachable("unexpected opcode!");
+  case AArch64::B:
+    return 64;
   case AArch64::TBNZW:
   case AArch64::TBZW:
   case AArch64::TBNZX:
   case AArch64::TBZX:
     return TBZDisplacementBits;
   case AArch64::CBNZW:
   case AArch64::CBZW:
   case AArch64::CBNZX:
   case AArch64::CBZX:
     return CBZDisplacementBits;
   case AArch64::Bcc:
     return BCCDisplacementBits;
   }
 }
 
-static unsigned getBranchMaxDisplacementBytes(unsigned Opc) {
-  if (Opc == AArch64::B)
-    return -1;
-
-  unsigned Bits = getBranchDisplacementBits(Opc);
-  unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
-
-  // Verify the displacement bits options have sane values.
-  // XXX: Is there a better place for this?
-  assert(MaxOffs >= 8 &&
-         "max branch displacement must be enough to jump"
+bool AArch64InstrInfo::isBranchOffsetInRange(unsigned BranchOp,
+                                             int64_t BrOffset) const {
+  unsigned Bits = getBranchDisplacementBits(BranchOp);
+  assert(Bits >= 3 && "max branch displacement must be enough to jump"
                       "over conditional branch expansion");
-
-  return MaxOffs;
+  return isIntN(Bits, BrOffset / 4);
 }
 
-bool AArch64InstrInfo::isBranchInRange(unsigned BranchOp, uint64_t BrOffset,
-                                       uint64_t DestOffset) const {
-  unsigned MaxOffs = getBranchMaxDisplacementBytes(BranchOp);
-
-  // Branch before the Dest.
-  if (BrOffset <= DestOffset)
-    return (DestOffset - BrOffset <= MaxOffs);
-  return (BrOffset - DestOffset <= MaxOffs);
+MachineBasicBlock *AArch64InstrInfo::getBranchDestBlock(
+  const MachineInstr &MI) const {
+  switch (MI.getOpcode()) {
+  default:
+    llvm_unreachable("unexpected opcode!");
+  case AArch64::B:
+    return MI.getOperand(0).getMBB();
+  case AArch64::TBZW:
+  case AArch64::TBNZW:
+  case AArch64::TBZX:
+  case AArch64::TBNZX:
+    return MI.getOperand(2).getMBB();
+  case AArch64::CBZW:
+  case AArch64::CBNZW:
+  case AArch64::CBZX:
+  case AArch64::CBNZX:
+  case AArch64::Bcc:
+    return MI.getOperand(1).getMBB();
+  }
 }
 
 // Branch analysis.
 bool AArch64InstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                      MachineBasicBlock *&TBB,
                                      MachineBasicBlock *&FBB,
                                      SmallVectorImpl<MachineOperand> &Cond,
                                      bool AllowModify) const {