[InstCombine] change conditions for transform of sub to xor

[spatel]

Summary

As discussed in in D128123, converting sub to xor can cause codegen regressions, and it may not be reversible with respect to no-wrap as shown here:
https://alive2.llvm.org/ce/z/vebvhH

The PhaseOrdering test is based on the example provided in the other review.

Generally, we prefer bitwise-logic to math ops in IR even if that means dropping no-wrap flags -- because that allows better bit-tracking. But as noted, we need to improve the backend before easing the conditions here to avoid sub-optimal codegen.

This makes the IR fold the same as SDAG other than avoiding the transform in the presence of nsw/nuw. We probably want to update SDAG too -- either with a similar check as here or with a TLI hook to restrict the fold for targets that prefer sub-from-constant form.

[nikic]

As discussed in in D128123, converting sub to xor can cause codegen regressions, and it may not be reversible with respect to no-wrap as shown here:
https://alive2.llvm.org/ce/z/CgOlZU

Your example seems to show that nsw can be recovered, only nuw can't be?

[spatel]

In D129650#3650902, @nikic wrote:

As discussed in in D128123, converting sub to xor can cause codegen regressions, and it may not be reversible with respect to no-wrap as shown here:
https://alive2.llvm.org/ce/z/CgOlZU

Your example seems to show that nsw can be recovered, only nuw can't be?

Oops - I was altering the constant values to see when the transform is and isn't bidirectional, and I grabbed the wrong link. The code comments don't match the code in that link.
These are the non-bidirectional examples (the mask is negative, but the subtract constant is not):
https://alive2.llvm.org/ce/z/vebvhH

In all other cases, the transform seems to be bidirectional:
https://alive2.llvm.org/ce/z/ffGPvL

Also note that there is an existing regression test (not altered by this patch) that shows the potential harm if we do the transform and lose the no-wrap:

