[TargetInstrInfo] Add new hook: AnalyzeBranchPredicate.

[sanjoy]

Summary

NFC: no one uses AnalyzeBranchPredicate yet.

Add TargetInstrInfo::AnalyzeBranchPredicate and implement for x86. A
later change adding support for page-fault based implicit null checks
depends on this.

[sanjoy]

ping

[sanjoy]

• address review: don't use CmpInst::Predicate, but use a separate enum instead

[ab]

This seems reasonable to me, but I'll let Andy have the final say.

-Ahmed

include/llvm/Target/TargetInstrInfo.h

23

This can go away now, right?

lib/Target/X86/X86InstrInfo.cpp

3619

Why not return true if Cond.size() == 0? (i.e. the branch isn't conditional?)

3642

OpCode -> Opcode

lib/Target/X86/X86InstrInfo.h

169

Inner -> Impl, perhaps?

[atrick]

Looks good but I have one comment inline...

lib/Target/X86/X86InstrInfo.cpp

3634–3635

This looks strange to me. Do you really need to prove that the ConditionDef only has a single use? If so, I think you should:

• check that EFLAGS is not live into any successors

• Walk backward from the branch looking for a Def of EFLAGS before any other use of EFLAGS.

You may have EFLAGS readers other than conditional branches.
killsRegister is a crutch that should be avoided whenever possible. It might not be accurate.

[sanjoy]

lib/Target/X86/X86InstrInfo.cpp

3634–3635

Do you really need to prove that the ConditionDef only has a single use?

Preferably. I'd like to remove the test instruction as part of the implicit null check optimization.

I'll make the change you suggested.

[sanjoy]

• address review

include/llvm/Target/TargetInstrInfo.h

23

Fixed, thanks.

lib/Target/X86/X86InstrInfo.cpp

3619

I agree, this should not be an assert.

3642

Fixed.

lib/Target/X86/X86InstrInfo.h

169

Fixed.

[atrick]

LGTM

include/llvm/Target/TargetInstrInfo.h

 #define LLVM_TARGET_TARGETINSTRINFO_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/MachineCombinerPattern.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/IR/Instructions.h"
 
 namespace llvm {
 
 class InstrItineraryData;
 class LiveVariables;
 class MCAsmInfo;
 class MachineMemOperand;
 class MachineRegisterInfo;
public:
   ///
   virtual bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                              MachineBasicBlock *&FBB,
                              SmallVectorImpl<MachineOperand> &Cond,
                              bool AllowModify = false) const {
     return true;
   }
 
+  /// Represents a predicate at the MachineFunction level.  The control flow a
+  /// MachineBranchPredicate represents is:
+  ///
+  ///  Reg <def>= LHS `Predicate` RHS         == ConditionDef
+  ///  if Reg then goto TrueDest else goto FalseDest
+  ///
+  struct MachineBranchPredicate {
+    CmpInst::Predicate Predicate;
+    MachineOperand LHS;
+    MachineOperand RHS;
+    MachineBasicBlock *TrueDest;
+    MachineBasicBlock *FalseDest;
+    MachineInstr *ConditionDef;
+
+    /// SingleUseCondition is true if ConditionDef is dead except for the
+    /// branch(es) at the end of the basic block.
+    ///
+    bool SingleUseCondition;
+
+    explicit MachineBranchPredicate()
+        : Predicate(CmpInst::BAD_ICMP_PREDICATE),
+          LHS(MachineOperand::CreateImm(0)), RHS(MachineOperand::CreateImm(0)),
+          TrueDest(nullptr), FalseDest(nullptr), ConditionDef(nullptr),
+          SingleUseCondition(false) {}
+  };
+
+  /// Analyze the branching code at the end of MBB and parse it into the
+  /// MachineBranchPredicate structure if possible.  Returns false on success
+  /// and true on failure.
+  ///
+  /// If AllowModify is true, then this routine is allowed to modify the basic
+  /// block (e.g. delete instructions after the unconditional branch).
+  ///
+  virtual bool AnalyzeBranchPredicate(MachineBasicBlock &MBB,
+                                      MachineBranchPredicate &MBP,
+                                      bool AllowModify = false) const {
+    return true;
+  }
+
   /// Remove the branching code at the end of the specific MBB.
   /// This is only invoked in cases where AnalyzeBranch returns success. It
   /// returns the number of instructions that were removed.
   virtual unsigned RemoveBranch(MachineBasicBlock &MBB) const {
     llvm_unreachable("Target didn't implement TargetInstrInfo::RemoveBranch!");
   }
 
   /// Insert branch code into the end of the specified MachineBasicBlock.

lib/Target/X86/X86InstrInfo.h

class X86InstrInfo final : public X86GenInstrInfo {
   MemOp2RegOpTableType MemOp2RegOpTable;
 
   static void AddTableEntry(RegOp2MemOpTableType &R2MTable,
                             MemOp2RegOpTableType &M2RTable,
                             unsigned RegOp, unsigned MemOp, unsigned Flags);
 
   virtual void anchor();
 
+  bool AnalyzeBranchInner(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
+                          MachineBasicBlock *&FBB,
+                          SmallVectorImpl<MachineOperand> &Cond,
+                          SmallVectorImpl<MachineInstr *> &CondBranches,
+                          bool AllowModify) const;
+
 public:
   explicit X86InstrInfo(X86Subtarget &STI);
 
   /// getRegisterInfo - TargetInstrInfo is a superset of MRegister info.  As
   /// such, whenever a client has an instance of instruction info, it should
   /// always be able to get register info as well (through this method).
   ///
   const X86RegisterInfo &getRegisterInfo() const { return RI; }
public:
   bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify) const override;
 
   bool getMemOpBaseRegImmOfs(MachineInstr *LdSt, bool &IsLoadOp,
                              unsigned &BaseReg, unsigned &Offset,
                              const TargetRegisterInfo *TRI) const override;
+  bool AnalyzeBranchPredicate(MachineBasicBlock &MBB,
+                              TargetInstrInfo::MachineBranchPredicate &MBP,
+                              bool AllowModify = false) const override;
+
   unsigned RemoveBranch(MachineBasicBlock &MBB) const override;
   unsigned InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                         MachineBasicBlock *FBB,
                         const SmallVectorImpl<MachineOperand> &Cond,
                         DebugLoc DL) const override;
   bool canInsertSelect(const MachineBasicBlock&,
                        const SmallVectorImpl<MachineOperand> &Cond,
                        unsigned, unsigned, int&, int&, int&) const override;

lib/Target/X86/X86InstrInfo.cpp

bool X86InstrInfo::isUnpredicatedTerminator(const MachineInstr *MI) const {
   // Conditional branch is a special case.
   if (MI->isBranch() && !MI->isBarrier())
     return true;
   if (!MI->isPredicable())
     return true;
   return !isPredicated(MI);
 }
 
-bool X86InstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
-                                 MachineBasicBlock *&TBB,
-                                 MachineBasicBlock *&FBB,
-                                 SmallVectorImpl<MachineOperand> &Cond,
-                                 bool AllowModify) const {
+bool X86InstrInfo::AnalyzeBranchInner(
+    MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB,
+    SmallVectorImpl<MachineInstr *> &CondBranches, bool AllowModify) const {
+
   // Start from the bottom of the block and work up, examining the
   // terminator instructions.
   MachineBasicBlock::iterator I = MBB.end();
   MachineBasicBlock::iterator UnCondBrIter = MBB.end();
   while (I != MBB.begin()) {
     --I;
     if (I->isDebugValue())
       continue;
if (Cond.empty()) {
         UnCondBrIter = MBB.end();
         I = MBB.end();
         continue;
       }
 
       FBB = TBB;
       TBB = I->getOperand(0).getMBB();
       Cond.push_back(MachineOperand::CreateImm(BranchCode));
+      CondBranches.push_back(I);
       continue;
     }
 
     // Handle subsequent conditional branches. Only handle the case where all
     // conditional branches branch to the same destination and their condition
     // opcodes fit one of the special multi-branch idioms.
     assert(Cond.size() == 1);
     assert(TBB);
else if ((OldBranchCode == X86::COND_P &&
              (OldBranchCode == X86::COND_NE &&
               BranchCode == X86::COND_P))
       BranchCode = X86::COND_NE_OR_P;
     else
       return true;
 
     // Update the MachineOperand.
     Cond[0].setImm(BranchCode);
+    CondBranches.push_back(I);
   }
 
   return false;
 }
 
+bool X86InstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
+                                 MachineBasicBlock *&TBB,
+                                 MachineBasicBlock *&FBB,
+                                 SmallVectorImpl<MachineOperand> &Cond,
+                                 bool AllowModify) const {
+  SmallVector<MachineInstr *, 4> CondBranches;
+  return AnalyzeBranchInner(MBB, TBB, FBB, Cond, CondBranches, AllowModify);
+}
+
+bool X86InstrInfo::AnalyzeBranchPredicate(MachineBasicBlock &MBB,
+                                          MachineBranchPredicate &MBP,
+                                          bool AllowModify) const {
+  using namespace std::placeholders;
+
+  SmallVector<MachineOperand, 4> Cond;
+  SmallVector<MachineInstr *, 4> CondBranches;
+  if (AnalyzeBranchInner(MBB, MBP.TrueDest, MBP.FalseDest, Cond, CondBranches,
+                         AllowModify))
+    return true;
+
+  assert(Cond.size() == 1 && MBP.TrueDest && "expected!");
+
+  if (!MBP.FalseDest)
+    MBP.FalseDest = MBB.getNextNode();
+
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+
+  auto DefFlagsI = std::find_if(
+      MBB.rbegin(), MBB.rend(),
+      std::bind(&MachineInstr::modifiesRegister, _1, X86::EFLAGS, TRI));
+
+  if (DefFlagsI == MBB.rend())
+    return true;
+
+  MBP.ConditionDef = &*DefFlagsI;
+  MBP.SingleUseCondition = CondBranches.size() == 1 &&
+                           CondBranches[0]->killsRegister(X86::EFLAGS, TRI);
+
+  // Currently we only recognize the simple pattern:
+  //
+  //   test %reg, %reg
+  //   je %label
+  //
+  const unsigned TestOpCode =
+    Subtarget.is64Bit() ? X86::TEST64rr : X86::TEST32rr;
+
+  if (DefFlagsI->getOpcode() == TestOpCode &&
+      DefFlagsI->getNumOperands() == 3 &&
+      DefFlagsI->getOperand(0).isIdenticalTo(DefFlagsI->getOperand(1)) &&
+      (Cond[0].getImm() == X86::COND_NE || Cond[0].getImm() == X86::COND_E)) {
+    MBP.LHS = DefFlagsI->getOperand(0);
+    MBP.RHS = MachineOperand::CreateImm(0);
+    MBP.Predicate =
+        Cond[0].getImm() == X86::COND_NE ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
+    return false;
+  }
+
+  return true;
+}
+
 unsigned X86InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
   MachineBasicBlock::iterator I = MBB.end();
   unsigned Count = 0;
 
   while (I != MBB.begin()) {
     --I;
     if (I->isDebugValue())
       continue;