thr3ads.net - llvm dev - [LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit [Dec 2009]

If this information is useful, please help other people find it:
Share via:

Javier Martinez

2009-Dec-01 03:22 UTC

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

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;
}

Eli Friedman

2009-Dec-01 03:59 UTC

head link

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

On Mon, Nov 30, 2009 at 7:22 PM, Javier Martinez <javier at jmartinez.org>
wrote:> 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?
[snip]

Please use "svn diff" to generate proposed patches; the form you used
is extremely difficult to read.

-Eli

Javier Martinez

2009-Dec-01 06:18 UTC

head link

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

Hi Eli,

I'm not familiar with how to use SVN that way plus my code is based off 2.4
so I can't compare with TOT. Attached are Unix diff and HTML reports of the
changes to ExpandShiftWithUnknownAmountBit using a different tool (Araxis
Merge). I hope this suffices.

Thanks,
Javier

On Mon, 30 Nov 2009 19:59:26 -0800, Eli Friedman <eli.friedman at
gmail.com>
wrote:> On Mon, Nov 30, 2009 at 7:22 PM, Javier Martinez <javier at
jmartinez.org>
> wrote:
>> 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?
> 
> [snip]
> 
> Please use "svn diff" to generate proposed patches; the form you
used
> is extremely difficult to read.
> 
> -Eli-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091130/70804e49/attachment.html>
-------------- next part --------------
18c18,19
<   SDValue Amt2 = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
--->   SDValue NVSizeSubAmt = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
>   SDValue AmtSubNVSize = DAG.getNode(ISD::SUB, dl, ShTy, Amt, NVBitsNode);27,28c28,31
<     Lo1 = DAG.getConstant(0, NVT);                  // Low part is zero.
<     Hi1 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo
part.
--->     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));31,34c34,35
<     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));
--->     Lo2 = DAG.getConstant(0, NVT);                           // Low part is
zero.
>     Hi2 = DAG.getNode(ISD::SHL, dl, NVT, InL, AmtSubNVSize); // High part
from Lo part.41,42c42,45
<     Hi1 = DAG.getConstant(0, NVT);                  // Hi part is zero.
<     Lo1 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi
part.
--->     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);45,48c48,49
<     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));
--->     Lo2 = DAG.getNode(ISD::SRL, dl, NVT, InH, AmtSubNVSize); // Lo part
from Hi part.
>     Hi2 = DAG.getConstant(0, NVT);                           // Hi part is
zero.55,57c56,59
<     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.
--->     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);60,63c62,63
<     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));
--->     Lo2 = DAG.getNode(ISD::SRA, dl, NVT, InH, AmtSubNVSize); // Lo part
from Hi part.
>     Hi2 = DAG.getConstant(0, NVT);                           // Hi part is
zero.72d71
<

Duncan Sands

2009-Dec-01 09:01 UTC

head link

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

Hi,
> 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?
can you please describe the problem and how you fix it (in words, not code).

Thanks,

Duncan.

Javier Martinez

2009-Dec-01 09:50 UTC

head link

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

Hi Duncan,

The problem is the implementation of the expansion. Perhaps an example 
can help illustrate better. Take the case of a 64-bit integer shifted 
left by say 6 bits and is decomposed using 32-bit registers. Because 6 
is less than the 32 (the register size) the resulting low part should be 
equal to the source low part shifted left by 6 bits. The current 
implementation places a zero instead. All other values have similar 
errors. Below is the current and proposed expansion in pseudo C++ for 
all shift functions. Please let me know if I something is unclear.

- SHL:
[Current]
dst.lo = (shift < regsize) ? 0 : src.lo << shift;
dst.hi = (shift < regsize) ? src.lo << shift : ((src.hi << shift)
|
(src.lo >> regsize - shift));

[Proposed]
dst.lo = (shift < regsize) ? src.lo << shift : 0;
dst.hi = (shift < regsize) ? ((src.hi << shift) | (src.lo >>
shift -
regsize)) : src.lo << shift - regsize;

- SRL/SRA
[Current]
dst.lo = (shift < regsize) ? src.hi >> shift : ((src.lo >> shift)
|
(src.hi << regsize - shift));
dst.hi = (shift < regsize) ? 0 : src.hi >> shift;

[Proposed]
dst.lo = (shift < regsize) ? ((src.lo >> shift) | (src.hi <<
regsize -
shift)) : src.hi << shift - regsize;
dst.hi = (shift < regsize) ? src.hi << shift : 0;

Thanks,
Javier

On 12/1/2009 1:01 AM, Duncan Sands wrote:> Hi,
>
>> 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?
>
> can you please describe the problem and how you fix it (in words, not 
> code).
>
> Thanks,
>
> Duncan.

Reasonably Related Threads

Search for more possibly parallel threads

llvm dev - Dec 2009 - [LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

[LLVMdev] Possible bug in ExpandShiftWithUnknownAmountBit

Reasonably Related Threads