define i1 @test_negative_combined_sub_signed_overflow(i8 %x) {
; CHECK-LABEL: @test_negative_combined_sub_signed_overflow(
; CHECK-NEXT:    ret i1 false
;
  %y = sub nsw i8 127, %x
  %z = icmp slt i8 %y, -1
  ret i1 %z
}

If we convert sub to xor first, we can't then fold the compare to false.

[bjope]

Thanks! Verified that it solves the regressions that I mentioned in D128123.

For future follow-ups: Maybe value/bit tracking implementations for sub can be taught about this kind of sub being an xor in disguise to get the wanted bit tracking also without transforming to sub? It is probably easier to deal with "known bits" of the non-constant operand while doing value/bit tracking compared to doing it during SCEV analysis (for the reverse - i.e. understanding that an xor is a sub in disguise).

This patch LGTM. But since @nikic had comments earlier I think you need to wait for an accept from Nikita as well.

[nikic]

At a high level, I find the notion of disabling folds to preserve nowrap flags somewhat concerning. Doing this means that an improvement in one place (which infers more nowrap flags) can disable a later optimization, because it now considers preserving those flags more important. We sometimes do this for correctness reasons (mainly in that an operation with nowrap flags cannot be guaranteed-not-poison), but do we have any precedent in InstCombine for doing this specifically to preserve the flags?

In this specific case, I think we should question the value of the entire transform, at least on the IR level. Is there some specific motivation for it (i.e. some chain of follow-on transforms it enables?) or are we just doing it because we can? Our KnownBits handling of sub is optimal, so for computeKnownBits() I believe it shouldn't matter whether the instruction is a sub or a xor (in cases where we convert one into the other based on known bits only). However, for ConstantRange for example we also have an optimal sub implementation, but xor is heavily approximated. Similarly SCEV does not understand xor, but understands sub. So I question the premise here that we want to prefer xor over sub as a canonical form. I believe on average, our support for sub is better (the only xor variant that has decently universal support is xor by minus one, aka not).

[spatel]

In D129650#3654287, @nikic wrote:

At a high level, I find the notion of disabling folds to preserve nowrap flags somewhat concerning. Doing this means that an improvement in one place (which infers more nowrap flags) can disable a later optimization, because it now considers preserving those flags more important. We sometimes do this for correctness reasons (mainly in that an operation with nowrap flags cannot be guaranteed-not-poison), but do we have any precedent in InstCombine for doing this specifically to preserve the flags?

I don't know of any other cases where we avoid a transform based on no-wrap. AFAIK, we have always leaned towards doing a transform to a simpler op even if it meant losing no-wrap.

In this specific case, I think we should question the value of the entire transform, at least on the IR level. Is there some specific motivation for it (i.e. some chain of follow-on transforms it enables?) or are we just doing it because we can? Our KnownBits handling of sub is optimal, so for computeKnownBits() I believe it shouldn't matter whether the instruction is a sub or a xor (in cases where we convert one into the other based on known bits only). However, for ConstantRange for example we also have an optimal sub implementation, but xor is heavily approximated. Similarly SCEV does not understand xor, but understands sub. So I question the premise here that we want to prefer xor over sub as a canonical form. I believe on average, our support for sub is better (the only xor variant that has decently universal support is xor by minus one, aka not).

We have been canonicalizing away from sub recently, and I assumed xor was better than sub for bit-tracking, so I didn't consider the opposite transform.

I tracked down the original fold to:
https://github.com/llvm/llvm-project/commit/010337c8385b919f
...so the motivation was really about codegen, but we've also generally assumed that bitwise ops are a better canonicalization than math.

The fold was moved to InstCombiner::visitSub() with:
D9417 / https://github.com/llvm/llvm-project/commit/ec6833420fa3c6f44c0e464ed2cbc6c483f37781
...and that brings us to the recent history:

1. I noticed that we could use the transform in SDAG, so I proposed to copy the InstCombine: D128080
2. Then, I saw that x86 had a stronger version of the fold, so I made that a generic SDAG fold: D128123
3. There was feedback that we could relax the constraints a bit more, so: d0eec5f7e787
4. I figured if we're doing this fold in both places, we should make it consistent: 79bb915fb60b

So it just accumulated to current state.
This reminds me of turning 'add' into 'or' with no common bits set (no carries) - that led to a long series of work-arounds to match new patterns with 'or'.
I'm not sure what (if any) SCEV changes were made to accommodate that transform, but it makes sense to me if we want to avoid that with sub->xor.

I think this patch is going to effectively prevent the transform in almost all cases because we seem to infer no-wrap on these patterns effectively. We could commit this, wait a bit to see if there's any fallout, then remove the transform completely.

That raises the question: do we want to canonicalize xor to sub? Maybe we just ignore that and live with both possibilities.

[syzaara]

This change is causing issues with creating a SCEV expression for the subtract. This leads to not being able to delinearizing some expressions which can have an impact on loop passes like loop interchange. For example, with the attached{F23852262} IR, we are no longer able to compute a simple SCEV expression for the subtract which is now an xor:
Output from -passes=print<scalar-evolution>

With the subtract:

  %_val_lda_ = load i32, i32* %.lda, align 4
  -->  %_val_lda_ U: full-set S: full-set
  %_conv = sext i32 %_val_lda_ to i64 
  -->  (sext i32 %_val_lda_ to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
  %_mult_tmp = shl nsw i64 %_conv, 3
  -->  (8 * (sext i32 %_val_lda_ to i64))<nsw> U: [0,-7) S: [-17179869184,17179869177)
  %_sub_tmp4 = sub nuw nsw i64 -8, %_mult_tmp
  -->  (-8 + (-8 * (sext i32 %_val_lda_ to i64))<nsw>)<nsw> U: [0,-7) S: [-17179869184,17179869177)
%a_ix_dim_0_ = getelementptr i8, i8* %a_rvo_based_addr_, i64 %_ix_x_len11
-->  {(-8 + %.a),+,(8 * (sext i32 %_val_lda_ to i64))<nsw>}<%_loop_2_do_>



With the xor:

  %_val_lda_ = load i32, i32* %.lda, align 4
  -->  %_val_lda_ U: full-set S: full-set
  %_conv = sext i32 %_val_lda_ to i64 
  -->  (sext i32 %_val_lda_ to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
  %_mult_tmp = shl nsw i64 %_conv, 3
  -->  (8 * (sext i32 %_val_lda_ to i64))<nsw> U: [0,-7) S: [-17179869184,17179869177)
  %_sub_tmp4 = xor i64 %_mult_tmp, -8
  -->  %_sub_tmp4 U: [0,-7) S: [-17179869184,17179869184)
%a_ix_dim_0_ = getelementptr i8, i8* %a_rvo_based_addr_, i64 %_ix_x_len11 
-->  {((8 * (sext i32 %_val_lda_ to i64))<nsw> + %_sub_tmp4 + %.a),+,(8 * (sext i32 %_val_lda_ to i64))<nsw>}<%_loop_2_do_>

Note that we do not recognize the xor as a subtract of 8 SCEV expression. This prevents further simplifications on expressions using _sub_tmp4, because it is now represented as a symbol rather than a recognized SCEV operation.
Would it be possible to revert this until we teach SCEV how to handle the XOR?

[spatel]

In D129650#3666042, @syzaara wrote:

Note that we do not recognize the xor as a subtract of 8 SCEV expression. This prevents further simplifications on expressions using _sub_tmp4, because it is now represented as a symbol rather than a recognized SCEV operation.
Would it be possible to revert this until we teach SCEV how to handle the XOR?

Please correct me if I've misunderstood: would this patch solve the problem that you are seeing? If we want to revert, that would be 79bb915fb60b ?

[syzaara]

In D129650#3666095, @spatel wrote:

In D129650#3666042, @syzaara wrote:

Note that we do not recognize the xor as a subtract of 8 SCEV expression. This prevents further simplifications on expressions using _sub_tmp4, because it is now represented as a symbol rather than a recognized SCEV operation.
Would it be possible to revert this until we teach SCEV how to handle the XOR?

Please correct me if I've misunderstood: would this patch solve the problem that you are seeing? If we want to revert, that would be 79bb915fb60b ?

Oh sorry! Yes, I meant to post this comment for 79bb915fb60b. And I have double checked that this patch solves the issue. Looking forward to this being committed, if we are not reverting 79bb915fb60b. Thanks.

[spatel]

In D129650#3666235, @syzaara wrote:

In D129650#3666095, @spatel wrote:

In D129650#3666042, @syzaara wrote:

Note that we do not recognize the xor as a subtract of 8 SCEV expression. This prevents further simplifications on expressions using _sub_tmp4, because it is now represented as a symbol rather than a recognized SCEV operation.
Would it be possible to revert this until we teach SCEV how to handle the XOR?

Please correct me if I've misunderstood: would this patch solve the problem that you are seeing? If we want to revert, that would be 79bb915fb60b ?

Oh sorry! Yes, I meant to post this comment for 79bb915fb60b. And I have double checked that this patch solves the issue. Looking forward to this being committed, if we are not reverting 79bb915fb60b. Thanks.

Thanks for confirming.

Ping @nikic - are you ok with this patch? (and follow-up to remove the fold entirely?)

[bjope]

In D129650#3666246, @spatel wrote:

In D129650#3666235, @syzaara wrote:

In D129650#3666095, @spatel wrote:

In D129650#3666042, @syzaara wrote:

Note that we do not recognize the xor as a subtract of 8 SCEV expression. This prevents further simplifications on expressions using _sub_tmp4, because it is now represented as a symbol rather than a recognized SCEV operation.
Would it be possible to revert this until we teach SCEV how to handle the XOR?

Please correct me if I've misunderstood: would this patch solve the problem that you are seeing? If we want to revert, that would be 79bb915fb60b ?

Oh sorry! Yes, I meant to post this comment for 79bb915fb60b. And I have double checked that this patch solves the issue. Looking forward to this being committed, if we are not reverting 79bb915fb60b. Thanks.

Thanks for confirming.

Ping @nikic - are you ok with this patch? (and follow-up to remove the fold entirely?)

This patch is better than nothing IMHO (the regressions we currently see without either applying this patch or reverting the recent patches involving sub->xor transforms are a bit annoying).
I also think that it is a bit weird (or rather hard to follow) if we only canonicalize based on if those NSW/NUW attributes are present or not (at least if we also want to canonicalize xor->sub for the opposite condition). So some kind of follow up to either just keep (or canonicalize) to sub up until instruction selection could be nice. If there are motivating examples for using xor instead of sub in the middle-end, then we might go in the other direction if we first make sure SCEV handles the xor in the same way as if it had been a sub.

Reverting rG79bb915fb60b2cd220d89e3bb54f67abb8cdb7bd is also an acceptable solution. Afaict it has only caused regressions, but I haven't seen (or heard about) any benchmarks being improved by that patch.

[nikic]

I think the right starting point here is to revert rG79bb915fb60b2cd220d89e3bb54f67abb8cdb7bd.

This reminds me of turning 'add' into 'or' with no common bits set (no carries) - that led to a long series of work-arounds to match new patterns with 'or'.
I'm not sure what (if any) SCEV changes were made to accommodate that transform, but it makes sense to me if we want to avoid that with sub->xor.

We have special SCEV handling for this here: https://github.com/llvm/llvm-project/blob/7068aa98412ade19a34b7ed126f4669f581b2311/llvm/lib/Analysis/ScalarEvolution.cpp#L7599 And I believe we have a bunch of haveNoCommonBitsSet() calls in various places to undo the add->or fold. I have some doubts about the value of the add->or canonicalization as well, but the justification is stronger there, and we already have necessary mitigations in place.

That raises the question: do we want to canonicalize xor to sub?

That would be the principled thing to do, but I'm not sure it would matter much in practice.

[spatel]

Ok - I reverted the earlier patch that created more xor with:
08091a99ae48

That should solve the immediate regressions that were mentioned here (and we still have the PhaseOrdering test in place, so it will be harder to trip over this in the future).

Note: we still convert sub from low-mask constant (eg 0x003fff...) into xor (that was the original fold that's been around for many years). I'm not sure if there's something about that pattern that avoids SCEV trouble, or if there's already a work-around for that pattern in SCEV.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Constant *C = dyn_cast<Constant>(Op0)) {
 
     Constant *C2;
 
     // C-(C2-X) --> X+(C-C2)
     if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
       return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));
   }
 
-  // If there's no chance any bit will need to borrow from an adjacent bit:
-  // sub C, X --> xor X, C
-  const APInt *Op0C;
-  if (match(Op0, m_APInt(Op0C)) &&
-      (~computeKnownBits(Op1, 0, &I).Zero).isSubsetOf(*Op0C))
-    return BinaryOperator::CreateXor(Op1, Op0);
-
   {
     Value *Y;
     // X-(X+Y) == -Y    X-(Y+X) == -Y
     if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
       return BinaryOperator::CreateNeg(Y);
 
     // (X-Y)-X == -Y
     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {
 
   // C - ctpop(X) => ctpop(~X) if C is bitwidth
   if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
       match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
     return replaceInstUsesWith(
         I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
                                    {Builder.CreateNot(X)}));
 
-  return TryToNarrowDeduceFlags();
+  if (Instruction *R = TryToNarrowDeduceFlags())
+    return R;
+
+  // If the subtract is equivalent to xor (no bits other than MSB could require
+  // a borrow), convert to xor for better bit-tracking.
+  // sub C, X --> xor X, C
+  // Avoid this fold if the sub has no-wrap flags because that could be an
+  // information-losing transform that we cannot recover from.
+  const APInt *Op0C;
+  if (!I.hasNoSignedWrap() && !I.hasNoUnsignedWrap() &&
+      match(Op0, m_APInt(Op0C))) {
+    const APInt &MaybeOnes = ~computeKnownBits(Op1, 0, &I).Zero;
+    if ((*Op0C - MaybeOnes) == (*Op0C ^ MaybeOnes))
+      return BinaryOperator::CreateXor(Op1, Op0);
+  }
+
+  return nullptr;
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I) {
   // This is limited with one-use because fneg is assumed better for
   // reassociation and cheaper in codegen than fmul/fdiv.
   // TODO: Should the m_OneUse restriction be removed?

llvm/test/Transforms/InstCombine/sub-xor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine -S < %s | FileCheck %s
 
 declare void @use(i32)
 
+; TODO: This could be converted to xor if the backend recognizes the sub equivalency.
+
 define i32 @low_mask_nsw_nuw(i32 %x) {
 ; CHECK-LABEL: @low_mask_nsw_nuw(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[SUB:%.*]] = xor i32 [[AND]], 63
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 63, [[AND]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %and = and i32 %x, 31
   %sub = sub i32 63, %and
   ret i32 %sub
 }
 
+; TODO: This could be converted to xor if the backend recognizes the sub equivalency.
+
 define <2 x i32> @low_mask_nsw_nuw_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @low_mask_nsw_nuw_vec(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[SUB:%.*]] = xor <2 x i32> [[AND]], <i32 63, i32 63>
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw <2 x i32> <i32 63, i32 63>, [[AND]]
 ; CHECK-NEXT:    ret <2 x i32> [[SUB]]
 ;
   %and = and <2 x i32> %x, <i32 31, i32 31>
   %sub = sub <2 x i32> <i32 63, i32 63>, %and
   ret <2 x i32> %sub
 }
 
+; TODO: This could be converted to xor if the backend recognizes the sub equivalency.
+
 define i8 @arbitrary_mask_sub_i8(i8 %x) {
 ; CHECK-LABEL: @arbitrary_mask_sub_i8(
 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[M:%.*]] = xor i8 [[A]], 11
+; CHECK-NEXT:    [[M:%.*]] = sub nuw nsw i8 11, [[A]]
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = and i8 %x, 10 ; 0b00001010
   %m = sub i8 11, %a ; 0b00001011
   ret i8 %m
 }
 
-; TODO: Borrow from the MSB is ok.
+; Borrow from the MSB is ok.
 
 define i8 @arbitrary_mask_sub_high_bit_dont_care_i8(i8 %x) {
 ; CHECK-LABEL: @arbitrary_mask_sub_high_bit_dont_care_i8(
 ; CHECK-NEXT:    [[MASKX:%.*]] = and i8 [[X:%.*]], -93
-; CHECK-NEXT:    [[S:%.*]] = sub i8 39, [[MASKX]]
+; CHECK-NEXT:    [[S:%.*]] = xor i8 [[MASKX]], 39
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %maskx = and i8 %x, 163 ; 0b10100011
   %s = sub i8 39, %maskx  ; 0b00100111
   ret i8 %s
 }
 
+; Converting to xor loses information - nsw cannot be recovered by later analysis.
+
 define i8 @arbitrary_mask_sub_nsw_high_bit_dont_care_i8(i8 %x) {
 ; CHECK-LABEL: @arbitrary_mask_sub_nsw_high_bit_dont_care_i8(
 ; CHECK-NEXT:    [[MASKX:%.*]] = and i8 [[X:%.*]], -93
 ; CHECK-NEXT:    [[S:%.*]] = sub nsw i8 39, [[MASKX]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %maskx = and i8 %x, 163     ; 0b10100011
   %s = sub nsw i8 39, %maskx  ; 0b00100111
   ret i8 %s
 }
 
+; Converting to xor loses information - nuw cannot be recovered by later analysis.
+
 define i8 @arbitrary_mask_sub_nuw_high_bit_dont_care_i8(i8 %x) {
 ; CHECK-LABEL: @arbitrary_mask_sub_nuw_high_bit_dont_care_i8(
 ; CHECK-NEXT:    [[MASKX:%.*]] = and i8 [[X:%.*]], -93
 ; CHECK-NEXT:    [[S:%.*]] = sub nuw i8 39, [[MASKX]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %maskx = and i8 %x, 163     ; 0b10100011
   %s = sub nuw i8 39, %maskx  ; 0b00100111
   ret i8 %s
 }
 
+; TODO: This could be converted to xor if the backend recognizes the sub equivalency.
+
 define <2 x i5> @arbitrary_mask_sub_v2i5(<2 x i5> %x) {
 ; CHECK-LABEL: @arbitrary_mask_sub_v2i5(
 ; CHECK-NEXT:    [[A:%.*]] = and <2 x i5> [[X:%.*]], <i5 -8, i5 -8>
-; CHECK-NEXT:    [[M:%.*]] = xor <2 x i5> [[A]], <i5 -6, i5 -6>
+; CHECK-NEXT:    [[M:%.*]] = sub nuw nsw <2 x i5> <i5 -6, i5 -6>, [[A]]
 ; CHECK-NEXT:    ret <2 x i5> [[M]]
 ;
   %a = and <2 x i5> %x, <i5 24, i5 24> ; 0b11000
   %m = sub <2 x i5> <i5 26, i5 26>, %a ; 0b11010
   ret <2 x i5> %m
 }
 
 ; negative test - sub constant isn't superset of masked bits
 
 define i8 @not_masked_sub_i8(i8 %x) {
 ; CHECK-LABEL: @not_masked_sub_i8(
 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], 7
 ; CHECK-NEXT:    [[M:%.*]] = sub nuw nsw i8 11, [[A]]
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = and i8 %x, 7  ; 0b00000111
   %m = sub i8 11, %a ; 0b00001011
   ret i8 %m
 }
 
 declare i32 @llvm.ctlz.i32(i32, i1)
 
+; TODO: This could be converted to xor if the backend recognizes the sub equivalency.
+
 define i32 @range_masked_sub(i32 %x) {
 ; CHECK-LABEL: @range_masked_sub(
 ; CHECK-NEXT:    [[COUNT:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true) #[[ATTR1:[0-9]+]], !range [[RNG0:![0-9]+]]
-; CHECK-NEXT:    [[SUB:%.*]] = xor i32 [[COUNT]], 31
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 31, [[COUNT]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %count = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true) nounwind readnone
   %sub = sub i32 31, %count
   ret i32 %sub
 }
 
 define i32 @xor_add(i32 %x) {

llvm/test/Transforms/PhaseOrdering/SystemZ/sub-xor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='default<O2>' -enable-matrix -S %s | FileCheck %s
 
 target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-a:8:16-n32:64"
 target triple = "systemz"
 
 @ARR = internal global [100 x i32] zeroinitializer, align 4
 
+; This test uses 'sub' instructions for gep offsets to allow
+; codegen (LSR) to create optimal asm. If 'sub' is canonicalized
+; to 'xor', then the backend needs to be able to see through
+; that transform to produce optimal asm.
+
 define dso_local zeroext i32 @foo(ptr noundef %a) #0 {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    tail call void @populate(ptr noundef nonnull @ARR) #[[ATTR2:[0-9]+]]
 ; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
 ; CHECK:       for.body4:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT_7:%.*]], [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[SUM_11:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD_7:%.*]], [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[IDX_NEG:%.*]] = sub nsw i64 0, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ADD_PTR]], align 4, !tbaa [[TBAA3:![0-9]+]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP0]], [[SUM_11]]
 ; CHECK-NEXT:    [[IDX_NEG_19:%.*]] = xor i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[ADD_PTR_110:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_19]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ADD_PTR_110]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_111:%.*]] = add i32 [[TMP1]], [[ADD]]
-; CHECK-NEXT:    [[IDX_NEG_216:%.*]] = xor i64 [[INDVARS_IV]], -2
+; CHECK-NEXT:    [[IDX_NEG_216:%.*]] = sub nuw nsw i64 -2, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_217:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_216]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[ADD_PTR_217]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_218:%.*]] = add i32 [[TMP2]], [[ADD_111]]
-; CHECK-NEXT:    [[IDX_NEG_3:%.*]] = xor i64 [[INDVARS_IV]], -3
+; CHECK-NEXT:    [[IDX_NEG_3:%.*]] = sub nuw nsw i64 -3, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_3:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_3]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[ADD_PTR_3]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_3:%.*]] = add i32 [[TMP3]], [[ADD_218]]
-; CHECK-NEXT:    [[IDX_NEG_4:%.*]] = xor i64 [[INDVARS_IV]], -4
+; CHECK-NEXT:    [[IDX_NEG_4:%.*]] = sub nuw nsw i64 -4, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_4:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_4]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr [[ADD_PTR_4]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_4:%.*]] = add i32 [[TMP4]], [[ADD_3]]
-; CHECK-NEXT:    [[IDX_NEG_5:%.*]] = xor i64 [[INDVARS_IV]], -5
+; CHECK-NEXT:    [[IDX_NEG_5:%.*]] = sub nuw nsw i64 -5, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_5:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_5]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = load i32, ptr [[ADD_PTR_5]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_5:%.*]] = add i32 [[TMP5]], [[ADD_4]]
-; CHECK-NEXT:    [[IDX_NEG_6:%.*]] = xor i64 [[INDVARS_IV]], -6
+; CHECK-NEXT:    [[IDX_NEG_6:%.*]] = sub nuw nsw i64 -6, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_6:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_6]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = load i32, ptr [[ADD_PTR_6]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_6:%.*]] = add i32 [[TMP6]], [[ADD_5]]
-; CHECK-NEXT:    [[IDX_NEG_7:%.*]] = xor i64 [[INDVARS_IV]], -7
+; CHECK-NEXT:    [[IDX_NEG_7:%.*]] = sub nuw nsw i64 -7, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR_7:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_7]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = load i32, ptr [[ADD_PTR_7]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[ADD_7]] = add i32 [[TMP7]], [[ADD_6]]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT_7]] = add nuw nsw i64 [[INDVARS_IV]], 8
 ; CHECK-NEXT:    [[EXITCOND_NOT_7:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_7]], 32
 ; CHECK-NEXT:    br i1 [[EXITCOND_NOT_7]], label [[FOR_BODY4_1:%.*]], label [[FOR_BODY4]], !llvm.loop [[LOOP7:![0-9]+]]
 ; CHECK:       for.body4.1:
 ; CHECK-NEXT:    [[INDVARS_IV_1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_1_7:%.*]], [[FOR_BODY4_1]] ], [ 0, [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[SUM_11_1:%.*]] = phi i32 [ [[ADD_1_7:%.*]], [[FOR_BODY4_1]] ], [ [[ADD_7]], [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[IDX_NEG_1:%.*]] = sub nsw i64 0, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = load i32, ptr [[ADD_PTR_1]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1:%.*]] = shl i32 [[TMP8]], 1
 ; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 [[MUL_1]], [[SUM_11_1]]
 ; CHECK-NEXT:    [[IDX_NEG_1_1:%.*]] = xor i64 [[INDVARS_IV_1]], -1
 ; CHECK-NEXT:    [[ADD_PTR_1_1:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_1]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = load i32, ptr [[ADD_PTR_1_1]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_1:%.*]] = shl i32 [[TMP9]], 1
 ; CHECK-NEXT:    [[ADD_1_1:%.*]] = add i32 [[MUL_1_1]], [[ADD_1]]
-; CHECK-NEXT:    [[IDX_NEG_1_2:%.*]] = xor i64 [[INDVARS_IV_1]], -2
+; CHECK-NEXT:    [[IDX_NEG_1_2:%.*]] = sub nuw nsw i64 -2, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_2:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_2]]
 ; CHECK-NEXT:    [[TMP10:%.*]] = load i32, ptr [[ADD_PTR_1_2]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_2:%.*]] = shl i32 [[TMP10]], 1
 ; CHECK-NEXT:    [[ADD_1_2:%.*]] = add i32 [[MUL_1_2]], [[ADD_1_1]]
