llvm dev - Oct 2008 - [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++
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.

On Oct 26, 2008, at 1:03 AM, Duncan Sands wrote:
> 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.

On Sun, Oct 26, 2008 at 2:03 AM, Duncan Sands <baldrick at free.fr>
wrote:
> 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.
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
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
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++
> 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.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev