llvm dev - Dec 2009 - [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.

Hi Javier,
> 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.
I'm not sure what you are saying, here is the code for shift-left.  In
the case of your example, Amt = 6, VTBits = 64 and NVTBits = 32.  I've
added comments at the end of various lines, like this: <== Comment.

   if (N->getOpcode() == ISD::SHL) { <== This branch is taken
     if (Amt > VTBits) { <== False
... not executed ...
     } else if (Amt > NVTBits) { <== False
... not executed ...
     } else if (Amt == NVTBits) { <== False
... not executed ...
     } else if (Amt == 1 &&
                TLI.isOperationLegalOrCustom(ISD::ADDC, 
TLI.getTypeToExpandTo(*DAG.getContext(), NVT))) { <== False
... not executed ...
     } else { <== This branch is taken
       Lo = DAG.getNode(ISD::SHL, dl, NVT, InL, DAG.getConstant(Amt, ShTy));
<==
Source low part is shifted left by 6 bits
       Hi = DAG.getNode(ISD::OR, dl, NVT,
                        DAG.getNode(ISD::SHL, dl, NVT, InH,
                                    DAG.getConstant(Amt, ShTy)),
                        DAG.getNode(ISD::SRL, dl, NVT, InL,
                                    DAG.getConstant(NVTBits-Amt, ShTy))); <==
Source high part is shifted left by 6 bits, and the top 6 bits of the low part 
is or'd in
     }
     return;
   }

In short, the current code seems to be correct.

Ciao,

Duncan.

Duncan,

It seems that the code you pasted came from the function
ExpandShiftByConstant and indeed it looks correct. In my example I used 6
as the shift amount but forgot to mention that it's stored in a register.
Otherwise ExpandShiftWithUnknownAmountBit wouldn't get called. Below is the
execution of DAGTypeLegalizer::ExpandIntRes_Shift() using my example
showing how ExpandShiftWithUnknownAmountBit gets called. My email is about
the logic of this function.

if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1))) {
<=False
  ...
}

if (ExpandShiftWithKnownAmountBit(N, Lo, Hi)) { <== The call returns False
  ...
}

if (N->getOpcode() == ISD::SHL) { <== Branch taken
    PartsOpc = ISD::SHL_PARTS;
} else if (N->getOpcode() == ISD::SRL) {
  ...
} else {
  ...
}

if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
      Action == TargetLowering::Custom) { <== False
  ...
}

if (N->getOpcode() == ISD::SHL) { <== Branch taken
} else if (N->getOpcode() == ISD::SRL) {
  ...
} else {
  ...
}

if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) { <==
Returns
False as I set the lib call name to NULL from the target selection lowering
constructor
  ...
}

if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi)) { <== Expand returns true
  ...
}

Thanks,
Javier

On Tue, 01 Dec 2009 11:07:21 +0100, Duncan Sands <baldrick at free.fr>
wrote:
> Hi Javier,
> 
>> 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.
> 
> I'm not sure what you are saying, here is the code for shift-left.  In
> the case of your example, Amt = 6, VTBits = 64 and NVTBits = 32.  I've
> added comments at the end of various lines, like this: <== Comment.
> 
>    if (N->getOpcode() == ISD::SHL) { <== This branch is taken
>      if (Amt > VTBits) { <== False
> ... not executed ...
>      } else if (Amt > NVTBits) { <== False
> ... not executed ...
>      } else if (Amt == NVTBits) { <== False
> ... not executed ...
>      } else if (Amt == 1 &&
>                 TLI.isOperationLegalOrCustom(ISD::ADDC, 
> TLI.getTypeToExpandTo(*DAG.getContext(), NVT))) { <== False
> ... not executed ...
>      } else { <== This branch is taken
>        Lo = DAG.getNode(ISD::SHL, dl, NVT, InL, DAG.getConstant(Amt,
>        ShTy)); <=> Source low part is shifted left by 6 bits
>        Hi = DAG.getNode(ISD::OR, dl, NVT,
>                         DAG.getNode(ISD::SHL, dl, NVT, InH,
>                                     DAG.getConstant(Amt, ShTy)),
>                         DAG.getNode(ISD::SRL, dl, NVT, InL,
>                                     DAG.getConstant(NVTBits-Amt, ShTy)));
>                                     <=> Source high part is shifted
left by 6 bits, and the top 6 bits of the low
> part 
> is or'd in
>      }
>      return;
>    }
> 
> In short, the current code seems to be correct.
> 
> Ciao,
> 
> Duncan.