Change the policy of ZERO_EXTEND/SIGN_EXTEND for SelectionDAG builder and legalization

[Jiangning]

Summary

Hi Tim,

In SelectionDAG builder, we simply insert ZERO_EXTEND for CopyToReg if only TLI thinks ZERO_EXTEND is free.

This is not optimal if the virtual register has multiple compare instruction users crossing basic blocks.

The operand of a compare instruction could be promoted (extended) to be a signed/unsigned value if the predicate of the compare instruction IsSigned()/IsUnsigned. If multiple compare instructions use the same operand, we will unavoidably have conflict extension.

We have two optimization opportunities here,

1. If we know the number of signed predicate user is greater than unsigned, we prefer to use signed promotion, and we use zero promotion otherwise.
2. Predicates EQ and NE are neither signed nor unsigned, so they can be treated as either signed or unsigned. if know the incoming value is AssertSext, we should prefer to do signed promotion.

With those two optimizations, fewer signed/zero extension instructions can be inserted, and then we can expose more opportunities to Machine CSE pass in back-end.

For Cortex-A57, the following two benchmark performance improvements are observed.

spec.cpu2006.ref.470_lbm 1862.8973 -6.85%
spec.cpu2006.ref.444_namd 1549.8160 -5.43%

Thanks,
-Jiangning

[t.p.northover]

Hi Jiangning,

I think this is mostly fine. As usual, just a few nits.

Cheers.

Tim.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

875

I think this can be generalized slightly. It looks like the check against TRUNCATE is really just guarding against us deciding to apply sign extension to (assertsext LHS, i16) when we're actually emitting an i8 setcc.

I'd suggest something like

