[SystemZ] Recognize INLINEASM_BR in backend

[jonpa]

Summary

The INLINEASM_BR (produced by asm goto) caused the backend to trigger an assertion without this patch, since that opcode was not recognized and properly handled.

This patch should handle all current cases in the backend by recognizing the opcode in getBranchInfo() and properly recording it in SystemZII::Branch. Since INLINEASM_BR is "variadic", and doesn't have any MCOperandInfo in the MCInstrDesc, I thought it best to not add any MachineOperand pointer from it in SystemZInstrInfo::getBranchInfo(). A new type SystemZII::AsmGoto is the SystemZII::BranchType given to it. I guess this could be SystemZII::Other instead, or something, since the AsmGoto type is not actually checked for anywhere.

An alternative would be to just detect the INLINEASM_BR opcode independently of getBranchInfo(), but I think that maybe would be less helpful the next time a branch needs to be analyzed - likely with getBranchInfo().

Places in backend I found that processes branches:

SystemZLongBranch:

I first thought this needed handling as well, but it turns out this is not needed since INLINEASM_BR returns false from both MI.isConditionalBranch() and MI.isUnconditionalBranch() called in SystemZLongBranch::describeTerminator().

Note: Is Large/branch-01.ll broken? I don't see any brcth in the output. Maybe just the comment is wrong? In fact it seems that the test now has Size==65204 which is less than MaxForwardRange so SystemZLongBranch does not actually run on it.

SystemZHazardRecognizer:

Needs no extra handling since branches are just checked for generally with the purpose to update the decoder group state (optimization).

SystemZMachineScheduler:

Needs to check that there is a branch Target operand, which is done by using the new isRelative() and hasMBBTarget() methods of SystemZII::Branch.

SystemZInstrInfo:
analyzeBranch() and removeBranch() needs to use hasMBBTarget().

The test asm-20.ll now runs with postra scheduling enabled (-mcpu=z14) which should make it test both analyzeBranch() and SystemZMachineScheduler().

[jonpa]

Fix: Remember to check for MBB equality in SystemZPostRASchedStrategy::enterMBB()

[uweigand]

lib/Target/SystemZ/SystemZInstrInfo.cpp

1550

Please add a comment why we're not registering any branch targets.

lib/Target/SystemZ/SystemZInstrInfo.h

128

The name seems weird. If the branch target is a register operand, we have an indirect branch, not a relative branch. (In fact, relative branches are those that have an MBB target operand!)

As I'm not sure there's anything we can ever do to optimize an indirect branch, I'm not sure why we even need this.

lib/Target/SystemZ/SystemZMachineScheduler.cpp

112

Aha, here's the user. But I don't understand it -- what is supposed to be testing? Why would we want to handle indirect branches here?

[jonpa]

Updated per review.

lib/Target/SystemZ/SystemZInstrInfo.h

128

Ouch - changed the name

lib/Target/SystemZ/SystemZMachineScheduler.cpp

112

The SchedStrategy knows the previously scheduled MBB that is going to have its state copied into the current MBB being entered ends with a branch. Since decoder groups are affected differently by Taken /NT branches it first of all figures that if the target of this branch is the current MBB, then it is a taken branch.

So, as I remember it, it seemed for some reason to be good to assume that an indirect branch is typically "taken". But this check seems crude/incomplete to me. Looking at it now it seems simpler to look at the MF linear layout of blocks and just check if it is the one immediately preceding or not. Not sure why I didn't do that. Maybe they result from jump tables that have all but one of the branches taken? Are there some special rules for those branches, maybe? But I don't think that really matters that much as those branches are relatively rare, IIRC.

[uweigand]

Anyway, given that it's already been this way, this patch LGTM. We can have a look at the indirect branch vs. scheduling question later.

lib/Target/SystemZ/SystemZMachineScheduler.cpp

112

