[GlobalISel] Extend not_cmp_fold to work on conditional expressions

[arsenm]

Tests missing

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2173–2174

This is only better if this is fed by a compare you can invert. This should probably not do this if it finds some other i1 def.

We also should probably check if the inverted condcode is legal, but I guess we're missing cond code legality infrastructure (and none of the targets with gisel now don't need it)

2176–2177

This is illegal, you can just assume these are registers

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2173–2174

This is only better if this is fed by a compare you can invert.

We process the whole expression tree and return false if we find anything that is not an AND or OR or a comparison.

[foad]

Remove unnecessary check. Improve comments.

[foad]

Add some tests.

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2154

A MIR-esque example would be handy here, just to make it explicit what's being matched.

2155

I don't think here's any reason to talk about an index I here; from the looks of it, the below loop can be a range-based for?

2162

Usually people assert that the result of MRI.getVRegDef(...) isn't null.

I'm not sure if that's actually necessary in this case though; I *think* that it can only be null when you have a physreg, but I'm not entirely sure.

2193

A MIR-esque example would be useful here too?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2162

getVRegDef should never fail for gMIR.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2155

No, it's slightly tricky. It can't be a range-based for because we push more stuff into RegsToNegate inside the loop. It's a worklist algorithm, but without using a separate worklist vector.

[aemerson]

Why isn't this caught in InstCombine?

[arsenm]

In D86709#2242520, @aemerson wrote:

Why isn't this caught in InstCombine?

This is going to show up as branch conditions are swapped for control flow lowering

[arsenm]

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir

224 ↗

(On Diff #288356)

Should have some cases where the conditions are a G_TRUNC or some other not-compare source

[foad]

Rebase. Add a non-matching test case.

[foad]

In D86709#2242546, @arsenm wrote:

In D86709#2242520, @aemerson wrote:

Why isn't this caught in InstCombine?

This is going to show up as branch conditions are swapped for control flow lowering

Right, the xor is introduced by IRTranslator::emitSwitchCase. Perhaps it could be optimized at that point, instead of later in a combiner pass, but I'm not sure how feasible that is. I guess at that point you can't do accurate hasOneNonDBGUse checks?

[aemerson]

LGTM.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2139

SmallVectorImpl?

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

public:
   /// LHS & mask == LHS. (E.g., an all-ones value.)
   ///
   /// \param [in] MI - The G_AND instruction.
   /// \param [out] Replacement - A register the G_AND should be replaced with on
   /// success.
   bool matchAndWithTrivialMask(MachineInstr &MI, Register &Replacement);
 
   /// Combine inverting a result of a compare into the opposite cond code.
-  bool matchNotCmp(MachineInstr &MI, Register &CmpReg);
-  bool applyNotCmp(MachineInstr &MI, Register &CmpReg);
+  bool matchNotCmp(MachineInstr &MI, SmallVector<Register, 4> &RegsToNegate);
+  bool applyNotCmp(MachineInstr &MI, SmallVector<Register, 4> &RegsToNegate);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 
 private:
   // Memcpy family optimization helpers.
   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,

llvm/include/llvm/Target/GlobalISel/Combine.td

 def and_trivial_mask_matchinfo : GIDefMatchData<"Register">;
 def and_trivial_mask: GICombineRule <
   (defs root:$root, and_trivial_mask_matchinfo:$matchinfo),
   (match (wip_match_opcode G_AND):$root,
          [{ return Helper.matchAndWithTrivialMask(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
 >;
 
-def not_cmp_fold_matchinfo : GIDefMatchData<"Register">;
+def not_cmp_fold_matchinfo : GIDefMatchData<"SmallVector<Register, 4>">;
 def not_cmp_fold : GICombineRule<
   (defs root:$d, not_cmp_fold_matchinfo:$info),
   (match (wip_match_opcode G_XOR): $d,
   [{ return Helper.matchNotCmp(*${d}, ${info}); }]),
   (apply [{ return Helper.applyNotCmp(*${d}, ${info}); }])
 >;
 
 // FIXME: These should use the custom predicate feature once it lands.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

bool CombinerHelper::matchAndWithTrivialMask(MachineInstr &MI,
   APInt Mask(DstTy.getSizeInBits(), Cst);
   if (!Mask.isMask())
     return false;
 
   // Now, let's check that x & Mask == x. If this is true, then x & ~Mask == 0.
   return KB->maskedValueIsZero(Replacement, ~Mask);
 }
 
-bool CombinerHelper::matchNotCmp(MachineInstr &MI, Register &CmpReg) {
+bool CombinerHelper::matchNotCmp(MachineInstr &MI,
+                                 SmallVector<Register, 4> &RegsToNegate) {
   assert(MI.getOpcode() == TargetOpcode::G_XOR);
   Register XorSrc;
   int64_t Cst;
   // We match xor(src, true) here.
   if (!mi_match(MI.getOperand(0).getReg(), MRI,
                 m_GXor(m_Reg(XorSrc), m_ICst(Cst))))
     return false;
 
   const auto &TLI = *Builder.getMF().getSubtarget().getTargetLowering();
   LLT Ty = MRI.getType(MI.getOperand(0).getReg());
   // For i1, Cst will always be -1 regardless of boolean contents.
   if (!isConstTrueVal(TLI, Cst) && !(Ty == LLT::scalar(1) && Cst == -1))
     return false;
 
-  // Now try match src to either icmp or fcmp.
-  if (!mi_match(XorSrc, MRI, m_GICmp(m_Pred(), m_Reg(), m_Reg()))) {
-    // Try fcmp.
-    if (!mi_match(XorSrc, MRI, m_GFCmp(m_Pred(), m_Reg(), m_Reg())))
+  // Check that XorSrc is the root of a tree of comparisons combined with ANDs
+  // and ORs. The suffix of RegsToNegate starting from index I is used a work
+  // list of tree nodes to visit.
+  RegsToNegate.push_back(XorSrc);
+  for (unsigned I = 0; I < RegsToNegate.size(); ++I) {
+    Register Reg = RegsToNegate[I];
+    if (!MRI.hasOneNonDBGUse(Reg))
       return false;
-  }
-  if (!MRI.hasOneNonDBGUse(XorSrc))
+    MachineInstr *Def = MRI.getVRegDef(Reg);
+    switch (Def->getOpcode()) {
+    default:
+      // Don't match if the tree contains anything other than ANDs, ORs and
+      // comparisons.
       return false;
-  CmpReg = XorSrc;
+    case TargetOpcode::G_ICMP:
+    case TargetOpcode::G_FCMP:
+      // When we apply the combine we will invert the predicate.
+      break;
+    case TargetOpcode::G_AND:
+    case TargetOpcode::G_OR:
+      // Implement De Morgan's laws:
+      // ~(x & y) -> ~x | ~y
+      // ~(x | y) -> ~x & ~y
+      // When we apply the combine we will change the opcode and recursively
+      // negate the operands.
+      RegsToNegate.push_back(Def->getOperand(1).getReg());
+      RegsToNegate.push_back(Def->getOperand(2).getReg());
+      break;
+    }
+  }
   return true;
 }
 
-bool CombinerHelper::applyNotCmp(MachineInstr &MI, Register &CmpReg) {
-  MachineInstr *CmpDef = MRI.getVRegDef(CmpReg);
-  assert(CmpDef && "Should have been given an MI reg");
-  assert(CmpDef->getOpcode() == TargetOpcode::G_ICMP ||
-         CmpDef->getOpcode() == TargetOpcode::G_FCMP);
-
-  Observer.changingInstr(*CmpDef);
-  MachineOperand &PredOp = CmpDef->getOperand(1);
+bool CombinerHelper::applyNotCmp(MachineInstr &MI,
+                                 SmallVector<Register, 4> &RegsToNegate) {
+  for (Register Reg : RegsToNegate) {
+    MachineInstr *Def = MRI.getVRegDef(Reg);
+    Observer.changingInstr(*Def);
+    // For each comparison, invert the opcode. For each AND and OR, change the
+    // opcode.
+    switch (Def->getOpcode()) {
+    default:
+      llvm_unreachable("Unexpected opcode");
+    case TargetOpcode::G_ICMP:
+    case TargetOpcode::G_FCMP: {
+      MachineOperand &PredOp = Def->getOperand(1);
       CmpInst::Predicate NewP = CmpInst::getInversePredicate(
           (CmpInst::Predicate)PredOp.getPredicate());
       PredOp.setPredicate(NewP);
-  Observer.changedInstr(*CmpDef);
+      break;
+    }
+    case TargetOpcode::G_AND:
+      Def->setDesc(Builder.getTII().get(TargetOpcode::G_OR));
+      break;
+    case TargetOpcode::G_OR:
+      Def->setDesc(Builder.getTII().get(TargetOpcode::G_AND));
+      break;
+    }
+    Observer.changedInstr(*Def);
+  }
 
-  replaceRegWith(MRI, MI.getOperand(0).getReg(),
-                 CmpDef->getOperand(0).getReg());
+  replaceRegWith(MRI, MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
   MI.eraseFromParent();
   return true;
 }
 
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   if (tryCombineExtendingLoads(MI))
     return true;
   if (tryCombineIndexedLoadStore(MI))
     return true;
   return false;
 }