Wrong code for i288 addition

[llvmbot]

Bugzilla Link	3401
Resolution	FIXED
Resolved on	Jan 31, 2009 09:51
Version	unspecified
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@lattner,@sunfishcode

Extended Description

LLVM 2.6svn, x86 code generation.

Here's a small test program:

define void @​add(i288, i288, i288*) {
_L1:
%3 = add i288 %0, %1
store i288 %3, i288* %2
ret void
}

And some C code to test it:

#include <stdio.h>

#define N 9

struct big { unsigned int x[N]; };

void add(struct big, struct big, struct big *);

main()
{
struct big a, b, c;
int i;
for (i = 0; i < N; i++) {
a.x[i] = 0x11111111;
b.x[i] = 0x22222222;
c.x[i] = 0x5a5a5a5a;
}
add(a,b,&c);
for (i = N-1; i >= 0; i--)
printf("%08x ", c.x[i]);
printf("\n");
}

This prints
fffffffe 00000000 00000001 ffffffff ffffffff ffffffff ffffffff fffffffe 33333333
which is clearly wrong. Changing i288 to i256 (and N to 8) makes it work.

[llvmbot]

The problem here seems to be that i288 parameters are being
passed wrong. [Note that there is no reason to assume that
i288 is passed the same way as struct big, and in general it
is not, so the example is invalid; nonetheless something is
wrong with parameter passing here]. The following modified
example shows that i288 addition works correctly:

define void @​add(i288* %v1p, i288* %v2p, i288* %rp) {
%v1 = load i288* %v1p
%v2 = load i288* %v2p
%r = add i288 %v1, %v2
store i288 %r, i288* %rp
ret void
}

#include <stdio.h>

#define N 9

struct big { unsigned int x[N]; };

void add(struct big*, struct big*, struct big *);

main()
{
struct big a, b, c;
int i;
for (i = 0; i < N; i++) {
a.x[i] = 0x11111111;
b.x[i] = 0x22222222;
c.x[i] = 0x5a5a5a5a;
}
add(&a,&b,&c);
for (i = N-1; i >= 0; i--)
printf("%08x ", c.x[i]);
printf("\n");
}

[llvmbot]

I'm not sure exactly what you mean. Do you mean that the original LLVM code I wrote (with i288 arguments) is illegal?
I'm perfectly fine with that, but in that case the code generator should not generate bad code, but instead complain.

If the LLVM code I wrote is legal, then the code generator is broken, because the generated machine code does not add two numbers.

[llvmbot]

No, I mean: why do you think that struct big is equivalent to i288?
AFAICS on all platforms except x86-32 (and on x86-32 with any other
calling convention) part of the i288 will be passed in registers,
and the rest on the stack, while struct big will be passed entirely
on the stack. In short, I'm saying that you have two versions of
"add":
define void @​add(i288, i288, i288*)
and
void add(struct big, struct big, struct big *)
and you are just lucky that they are compatible on this platform.

Finally, as I pointed out, i288 addition works fine. The problem
is not addition, the problem is parameter passing. This seems
to be broken for parameters bigger than i256. [Historical note:
when I implemented apint codegen the maximum integer size that
codegen supported was i256, and I tested parameter passing for
all integer sizes up to and including this; later Dan used a
clever trick to extend to integers of basically any size, but I
never tested this myself. So I don't know if this never worked
properly, or if it used to work and broke at some point].

[llvmbot]

OK. I had no hope that my code would work on anything but x86. :)
I just wanted to make a simple test example that illustrated that the code in add did something weird.
As you say (and as I saw when using i288*) addition seems to work fine, and it is parameter passing that is at fault. I should have been less quick in my judgement of what was at fault.

Even so, something is broken.

[llvmbot]

I've found the problem: on x86-32, all shift amounts are held in
an i8. When doing apint codegen with integers bigger than 256
bits then you pretty quickly come across shifts by 128 bits or
more (for example, when passing an i288 as a parameter). Such
shifts can also be created by the user for apints bigger than
128 bits. Such shifts are considered negative (or, if truly huge,
some strange value) by codegen, which results in all kinds of
oddness. In particular the failure of the testcase.

It seems to me that the solution is to allow the shift amount
to be of any type before type legalization (probably i32 or
i64 should be used everywhere), and teach the type legalizer
how to change these into shifts of a legal type. On x86-32
this will result in i32 shift amounts being present after
type legalization. The operation legalizer would need to
be taught to truncate or extend the amount to the target's
getShiftAmountTy. Probably it should look at all shifts
and automatically correct the amount type if it is not
getShiftAmountTy.

[sunfishcode]

a sketch of a fix
Thanks Duncan! Your analysis and suggested solution sound
good to me. Attached is a sketch of an implementation of it,
which fixes the given testcase, though I need to verify
some things in it.

[llvmbot]