-; CHECK-NEXT:    [[IDX_NEG_1_3:%.*]] = xor i64 [[INDVARS_IV_1]], -3
+; CHECK-NEXT:    [[IDX_NEG_1_3:%.*]] = sub nuw nsw i64 -3, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_3:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_3]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = load i32, ptr [[ADD_PTR_1_3]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_3:%.*]] = shl i32 [[TMP11]], 1
 ; CHECK-NEXT:    [[ADD_1_3:%.*]] = add i32 [[MUL_1_3]], [[ADD_1_2]]
-; CHECK-NEXT:    [[IDX_NEG_1_4:%.*]] = xor i64 [[INDVARS_IV_1]], -4
+; CHECK-NEXT:    [[IDX_NEG_1_4:%.*]] = sub nuw nsw i64 -4, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_4:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_4]]
 ; CHECK-NEXT:    [[TMP12:%.*]] = load i32, ptr [[ADD_PTR_1_4]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_4:%.*]] = shl i32 [[TMP12]], 1
 ; CHECK-NEXT:    [[ADD_1_4:%.*]] = add i32 [[MUL_1_4]], [[ADD_1_3]]
-; CHECK-NEXT:    [[IDX_NEG_1_5:%.*]] = xor i64 [[INDVARS_IV_1]], -5
+; CHECK-NEXT:    [[IDX_NEG_1_5:%.*]] = sub nuw nsw i64 -5, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_5:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_5]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = load i32, ptr [[ADD_PTR_1_5]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_5:%.*]] = shl i32 [[TMP13]], 1
 ; CHECK-NEXT:    [[ADD_1_5:%.*]] = add i32 [[MUL_1_5]], [[ADD_1_4]]
