Add "SkipDead" parameter to TargetInstrInfo::DefinesPredicate

[NickGuy]

Summary

Some instructions may be removable through processes such as IfConversion,
however DefinesPredicate can not be made aware of when this should be considered.
This parameter allows DefinesPredicate to distinguish these removable instructions
on a per-call basis, allowing for more fine-grained control from processes like
ifConversion.

Renames DefinesPredicate to ClobbersPredicate, to better reflect it's purpose.

[efriedma]

I guess under this your classification, there are basically three possible kinds of predicable instruction:

1. The instruction doesn't define a predicate
2. The instruction defines a predicate, but the predicate is dead, and predicating it will make the definition go away.
3. The instruction defines a predicate, and it will continue to define a predicate after predication.

If the boolean is specified, we check for 3, but not 2?

Do we really need the boolean to default to false? There are only two callers, as far as I can tell.

Can we rename the function to something like "ClobbersPredicate", if that's what we actually care about here?

I'm a little concerned IfConversion isn't really prepared to deal with the distinction here: in some cases, if conversion doesn't predicate all the instructions in the if-converted block.

For Thumb, would it ever make sense to undo size reduction if it would unblock if-conversion? (Off the top of my head, I guess this would only have an impact if we wanted to predicate something like an "adds" with a predicate that isn't dead, so maybe not worth investing any effort.)

[samparker]

Can we rename the function to something like "ClobbersPredicate", if that's what we actually care about here?

+1 from me. I also wonder renaming IncludesRemovable to something like Ignore/SkipDead?

[NickGuy]

Do we really need the boolean to default to false? There are only two callers, as far as I can tell.

It was done to reduce the footprint of this patch to be the interface change only, with any implementation changes in subsequent patches. I'll remove the default and hoist the call site changes up to this patch.

Can we rename the function to something like "ClobbersPredicate", if that's what we actually care about here?

I don't think that that's all we care about, unfortunately. A number of the backends this change effects check whether a predicate is defined or clobbered, while a few don't seem to have a concept of predicate clobbering (e.g. in R600InstrInfo).

For Thumb, would it ever make sense to undo size reduction if it would unblock if-conversion? (Off the top of my head, I guess this would only have an impact if we wanted to predicate something like an "adds" with a predicate that isn't dead, so maybe not worth investing any effort.)

Currently, the Thumb reduction pass is only invoked before IfConversion if we're optimising for size, so we'd prefer to keep the smaller size if possible (this change is an attempt to find a happy middle-ground, getting the performance gain from IfConversion while not sacrificing size)

I also wonder renaming IncludesRemovable to something like Ignore/SkipDead?

Done, will be included in the next patch

[NickGuy]

I'm a little concerned IfConversion isn't really prepared to deal with the distinction here: in some cases, if conversion doesn't predicate all the instructions in the if-converted block.

I can't see any case where IfConversion would only predicate a portion of a block. The closest I can find is with common instructions and diamond conversion, but the common instructions are moved to the preceding block, and the IfConversion feasibility is then re-evaluated before any predication is performed.

[efriedma]

LGTM

but the common instructions are moved to the preceding block, and the IfConversion feasibility is then re-evaluated before any predication is performed.

I don't think that's an accurate description of how it works... but I guess the conclusion is correct: instructions we plan to CSE are treated separately from instructions we plan to predicate.

[SjoerdMeijer]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

1402

A post-commit nit while I am catching up with this.
I found Eli's explanation very useful:

1. The instruction doesn't define a predicate
2. The instruction defines a predicate, but the predicate is dead, and predicating it will make the definition go away.
3. The instruction defines a predicate, and it will continue to define a predicate after predication.

I think would be useful to add this to the comments, plus what SkipDead effects.
Don't think that would need a review.

llvm/include/llvm/CodeGen/TargetInstrInfo.h

public:
   virtual bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
                                  ArrayRef<MachineOperand> Pred2) const {
     return false;
   }
 
   /// If the specified instruction defines any predicate
   /// or condition code register(s) used for predication, returns true as well
   /// as the definition predicate(s) by reference.
-  virtual bool DefinesPredicate(MachineInstr &MI,
-                                std::vector<MachineOperand> &Pred) const {
+  /// SkipDead should be set to false at any point that dead
+  /// predicate instructions should be considered as being defined.
+  /// A dead predicate instruction is one that is guaranteed to be removed
+  /// after a call to PredicateInstruction.
+  virtual bool ClobbersPredicate(MachineInstr &MI,
+                                 std::vector<MachineOperand> &Pred,
+                                 bool SkipDead) const {
     return false;
   }
 
   /// Return true if the specified instruction can be predicated.
   /// By default, this returns true for every instruction with a
   /// PredicateOperand.
   virtual bool isPredicable(const MachineInstr &MI) const {
     return MI.getDesc().isPredicable();

llvm/lib/CodeGen/IfConversion.cpp

while (TIB != TIE && FIB != FIE) {
     FIB = skipDebugInstructionsForward(FIB, FIE);
     if (TIB == TIE || FIB == FIE)
       break;
     if (!TIB->isIdenticalTo(*FIB))
       break;
     // A pred-clobbering instruction in the shared portion prevents
     // if-conversion.
     std::vector<MachineOperand> PredDefs;
-    if (TII->DefinesPredicate(*TIB, PredDefs))
+    if (TII->ClobbersPredicate(*TIB, PredDefs, false))
       return false;
     // If we get all the way to the branch instructions, don't count them.
     if (!TIB->isBranch())
       ++Dups1;
     ++TIB;
     ++FIB;
   }
 
if (BBI.ClobbersPred && !isPredicated) {
       // unpredicated instructions cannot be correctly predicated.
       BBI.IsUnpredicable = true;
       return;
     }
 
     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
     // still potentially predicable.
     std::vector<MachineOperand> PredDefs;
-    if (TII->DefinesPredicate(MI, PredDefs))
+    if (TII->ClobbersPredicate(MI, PredDefs, true))
       BBI.ClobbersPred = true;
 
     if (!TII->isPredicable(MI)) {
       BBI.IsUnpredicable = true;
       return;
     }
   }
 }

llvm/lib/Target/AMDGPU/R600InstrInfo.h

bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles,
                            BranchProbability Probability) const override ;
 
   bool isProfitableToIfCvt(MachineBasicBlock &TMBB,
                            unsigned NumTCycles, unsigned ExtraTCycles,
                            MachineBasicBlock &FMBB,
                            unsigned NumFCycles, unsigned ExtraFCycles,
                            BranchProbability Probability) const override;
 