Hi Dan, thanks for these thoughts.

 uint64_t getIntegerVTBitMask() const {

•  assert(isInteger() && !isVector() && "Only applies to int scalars!");
  

•  return ~uint64_t(0UL) >> (64-getSizeInBits());
  

•  assert(isInteger() && "Only applies to integers!");
  

•  MVT EltVT = isVector() ? getVectorElementType() : *this;
  

•  assert(EltVT.getSizeInBits() <= 64 &&
  

•         "getIntegerVTBitMask doesn't use APInt!");
  

•  return ~uint64_t(0UL) >> (64-EltVT.getSizeInBits());
  

Not sure what this is about.

SDValue DAGTypeLegalizer::PromoteIntRes_SHL(SDNode *N) {

• SDValue ShAmt = N->getOperand(1);
• if (ShAmt.getValueType() != TLI.getShiftAmountTy())
• ShAmt = GetPromotedInteger(N->getOperand(1));

For all these guys I would rather it was done differently.
First of all, please don't this during result type
legalization: this method is only called if the shift
result type is illegal. This has nothing to do with
whether operand 1 is illegal. It won't be called at all
for nodes which return a legal type but shift by an illegal
shift amount. Please introduce a new operand promotion
method. Since operand promotion methods are only called when
all result types are legal, if the method is called then you
are sure that it is the shift amount type that needs fixing
(and that nothing needs to be done for the value being shifted).
Thus there is no need for testing types etc. Also, you should
use SExtPromotedInteger not GetPromotedInteger (which returns
rubbish in the upper bits; I say SExt rather than ZExt
because shift amounts are signed, right?). I can write these
routines for you if you like.

@@ -996,14 +1004,13 @@
MVT NVT = InL.getValueType();
unsigned VTBits = N->getValueType(0).getSizeInBits();
unsigned NVTBits = NVT.getSizeInBits();

• MVT ShTy = N->getOperand(1).getValueType();

  if (N->getOpcode() == ISD::SHL) {
  if (Amt > VTBits) {
  Lo = Hi = DAG.getConstant(0, NVT);
  } else if (Amt > NVTBits) {
  Lo = DAG.getConstant(0, NVT);

•  Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
  

•  Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,NVT));
  

  } else if (Amt == NVTBits) {
  Lo = DAG.getConstant(0, NVT);
  Hi = InL;

I'm not sure what the point of these changes is. In order to
handle shift amounts by a type that requires expansion, you
just need to introduce a new operand expansion method. Since
operand expansion is only done for nodes for which all result
types are legal, this method will only be called if the shift
amount needs expanding (nothing needs to be done for the shifted
value). It is enough to keep the lower half of the expanded
shift amount. I can write these routines for you if you like.

• // If the shift count needs expanding, expand it and ignore the high
• // half of the value, because it can't possibly contain relevant bits. fixme
• SDValue Amt = N->getOperand(1);
• if (Amt.getValueType() != TLI.getShiftAmountTy()) {
• SDValue Ignore;
• GetExpandedInteger(Amt, Amt, Ignore);
• }

As mentioned above, there is no point to any of this. Also,
since these routines are only called if the result type is
illegal and needs expanding, they won't be called at all for
shifts that return a legal result type, but shift by an amount
that needs expanding. Please add an operand expansion method
as described above.

SDValue SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) {

• assert((VT.getSizeInBits() >= 64 ||

•     (uint64_t)((int64_t)Val >> VT.getSizeInBits()) + 1 < 2) &&
  

•     "getConstant with a uint64_t value that doesn't fit in the type!");
  

Note sure what this is about.

+/// getShiftAmountOperand - Return the specified value casted to
+/// the target's desired shift amount type.
+SDValue SelectionDAG::getShiftAmountOperand(SDValue Op) {

• MVT OpTy = Op.getValueType();
• MVT ShTy = TLI.getShiftAmountTy();
• if (OpTy == ShTy || OpTy.isVector()) return Op;
• ISD::NodeType Opcode = OpTy.getSizeInBits() > ShTy.getSizeInBits() ?
• ISD::TRUNCATE : ISD::ZERO_EXTEND;

Shouldn't this be a sign extend?

The rest looks good to me. Thanks for doing this!

[sunfishcode]

Hi Duncan, thanks for the review!

I split out the pieces that you weren't sure about and committed
those as r63128 so that they can be reviewed separately. They're
setting up an assertion failure to catch problems like this before
they end up causing miscompilations.

Shift amounts are unsigned.

What you're saying about the LegalizeTypes changes makes
sense, and sounds like it would be substantially simpler than the
approach my patch took. If you'd like to write these routines,
please do. Otherwise, I'll look into it when I get a chance.

[llvmbot]

LegalizeTypes support for funky shift amount types
This totally untested patch should take care of legalizing shift
amount types. Note that various places in LegalizeTypes use
getShiftAmountTy, and these most likely need to be changed to use
i32 or whatever, but I didn't try to address that.

[lattner]

This is probably the same issue as Bug 3401

[lattner]

*** Bug llvm/llvm-bugzilla-archive#3449 has been marked as a duplicate of this bug. ***

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#3450 has been marked as a duplicate of this bug. ***

[llvmbot]

Fixed here using a different strategy:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090126/073021.html

[lattner]

mentioned in issue llvm/llvm-bugzilla-archive#3449

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#3450