Turning on LegalizeTypes by default

Hi all, I plan to turn on the new type legalization infrastructure
"LegalizeTypes" by default tomorrow. This is a redesign/reimplementation
of the logic currently in LegalizeDAG that turns (for example) 64 bit
arithmetic on a 32 bit machine into a series of 32 bit operations. As well
as being a cleaner design, it also supports code generation for arbitrary
precision integers such as i123.

This is likely to cause some breakage since I mostly only added support for
operations for which I had a testcase (by running "make check" or compiling
the testsuite etc), and I was only able to test on x86 linux (32 and 64 bit).
However it is usually easy to add support for missing operations, so I expect
all such problems to be fixed promptly.

LegalizeTypes was turned on once before. It broke llvm-gcc bootstrap on
darwin at a time when, it seems, such breakage was particularly annoying,
and was turned off again. As a result it has been sitting forgotten in the
tree, bitrotting as fixes and improvements were made only to LegalizeDAG.
I don't want this to happen again.

So please: if LegalizeTypes breaks something, send me a bitcode testcase
rather than turning LegalizeTypes off again. With a major change like this
there is bound to be some pain, but I don't expect it to last more than a
week or two.

Once LegalizeTypes has stabilized, I plan to progressively delete type
legalization functionality from LegalizeDAG, checking that LegalizeTypes
has the same functionality as I go, and adding it if not.

Testsuite results are as follows:

(a) "make check" has two failures:
  ARM/cse-libcalls.ll - this is because of a bug in UpdateNodeOperands
which does not do CSE on calls correctly. The question here is how best
to fix this while minimizing code duplication. This will doubtless be
fixed soon.
  PowerPC/vec_spat.ll (@splat_h) - here code got slightly worse. The
problem here is that LegalizeDAG "cheats": it constructs a BUILD_VECTOR
where the type of the operands doesn't match the vector element type (this
is supposed to be illegal), while LegalizeTypes correctly constructs a
BUILD_VECTOR where the operand type is equal to the vector element type,
but then the PPC custom code doesn't handle this optimally. Two solutions:
decide that in fact
  v8i16 = BUILD_VECTOR(i32, i32, ..., i32)
is legal and modify LegalizeTypes to take advantage of this; or improve
the PPC so it better handles the code coming out of LegalizeTypes.

(b) llvm-gcc builds with languages Ada, C, C++, Fortran, Objc and Obj-c++
on x86-32-linux, and bootstraps with languages C, C++ and Fortran on
x86-64-linux. This is the same as without LegalizeTypes.

(c) No additional failures in the full testsuite for x86 linux (32 and
64 bit).

(d) No additional failures in the Ada ACATS testsuite (x86-32 linux).

Ciao,

Duncan.

Hi all, I plan to turn on the new type legalization infrastructure
"LegalizeTypes" by default tomorrow. This is a redesign/reimplementation
of the logic currently in LegalizeDAG that turns (for example) 64 bit
arithmetic on a 32 bit machine into a series of 32 bit operations. As well
as being a cleaner design, it also supports code generation for arbitrary
precision integers such as i123.

Woo hoo!

So please: if LegalizeTypes breaks something, send me a bitcode testcase
rather than turning LegalizeTypes off again. With a major change like this
there is bound to be some pain, but I don't expect it to last more than a
week or two.

Makes sense to me.

Once LegalizeTypes has stabilized, I plan to progressively delete type
legalization functionality from LegalizeDAG, checking that LegalizeTypes
has the same functionality as I go, and adding it if not.

This sounds good. Note that this is somewhat trickier than it seems and may also expose bugs. The problems that I hit when I was working on legalize types ages ago was that custom lowering ops on some targets generates nodes with illegal types. One example (that I think was fixed) was that legalizing a uitofp from 32-bit to double turns into a 64-bit sitofp on x87. Just expect a bit of fallout when removing chunks from legalizedag.

Testsuite results are as follows:

(a) "make check" has two failures:
ARM/cse-libcalls.ll - this is because of a bug in UpdateNodeOperands
which does not do CSE on calls correctly. The question here is how best
to fix this while minimizing code duplication. This will doubtless be
fixed soon.

Ok.

PowerPC/vec_spat.ll (@splat_h) - here code got slightly worse. The
problem here is that LegalizeDAG "cheats": it constructs a BUILD_VECTOR
where the type of the operands doesn't match the vector element type (this
is supposed to be illegal), while LegalizeTypes correctly constructs a
BUILD_VECTOR where the operand type is equal to the vector element type,
but then the PPC custom code doesn't handle this optimally.

After looking at this a bit, I don't think this is the real reason. The issue (I think) is a phase ordering issue between legalize types and custom lowering. In the old legalize case, legalize just custom lowers the build_vector-of-i16 right away. In the legalize types case, legalize types modifies the DAG quite a bit to eliminate the i16 operations, and the PPC backend doesn't match on what it expects.

