Fix shift legalization and lowering for big constants.

[chfast]

Summary

If shift amount is a constant value > 64 bit it is handled incorrectly during type legalization and X86 lowering. This patch the type of shift amount argument in function DAGTypeLegalizer::ExpandShiftByConstant from unsigned to APInt.

[chfast]

Ping.

[chfast]

Ping².

[sanjoy]

I don't see anything wrong with the change, but I don't understand the ins and outs (no pun intended!) of SelectionDAG well enough to give an explicit LGTM.

[chfast]

Ok, thanks, I will wait some more.

The change is not much about SelectionDAG. I just want to avoid calling getZExtValue() at line 2180 when the value of the APInt cannot fit 64 bits.

[chfast]

However, I would be very happy if I could commit that before 3.7 release is branched.

[RKSimon]

Hi Paweł - comments below.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2175

I'm not sure about this - ExpandShiftByConstant already handles shift amounts out of range, setting the result to zero/signbit for logical/arithmetic shifts instead of undef.

I think it better to change ExpandShiftByConstant shift amount to take an APInt type instead of an unsigned and update its handling to compare using APInt.

If you want to make a case for returning undef for constant shift results it should be in a separate patch.

test/CodeGen/X86/legalize-shl-vec.ll

4

It would be better if these tests checked the resultant codegen, rather than just test for a crash.

[chfast]

Thanks Simon for the comments. I will do as you suggested.

[chfast]

I changed DAGTypeLegalizer::ExpandShiftByConstant to accept APInt as the shift amount.
There is one quirk in that: because there is not operator- for pair (uint64_t, APInt)
I workarounded it with strage looking -Amt + NVTBits.

[RKSimon]

LGTM, thanks.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

std::pair <SDValue, SDValue> DAGTypeLegalizer::ExpandAtomic(SDNode *Node) {
   unsigned Opc = Node->getOpcode();
   MVT VT = cast<AtomicSDNode>(Node)->getMemoryVT().getSimpleVT();
   RTLIB::Libcall LC = RTLIB::getATOMIC(Opc, VT);
   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected atomic op or value type!");
 
   return ExpandChainLibCall(LC, Node, false);
 }
 
-/// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
+/// N is a shift by a value that needs to be expanded,
 /// and the shift amount is a constant 'Amt'.  Expand the operation.
