[InstCombine] Teach visitICmpInst to not break integer absolute value idioms

[craig.topper]

Summary

This patch adds an early out to visitICmpInst if we are looking at a compare as part of an integer absolute value idiom. Similar is already done for min/max.

In the particular case I observed in a benchmark we had an absolute value of a load from an indexed global. We simplified the compare using foldCmpLoadFromIndexedGlobal into a magic bit vector, a shift, and an and. But the load result was still used for the select and the negate part of the absolute valute idiom. So we overcomplicated the code and lost the ability to recognize it as an absolute value.

I've chosen a simpler case for the test here.

[craig.topper]

Add full context

[spatel]

Should we recognize (and canonicalize) this abs() pattern:

define i64 @abs5(i64 %x) {
  %signbit = ashr i64 %x, 63      ; smear the sign bit
  %add = add i64 %x, %signbit     ; add 0 or -1
  %abs = xor i64 %add, %signbit   ; x < 0 ? -x : x
  ret i64 %abs
}

(note: I mentioned this pattern to the group looking at matching vector idioms earlier this year - not sure what happened to that effort).

Independent of that, how about calling ValueTracking's matchSelectPattern()? Then, we could check all of min/max/abs in one shot without repeating the logic here.

[craig.topper]

Use matchSelectPattern instead. Use user_back instead of user_begin since it does that same thing without the explicit dereference. Also updated the equivalent place in visitFCmp.

[spatel]

LGTM.

[• lillyrowling18]

In D39766#921760, @spatel wrote:

Should we recognize (and canonicalize) this abs() pattern:

define i64 @abs5(i64 %x) {
  %signbit = ashr i64 %x, 63      ; smear the sign bit
  %add = add i64 %x, %signbit     ; add 0 or -1
  %abs = xor i64 %add, %signbit   ; x < 0 ? -x : x
  ret i64 %abs
}

(note: I mentioned this pattern to the group looking at matching vector idioms earlier this year - not sure what happened to that effort).

Independent of that, how about calling ValueTracking's matchSelectPattern()? Then, we could check all of min/max/abs in one shot without repeating the logic here.

I also had the same question, thanks for help.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
 
   // Test if the ICmpInst instruction is used exclusively by a select as
   // part of a minimum or maximum operation. If so, refrain from doing
   // any other folding. This helps out other analyses which understand
   // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
   // and CodeGen. And in this case, at least one of the comparison
   // operands has at least one user besides the compare (the select),
   // which would often largely negate the benefit of folding anyway.
+  //
+  // Do the same for the other patterns recognized by matchSelectPattern.
   if (I.hasOneUse())
-    if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
-      if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
-          (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
+    if (SelectInst *SI = dyn_cast<SelectInst>(I.user_back())) {
+      Value *A, *B;
+      SelectPatternResult SPR = matchSelectPattern(SI, A, B);
+      if (SPR.Flavor != SPF_UNKNOWN)
         return nullptr;
+    }
 
   // Do this after checking for min/max to prevent infinite looping.
   if (Instruction *Res = foldICmpWithZero(I))
     return Res;
 
   // FIXME: We only do this after checking for min/max to prevent infinite
   // looping caused by a reverse canonicalization of these patterns for min/max.
   // FIXME: The organization of folds is a mess. These would naturally go into
Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {
   // Test if the FCmpInst instruction is used exclusively by a select as
   // part of a minimum or maximum operation. If so, refrain from doing
   // any other folding. This helps out other analyses which understand
   // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
   // and CodeGen. And in this case, at least one of the comparison
   // operands has at least one user besides the compare (the select),
   // which would often largely negate the benefit of folding anyway.
   if (I.hasOneUse())
-    if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
-      if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
-          (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
+    if (SelectInst *SI = dyn_cast<SelectInst>(I.user_back())) {
+      Value *A, *B;
+      SelectPatternResult SPR = matchSelectPattern(SI, A, B);
+      if (SPR.Flavor != SPF_UNKNOWN)
         return nullptr;
+    }
 
   // Handle fcmp with constant RHS
   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
       switch (LHSI->getOpcode()) {
       case Instruction::FPExt: {
         // fcmp (fpext x), C -> fcmp x, (fptrunc C) if fptrunc is lossless
         FPExtInst *LHSExt = cast<FPExtInst>(LHSI);

llvm/trunk/test/Transforms/InstCombine/icmp.ll

 ;
   %a1 = and i8 %a, 133
   %a2 = or i8 %a1, 4
   %b1 = and i8 %b, 7
   %b2 = or i8 %b1, 5
   %c = icmp sgt i8 %b2, %a2
   ret i1 %c
 }
+
+; Make sure InstCombine doesn't try too hard to simplify the icmp and break the abs idiom
+define i32 @abs_preserve(i32 %x) {
+; CHECK-LABEL: @abs_preserve(
+; CHECK-NEXT:    [[A:%.*]] = shl nsw i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i32 [[A]], -1
+; CHECK-NEXT:    [[NEGA:%.*]] = sub i32 0, [[A]]
+; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[C]], i32 [[A]], i32 [[NEGA]]
+; CHECK-NEXT:    ret i32 [[ABS]]
+;
+  %a = mul nsw i32 %x, 2
+  %c = icmp sge i32 %a, 0
+  %nega = sub i32 0, %a
+  %abs = select i1 %c, i32 %a, i32 %nega
+  ret i32 %abs
+}