[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 ↗

(On Diff #27425)

This can go away now, right?

lib/Target/X86/X86InstrInfo.cpp

3625 ↗

(On Diff #27425)

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

3648 ↗

(On Diff #27425)

OpCode -> Opcode

lib/Target/X86/X86InstrInfo.h

169 ↗

(On Diff #27425)

Inner -> Impl, perhaps?

[atrick]

Looks good but I have one comment inline...

lib/Target/X86/X86InstrInfo.cpp

3640–3641 ↗

(On Diff #27425)

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

3640–3641 ↗

(On Diff #27425)

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 ↗

(On Diff #27425)

Fixed, thanks.

lib/Target/X86/X86InstrInfo.cpp

3625 ↗

(On Diff #27425)

I agree, this should not be an assert.

3648 ↗

(On Diff #27425)

Fixed.

lib/Target/X86/X86InstrInfo.h

169 ↗

(On Diff #27425)

Fixed.

[atrick]

LGTM

llvm/trunk/include/llvm/Target/TargetInstrInfo.h

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 {
+    enum ComparePredicate {
+      PRED_EQ,     // True if two values are equal
+      PRED_NE,     // True if two values are not equal
+      PRED_INVALID // Sentinel value
+    };
+
+    ComparePredicate 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(PRED_INVALID), 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.

llvm/trunk/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 AnalyzeBranchImpl(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, 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, ArrayRef<MachineOperand> Cond,
                         DebugLoc DL) const override;
   bool canInsertSelect(const MachineBasicBlock&, ArrayRef<MachineOperand> Cond,
                        unsigned, unsigned, int&, int&, int&) const override;
   void insertSelect(MachineBasicBlock &MBB,
                     MachineBasicBlock::iterator MI, DebugLoc DL,

llvm/trunk/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::AnalyzeBranchImpl(
+    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 AnalyzeBranchImpl(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 (AnalyzeBranchImpl(MBB, MBP.TrueDest, MBP.FalseDest, Cond, CondBranches,
+                        AllowModify))
+    return true;
+
+  if (Cond.size() != 1)
+    return true;
+
+  assert(MBP.TrueDest && "expected!");
+
+  if (!MBP.FalseDest)
+    MBP.FalseDest = MBB.getNextNode();
+
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+
+  MachineInstr *ConditionDef = nullptr;
+  bool SingleUseCondition = true;
+
+  for (auto I = std::next(MBB.rbegin()), E = MBB.rend(); I != E; ++I) {
+    if (I->modifiesRegister(X86::EFLAGS, TRI)) {
+      ConditionDef = &*I;
+      break;
+    }
+
+    if (I->readsRegister(X86::EFLAGS, TRI))
+      SingleUseCondition = false;
+  }
+
+  if (!ConditionDef)
+    return true;
+
+  if (SingleUseCondition) {
+    for (auto *Succ : MBB.successors())
+      if (Succ->isLiveIn(X86::EFLAGS))
+        SingleUseCondition = false;
+  }
+
+  MBP.ConditionDef = ConditionDef;
+  MBP.SingleUseCondition = SingleUseCondition;
+
+  // Currently we only recognize the simple pattern:
+  //
+  //   test %reg, %reg
+  //   je %label
+  //
+  const unsigned TestOpcode =
+      Subtarget.is64Bit() ? X86::TEST64rr : X86::TEST32rr;
+
+  if (ConditionDef->getOpcode() == TestOpcode &&
+      ConditionDef->getNumOperands() == 3 &&
+      ConditionDef->getOperand(0).isIdenticalTo(ConditionDef->getOperand(1)) &&
+      (Cond[0].getImm() == X86::COND_NE || Cond[0].getImm() == X86::COND_E)) {
+    MBP.LHS = ConditionDef->getOperand(0);
+    MBP.RHS = MachineOperand::CreateImm(0);
+    MBP.Predicate = Cond[0].getImm() == X86::COND_NE
+                        ? MachineBranchPredicate::PRED_NE
+                        : MachineBranchPredicate::PRED_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;