[GlobalISel] Extend not_cmp_fold to work on conditional expressions

[arsenm]

Tests missing

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2289–2290

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)

2292–2293

This is illegal, you can just assume these are registers

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2289–2290

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

2268–2276

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

2269

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?

2278

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.

2329

A MIR-esque example would be useful here too?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2278

getVRegDef should never fail for gMIR.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2269

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

227

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

2247

SmallVectorImpl?

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

public:
   /// \param [out] Replacement - A register the G_AND should be replaced with on
   /// success.
   bool matchAndWithTrivialMask(MachineInstr &MI, Register &Replacement);
 
   /// \return true if \p MI is a G_SEXT_INREG that can be erased.
   bool matchRedundantSExtInReg(MachineInstr &MI);
 
   /// 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, SmallVectorImpl<Register> &RegsToNegate);
+  bool applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &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 ext_ext_fold_matchinfo : GIDefMatchData<"std::tuple<Register, unsigned>">;
 def ext_ext_fold: GICombineRule <
   (defs root:$root, ext_ext_fold_matchinfo:$matchinfo),
   (match (wip_match_opcode G_ANYEXT, G_SEXT, G_ZEXT):$root,
          [{ return Helper.matchCombineExtOfExt(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.applyCombineExtOfExt(*${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

 
 static bool isConstValidTrue(const TargetLowering &TLI, unsigned ScalarSizeBits,
                              int64_t Cst, bool IsVector, bool IsFP) {
   // For i1, Cst will always be -1 regardless of boolean contents.
   return (ScalarSizeBits == 1 && Cst == -1) ||
          isConstTrueVal(TLI, Cst, IsVector, IsFP);
 }
 
-bool CombinerHelper::matchNotCmp(MachineInstr &MI, Register &CmpReg) {
+bool CombinerHelper::matchNotCmp(MachineInstr &MI,
+                                 SmallVectorImpl<Register> &RegsToNegate) {
   assert(MI.getOpcode() == TargetOpcode::G_XOR);
   LLT Ty = MRI.getType(MI.getOperand(0).getReg());
   const auto &TLI = *Builder.getMF().getSubtarget().getTargetLowering();
   Register XorSrc;
   Register CstReg;
-  int64_t Cst;
   // We match xor(src, true) here.
   if (!mi_match(MI.getOperand(0).getReg(), MRI,
                 m_GXor(m_Reg(XorSrc), m_Reg(CstReg))))
     return false;
 
   if (!MRI.hasOneNonDBGUse(XorSrc))
     return false;
 
-  // Now try match src to either icmp or fcmp.
+  // 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);
+  // Remember whether the comparisons are all integer or all floating point.
+  bool IsInt = false;
   bool IsFP = false;
-  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())))
+  for (unsigned I = 0; I < RegsToNegate.size(); ++I) {
+    Register Reg = RegsToNegate[I];
+    if (!MRI.hasOneNonDBGUse(Reg))
+      return false;
+    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;
+    case TargetOpcode::G_ICMP:
+      if (IsFP)
+        return false;
+      IsInt = true;
+      // When we apply the combine we will invert the predicate.
+      break;
+    case TargetOpcode::G_FCMP:
+      if (IsInt)
         return false;
       IsFP = true;
+      // 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;
+    }
   }
 
+  // Now we know whether the comparisons are integer or floating point, check
+  // the constant in the xor.
+  int64_t Cst;
   if (Ty.isVector()) {
     MachineInstr *CstDef = MRI.getVRegDef(CstReg);
     auto MaybeCst = getBuildVectorConstantSplat(*CstDef, MRI);
     if (!MaybeCst)
       return false;
     if (!isConstValidTrue(TLI, Ty.getScalarSizeInBits(), *MaybeCst, true, IsFP))
       return false;
   } else {
     if (!mi_match(CstReg, MRI, m_ICst(Cst)))
       return false;
     if (!isConstValidTrue(TLI, Ty.getSizeInBits(), Cst, false, IsFP))
       return false;
   }
 
-  CmpReg = XorSrc;
   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,
+                                 SmallVectorImpl<Register> &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;
 }

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

bb.1:
     %2:_(s1) = G_CONSTANT i1 1
     %splat_true:_(<4 x s1>) = G_BUILD_VECTOR %2, %2, %2, %2
     %3:_(<4 x s1>) = G_ICMP intpred(sgt), %0(<4 x s32>), %splat_op2
     %4:_(<4 x s1>) = G_XOR %3, %splat_true
     %5:_(<4 x s32>) = G_ANYEXT %4
     $q0 = COPY %5(<4 x s32>)
     RET_ReallyLR implicit $q0
 ...
+---
+name: icmp_and_icmp
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp_and_icmp
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sle), [[COPY]](s64), [[C]]
+    ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ule), [[COPY]](s64), [[C]]
+    ; CHECK: [[OR:%[0-9]+]]:_(s1) = G_OR [[ICMP]], [[ICMP1]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[OR]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_ICMP intpred(ugt), %0(s64), %1
+    %5:_(s1) = G_AND %3, %4
+    %6:_(s1) = G_XOR %5, %2
+    %7:_(s32) = G_ANYEXT %6
+    $w0 = COPY %7(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name: icmp_or_icmp
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp_or_icmp
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sle), [[COPY]](s64), [[C]]
+    ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ule), [[COPY]](s64), [[C]]
+    ; CHECK: [[AND:%[0-9]+]]:_(s1) = G_AND [[ICMP]], [[ICMP1]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[AND]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_ICMP intpred(ugt), %0(s64), %1
+    %5:_(s1) = G_OR %3, %4
+    %6:_(s1) = G_XOR %5, %2
+    %7:_(s32) = G_ANYEXT %6
+    $w0 = COPY %7(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name: icmp_and_icmp_or_icmp
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp_and_icmp_or_icmp
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sle), [[COPY]](s64), [[C]]
+    ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ule), [[COPY]](s64), [[C]]
+    ; CHECK: [[OR:%[0-9]+]]:_(s1) = G_OR [[ICMP]], [[ICMP1]]
+    ; CHECK: [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s64), [[C]]
+    ; CHECK: [[AND:%[0-9]+]]:_(s1) = G_AND [[OR]], [[ICMP2]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[AND]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_ICMP intpred(ugt), %0(s64), %1
+    %5:_(s1) = G_AND %3, %4
+    %6:_(s1) = G_ICMP intpred(ne), %0(s64), %1
+    %7:_(s1) = G_OR %5, %6
+    %8:_(s1) = G_XOR %7, %2
+    %9:_(s32) = G_ANYEXT %8
+    $w0 = COPY %9(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name: icmp_and_trunc
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp_and_trunc
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[C1:%[0-9]+]]:_(s1) = G_CONSTANT i1 true
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sgt), [[COPY]](s64), [[C]]
+    ; CHECK: [[TRUNC:%[0-9]+]]:_(s1) = G_TRUNC [[COPY]](s64)
+    ; CHECK: [[AND:%[0-9]+]]:_(s1) = G_AND [[ICMP]], [[TRUNC]]
+    ; CHECK: [[XOR:%[0-9]+]]:_(s1) = G_XOR [[AND]], [[C1]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[XOR]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_TRUNC %0(s64)
+    %5:_(s1) = G_AND %3, %4
+    %6:_(s1) = G_XOR %5, %2
+    %7:_(s32) = G_ANYEXT %6
+    $w0 = COPY %7(s32)
+    RET_ReallyLR implicit $w0
+...