-void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
+void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, const APInt &Amt,
                                              SDValue &Lo, SDValue &Hi) {
   SDLoc DL(N);
   // Expand the incoming operand to be shifted, so that we have its parts
   SDValue InL, InH;
   GetExpandedInteger(N->getOperand(0), InL, InH);
 
   // Though Amt shouldn't usually be 0, it's possible. E.g. when legalization
   // splitted a vector shift, like this: <op1, op2> SHL <0, 2>.
   if (!Amt) {
     Lo = InL;
     Hi = InH;
     return;
   }
 
   EVT NVT = InL.getValueType();
   unsigned VTBits = N->getValueType(0).getSizeInBits();
   unsigned NVTBits = NVT.getSizeInBits();
   EVT ShTy = N->getOperand(1).getValueType();
 
   if (N->getOpcode() == ISD::SHL) {
-    if (Amt > VTBits) {
+    if (Amt.ugt(VTBits)) {
       Lo = Hi = DAG.getConstant(0, DL, NVT);
-    } else if (Amt > NVTBits) {
+    } else if (Amt.ugt(NVTBits)) {
       Lo = DAG.getConstant(0, DL, NVT);
       Hi = DAG.getNode(ISD::SHL, DL,
-                       NVT, InL, DAG.getConstant(Amt - NVTBits, DL, ShTy));
+                       NVT, InL, DAG.getConstant(-Amt + NVTBits, DL, ShTy));
     } else if (Amt == NVTBits) {
       Lo = DAG.getConstant(0, DL, NVT);
       Hi = InL;
     } else if (Amt == 1 &&
                TLI.isOperationLegalOrCustom(ISD::ADDC,
                               TLI.getTypeToExpandTo(*DAG.getContext(), NVT))) {
       // Emit this X << 1 as X+X.
       SDVTList VTList = DAG.getVTList(NVT, MVT::Glue);
       SDValue LoOps[2] = { InL, InL };
       Lo = DAG.getNode(ISD::ADDC, DL, VTList, LoOps);
       SDValue HiOps[3] = { InH, InH, Lo.getValue(1) };
       Hi = DAG.getNode(ISD::ADDE, DL, VTList, HiOps);
     } else {
       Lo = DAG.getNode(ISD::SHL, DL, NVT, InL, DAG.getConstant(Amt, DL, ShTy));
       Hi = DAG.getNode(ISD::OR, DL, NVT,
                        DAG.getNode(ISD::SHL, DL, NVT, InH,
                                    DAG.getConstant(Amt, DL, ShTy)),
                        DAG.getNode(ISD::SRL, DL, NVT, InL,
-                                   DAG.getConstant(NVTBits - Amt, DL, ShTy)));
+                                   DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
     }
     return;
   }
 
   if (N->getOpcode() == ISD::SRL) {
-    if (Amt > VTBits) {
-      Lo = DAG.getConstant(0, DL, NVT);
-      Hi = DAG.getConstant(0, DL, NVT);
-    } else if (Amt > NVTBits) {
+    if (Amt.ugt(VTBits)) {
+      Lo = Hi = DAG.getConstant(0, DL, NVT);
+    } else if (Amt.ugt(NVTBits)) {
       Lo = DAG.getNode(ISD::SRL, DL,
                        NVT, InH, DAG.getConstant(Amt - NVTBits, DL, ShTy));
       Hi = DAG.getConstant(0, DL, NVT);
     } else if (Amt == NVTBits) {
       Lo = InH;
       Hi = DAG.getConstant(0, DL, NVT);
     } else {
       Lo = DAG.getNode(ISD::OR, DL, NVT,
                        DAG.getNode(ISD::SRL, DL, NVT, InL,
                                    DAG.getConstant(Amt, DL, ShTy)),
                        DAG.getNode(ISD::SHL, DL, NVT, InH,
-                                   DAG.getConstant(NVTBits - Amt, DL, ShTy)));
+                                   DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
       Hi = DAG.getNode(ISD::SRL, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
     }
     return;
   }
 
   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
-  if (Amt > VTBits) {
+  if (Amt.ugt(VTBits)) {
     Hi = Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
                           DAG.getConstant(NVTBits - 1, DL, ShTy));
-  } else if (Amt > NVTBits) {
+  } else if (Amt.ugt(NVTBits)) {
     Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
-                     DAG.getConstant(Amt-NVTBits, DL, ShTy));
+                     DAG.getConstant(Amt - NVTBits, DL, ShTy));
     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
                      DAG.getConstant(NVTBits - 1, DL, ShTy));
   } else if (Amt == NVTBits) {
     Lo = InH;
     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
                      DAG.getConstant(NVTBits - 1, DL, ShTy));
   } else {
     Lo = DAG.getNode(ISD::OR, DL, NVT,
                      DAG.getNode(ISD::SRL, DL, NVT, InL,
                                  DAG.getConstant(Amt, DL, ShTy)),
                      DAG.getNode(ISD::SHL, DL, NVT, InH,
-                                 DAG.getConstant(NVTBits - Amt, DL, ShTy)));
+                                 DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
   }
 }
 
 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
 /// this shift based on knowledge of the high bit of the shift amount.  If we
 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
 /// shift amount.

 void DAGTypeLegalizer::ExpandIntRes_Shift(SDNode *N,
                                           SDValue &Lo, SDValue &Hi) {
   EVT VT = N->getValueType(0);
   SDLoc dl(N);
 
   // If we can emit an efficient shift operation, do so now.  Check to see if
   // the RHS is a constant.
   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
-    return ExpandShiftByConstant(N, CN->getZExtValue(), Lo, Hi);
+    return ExpandShiftByConstant(N, CN->getAPIntValue(), Lo, Hi);
 
   // If we can determine that the high bit of the shift is zero or one, even if
   // the low bits are variable, emit this shift in an optimized form.
   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
     return;
 
   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
   unsigned PartsOpc;

lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   /// DisintegrateMERGE_VALUES - Replace each result of the given MERGE_VALUES
   /// node with the corresponding input operand, except for the result 'ResNo',
   /// for which the corresponding input operand is returned.
   SDValue DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo);
 
   SDValue GetVectorElementPointer(SDValue VecPtr, EVT EltVT, SDValue Index);
   SDValue JoinIntegers(SDValue Lo, SDValue Hi);
   SDValue LibCallify(RTLIB::Libcall LC, SDNode *N, bool isSigned);