Hmm. The SinglePredMBB must be known to be a predecessor of the current MBB, right? Is LLVM able to track predecessor relationships across indirect branches in the first place?

Do you have an example where this check triggers?

[jonpa]

r371048

lib/Target/SystemZ/SystemZInstrInfo.h

enum BranchType {
   BranchCLG,
 
   // An instruction that decrements a 32-bit register and branches if
   // the result is nonzero.
   BranchCT,
 
   // An instruction that decrements a 64-bit register and branches if
   // the result is nonzero.
-  BranchCTG
+  BranchCTG,
+
+  // An instruction representing an asm goto statement.
+  AsmGoto
 };
 
 // Information about a branch instruction.
-struct Branch {
+class Branch {
+  // The target of the branch. In case of INLINEASM_BR, this is nullptr.
+  const MachineOperand *Target;
+
+public:
   // The type of the branch.
   BranchType Type;
 
   // CCMASK_<N> is set if CC might be equal to N.
   unsigned CCValid;
 
   // CCMASK_<N> is set if the branch should be taken when CC == N.
   unsigned CCMask;
 
-  // The target of the branch.
-  const MachineOperand *Target;
-
   Branch(BranchType type, unsigned ccValid, unsigned ccMask,
          const MachineOperand *target)
-    : Type(type), CCValid(ccValid), CCMask(ccMask), Target(target) {}
+    : Target(target), Type(type), CCValid(ccValid), CCMask(ccMask) {}
+
+  bool isRelative() { return Target != nullptr && Target->isReg(); }
+  bool hasMBBTarget() { return Target != nullptr && Target->isMBB(); }
+  MachineBasicBlock *getMBBTarget() {
+    return hasMBBTarget() ? Target->getMBB() : nullptr;
+  }
 };
 
 // Kinds of fused compares in compare-and-* instructions.  Together with type
 // of the converted compare, this identifies the compare-and-*
 // instruction.
 enum FusedCompareType {
   // Relative branch - CRJ etc.
   CompareAndBranch,

lib/Target/SystemZ/SystemZInstrInfo.cpp

while (I != MBB.begin()) {
 
     // A terminator that isn't a branch can't easily be handled by this
     // analysis.
     if (!I->isBranch())
       return true;
 
     // Can't handle indirect branches.
     SystemZII::Branch Branch(getBranchInfo(*I));
-    if (!Branch.Target->isMBB())
+    if (!Branch.hasMBBTarget())
       return true;
 
     // Punt on compound branches.
     if (Branch.Type != SystemZII::BranchNormal)
       return true;
 
     if (Branch.CCMask == SystemZ::CCMASK_ANY) {
       // Handle unconditional branches.
       if (!AllowModify) {
-        TBB = Branch.Target->getMBB();
+        TBB = Branch.getMBBTarget();
         continue;
       }
 
       // If the block has any instructions after a JMP, delete them.
       while (std::next(I) != MBB.end())
         std::next(I)->eraseFromParent();
 
       Cond.clear();
       FBB = nullptr;
 
       // Delete the JMP if it's equivalent to a fall-through.
-      if (MBB.isLayoutSuccessor(Branch.Target->getMBB())) {
+      if (MBB.isLayoutSuccessor(Branch.getMBBTarget())) {
         TBB = nullptr;
         I->eraseFromParent();
         I = MBB.end();
         continue;
       }
 
       // TBB is used to indicate the unconditinal destination.
-      TBB = Branch.Target->getMBB();
+      TBB = Branch.getMBBTarget();
       continue;
     }
 
     // Working from the bottom, handle the first conditional branch.
     if (Cond.empty()) {
       // FIXME: add X86-style branch swap
       FBB = TBB;
-      TBB = Branch.Target->getMBB();
+      TBB = Branch.getMBBTarget();
       Cond.push_back(MachineOperand::CreateImm(Branch.CCValid));
       Cond.push_back(MachineOperand::CreateImm(Branch.CCMask));
       continue;
     }
 
     // Handle subsequent conditional branches.
     assert(Cond.size() == 2 && TBB && "Should have seen a conditional branch");
 
     // Only handle the case where all conditional branches branch to the same
     // destination.
-    if (TBB != Branch.Target->getMBB())
+    if (TBB != Branch.getMBBTarget())
       return true;
 
     // If the conditions are the same, we can leave them alone.
     unsigned OldCCValid = Cond[0].getImm();
     unsigned OldCCMask = Cond[1].getImm();
     if (OldCCValid == Branch.CCValid && OldCCMask == Branch.CCMask)
       continue;
 
unsigned SystemZInstrInfo::removeBranch(MachineBasicBlock &MBB,
   unsigned Count = 0;
 
   while (I != MBB.begin()) {
     --I;
     if (I->isDebugInstr())
       continue;
     if (!I->isBranch())
       break;
-    if (!getBranchInfo(*I).Target->isMBB())
+    if (!getBranchInfo(*I).hasMBBTarget())
       break;
     // Remove the branch.
     I->eraseFromParent();
     I = MBB.end();
     ++Count;
   }
 
   return Count;
case SystemZ::CGRJ:
     return SystemZII::Branch(SystemZII::BranchCG, SystemZ::CCMASK_ICMP,
                              MI.getOperand(2).getImm(), &MI.getOperand(3));
 
   case SystemZ::CLGIJ:
   case SystemZ::CLGRJ:
     return SystemZII::Branch(SystemZII::BranchCLG, SystemZ::CCMASK_ICMP,
                              MI.getOperand(2).getImm(), &MI.getOperand(3));
 
+  case SystemZ::INLINEASM_BR:
+    return SystemZII::Branch(SystemZII::AsmGoto, 0, 0, nullptr);
+
   default:
     llvm_unreachable("Unrecognized branch opcode");
   }
 }
 
 void SystemZInstrInfo::getLoadStoreOpcodes(const TargetRegisterClass *RC,
                                            unsigned &LoadOpcode,
                                            unsigned &StoreOpcode) const {

lib/Target/SystemZ/SystemZLongBranch.cpp

case SystemZ::CLGIJ:
       // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
       Terminator.ExtraRelaxSize = 6;
       break;
     default:
       llvm_unreachable("Unrecognized branch instruction");
     }
     Terminator.Branch = &MI;
     Terminator.TargetBlock =
-      TII->getBranchInfo(MI).Target->getMBB()->getNumber();
+      TII->getBranchInfo(MI).getMBBTarget()->getNumber();
   }
   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() {

lib/Target/SystemZ/SystemZMachineScheduler.cpp

void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
   LLVM_DEBUG(HazardRec->dumpState(););
 
   // Emit incoming terminator(s). Be optimistic and assume that branch
   // prediction will generally do "the right thing".
   for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
        I != SinglePredMBB->end(); I++) {
     LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
     bool TakenBranch = (I->isBranch() &&
-      (TII->getBranchInfo(*I).Target->isReg() || // Relative branch
-       TII->getBranchInfo(*I).Target->getMBB() == MBB));
+                        (TII->getBranchInfo(*I).isRelative() ||
+                         TII->getBranchInfo(*I).getMBBTarget() == MBB));
     HazardRec->emitInstruction(&*I, TakenBranch);
     if (TakenBranch)
       break;
   }
 }
 
 void SystemZPostRASchedStrategy::leaveMBB() {
   LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);

test/CodeGen/SystemZ/asm-20.ll

+; Test that asm goto can be compiled.
+;
+; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z14
+
+define i32 @c() {
+entry:
+  callbr void asm sideeffect "j d", "X"(i8* blockaddress(@c, %d))
+          to label %asm.fallthrough [label %d]
+
+asm.fallthrough:               ; preds = %entry
+  br label %d
+
+d:                             ; preds = %asm.fallthrough, %entry
+  ret i32 undef
+}