-; CHECK-NEXT:    [[IDX_NEG_1_6:%.*]] = xor i64 [[INDVARS_IV_1]], -6
+; CHECK-NEXT:    [[IDX_NEG_1_6:%.*]] = sub nuw nsw i64 -6, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_6:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_6]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = load i32, ptr [[ADD_PTR_1_6]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_6:%.*]] = shl i32 [[TMP14]], 1
 ; CHECK-NEXT:    [[ADD_1_6:%.*]] = add i32 [[MUL_1_6]], [[ADD_1_5]]
-; CHECK-NEXT:    [[IDX_NEG_1_7:%.*]] = xor i64 [[INDVARS_IV_1]], -7
+; CHECK-NEXT:    [[IDX_NEG_1_7:%.*]] = sub nuw nsw i64 -7, [[INDVARS_IV_1]]
 ; CHECK-NEXT:    [[ADD_PTR_1_7:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_1_7]]
 ; CHECK-NEXT:    [[TMP15:%.*]] = load i32, ptr [[ADD_PTR_1_7]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_1_7:%.*]] = shl i32 [[TMP15]], 1
 ; CHECK-NEXT:    [[ADD_1_7]] = add i32 [[MUL_1_7]], [[ADD_1_6]]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT_1_7]] = add nuw nsw i64 [[INDVARS_IV_1]], 8
 ; CHECK-NEXT:    [[EXITCOND_1_NOT_7:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_1_7]], 32
 ; CHECK-NEXT:    br i1 [[EXITCOND_1_NOT_7]], label [[FOR_BODY4_2:%.*]], label [[FOR_BODY4_1]], !llvm.loop [[LOOP7]]
 ; CHECK:       for.body4.2:
 ; CHECK-NEXT:    [[INDVARS_IV_2:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_2_7:%.*]], [[FOR_BODY4_2]] ], [ 0, [[FOR_BODY4_1]] ]
 ; CHECK-NEXT:    [[SUM_11_2:%.*]] = phi i32 [ [[ADD_2_7:%.*]], [[FOR_BODY4_2]] ], [ [[ADD_1_7]], [[FOR_BODY4_1]] ]
 ; CHECK-NEXT:    [[IDX_NEG_2:%.*]] = sub nsw i64 0, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2]]
 ; CHECK-NEXT:    [[TMP16:%.*]] = load i32, ptr [[ADD_PTR_2]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2:%.*]] = mul i32 [[TMP16]], 3
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add i32 [[MUL_2]], [[SUM_11_2]]
 ; CHECK-NEXT:    [[IDX_NEG_2_1:%.*]] = xor i64 [[INDVARS_IV_2]], -1
 ; CHECK-NEXT:    [[ADD_PTR_2_1:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_1]]
 ; CHECK-NEXT:    [[TMP17:%.*]] = load i32, ptr [[ADD_PTR_2_1]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_1:%.*]] = mul i32 [[TMP17]], 3
 ; CHECK-NEXT:    [[ADD_2_1:%.*]] = add i32 [[MUL_2_1]], [[ADD_2]]