Two solutions:
decide that in fact
v8i16 = BUILD_VECTOR(i32, i32, ..., i32)
is legal and modify LegalizeTypes to take advantage of this

Are you saying that the build_vector would have 8 i32 inputs, or only 4? If 8, I really don't like it because it breaks a lot of invariants. If 4 then it should be the same as the current v4i32 build vector that we're getting.

or improve
the PPC so it better handles the code coming out of LegalizeTypes.

Another option would be to have legalizetypes invoke the ppc custom lowering hook for BUILD_VECTOR when it sees the build_vector of i16. This way, the ppc backend would see the input build_vector unmolested.

Thanks for spearheading this Duncan!

-Chris

Hi Chris,

> Once LegalizeTypes has stabilized, I plan to progressively delete type
> legalization functionality from LegalizeDAG, checking that
> LegalizeTypes
> has the same functionality as I go, and adding it if not.

This sounds good. Note that this is somewhat trickier than it seems
and may also expose bugs. The problems that I hit when I was working
on legalize types ages ago was that custom lowering ops on some
targets generates nodes with illegal types. One example (that I think
was fixed) was that legalizing a uitofp from 32-bit to double turns
into a 64-bit sitofp on x87. Just expect a bit of fallout when
removing chunks from legalizedag.

yes, I'm sure there'll be quite a bit of this kind of thing.

> PowerPC/vec_spat.ll (@splat_h) - here code got slightly worse. The
> problem here is that LegalizeDAG "cheats": it constructs a
> BUILD_VECTOR
> where the type of the operands doesn't match the vector element type
> (this
> is supposed to be illegal), while LegalizeTypes correctly constructs a
> BUILD_VECTOR where the operand type is equal to the vector element
> type,
> but then the PPC custom code doesn't handle this optimally.

After looking at this a bit, I don't think this is the real reason.
The issue (I think) is a phase ordering issue between legalize types
and custom lowering. In the old legalize case, legalize just custom
lowers the build_vector-of-i16 right away. In the legalize types
case, legalize types modifies the DAG quite a bit to eliminate the i16
operations, and the PPC backend doesn't match on what it expects.

You are right. LegalizeTypes does allow custom lowering, in fact it
handles custom lowering in more unified and systematic way than
LegalizeDAG, but it always tests for whether custom lowering is needed
like this:
  if (TLI.getOperationAction(OpCode, IllegalType) == Custom)

So in the case of BUILD_VECTOR with an illegal (i16) operand type,
this becomes TLI.getOperationAction(BUILD_VECTOR, i16) [the vector
type v816 is itself legal]. However targets like to use the vector
type when setting custom operations, for example PowerPC does:

    setOperationAction(ISD::BUILD_VECTOR, MVT::v16i8, Custom);
    setOperationAction(ISD::BUILD_VECTOR, MVT::v8i16, Custom);
    setOperationAction(ISD::BUILD_VECTOR, MVT::v4i32, Custom);
    setOperationAction(ISD::BUILD_VECTOR, MVT::v4f32, Custom);

One solution would be to add:
    setOperationAction(ISD::BUILD_VECTOR, MVT::i16, Custom);

I guess it would also be possible to query the vector type, but
I don't like that much. What do you think?

> Two solutions:
> decide that in fact
> v8i16 = BUILD_VECTOR(i32, i32, ..., i32)
> is legal and modify LegalizeTypes to take advantage of this

Are you saying that the build_vector would have 8 i32 inputs, or only
4? If 8, I really don't like it because it breaks a lot of
invariants.

I mean 8. I don't like it either, yet many places used to build
such vectors (I cleaned them up a few months ago) so it at least
works most of the time!

If 4 then it should be the same as the current v4i32
build vector that we're getting.

> or improve
> the PPC so it better handles the code coming out of LegalizeTypes.

Another option would be to have legalizetypes invoke the ppc custom
lowering hook for BUILD_VECTOR when it sees the build_vector of i16.
This way, the ppc backend would see the input build_vector unmolested.

See above.

Ciao,

Duncan.

Hi Chris,

> PowerPC/vec_spat.ll (@splat_h) - here code got slightly worse. The
> problem here is that LegalizeDAG "cheats": it constructs a
> BUILD_VECTOR
> where the type of the operands doesn't match the vector element type
> (this
> is supposed to be illegal), while LegalizeTypes correctly constructs a
> BUILD_VECTOR where the operand type is equal to the vector element
> type,
> but then the PPC custom code doesn't handle this optimally.

After looking at this a bit, I don't think this is the real reason.
The issue (I think) is a phase ordering issue between legalize types
and custom lowering. In the old legalize case, legalize just custom
lowers the build_vector-of-i16 right away. In the legalize types
case, legalize types modifies the DAG quite a bit to eliminate the i16
operations, and the PPC backend doesn't match on what it expects.

actually we were both wrong. LegalizeDAG does call PPC custom lowering
right away, but that doesn't do anything because the element is not
constant. It then falls through to ExpandBUILD_VECTOR. This is
splat of one value case:

  if (SplatValue.getNode()) { // Splat of one value?
...

The resulting scalar-to-vector and vector_shuffle then get legalized and
presumably custom lowered. In the LegalizeTypes case we also get to
ExpandBUILD_VECTOR but this time with a v4i32 rather than a v8i16 (due
to type legalization), again in the "splat of one value" case. However
this time subsequent legalization and custom operation lowering creates
more of a mess rather than cleaning things up.

Ciao,

Duncan.

You state that it properly lowers higher bit mathematics and odd
precision ints on systems. Will it handle, say, an i1097 on an x86
system, by lowering it to high precision math, or will it ignore it
and have the compile fail as normal?

Hi,

You state that it properly lowers higher bit mathematics and odd
precision ints on systems. Will it handle, say, an i1097 on an x86
system, by lowering it to high precision math, or will it ignore it
and have the compile fail as normal?

the maximum size is i256. As for the rest of your question,
can you please be more explicit.

Ciao,

Duncan.

LegalizeTypes does add lots of good features, but at the end of the day
it lacked the essential part of our needs...
Part of the problem stems from the way that custom types are defined
which is not much different from LegalizeDAG.
Our target is 8 bit, but it also supports 16 bit pointers. The
setOperationAction(...) form of defining legal/illegal/custom types
indiscriminately tries to call the custom operation for all nodes if the
result is illegal, but for example for us, we want to keep some
operations 16 bit, while in some other situations the same is illegal,
forcing us to define our own target nodes and completely work our way
around llvm nodes for load/store.
I think this part of the work can benefit from tablegen to check for
patterns of SDNode instead of just checking for particular operation and
its type, but I haven't had time to sit down and think how....

Regardless, LegalizeTypes is a great improvement.

Thanks
Ali

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]

On

Behalf Of Duncan Sands
Sent: Sunday, October 26, 2008 1:03 AM
To: LLVM Developers Mailing List
Subject: [LLVMdev] Turning on LegalizeTypes by default

Hi all, I plan to turn on the new type legalization infrastructure
"LegalizeTypes" by default tomorrow. This is a

redesign/reimplementation

of the logic currently in LegalizeDAG that turns (for example) 64 bit
arithmetic on a 32 bit machine into a series of 32 bit operations. As
well
as being a cleaner design, it also supports code generation for

arbitrary

precision integers such as i123.

This is likely to cause some breakage since I mostly only added

support

for
operations for which I had a testcase (by running "make check" or
compiling
the testsuite etc), and I was only able to test on x86 linux (32 and

64

bit).
However it is usually easy to add support for missing operations, so I
expect
all such problems to be fixed promptly.

LegalizeTypes was turned on once before. It broke llvm-gcc bootstrap

on

darwin at a time when, it seems, such breakage was particularly

annoying,

and was turned off again. As a result it has been sitting forgotten

in

the
tree, bitrotting as fixes and improvements were made only to

LegalizeDAG.

I don't want this to happen again.

So please: if LegalizeTypes breaks something, send me a bitcode

testcase

rather than turning LegalizeTypes off again. With a major change like
this
there is bound to be some pain, but I don't expect it to last more

than a

week or two.

Once LegalizeTypes has stabilized, I plan to progressively delete type
legalization functionality from LegalizeDAG, checking that

LegalizeTypes

has the same functionality as I go, and adding it if not.

Testsuite results are as follows:

(a) "make check" has two failures:
  ARM/cse-libcalls.ll - this is because of a bug in UpdateNodeOperands
which does not do CSE on calls correctly. The question here is how

best

to fix this while minimizing code duplication. This will doubtless be
fixed soon.
  PowerPC/vec_spat.ll (@splat_h) - here code got slightly worse. The
problem here is that LegalizeDAG "cheats": it constructs a

BUILD_VECTOR

where the type of the operands doesn't match the vector element type

(this

is supposed to be illegal), while LegalizeTypes correctly constructs a
BUILD_VECTOR where the operand type is equal to the vector element

type,

but then the PPC custom code doesn't handle this optimally. Two
solutions:
decide that in fact
  v8i16 = BUILD_VECTOR(i32, i32, ..., i32)
is legal and modify LegalizeTypes to take advantage of this; or

improve

the PPC so it better handles the code coming out of LegalizeTypes.

(b) llvm-gcc builds with languages Ada, C, C++, Fortran, Objc and

Obj-c++