if (OpL->getOpcode() == ISD::AssertSext &&
    cast<VTSDNode>(OpL->getOperand(1))->getVT() == NewLHS.getValueType() &&
    [...]

878–879

Since we know the node is AssertSext at this point we don't need to do it again. You can just set NewLHS to OpL and NewRHS to OpR.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

778–779

Isn't there a "V->users()" adapter so you can use a range-based loop here?

It might be neater to split this logic into a separate static function too ("getPreferredExtendForValue" or something). I can see the body of that loop growing over time (with sdiv and udiv being the obvious extensions, but probably not the only ones).

[Jiangning]

Uploaded new patch.

[Jiangning]

Hi Tim,

Thanks for your comments! And I updated the code following your comments.

Thanks again!
-Jiangning

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

875

OK. I changed the code to be like this. But I think the only case is NewLHS and NEWRHS are TRUNCATE, so I added assertions inside the if body. Is there any other case except TRUNCATE?

878–879

Accepted and code is changed accordingly.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

778–779

Accepted and code is changed accordingly.

[t.p.northover]

Hi Jiangning,

Thanks for the update. I think those asserts will be a problem though:

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

875

Yes. In principle, it could come from any DAG combine or other inference (computeKnownBits for example) that inspected the input.

The simplest example I was able to exploit was PromoteIntRes_FP_TO_XINT. This program crashes with the asserts present:

define i1 @foo(float %inl, float %inr) {
  %lval = fptosi float %inl to i8
  %rval = fptosi float %inr to i8
  %sum = icmp eq i8 %lval, %rval
  ret i1 %sum
}

[Jiangning]

Hi Tim,

OK. I removed the asserts and added your small case in the test.

Thanks,
-Jiangning

[t.p.northover]

Hi Jiangning,

Thanks for updating again. I think this looks fine apart from one tiny formatting thing I spotted (sorry). Feel free to commit it with that change.

Tim.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

760–761

Formatting.

[Eugene.Zelenko]

Committed in rL216066.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

   switch (CCCode) {
   default: llvm_unreachable("Unknown integer comparison!");
   case ISD::SETEQ:
-  case ISD::SETNE:
+  case ISD::SETNE: {
+    SDValue OpL, OpR;
+
+    OpL = GetPromotedInteger(NewLHS);
+    OpR = GetPromotedInteger(NewRHS);
+
+    // We would prefer to promote the comparison operand with sign extension,
+    // if we find the operand is actually to truncate an AssertSext. With this
+    // optimization, we can avoid inserting real truncate instruction, which
+    // is redudant eventually.
+    if (OpL->getOpcode() == ISD::AssertSext &&
+        NewLHS->getOpcode() == ISD::TRUNCATE &&
+        OpR->getOpcode() == ISD::AssertSext &&
+        NewRHS->getOpcode() == ISD::TRUNCATE) {
+      NewLHS = SExtPromotedInteger(NewLHS);
+      NewRHS = SExtPromotedInteger(NewRHS);
+    } else {
+      NewLHS = ZExtPromotedInteger(NewLHS);
+      NewRHS = ZExtPromotedInteger(NewRHS);
+    }
+    break;
+  }
   case ISD::SETUGE:
   case ISD::SETUGT:
   case ISD::SETULE:

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

                                  const Value *V) const {
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
 
+  // For the users of the source value being used for compare instruction, if
+  // the number of signed predicate is greater than unsigned predicate, we
+  // prefer to use SIGN_EXTEND.
+  //
+  // With this optimization, we would be able to reduce some redundant sign or
+  // zero extension instruction, and eventually more machine CSE opportunities
+  // can be exposed.
+  ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
+  unsigned int NumOfSigned = 0, NumOfUnsigned = 0;
+  for (Value::const_user_iterator I = V->user_begin(), E = V->user_end();
+       I != E; ++I) {
+    const User *UI = *I;
+    if (const CmpInst *CI = dyn_cast<CmpInst>(UI)) {
+      NumOfSigned += CI->isSigned();
+      NumOfUnsigned += CI->isUnsigned();
+    }
+  }
+  if (NumOfSigned > NumOfUnsigned)
+    ExtendKind = ISD::SIGN_EXTEND;
+
   // Get the list of the values's legal parts.
   unsigned NumRegs = Regs.size();
   SmallVector<SDValue, 8> Parts(NumRegs);

     EVT ValueVT = ValueVTs[Value];
     unsigned NumParts = TLI.getNumRegisters(*DAG.getContext(), ValueVT);
     MVT RegisterVT = RegVTs[Value];
-    ISD::NodeType ExtendKind =
-      TLI.isZExtFree(Val, RegisterVT)? ISD::ZERO_EXTEND: ISD::ANY_EXTEND;
+
+    if (ExtendKind == ISD::ANY_EXTEND && TLI.isZExtFree(Val, RegisterVT))
+      ExtendKind = ISD::ZERO_EXTEND;
 
     getCopyToParts(DAG, dl, Val.getValue(Val.getResNo() + Value),
                    &Parts[Part], NumParts, RegisterVT, V, ExtendKind);

test/CodeGen/AArch64/atomic-ops.ll

 ; CHECK-LABEL: test_atomic_load_min_i8:
    %old = atomicrmw min i8* @var8, i8 %offset acquire
 ; CHECK-NOT: dmb
+; CHECK: sxtb w[[TMP:[0-9]+]], w0
 ; CHECK: adrp [[TMPADDR:x[0-9]+]], var8
 ; CHECK: add x[[ADDR:[0-9]+]], [[TMPADDR]], {{#?}}:lo12:var8
 

   ;  function there.
 
 ; CHECK-NEXT: sxtb w[[OLD_EXT:[0-9]+]], w[[OLD]]
-; CHECK-NEXT: cmp w[[OLD_EXT]], w0, sxtb
-; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w0, le
+; CHECK-NEXT: cmp w[[OLD_EXT]], w[[TMP]]
+; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w[[TMP]], le
 
 ; CHECK-NEXT: stxrb [[STATUS:w[0-9]+]], [[NEW]], [x[[ADDR]]]
 ; CHECK-NEXT: cbnz [[STATUS]], .LBB{{[0-9]+}}_1
 ; CHECK-NOT: dmb
 
-; CHECK: mov {{[xw]}}0, {{[xw]}}[[OLD]]
    ret i8 %old
 }
 

 ; CHECK-LABEL: test_atomic_load_min_i16:
    %old = atomicrmw min i16* @var16, i16 %offset release
 ; CHECK-NOT: dmb
+; CHECK: sxth w[[TMP:[0-9]+]], w0
 ; CHECK: adrp [[TMPADDR:x[0-9]+]], var16
 ; CHECK: add x[[ADDR:[0-9]+]], [[TMPADDR]], {{#?}}:lo12:var16
 

   ;  function there.
 
 ; CHECK-NEXT: sxth w[[OLD_EXT:[0-9]+]], w[[OLD]]
-; CHECK-NEXT: cmp w[[OLD_EXT]], w0, sxth
-; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w0, le
+; CHECK-NEXT: cmp w[[OLD_EXT]], w[[TMP]]
+; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w[[TMP]], le
 
 
 ; CHECK-NEXT: stlxrh [[STATUS:w[0-9]+]], [[NEW]], [x[[ADDR]]]
 ; CHECK-NEXT: cbnz [[STATUS]], .LBB{{[0-9]+}}_1
 ; CHECK-NOT: dmb
 
-; CHECK: mov {{[xw]}}0, {{[xw]}}[[OLD]]
    ret i16 %old
 }
 

 ; CHECK-LABEL: test_atomic_load_max_i8:
    %old = atomicrmw max i8* @var8, i8 %offset seq_cst
 ; CHECK-NOT: dmb
+; CHECK: sxtb w[[TMP:[0-9]+]], w0
 ; CHECK: adrp [[TMPADDR:x[0-9]+]], var8
 ; CHECK: add x[[ADDR:[0-9]+]], [[TMPADDR]], {{#?}}:lo12:var8
 

   ;  function there.
 
 ; CHECK-NEXT: sxtb w[[OLD_EXT:[0-9]+]], w[[OLD]]
-; CHECK-NEXT: cmp w[[OLD_EXT]], w0, sxtb
-; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w0, gt
+; CHECK-NEXT: cmp w[[OLD_EXT]], w[[TMP]]
+; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w[[TMP]], gt
 
 
 ; CHECK-NEXT: stlxrb [[STATUS:w[0-9]+]], [[NEW]], [x[[ADDR]]]
 ; CHECK-NEXT: cbnz [[STATUS]], .LBB{{[0-9]+}}_1
 ; CHECK-NOT: dmb
 
-; CHECK: mov {{[xw]}}0, {{[xw]}}[[OLD]]
    ret i8 %old
 }
 

 ; CHECK-LABEL: test_atomic_load_max_i16:
    %old = atomicrmw max i16* @var16, i16 %offset acquire
 ; CHECK-NOT: dmb
+; CHECK: sxth w[[TMP:[0-9]+]], w0
 ; CHECK: adrp [[TMPADDR:x[0-9]+]], var16
 ; CHECK: add x[[ADDR:[0-9]+]], [[TMPADDR]], {{#?}}:lo12:var16
 

   ;  function there.
 
 ; CHECK-NEXT: sxth w[[OLD_EXT:[0-9]+]], w[[OLD]]
-; CHECK-NEXT: cmp w[[OLD_EXT]], w0, sxth
-; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w0, gt
+; CHECK-NEXT: cmp w[[OLD_EXT]], w[[TMP]]
+; CHECK-NEXT: csel [[NEW:w[0-9]+]], w[[OLD]], w[[TMP]], gt
 
 
 ; CHECK-NEXT: stxrh [[STATUS:w[0-9]+]], [[NEW]], [x[[ADDR]]]
 ; CHECK-NEXT: cbnz [[STATUS]], .LBB{{[0-9]+}}_1
 ; CHECK-NOT: dmb
 
-; CHECK: mov {{[xw]}}0, {{[xw]}}[[OLD]]
    ret i16 %old
 }
 

test/CodeGen/AArch64/rm_redundant_cmp.ll

+; RUN: llc < %s -mtriple=aarch64-linux-gnuabi -O2 | FileCheck %s
+
+%struct.s_signed = type { i16, i16, i16 }
+%struct.s_unsigned = type { i16, i16, i16 }
+
+@cost_s = common global %struct.s_signed zeroinitializer, align 2
+@cost_u = common global %struct.s_unsigned zeroinitializer, align 2
+
+define void @test_2cmp_signed_1() {
+; CHECK-LABEL: test_2cmp_signed_1
+; CHECK: cmp {{w[0-9]+}}, {{w[0-9]+}}
+; CHECK-NEXT: b.gt
+; CHECK-NOT: cmp
+; CHECK: b.ne
+entry:
+  %0 = load i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 1), align 2
+  %1 = load i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 2), align 2
+  %cmp = icmp sgt i16 %0, %1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  store i16 %0, i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.else:                                          ; preds = %entry
+  %cmp5 = icmp eq i16 %0, %1
+  br i1 %cmp5, label %if.then7, label %if.end8
+
+if.then7:                                         ; preds = %if.else
+  store i16 %0, i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.end8:                                          ; preds = %if.else, %if.then7, %if.then
+  ret void
+}
+
+define void @test_2cmp_signed_2() {
+; CHECK-LABEL: test_2cmp_signed_2
+; CHECK: cmp {{w[0-9]+}}, {{w[0-9]+}}
+; CHECK-NEXT: b.le
+; CHECK-NOT: cmp
+; CHECK: b.ge
+entry:
+  %0 = load i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 1), align 2
+  %1 = load i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 2), align 2
+  %cmp = icmp sgt i16 %0, %1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  store i16 %0, i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.else:                                          ; preds = %entry
+  %cmp5 = icmp slt i16 %0, %1
+  br i1 %cmp5, label %if.then7, label %if.end8
+
+if.then7:                                         ; preds = %if.else
+  store i16 %1, i16* getelementptr inbounds (%struct.s_signed* @cost_s, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.end8:                                          ; preds = %if.else, %if.then7, %if.then
+  ret void
+}
+
+define void @test_2cmp_unsigned_1() {
+; CHECK-LABEL: test_2cmp_unsigned_1
+; CHECK: cmp {{w[0-9]+}}, {{w[0-9]+}}
+; CHECK-NEXT: b.hi
+; CHECK-NOT: cmp
+; CHECK: b.ne
+entry:
+  %0 = load i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 1), align 2
+  %1 = load i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 2), align 2
+  %cmp = icmp ugt i16 %0, %1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  store i16 %0, i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.else:                                          ; preds = %entry
+  %cmp5 = icmp eq i16 %0, %1
+  br i1 %cmp5, label %if.then7, label %if.end8
+
+if.then7:                                         ; preds = %if.else
+  store i16 %0, i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.end8:                                          ; preds = %if.else, %if.then7, %if.then
+  ret void
+}
+
+define void @test_2cmp_unsigned_2() {
+; CHECK-LABEL: test_2cmp_unsigned_2
+; CHECK: cmp {{w[0-9]+}}, {{w[0-9]+}}
+; CHECK-NEXT: b.ls
+; CHECK-NOT: cmp
+; CHECK: b.hs
+entry:
+  %0 = load i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 1), align 2
+  %1 = load i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 2), align 2
+  %cmp = icmp ugt i16 %0, %1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  store i16 %0, i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.else:                                          ; preds = %entry
+  %cmp5 = icmp ult i16 %0, %1
+  br i1 %cmp5, label %if.then7, label %if.end8
+
+if.then7:                                         ; preds = %if.else
+  store i16 %1, i16* getelementptr inbounds (%struct.s_unsigned* @cost_u, i64 0, i32 0), align 2
+  br label %if.end8
+
+if.end8:                                          ; preds = %if.else, %if.then7, %if.then
+  ret void
+}