-; CHECK-NEXT:    [[IDX_NEG_2_2:%.*]] = xor i64 [[INDVARS_IV_2]], -2
+; CHECK-NEXT:    [[IDX_NEG_2_2:%.*]] = sub nuw nsw i64 -2, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_2:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_2]]
 ; CHECK-NEXT:    [[TMP18:%.*]] = load i32, ptr [[ADD_PTR_2_2]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_2:%.*]] = mul i32 [[TMP18]], 3
 ; CHECK-NEXT:    [[ADD_2_2:%.*]] = add i32 [[MUL_2_2]], [[ADD_2_1]]
-; CHECK-NEXT:    [[IDX_NEG_2_3:%.*]] = xor i64 [[INDVARS_IV_2]], -3
+; CHECK-NEXT:    [[IDX_NEG_2_3:%.*]] = sub nuw nsw i64 -3, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_3:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_3]]
 ; CHECK-NEXT:    [[TMP19:%.*]] = load i32, ptr [[ADD_PTR_2_3]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_3:%.*]] = mul i32 [[TMP19]], 3
 ; CHECK-NEXT:    [[ADD_2_3:%.*]] = add i32 [[MUL_2_3]], [[ADD_2_2]]
-; CHECK-NEXT:    [[IDX_NEG_2_4:%.*]] = xor i64 [[INDVARS_IV_2]], -4
+; CHECK-NEXT:    [[IDX_NEG_2_4:%.*]] = sub nuw nsw i64 -4, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_4:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_4]]
 ; CHECK-NEXT:    [[TMP20:%.*]] = load i32, ptr [[ADD_PTR_2_4]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_4:%.*]] = mul i32 [[TMP20]], 3
 ; CHECK-NEXT:    [[ADD_2_4:%.*]] = add i32 [[MUL_2_4]], [[ADD_2_3]]
