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

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.

Hi Javier,
> 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.
I see, sorry I didn't read your email more carefully.  It does look like
ExpandShiftWithUnknownAmountBit is bogus - at a glance it looks like the
Cmp condition is inverted.  I may have time to take a closer look tomorrow.

Best wishes,

Duncan.

Hi Duncan,

Just wondering if you had a chance to look at the expansion.

Thanks,
Javier

On Tue, 01 Dec 2009 20:20:14 +0100, Duncan Sands <baldrick at free.fr>
wrote:
> Hi Javier,
> 
>> 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.
> 
> I see, sorry I didn't read your email more carefully.  It does look
like
> ExpandShiftWithUnknownAmountBit is bogus - at a glance it looks like the
> Cmp condition is inverted.  I may have time to take a closer look
tomorrow.
> 
> Best wishes,
> 
> Duncan.