-  bool DefinesPredicate(MachineInstr &MI,
-                        std::vector<MachineOperand> &Pred) const override;
+  bool ClobbersPredicate(MachineInstr &MI, std::vector<MachineOperand> &Pred,
+                         bool SkipDead) const override;
 
   bool isProfitableToUnpredicate(MachineBasicBlock &TMBB,
                                  MachineBasicBlock &FMBB) const override;
 
   bool PredicateInstruction(MachineInstr &MI,
                             ArrayRef<MachineOperand> Pred) const override;
 
   unsigned int getPredicationCost(const MachineInstr &) const override;

llvm/lib/Target/AMDGPU/R600InstrInfo.cpp

case R600::PRED_SEL_ONE:
     MO2.setReg(R600::PRED_SEL_ZERO);
     break;
   default:
     return true;
   }
   return false;
 }
 
-bool R600InstrInfo::DefinesPredicate(MachineInstr &MI,
-                                     std::vector<MachineOperand> &Pred) const {
+bool R600InstrInfo::ClobbersPredicate(MachineInstr &MI,
+                                      std::vector<MachineOperand> &Pred,
+                                      bool SkipDead) const {
   return isPredicateSetter(MI.getOpcode());
 }
 
 bool R600InstrInfo::PredicateInstruction(MachineInstr &MI,
                                          ArrayRef<MachineOperand> Pred) const {
   int PIdx = MI.findFirstPredOperandIdx();
 
   if (MI.getOpcode() == R600::CF_ALU) {

llvm/lib/Target/ARM/ARMBaseInstrInfo.h

public:
   }
 
   bool PredicateInstruction(MachineInstr &MI,
                             ArrayRef<MachineOperand> Pred) const override;
 
   bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
                          ArrayRef<MachineOperand> Pred2) const override;
 
-  bool DefinesPredicate(MachineInstr &MI,
-                        std::vector<MachineOperand> &Pred) const override;
+  bool ClobbersPredicate(MachineInstr &MI, std::vector<MachineOperand> &Pred,
+                         bool SkipDead) const override;
 
   bool isPredicable(const MachineInstr &MI) const override;
 
   // CPSR defined in instruction
   static bool isCPSRDefined(const MachineInstr &MI);
   bool isAddrMode3OpImm(const MachineInstr &MI, unsigned Op) const;
   bool isAddrMode3OpMinusReg(const MachineInstr &MI, unsigned Op) const;
 

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

case ARMCC::LS:
     return CC2 == ARMCC::LO || CC2 == ARMCC::EQ;
   case ARMCC::GE:
     return CC2 == ARMCC::GT;
   case ARMCC::LE:
     return CC2 == ARMCC::LT;
   }
 }
 