-; CHECK-NEXT:    [[IDX_NEG_2_5:%.*]] = xor i64 [[INDVARS_IV_2]], -5
+; CHECK-NEXT:    [[IDX_NEG_2_5:%.*]] = sub nuw nsw i64 -5, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_5:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_5]]
 ; CHECK-NEXT:    [[TMP21:%.*]] = load i32, ptr [[ADD_PTR_2_5]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_5:%.*]] = mul i32 [[TMP21]], 3
 ; CHECK-NEXT:    [[ADD_2_5:%.*]] = add i32 [[MUL_2_5]], [[ADD_2_4]]
-; CHECK-NEXT:    [[IDX_NEG_2_6:%.*]] = xor i64 [[INDVARS_IV_2]], -6
+; CHECK-NEXT:    [[IDX_NEG_2_6:%.*]] = sub nuw nsw i64 -6, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_6:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_6]]
 ; CHECK-NEXT:    [[TMP22:%.*]] = load i32, ptr [[ADD_PTR_2_6]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_6:%.*]] = mul i32 [[TMP22]], 3
 ; CHECK-NEXT:    [[ADD_2_6:%.*]] = add i32 [[MUL_2_6]], [[ADD_2_5]]
-; CHECK-NEXT:    [[IDX_NEG_2_7:%.*]] = xor i64 [[INDVARS_IV_2]], -7
+; CHECK-NEXT:    [[IDX_NEG_2_7:%.*]] = sub nuw nsw i64 -7, [[INDVARS_IV_2]]
 ; CHECK-NEXT:    [[ADD_PTR_2_7:%.*]] = getelementptr inbounds i32, ptr getelementptr inbounds ([100 x i32], ptr @ARR, i64 0, i64 99), i64 [[IDX_NEG_2_7]]
 ; CHECK-NEXT:    [[TMP23:%.*]] = load i32, ptr [[ADD_PTR_2_7]], align 4, !tbaa [[TBAA3]]
 ; CHECK-NEXT:    [[MUL_2_7:%.*]] = mul i32 [[TMP23]], 3
 ; CHECK-NEXT:    [[ADD_2_7]] = add i32 [[MUL_2_7]], [[ADD_2_6]]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT_2_7]] = add nuw nsw i64 [[INDVARS_IV_2]], 8
 ; CHECK-NEXT:    [[EXITCOND_2_NOT_7:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_2_7]], 32
 ; CHECK-NEXT:    br i1 [[EXITCOND_2_NOT_7]], label [[FOR_INC5_2:%.*]], label [[FOR_BODY4_2]], !llvm.loop [[LOOP7]]
 ; CHECK:       for.inc5.2: