[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[Javier Martinez]

Hello,

I'm working in adding support for 64-bit integers to my target. I'm using
LLVM to decompose the 64-bit integer operations by using 32-bit registers
wherever possible and emulating support where not. When looking at the bit
shift decomposition I saw what seems to be a bug in the implementation. The
affected function is ExpandShiftWithUnknownAmountBit in
LegalizeIntegerTypes.cpp. Below is the original code and the proposed fix.
Could someone please review the changes? If they are correct how do I go
about submitting a patch?

Thanks,
Javier

[Original]
/// ExpandShiftWithUnknownAmountBit - Fully general expansion of integer
shift
/// of any size.
bool DAGTypeLegalizer::
ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
  SDValue Amt = N->getOperand(1);
  EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(),
N->getValueType(0));
  EVT ShTy = Amt.getValueType();
  unsigned NVTBits = NVT.getSizeInBits();
  assert(isPowerOf2_32(NVTBits) &&
         "Expanded integer type size not a power of two!");
  DebugLoc dl = N->getDebugLoc();

  // Get the incoming operand to be shifted.
  SDValue InL, InH;
  GetExpandedInteger(N->getOperand(0), InL, InH);

  SDValue NVBitsNode = DAG.getConstant(NVTBits, ShTy);
  SDValue Amt2 = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
  SDValue Cmp = DAG.getSetCC(dl, TLI.getSetCCResultType(ShTy),
                             Amt, NVBitsNode, ISD::SETULT);

  SDValue Lo1, Hi1, Lo2, Hi2;
  switch (N->getOpcode()) {
  default: llvm_unreachable("Unknown shift");
  case ISD::SHL:
    // ShAmt < NVTBits
    Lo1 = DAG.getConstant(0, NVT);                  // Low part is zero.
    Hi1 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo
part.

    // ShAmt >= NVTBits
    Lo2 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);
    Hi2 = DAG.getNode(ISD::OR, dl, NVT,
                      DAG.getNode(ISD::SHL, dl, NVT, InH, Amt),
                      DAG.getNode(ISD::SRL, dl, NVT, InL, Amt2));

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  case ISD::SRL:
    // ShAmt < NVTBits
    Hi1 = DAG.getConstant(0, NVT);                  // Hi part is zero.
    Lo1 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi
part.

    // ShAmt >= NVTBits
    Hi2 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);
    Lo2 = DAG.getNode(ISD::OR, dl, NVT,
                     DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
                     DAG.getNode(ISD::SHL, dl, NVT, InH, Amt2));

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  case ISD::SRA:
    // ShAmt < NVTBits
    Hi1 = DAG.getNode(ISD::SRA, dl, NVT, InH,       // Sign extend high
part.
                       DAG.getConstant(NVTBits-1, ShTy));
    Lo1 = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt); // Lo part from Hi
part.

    // ShAmt >= NVTBits
    Hi2 = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);
    Lo2 = DAG.getNode(ISD::OR, dl, NVT,
                      DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
                      DAG.getNode(ISD::SHL, dl, NVT, InH, Amt2));

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  }

  return false;
}

[Proposed]
/// ExpandShiftWithUnknownAmountBit - Fully general expansion of integer
shift
/// of any size.
bool DAGTypeLegalizer::
ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
  SDValue Amt = N->getOperand(1);
  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
  MVT ShTy = Amt.getValueType();
  unsigned NVTBits = NVT.getSizeInBits();
  LLVM_ASSERT(isPowerOf2_32(NVTBits) &&
         "Expanded integer type size not a power of two!");
  DebugLoc dl = N->getDebugLoc();

  // Get the incoming operand to be shifted.
  SDValue InL, InH;
  GetExpandedInteger(N->getOperand(0), InL, InH);

  SDValue NVBitsNode = DAG.getConstant(NVTBits, ShTy);
  SDValue NVSizeSubAmt = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
  SDValue AmtSubNVSize = DAG.getNode(ISD::SUB, dl, ShTy, Amt, NVBitsNode);
  SDValue Cmp = DAG.getSetCC(dl, TLI.getSetCCResultType(ShTy),
                             Amt, NVBitsNode, ISD::SETULT);

  SDValue Lo1, Hi1, Lo2, Hi2;
  switch (N->getOpcode()) {
  default: LLVM_ASSERT(0 && "Unknown shift");
  case ISD::SHL:
    // ShAmt < NVTBits
    Lo1 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);
    Hi1 = DAG.getNode(ISD::OR, dl, NVT,
                      DAG.getNode(ISD::SHL, dl, NVT, InH, Amt),
                      DAG.getNode(ISD::SRL, dl, NVT, InL, NVSizeSubAmt));

    // ShAmt >= NVTBits
    Lo2 = DAG.getConstant(0, NVT);                           // Low part is
zero.
    Hi2 = DAG.getNode(ISD::SHL, dl, NVT, InL, AmtSubNVSize); // High part
from Lo part.

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  case ISD::SRL:
    // ShAmt < NVTBits
    Lo1 = DAG.getNode(ISD::OR, dl, NVT,
                     DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
                     DAG.getNode(ISD::SHL, dl, NVT, InH, NVSizeSubAmt));
    Hi1 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);

    // ShAmt >= NVTBits
    Lo2 = DAG.getNode(ISD::SRL, dl, NVT, InH, AmtSubNVSize); // Lo part
from Hi part.
    Hi2 = DAG.getConstant(0, NVT);                           // Hi part is
zero.

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  case ISD::SRA:
    // ShAmt < NVTBits
    Lo1 = DAG.getNode(ISD::OR, dl, NVT,
                     DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
                     DAG.getNode(ISD::SHL, dl, NVT, InH, NVSizeSubAmt));
    Hi1 = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);

    // ShAmt >= NVTBits
    Lo2 = DAG.getNode(ISD::SRA, dl, NVT, InH, AmtSubNVSize); // Lo part
from Hi part.
    Hi2 = DAG.getConstant(0, NVT);                           // Hi part is
zero.

    Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
    Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
    return true;
  }

  return false;
}