-bool ARMBaseInstrInfo::DefinesPredicate(
-    MachineInstr &MI, std::vector<MachineOperand> &Pred) const {
+bool ARMBaseInstrInfo::ClobbersPredicate(MachineInstr &MI,
+                                         std::vector<MachineOperand> &Pred,
+                                         bool SkipDead) const {
   bool Found = false;
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI.getOperand(i);
     if ((MO.isRegMask() && MO.clobbersPhysReg(ARM::CPSR)) ||
         (MO.isReg() && MO.isDef() && MO.getReg() == ARM::CPSR)) {
       Pred.push_back(MO);
       Found = true;
     }

llvm/lib/Target/Hexagon/HexagonInstrInfo.h

public:
   /// Returns true if the first specified predicate
   /// subsumes the second, e.g. GE subsumes GT.
   bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
                          ArrayRef<MachineOperand> Pred2) const override;
 
   /// If the specified instruction defines any predicate
   /// or condition code register(s) used for predication, returns true as well
   /// as the definition predicate(s) by reference.
-  bool DefinesPredicate(MachineInstr &MI,
-                        std::vector<MachineOperand> &Pred) const override;
+  bool ClobbersPredicate(MachineInstr &MI, std::vector<MachineOperand> &Pred,
+                         bool SkipDead) const override;
 
   /// Return true if the specified instruction can be predicated.
   /// By default, this returns true for every instruction with a
   /// PredicateOperand.
   bool isPredicable(const MachineInstr &MI) const override;
 
   /// Test if the given instruction should be considered a scheduling boundary.
   /// This primarily includes labels and terminators.

llvm/lib/Target/Hexagon/HexagonInstrInfo.cpp

 }
 
 bool HexagonInstrInfo::SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
       ArrayRef<MachineOperand> Pred2) const {
   // TODO: Fix this
   return false;
 }
 
-bool HexagonInstrInfo::DefinesPredicate(MachineInstr &MI,
-      std::vector<MachineOperand> &Pred) const {
+bool HexagonInstrInfo::ClobbersPredicate(MachineInstr &MI,
+                                         std::vector<MachineOperand> &Pred,
+                                         bool SkipDead) const {
   const HexagonRegisterInfo &HRI = *Subtarget.getRegisterInfo();
 
   for (unsigned oper = 0; oper < MI.getNumOperands(); ++oper) {
     MachineOperand MO = MI.getOperand(oper);
     if (MO.isReg()) {
       if (!MO.isDef())
         continue;
       const TargetRegisterClass* RC = HRI.getMinimalPhysRegClass(MO.getReg());

llvm/lib/Target/PowerPC/PPCInstrInfo.h

bool isSchedulingBoundary(const MachineInstr &MI,
                             const MachineFunction &MF) const override;
 
   bool PredicateInstruction(MachineInstr &MI,
                             ArrayRef<MachineOperand> Pred) const override;
 
   bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
                          ArrayRef<MachineOperand> Pred2) const override;
 
-  bool DefinesPredicate(MachineInstr &MI,
-                        std::vector<MachineOperand> &Pred) const override;
+  bool ClobbersPredicate(MachineInstr &MI, std::vector<MachineOperand> &Pred,
+                         bool SkipDead) const override;
 
   // Comparison optimization.
 
   bool analyzeCompare(const MachineInstr &MI, Register &SrcReg,
                       Register &SrcReg2, int &Mask, int &Value) const override;
 
   bool optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg,
                             Register SrcReg2, int Mask, int Value,

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

if (P1 == PPC::PRED_LE &&
     return true;
   if (P1 == PPC::PRED_GE &&
       (P2 == PPC::PRED_GT || P2 == PPC::PRED_EQ))
     return true;
 
   return false;
 }
 
-bool PPCInstrInfo::DefinesPredicate(MachineInstr &MI,
-                                    std::vector<MachineOperand> &Pred) const {
+bool PPCInstrInfo::ClobbersPredicate(MachineInstr &MI,
+                                     std::vector<MachineOperand> &Pred,
+                                     bool SkipDead) const {
   // Note: At the present time, the contents of Pred from this function is
   // unused by IfConversion. This implementation follows ARM by pushing the
   // CR-defining operand. Because the 'DZ' and 'DNZ' count as types of
   // predicate, instructions defining CTR or CTR8 are also included as
   // predicate-defining instructions.
 
   const TargetRegisterClass *RCs[] =
     { &PPC::CRRCRegClass, &PPC::CRBITRCRegClass,