-  
   std::pair<SDValue, SDValue> ExpandChainLibCall(RTLIB::Libcall LC,
                                                  SDNode *Node, bool isSigned);
   std::pair<SDValue, SDValue> ExpandAtomic(SDNode *Node);
 
   SDValue PromoteTargetBoolean(SDValue Bool, EVT ValVT);
   void ReplaceValueWith(SDValue From, SDValue To);
   void SplitInteger(SDValue Op, SDValue &Lo, SDValue &Hi);
   void SplitInteger(SDValue Op, EVT LoVT, EVT HiVT,
private:
   void ExpandIntRes_Shift             (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandIntRes_SADDSUBO          (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_UADDSUBO          (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_XMULO             (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandIntRes_ATOMIC_LOAD       (SDNode *N, SDValue &Lo, SDValue &Hi);
 
-  void ExpandShiftByConstant(SDNode *N, unsigned Amt,
+  void ExpandShiftByConstant(SDNode *N, const APInt &Amt,
                              SDValue &Lo, SDValue &Hi);
   bool ExpandShiftWithKnownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi);
   bool ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi);
 
   // Integer Operand Expansion.
   bool ExpandIntegerOperand(SDNode *N, unsigned OperandNo);
   SDValue ExpandIntOp_BITCAST(SDNode *N);
   SDValue ExpandIntOp_BR_CC(SDNode *N);

lib/Target/X86/X86ISelLowering.cpp

static SDValue PerformSHLCombine(SDNode *N, SelectionDAG &DAG) {
   // shl.
   // (shl V, 1) -> add V,V
   if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
     if (auto *N1SplatC = N1BV->getConstantSplatNode()) {
       assert(N0.getValueType().isVector() && "Invalid vector shift type");
       // We shift all of the values by one. In many cases we do not have
       // hardware support for this operation. This is better expressed as an ADD
       // of two values.
-      if (N1SplatC->getZExtValue() == 1)
+      if (N1SplatC->getAPIntValue() == 1)
         return DAG.getNode(ISD::ADD, SDLoc(N), VT, N0, N0);
     }
 
   return SDValue();
 }
 
 /// \brief Returns a vector of 0s if the node in input is a vector logical
 /// shift by a constant amount which is known to be bigger than or equal

test/CodeGen/X86/legalize-shl-vec.ll

+; RUN: llc < %s -march=x86-64 | FileCheck %s
+
+define <2 x i256> @test_shl(<2 x i256> %In) {
+  %Amt = insertelement <2 x i256> undef, i256 -1, i32 0
+  %Out = shl <2 x i256> %In, %Amt
+  ret <2 x i256> %Out
+
+  ; CHECK-LABEL: test_shl
+  ; CHECK:       movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK:       retq
+}
+
+define <2 x i256> @test_srl(<2 x i256> %In) {
+  %Amt = insertelement <2 x i256> undef, i256 -1, i32 0
+  %Out = lshr <2 x i256> %In, %Amt
+  ret <2 x i256> %Out
+
+  ; CHECK-LABEL: test_srl
+  ; CHECK:       movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK-NEXT:  movq $0
+  ; CHECK:       retq
+}
+
+define <2 x i256> @test_sra(<2 x i256> %In) {
+  %Amt = insertelement <2 x i256> undef, i256 -1, i32 0
+  %Out = ashr <2 x i256> %In, %Amt
+  ret <2 x i256> %Out
+
+  ; CHECK-LABEL: test_sra
+  ; CHECK:       sarq $63
+}