[SelectionDAG][DAGCombiner] Reuse exist node by reassociate

[bcl5980]

Summary

When already have (op N0, N2), reassociate (op (op N0, N1), N2) to (op (op N0, N2), N1) to reuse the exist (op N0, N2)

[pengfei]

llvm/test/CodeGen/X86/masked-iv-safe.ll

269 ↗

(On Diff #418434)

This seems regression. The same below.

[bcl5980]

llvm/test/CodeGen/X86/masked-iv-safe.ll

269 ↗

(On Diff #418434)

Yeah, this change brings some regressions because of two reasons:

1. The case you comment, instruction sequence change causes extra compare instructions
2. [load/store (add (add x, y), constant)]. Many targets support ld/st with imm offset. If we reassociate instructions, it will miss the address mode pattern match.

But I think they should be fixed on every backend's isReassocProfitable. I prefer to fix these on individual changes.

[pengfei]

llvm/test/CodeGen/X86/masked-iv-safe.ll

269 ↗

(On Diff #418434)

We shouldn't commit a patch with any known regressions. An individual fix is fine, but it should be ahead of this one so that we won't bring the regression at any time.

[bcl5980]

Waiting for other changes check in

[bcl5980]

fix all regressions

[bcl5980]

remove condition legalDag

[RKSimon]

A few style comments

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1022–1024

if (auto *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {

1101

if (auto *GA = dyn_cast<GlobalAddressSDNode>(N0.getOperand(1)))

1108

(style) Early-out:

auto *LoadStore = dyn_cast<MemSDNode>(Node);
if (!LoadStore)
  return false;

[bcl5980]

fix coding style issue

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1062

auto *LoadStore

[bcl5980]

update coding style

[RKSimon]

LGTM - with one more style minor

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1037

if (auto *LoadStore = dyn_cast<MemSDNode>(Node);)

[dyung]

Hi @bcl5980, one of our internal tests started to hit an assertion failure while building which I bisected back to this change. I have filed the details as issue #56170, can you take a look?

[kripken]

This somehow caused a regression in the wasm targets, which I bisected to here. Certain files when compiled with -O1 appear to hang for a very long time (maybe forever). This happened on the Bullet physics engine codebase in the Emscripten test suite, but affects all wasm targets (wasm32-unknown-unknown, -wasi, and -emscripten).

This doesn't affect other targets, which I guess is why it wasn't noticed before it reached our CI. So maybe this uncovered an existing wasm bug.

@tlively is reducing this atm. Posting the original testcase here for future reference.

bug.cpp338 KBDownload

STR: clang++ -target wasm32-unknown-unknown -O1 -c bug.cpp. That should take less than a second normally, but from this change landing it hangs a very long time (I measured at least 10 seconds during bisection).

[bcl5980]

Reverted by rG9c2bf534f59.
Will try to fix issues later.

[bcl5980]

In D122539#3603739, @kripken wrote:

This somehow caused a regression in the wasm targets, which I bisected to here. Certain files when compiled with -O1 appear to hang for a very long time (maybe forever). This happened on the Bullet physics engine codebase in the Emscripten test suite, but affects all wasm targets (wasm32-unknown-unknown, -wasi, and -emscripten).

This doesn't affect other targets, which I guess is why it wasn't noticed before it reached our CI. So maybe this uncovered an existing wasm bug.

@tlively is reducing this atm. Posting the original testcase here for future reference.

bug.cpp338 KBDownload

STR: clang++ -target wasm32-unknown-unknown -O1 -c bug.cpp. That should take less than a second normally, but from this change landing it hangs a very long time (I measured at least 10 seconds during bisection).

Thanks for the case. I try to minimize the test:

target triple = "wasm32-unknown-unknown"

define float @reassociate_xor(float %x, float %y) {
entry:                                           ; preds = %if.then, %entry
  %cmp0 = fcmp ule float %x, 0x3E80000000000000
  %cmp1 = fcmp ugt float %y, 0x3E80000000000000
  %cmp2 = xor i1 %cmp0, %cmp1
  br i1 %cmp2, label %if.end.i, label %if.then.i

if.then.i:                                        ; preds = %if.end
  br label %if.end.i

if.end.i:                                         ; preds = %if.then.i, %if.end
  %s = phi i32 [ 1, %entry ], [ 0, %if.then.i ]
  ret float %x
}

It looks rebuildSetCC will visitXor in a loop keep the original dag before reassoicate cause deadloop.
I will continue work on it to find a solution.

[RKSimon]

Use getMinSignedBits instead of getBitwidth - fixes for Issue #56170

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1028

Are these redundant? CombinedValueIntVal handles this better below

1031

getBitWidth() -> getMinSignedBits()

1059

if (C2APIntVal.getMinSignedBits() > 64)
  return false;

[bcl5980]

fix 56170

[bcl5980]

fix dead loop in rebuildSetCC

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1039

We have a C2APIntVal use here that I don't think has a getSignificantBits check?

llvm/test/Transforms/Reassociate/pr56170.ll

4 ↗

(On Diff #439631)

Shouldn't this be in tests/Codegen/X86?

[bcl5980]

llvm/test/Transforms/Reassociate/pr56170.ll

4 ↗

(On Diff #439631)

Actually almost every target can trigger this issue. Move the test to x86 is OK for me.

[bcl5980]

add c2 sign bits check
move pr56170.ll to Codegen/X86

[RKSimon]

LGTM cheers

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool DAGCombiner::reassociationCanBreakAddressingModePattern(unsigned Opc,
                                                              SDValue N0,
                                                              SDValue N1) {
   // Currently this only tries to ensure we don't undo the GEP splits done by
   // CodeGenPrepare when shouldConsiderGEPOffsetSplit is true. To ensure this,
   // we check if the following transformation would be problematic:
   // (load/store (add, (add, x, offset1), offset2)) ->
   // (load/store (add, x, offset1+offset2)).
 
+  // (load/store (add, (add, x, y), offset2)) ->
+  // (load/store (add, (add, x, offset2), y)).
+
   if (Opc != ISD::ADD || N0.getOpcode() != ISD::ADD)
     return false;
 
-  if (N0.hasOneUse())
+  auto *C2 = dyn_cast<ConstantSDNode>(N1);
+  if (!C2)
     return false;
 
-  auto *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1));
-  auto *C2 = dyn_cast<ConstantSDNode>(N1);
-  if (!C1 || !C2)
+  const APInt &C2APIntVal = C2->getAPIntValue();
+  if (auto *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
+    if (N0.hasOneUse())
       return false;
 
     const APInt &C1APIntVal = C1->getAPIntValue();
-  const APInt &C2APIntVal = C2->getAPIntValue();
     if (C1APIntVal.getBitWidth() > 64 || C2APIntVal.getBitWidth() > 64)
       return false;
 
     const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
     if (CombinedValueIntVal.getBitWidth() > 64)
       return false;
     const int64_t CombinedValue = CombinedValueIntVal.getSExtValue();
 
     for (SDNode *Node : N->uses()) {
-    auto LoadStore = dyn_cast<MemSDNode>(Node);
-    if (LoadStore) {
+      if (auto *LoadStore = dyn_cast<MemSDNode>(Node)) {
         // Is x[offset2] already not a legal addressing mode? If so then
         // reassociating the constants breaks nothing (we test offset2 because
         // that's the one we hope to fold into the load or store).
         TargetLoweringBase::AddrMode AM;
         AM.HasBaseReg = true;
         AM.BaseOffs = C2APIntVal.getSExtValue();
         EVT VT = LoadStore->getMemoryVT();
         unsigned AS = LoadStore->getAddressSpace();
         Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
         if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
           continue;
 
         // Would x[offset1+offset2] still be a legal addressing mode?
         AM.BaseOffs = CombinedValue;
         if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
           return true;
       }
     }
+  } else {
+    if (auto *GA = dyn_cast<GlobalAddressSDNode>(N0.getOperand(1)))
+      if (GA->getOpcode() == ISD::GlobalAddress && TLI.isOffsetFoldingLegal(GA))
+        return false;
+
+    for (SDNode *Node : N->uses()) {
+      auto *LoadStore = dyn_cast<MemSDNode>(Node);
+      if (!LoadStore)
+        return false;
+
+      // Is x[offset2] a legal addressing mode? If so then
+      // reassociating the constants breaks address pattern
+      TargetLoweringBase::AddrMode AM;
+      AM.HasBaseReg = true;
+      AM.BaseOffs = C2APIntVal.getSExtValue();
+      EVT VT = LoadStore->getMemoryVT();
+      unsigned AS = LoadStore->getAddressSpace();
+      Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
+      if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
+        return false;
+    }
+    return true;
+  }
 
   return false;
 }
 
 // Helper for DAGCombiner::reassociateOps. Try to reassociate an expression
 // such as (Opc N0, N1), if \p N0 is the same kind of operation as \p Opc.
 SDValue DAGCombiner::reassociateOpsCommutative(unsigned Opc, const SDLoc &DL,
                                                SDValue N0, SDValue N1) {
   EVT VT = N0.getValueType();
 
   if (N0.getOpcode() != Opc)
     return SDValue();
 
   SDValue N00 = N0.getOperand(0);
   SDValue N01 = N0.getOperand(1);
 
   if (DAG.isConstantIntBuildVectorOrConstantInt(peekThroughBitcasts(N01))) {
     if (DAG.isConstantIntBuildVectorOrConstantInt(peekThroughBitcasts(N1))) {
       // Reassociate: (op (op x, c1), c2) -> (op x, (op c1, c2))
       if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, DL, VT, {N01, N1}))
         return DAG.getNode(Opc, DL, VT, N00, OpNode);
       return SDValue();
     }
     if (TLI.isReassocProfitable(DAG, N0, N1)) {
       // Reassociate: (op (op x, c1), y) -> (op (op x, y), c1)
       //              iff (op x, c1) has one use
       SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N00, N1);
       return DAG.getNode(Opc, DL, VT, OpNode, N01);
     }
   }
 
   // Check for repeated operand logic simplifications.
   if (Opc == ISD::AND || Opc == ISD::OR) {
     // (N00 & N01) & N00 --> N00 & N01
     // (N00 & N01) & N01 --> N00 & N01
     // (N00 | N01) | N00 --> N00 | N01
     // (N00 | N01) | N01 --> N00 | N01
     if (N1 == N00 || N1 == N01)
       return N0;
   }
   if (Opc == ISD::XOR) {
     // (N00 ^ N01) ^ N00 --> N01
     if (N1 == N00)
       return N01;
     // (N00 ^ N01) ^ N01 --> N00
     if (N1 == N01)
       return N00;
   }
 
+  if (TLI.isReassocProfitable(DAG, N0, N1)) {
+    // Reassociate if (op N00, N1) already exist
+    if (N1 != N01)
+      if (SDNode *ExistNode =
+              DAG.getNodeIfExists(Opc, DAG.getVTList(VT), {N00, N1}))
+        return DAG.getNode(Opc, DL, VT, SDValue(ExistNode, 0), N01);
+
+    // Reassociate if (op N01, N1) already exist
+    if (N1 != N00)
+      if (SDNode *ExistNode =
+              DAG.getNodeIfExists(Opc, DAG.getVTList(VT), {N01, N1}))
+        return DAG.getNode(Opc, DL, VT, SDValue(ExistNode, 0), N00);
+  }
+
   return SDValue();
 }
 
 // Try to reassociate commutative binops.
 SDValue DAGCombiner::reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
                                     SDValue N1, SDNodeFlags Flags) {
   assert(TLI.isCommutativeBinOp(Opc) && "Operation not commutative.");
 

llvm/test/CodeGen/AMDGPU/xor3-i1-const.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=amdgcn -mcpu=bonaire -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 
 ; This test used to crash
 define amdgpu_ps float @xor3_i1_const(float inreg %arg1, i32 inreg %arg2) {
 ; GCN-LABEL: xor3_i1_const:
 ; GCN:       ; %bb.0: ; %main_body
-; GCN-NEXT:    v_mov_b32_e32 v1, 0x42640000
 ; GCN-NEXT:    s_mov_b32 m0, s1
-; GCN-NEXT:    v_cmp_lt_f32_e64 s[2:3], s0, 0
-; GCN-NEXT:    v_cmp_lt_f32_e32 vcc, s0, v1
+; GCN-NEXT:    v_mov_b32_e32 v1, 0x42640000
+; GCN-NEXT:    v_cmp_nlt_f32_e64 s[2:3], s0, 0
 ; GCN-NEXT:    v_interp_p2_f32 v0, v0, attr0.x
-; GCN-NEXT:    s_and_b64 s[2:3], s[2:3], vcc
+; GCN-NEXT:    v_cmp_nlt_f32_e32 vcc, s0, v1
 ; GCN-NEXT:    v_cmp_gt_f32_e64 s[0:1], 0, v0
-; GCN-NEXT:    s_xor_b64 s[4:5], s[2:3], -1
-; GCN-NEXT:    s_and_b64 s[0:1], s[0:1], s[4:5]
-; GCN-NEXT:    s_xor_b64 s[2:3], s[0:1], s[2:3]
-; GCN-NEXT:    s_xor_b64 s[2:3], s[2:3], -1
+; GCN-NEXT:    s_or_b64 s[2:3], s[2:3], vcc
+; GCN-NEXT:    s_and_b64 s[0:1], s[0:1], s[2:3]
+; GCN-NEXT:    s_xor_b64 s[2:3], s[2:3], s[0:1]
 ; GCN-NEXT:    s_or_b64 s[0:1], s[2:3], s[0:1]
 ; GCN-NEXT:    v_cndmask_b32_e64 v0, 0, 1.0, s[0:1]
 ; GCN-NEXT:    ; return to shader part epilog
 main_body:
   %tmp26 = fcmp nsz olt float %arg1, 0.000000e+00
   %tmp28 = call nsz float @llvm.amdgcn.interp.p2(float undef, float undef, i32 0, i32 0, i32 %arg2)
   %tmp29 = fcmp nsz olt float %arg1, 5.700000e+01
   %tmp31 = fcmp nsz olt float %tmp28, 0.000000e+00

llvm/test/CodeGen/X86/2009-03-23-MultiUseSched.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; REQUIRES: asserts
 ; RUN: llc < %s -mtriple=x86_64-linux -mcpu=corei7 -relocation-model=static | FileCheck %s
 
 ; The register-pressure scheduler should be able to schedule this in a
 ; way that does not require spills.
 
 @X = external dso_local global i64    ; <i64*> [#uses=25]
 
 define fastcc i64 @foo() nounwind {
 ; CHECK-LABEL: foo:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    pushq %r15
 ; CHECK-NEXT:    pushq %r14
+; CHECK-NEXT:    pushq %r13
 ; CHECK-NEXT:    pushq %r12
 ; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    movq X(%rip), %r8
-; CHECK-NEXT:    movq X(%rip), %r10
 ; CHECK-NEXT:    movq X(%rip), %r9
-; CHECK-NEXT:    movq X(%rip), %r12
 ; CHECK-NEXT:    movq X(%rip), %r15
+; CHECK-NEXT:    movq X(%rip), %rax
+; CHECK-NEXT:    movq X(%rip), %rdx
+; CHECK-NEXT:    movq X(%rip), %r12
 ; CHECK-NEXT:    movq X(%rip), %r14
 ; CHECK-NEXT:    movq X(%rip), %r11
-; CHECK-NEXT:    movq X(%rip), %rdx
-; CHECK-NEXT:    addq %r15, %rdx
-; CHECK-NEXT:    movq X(%rip), %rsi
-; CHECK-NEXT:    bswapq %rsi
-; CHECK-NEXT:    leaq (%r11,%r14), %rbx
-; CHECK-NEXT:    addq %r15, %rbx
-; CHECK-NEXT:    addq %rdx, %rbx
-; CHECK-NEXT:    addq %rsi, %rbx
-; CHECK-NEXT:    leaq (%r9,%r10), %rdx
-; CHECK-NEXT:    addq %rdx, %rdx
-; CHECK-NEXT:    addq %r8, %rdx
 ; CHECK-NEXT:    movq X(%rip), %rdi
-; CHECK-NEXT:    addq %rbx, %r12
-; CHECK-NEXT:    addq %r8, %rdx
-; CHECK-NEXT:    addq %rbx, %rdx
-; CHECK-NEXT:    bswapq %rdi
-; CHECK-NEXT:    leaq (%r15,%r14), %rsi
-; CHECK-NEXT:    addq %r12, %rsi
-; CHECK-NEXT:    addq %r11, %rdi
-; CHECK-NEXT:    addq %rsi, %rdi
-; CHECK-NEXT:    leaq (%r10,%r8), %rsi
-; CHECK-NEXT:    addq %rsi, %rsi
-; CHECK-NEXT:    addq %rdx, %rsi
-; CHECK-NEXT:    movq X(%rip), %rbx
 ; CHECK-NEXT:    addq %r12, %rdi
-; CHECK-NEXT:    addq %rdi, %r9
-; CHECK-NEXT:    addq %rdx, %rsi
+; CHECK-NEXT:    movq X(%rip), %rcx
+; CHECK-NEXT:    movq X(%rip), %rbx
+; CHECK-NEXT:    bswapq %rcx
+; CHECK-NEXT:    leaq (%r11,%r14), %rsi
+; CHECK-NEXT:    addq %r12, %rsi
 ; CHECK-NEXT:    addq %rdi, %rsi
+; CHECK-NEXT:    addq %rcx, %rsi
+; CHECK-NEXT:    leaq (%r15,%r9), %r8
+; CHECK-NEXT:    leaq (%r8,%rax), %r10
+; CHECK-NEXT:    addq %rsi, %rdx
+; CHECK-NEXT:    addq %r10, %r10
 ; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%r12,%r15), %rdi
-; CHECK-NEXT:    addq %r9, %rdi
-; CHECK-NEXT:    addq %r14, %rbx
-; CHECK-NEXT:    addq %rdi, %rbx
-; CHECK-NEXT:    leaq (%rdx,%r8), %rdi
-; CHECK-NEXT:    addq %rdi, %rdi
-; CHECK-NEXT:    addq %rsi, %rdi
+; CHECK-NEXT:    addq %rsi, %r10
+; CHECK-NEXT:    addq %r11, %rbx
+; CHECK-NEXT:    leaq (%r12,%r14), %rcx
+; CHECK-NEXT:    addq %rdx, %rcx
+; CHECK-NEXT:    addq %rcx, %rbx
+; CHECK-NEXT:    addq %r8, %r8
+; CHECK-NEXT:    addq %r10, %r8
 ; CHECK-NEXT:    movq X(%rip), %rcx
-; CHECK-NEXT:    addq %r9, %rbx
-; CHECK-NEXT:    addq %rbx, %r10
-; CHECK-NEXT:    addq %rsi, %rdi
-; CHECK-NEXT:    addq %rbx, %rdi
+; CHECK-NEXT:    addq %rdx, %rbx
+; CHECK-NEXT:    addq %rbx, %rax
+; CHECK-NEXT:    addq %r10, %r8
+; CHECK-NEXT:    addq %rbx, %r8
 ; CHECK-NEXT:    bswapq %rcx
-; CHECK-NEXT:    leaq (%r9,%r12), %rax
-; CHECK-NEXT:    addq %r10, %rax
-; CHECK-NEXT:    addq %r15, %rcx
+; CHECK-NEXT:    leaq (%rdx,%r12), %rsi
+; CHECK-NEXT:    addq %rax, %rsi
+; CHECK-NEXT:    addq %r14, %rcx
+; CHECK-NEXT:    addq %rsi, %rcx
+; CHECK-NEXT:    leaq (%r10,%r9), %rbx
+; CHECK-NEXT:    addq %rbx, %rbx
+; CHECK-NEXT:    addq %r8, %rbx
+; CHECK-NEXT:    movq X(%rip), %rdi
 ; CHECK-NEXT:    addq %rax, %rcx
-; CHECK-NEXT:    leaq (%rsi,%rdx), %r11
-; CHECK-NEXT:    addq %r11, %r11
-; CHECK-NEXT:    addq %rdi, %r11
-; CHECK-NEXT:    movq X(%rip), %rbx
-; CHECK-NEXT:    addq %r10, %rcx
-; CHECK-NEXT:    addq %rcx, %r8
-; CHECK-NEXT:    addq %rdi, %r11
-; CHECK-NEXT:    addq %rcx, %r11
-; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%r10,%r9), %rcx
-; CHECK-NEXT:    addq %r8, %rcx
-; CHECK-NEXT:    addq %r12, %rbx
+; CHECK-NEXT:    addq %rcx, %r15
+; CHECK-NEXT:    addq %r8, %rbx
 ; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    leaq (%rdi,%rsi), %r14
+; CHECK-NEXT:    bswapq %rdi
+; CHECK-NEXT:    leaq (%rax,%rdx), %rcx
+; CHECK-NEXT:    addq %r15, %rcx
+; CHECK-NEXT:    addq %r12, %rdi
+; CHECK-NEXT:    addq %rcx, %rdi
+; CHECK-NEXT:    leaq (%r8,%r10), %r12
+; CHECK-NEXT:    addq %r12, %r12
+; CHECK-NEXT:    addq %rbx, %r12
+; CHECK-NEXT:    movq X(%rip), %rcx
+; CHECK-NEXT:    addq %r15, %rdi
+; CHECK-NEXT:    addq %rdi, %r9
+; CHECK-NEXT:    addq %rbx, %r12
+; CHECK-NEXT:    addq %rdi, %r12
+; CHECK-NEXT:    bswapq %rcx
+; CHECK-NEXT:    leaq (%r15,%rax), %rdi
+; CHECK-NEXT:    addq %r9, %rdi
+; CHECK-NEXT:    addq %rdx, %rcx
+; CHECK-NEXT:    addq %rdi, %rcx
+; CHECK-NEXT:    leaq (%rbx,%r8), %r13
+; CHECK-NEXT:    addq %r13, %r13
+; CHECK-NEXT:    addq %r12, %r13
+; CHECK-NEXT:    movq X(%rip), %rdx
+; CHECK-NEXT:    addq %r9, %rcx
+; CHECK-NEXT:    addq %rcx, %r10
+; CHECK-NEXT:    addq %r12, %r13
+; CHECK-NEXT:    addq %rcx, %r13
+; CHECK-NEXT:    bswapq %rdx
+; CHECK-NEXT:    leaq (%r9,%r15), %rcx
+; CHECK-NEXT:    addq %r10, %rcx
+; CHECK-NEXT:    addq %rax, %rdx
+; CHECK-NEXT:    addq %rcx, %rdx
+; CHECK-NEXT:    leaq (%r12,%rbx), %r14
 ; CHECK-NEXT:    addq %r14, %r14
-; CHECK-NEXT:    addq %r11, %r14
+; CHECK-NEXT:    addq %r13, %r14
 ; CHECK-NEXT:    movq X(%rip), %rax
-; CHECK-NEXT:    addq %r8, %rbx
-; CHECK-NEXT:    addq %rbx, %rdx
-; CHECK-NEXT:    addq %r11, %r14
-; CHECK-NEXT:    addq %rbx, %r14
+; CHECK-NEXT:    addq %r10, %rdx
+; CHECK-NEXT:    addq %rdx, %r8
+; CHECK-NEXT:    addq %r13, %r14
+; CHECK-NEXT:    addq %rdx, %r14
 ; CHECK-NEXT:    bswapq %rax
-; CHECK-NEXT:    leaq (%r8,%r10), %rbx
-; CHECK-NEXT:    addq %rdx, %rbx
-; CHECK-NEXT:    addq %r9, %rax
+; CHECK-NEXT:    leaq (%r10,%r9), %rcx
+; CHECK-NEXT:    addq %r8, %rcx
+; CHECK-NEXT:    addq %r15, %rax
+; CHECK-NEXT:    addq %rcx, %rax
+; CHECK-NEXT:    leaq (%r13,%r12), %r11
+; CHECK-NEXT:    addq %r11, %r11
+; CHECK-NEXT:    addq %r14, %r11
+; CHECK-NEXT:    movq X(%rip), %rcx
+; CHECK-NEXT:    addq %r8, %rax
+; CHECK-NEXT:    addq %rax, %rbx
+; CHECK-NEXT:    addq %r14, %r11
+; CHECK-NEXT:    addq %rax, %r11
+; CHECK-NEXT:    bswapq %rcx
+; CHECK-NEXT:    leaq (%r8,%r10), %rax
 ; CHECK-NEXT:    addq %rbx, %rax
-; CHECK-NEXT:    leaq (%r11,%rdi), %r9
+; CHECK-NEXT:    addq %r9, %rcx
+; CHECK-NEXT:    addq %rax, %rcx
+; CHECK-NEXT:    leaq (%r14,%r13), %r9
 ; CHECK-NEXT:    addq %r9, %r9
-; CHECK-NEXT:    addq %r14, %r9
-; CHECK-NEXT:    movq X(%rip), %rbx
-; CHECK-NEXT:    addq %rdx, %rax
-; CHECK-NEXT:    addq %rax, %rsi
-; CHECK-NEXT:    addq %r14, %r9
-; CHECK-NEXT:    addq %rax, %r9
-; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%rdx,%r8), %rax
-; CHECK-NEXT:    addq %rsi, %rax
-; CHECK-NEXT:    addq %r10, %rbx
-; CHECK-NEXT:    addq %rax, %rbx
-; CHECK-NEXT:    leaq (%r14,%r11), %r10
+; CHECK-NEXT:    addq %r11, %r9
+; CHECK-NEXT:    movq X(%rip), %rax
+; CHECK-NEXT:    addq %rbx, %rcx
+; CHECK-NEXT:    addq %rcx, %r12
+; CHECK-NEXT:    addq %r11, %r9
+; CHECK-NEXT:    addq %rcx, %r9
+; CHECK-NEXT:    bswapq %rax
+; CHECK-NEXT:    leaq (%rbx,%r8), %rcx
+; CHECK-NEXT:    addq %r12, %rcx
+; CHECK-NEXT:    addq %r10, %rax
+; CHECK-NEXT:    addq %rcx, %rax
+; CHECK-NEXT:    leaq (%r11,%r14), %r10
 ; CHECK-NEXT:    addq %r10, %r10
 ; CHECK-NEXT:    addq %r9, %r10
-; CHECK-NEXT:    movq X(%rip), %rax
-; CHECK-NEXT:    addq %rsi, %rbx
-; CHECK-NEXT:    addq %rbx, %rdi
+; CHECK-NEXT:    movq X(%rip), %rsi
+; CHECK-NEXT:    addq %r12, %rax
+; CHECK-NEXT:    addq %rax, %r13
 ; CHECK-NEXT:    addq %r9, %r10
-; CHECK-NEXT:    addq %rbx, %r10
+; CHECK-NEXT:    addq %rax, %r10
+; CHECK-NEXT:    bswapq %rsi
+; CHECK-NEXT:    leaq (%r12,%rbx), %rax
+; CHECK-NEXT:    addq %r13, %rax
+; CHECK-NEXT:    addq %r8, %rsi
+; CHECK-NEXT:    addq %rax, %rsi
+; CHECK-NEXT:    leaq (%r9,%r11), %rdx
+; CHECK-NEXT:    addq %rdx, %rdx
+; CHECK-NEXT:    addq %r10, %rdx
+; CHECK-NEXT:    movq X(%rip), %rax
+; CHECK-NEXT:    addq %r13, %rsi
+; CHECK-NEXT:    addq %rsi, %r14
+; CHECK-NEXT:    addq %r10, %rdx
+; CHECK-NEXT:    addq %rsi, %rdx
 ; CHECK-NEXT:    bswapq %rax
-; CHECK-NEXT:    leaq (%rsi,%rdx), %rbx
-; CHECK-NEXT:    addq %rdi, %rbx
-; CHECK-NEXT:    addq %r8, %rax
+; CHECK-NEXT:    leaq (%r13,%r12), %rsi
+; CHECK-NEXT:    addq %r14, %rsi
 ; CHECK-NEXT:    addq %rbx, %rax
-; CHECK-NEXT:    leaq (%r9,%r14), %r8
+; CHECK-NEXT:    addq %rsi, %rax
+; CHECK-NEXT:    leaq (%r10,%r9), %r8
 ; CHECK-NEXT:    addq %r8, %r8
-; CHECK-NEXT:    addq %r10, %r8
-; CHECK-NEXT:    movq X(%rip), %rbx
-; CHECK-NEXT:    addq %rdi, %rax
+; CHECK-NEXT:    addq %rdx, %r8
+; CHECK-NEXT:    movq X(%rip), %rsi
+; CHECK-NEXT:    addq %r14, %rax
 ; CHECK-NEXT:    addq %rax, %r11
-; CHECK-NEXT:    addq %r10, %r8
+; CHECK-NEXT:    addq %rdx, %r8
 ; CHECK-NEXT:    addq %rax, %r8
-; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%rdi,%rsi), %rax
+; CHECK-NEXT:    bswapq %rsi
+; CHECK-NEXT:    leaq (%r14,%r13), %rax
 ; CHECK-NEXT:    addq %r11, %rax
-; CHECK-NEXT:    addq %rdx, %rbx
-; CHECK-NEXT:    addq %rax, %rbx
-; CHECK-NEXT:    leaq (%r10,%r9), %r15
-; CHECK-NEXT:    addq %r15, %r15
-; CHECK-NEXT:    addq %r8, %r15
-; CHECK-NEXT:    movq X(%rip), %rax
-; CHECK-NEXT:    addq %r11, %rbx
-; CHECK-NEXT:    addq %rbx, %r14
-; CHECK-NEXT:    addq %r8, %r15
-; CHECK-NEXT:    addq %rbx, %r15
-; CHECK-NEXT:    bswapq %rax
-; CHECK-NEXT:    leaq (%r11,%rdi), %rbx
-; CHECK-NEXT:    addq %r14, %rbx
+; CHECK-NEXT:    addq %r12, %rsi
+; CHECK-NEXT:    addq %rax, %rsi
+; CHECK-NEXT:    leaq (%rdx,%r10), %rax
+; CHECK-NEXT:    addq %rax, %rax
+; CHECK-NEXT:    addq %r8, %rax
+; CHECK-NEXT:    movq X(%rip), %rdi
+; CHECK-NEXT:    addq %r11, %rsi
+; CHECK-NEXT:    addq %rsi, %r9
+; CHECK-NEXT:    addq %r8, %rax
 ; CHECK-NEXT:    addq %rsi, %rax
-; CHECK-NEXT:    addq %rbx, %rax
-; CHECK-NEXT:    leaq (%r8,%r10), %rsi
+; CHECK-NEXT:    bswapq %rdi
+; CHECK-NEXT:    leaq (%r11,%r14), %rsi
+; CHECK-NEXT:    addq %r9, %rsi
+; CHECK-NEXT:    addq %r13, %rdi
+; CHECK-NEXT:    addq %rsi, %rdi
+; CHECK-NEXT:    leaq (%r8,%rdx), %rsi
 ; CHECK-NEXT:    addq %rsi, %rsi
-; CHECK-NEXT:    addq %r15, %rsi
-; CHECK-NEXT:    movq X(%rip), %rbx
-; CHECK-NEXT:    addq %r14, %rax
-; CHECK-NEXT:    addq %rax, %r9
-; CHECK-NEXT:    addq %r15, %rsi
 ; CHECK-NEXT:    addq %rax, %rsi
-; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%r14,%r11), %rax
-; CHECK-NEXT:    addq %r9, %rax
-; CHECK-NEXT:    addq %rdi, %rbx
-; CHECK-NEXT:    addq %rax, %rbx
-; CHECK-NEXT:    leaq (%r15,%r8), %r12
-; CHECK-NEXT:    addq %r12, %r12
-; CHECK-NEXT:    addq %rsi, %r12
 ; CHECK-NEXT:    movq X(%rip), %rcx
-; CHECK-NEXT:    addq %r9, %rbx
-; CHECK-NEXT:    addq %rbx, %r10
-; CHECK-NEXT:    addq %rsi, %r12
-; CHECK-NEXT:    addq %rbx, %r12
+; CHECK-NEXT:    addq %r9, %rdi
+; CHECK-NEXT:    addq %rdi, %r10
+; CHECK-NEXT:    addq %rax, %rsi
+; CHECK-NEXT:    addq %rdi, %rsi
 ; CHECK-NEXT:    bswapq %rcx
-; CHECK-NEXT:    leaq (%r9,%r14), %rax
-; CHECK-NEXT:    addq %r10, %rax
-; CHECK-NEXT:    addq %r11, %rcx
-; CHECK-NEXT:    addq %rax, %rcx
-; CHECK-NEXT:    leaq (%rsi,%r15), %rax
-; CHECK-NEXT:    addq %rax, %rax
-; CHECK-NEXT:    addq %r12, %rax
-; CHECK-NEXT:    movq X(%rip), %rbx
+; CHECK-NEXT:    leaq (%r9,%r11), %rdi
+; CHECK-NEXT:    addq %r10, %rdi
+; CHECK-NEXT:    addq %r14, %rcx
+; CHECK-NEXT:    addq %rdi, %rcx
+; CHECK-NEXT:    leaq (%rax,%r8), %rdi
+; CHECK-NEXT:    addq %rdi, %rdi
+; CHECK-NEXT:    addq %rsi, %rdi
 ; CHECK-NEXT:    addq %r10, %rcx
-; CHECK-NEXT:    addq %rcx, %r8
-; CHECK-NEXT:    addq %r12, %rax
-; CHECK-NEXT:    addq %rcx, %rax
-; CHECK-NEXT:    bswapq %rbx
-; CHECK-NEXT:    leaq (%r10,%r9), %rcx
-; CHECK-NEXT:    addq %r8, %rcx
-; CHECK-NEXT:    addq %r14, %rbx
-; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    leaq (%r12,%rsi), %rcx
-; CHECK-NEXT:    addq %rcx, %rcx
-; CHECK-NEXT:    addq %rax, %rcx
-; CHECK-NEXT:    movq X(%rip), %rdx
-; CHECK-NEXT:    addq %r8, %rbx
-; CHECK-NEXT:    addq %rbx, %r15
-; CHECK-NEXT:    addq %rax, %rcx
-; CHECK-NEXT:    addq %rbx, %rcx
-; CHECK-NEXT:    bswapq %rdx
-; CHECK-NEXT:    leaq (%r8,%r10), %rbx
-; CHECK-NEXT:    addq %r15, %rbx
-; CHECK-NEXT:    addq %r9, %rdx
-; CHECK-NEXT:    addq %rbx, %rdx
-; CHECK-NEXT:    leaq (%rax,%r12), %rbx
-; CHECK-NEXT:    addq %rbx, %rbx
-; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    addq %r15, %rdx
-; CHECK-NEXT:    addq %rdx, %rsi
-; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    addq %rdx, %rbx
-; CHECK-NEXT:    movq X(%rip), %rdx
-; CHECK-NEXT:    bswapq %rdx
-; CHECK-NEXT:    addq %r10, %rdx
-; CHECK-NEXT:    leaq (%r15,%r8), %rdi
+; CHECK-NEXT:    addq %rcx, %rdx
 ; CHECK-NEXT:    addq %rsi, %rdi
-; CHECK-NEXT:    addq %rdi, %rdx
-; CHECK-NEXT:    addq %rax, %rcx
-; CHECK-NEXT:    addq %rcx, %rcx
-; CHECK-NEXT:    addq %rbx, %rcx
+; CHECK-NEXT:    addq %rcx, %rdi
+; CHECK-NEXT:    movq X(%rip), %rcx
+; CHECK-NEXT:    bswapq %rcx
+; CHECK-NEXT:    addq %r11, %rcx
+; CHECK-NEXT:    leaq (%r10,%r9), %rbx
+; CHECK-NEXT:    addq %rdx, %rbx
 ; CHECK-NEXT:    addq %rbx, %rcx
-; CHECK-NEXT:    addq %rsi, %rdx
-; CHECK-NEXT:    addq %rdx, %r12
+; CHECK-NEXT:    addq %rax, %rsi
+; CHECK-NEXT:    addq %rsi, %rsi
+; CHECK-NEXT:    addq %rdi, %rsi
+; CHECK-NEXT:    addq %rdi, %rsi
 ; CHECK-NEXT:    addq %rdx, %rcx
+; CHECK-NEXT:    addq %rcx, %r8
+; CHECK-NEXT:    addq %rcx, %rsi
 ; CHECK-NEXT:    movq X(%rip), %rax
 ; CHECK-NEXT:    bswapq %rax
-; CHECK-NEXT:    addq %r15, %rsi
+; CHECK-NEXT:    addq %r10, %rdx
 ; CHECK-NEXT:    movq %rax, X(%rip)
+; CHECK-NEXT:    addq %r9, %rax
+; CHECK-NEXT:    addq %r8, %rdx
+; CHECK-NEXT:    addq %rdx, %rax
 ; CHECK-NEXT:    addq %r8, %rax
-; CHECK-NEXT:    addq %r12, %rsi
 ; CHECK-NEXT:    addq %rsi, %rax
-; CHECK-NEXT:    addq %r12, %rax
-; CHECK-NEXT:    addq %rcx, %rax
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    popq %r12
+; CHECK-NEXT:    popq %r13
 ; CHECK-NEXT:    popq %r14
 ; CHECK-NEXT:    popq %r15
 ; CHECK-NEXT:    retq
   %tmp = load volatile i64, i64* @X    ; <i64> [#uses=7]
   %tmp1 = load volatile i64, i64* @X    ; <i64> [#uses=5]
   %tmp2 = load volatile i64, i64* @X    ; <i64> [#uses=3]
   %tmp3 = load volatile i64, i64* @X    ; <i64> [#uses=1]
   %tmp4 = load volatile i64, i64* @X    ; <i64> [#uses=5]

llvm/test/CodeGen/X86/ctpop-combine.ll

; NO-POPCOUNT-NEXT:    retq
   %cmp = icmp ne i64 %count, 1
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define i1 @ctpop_trunc_non_power2(i255 %x) nounwind {
 ; CHECK-LABEL: ctpop_trunc_non_power2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %rbx
 ; CHECK-NEXT:    movabsq $9223372036854775807, %r8 # imm = 0x7FFFFFFFFFFFFFFF
 ; CHECK-NEXT:    movq %rcx, %r9
 ; CHECK-NEXT:    andq %r8, %r9
-; CHECK-NEXT:    movq %rdi, %r11
-; CHECK-NEXT:    addq $-1, %r11
-; CHECK-NEXT:    movq %rsi, %r10
-; CHECK-NEXT:    adcq $-1, %r10
-; CHECK-NEXT:    movq %rdx, %rax
+; CHECK-NEXT:    movq %rdi, %r10
+; CHECK-NEXT:    addq $-1, %r10
+; CHECK-NEXT:    movq %rsi, %rax
 ; CHECK-NEXT:    adcq $-1, %rax
-; CHECK-NEXT:    movq %rcx, %rbx
-; CHECK-NEXT:    adcq %r8, %rbx
-; CHECK-NEXT:    andq %rdi, %r11
-; CHECK-NEXT:    andq %rdx, %rax
+; CHECK-NEXT:    movq %rdx, %r11
+; CHECK-NEXT:    adcq $-1, %r11
+; CHECK-NEXT:    adcq %r8, %rcx
+; CHECK-NEXT:    andq %rdi, %r10
+; CHECK-NEXT:    andq %rdx, %r11
+; CHECK-NEXT:    orq %r10, %r11
+; CHECK-NEXT:    andq %r9, %rcx
+; CHECK-NEXT:    andq %rsi, %rax
+; CHECK-NEXT:    orq %rcx, %rax
 ; CHECK-NEXT:    orq %r11, %rax
-; CHECK-NEXT:    andq %rsi, %r10
-; CHECK-NEXT:    andq %r8, %rbx
-; CHECK-NEXT:    andq %rcx, %rbx
-; CHECK-NEXT:    orq %r10, %rbx
-; CHECK-NEXT:    orq %rax, %rbx
 ; CHECK-NEXT:    sete %cl
 ; CHECK-NEXT:    orq %rdx, %rdi
 ; CHECK-NEXT:    orq %rsi, %r9
 ; CHECK-NEXT:    orq %rdi, %r9
 ; CHECK-NEXT:    setne %al
 ; CHECK-NEXT:    andb %cl, %al
-; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
   %a = call i255 @llvm.ctpop.i255(i255 %x)
   %b = trunc i255 %a to i8 ; largest value from ctpop is 255, fits in 8 bits.
   %c = icmp eq i8 %b, 1
   ret i1 %c
 }
 declare i255 @llvm.ctpop.i255(i255)