[M3devel] comparisons vs. subranges

[Tony Hosking]

On 13 Mar 2010, at 13:26, Jay K wrote:

> Tony these are simple target-independent optimizations. I would dislike for each backend to do target-independent optimizations. Where can we put those? The front end currently does several. For example, operations on sets that fit in an integer. Division by powers of 2, Unrolling comparisons of records and sets (at least up to a certain size), removing runtime operations that are known to violate subranges (e.g. in insert/extract), occasional constant folding (in the same functions I modified), etc.
>  
>  
> What is the point of these functions Fold?

So that constants can be manipulated as first-class values in the language.  See http://www.cs.purdue.edu/homes/hosking/m3/reference/constexpr.html.  There are many places where a compile-time constant expression is required.  Fold is *not* intended for performing optimisations.

> Why does it have these various "cost" computations?

Which cost computations are you referring to?

> Granted, they are rough.
>  
>  
> Should we beef up m3middle?

That might be the place...  but ad hoc add-ons to m3front like you have been leaning towards are probably not the right place.  Designing a reasonable place for all of these optimisations will take effort.  I don't want to see us degrading the maintainability of m3front with gratuitous optimisations of dubious value.

> m3back doesn't optimize comparisons to constants, and a *lot* of what it does is target-independent.
> It would be nice to factor it better so that x86-independent code is not in files with "x86" in their name.
> It'd be nice to extend it to AMD64 for example (which is why I was worrying about my notions of "TypeIs64" and multiplying register counts times 4 to get byte counts, etc..) and maybe even to Sparc, PPC, ARM, etc.

Designing a decent optimising middle-end takes significant time and effort, and will require more thought.

>  m3back is correct or extremely close to correct as far as I know.
> It is missing atomic operations for 8, 16, 64 bit operands.
>  (PPC32 seems unable to support 64bit atomics btw.)

Correct.

> I have to test the subrange stuff for 64bit operands. It might work, but I think optimizations are missing there as well.
>  
>  
> I'd also like to maybe inline more operations..and I was thinking about implementing inlining in general. It might not be so difficult.
>  
>  
>  - Jay
> 
>  
> From: hosking at cs.purdue.edu
> Date: Sat, 13 Mar 2010 13:03:18 -0500
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] comparisons vs. subranges
> 
> Jay,
> 
> I am disturbed that you are inserting optimisations into the front-end that don't really belong there.  The front-end is responsible for semantics and not optimisation. It was never designed to be an optimising compiler.  There are better ways to go about working in optimisation, but I would hate to muddy the waters of the front-end the way you seem to intend.   Let's not go down this path until there is consensus!   One approach would involve communicating more information to the "back"-ends (actually, the gcc back-end should be considered a middle-end from the global perspective of optimising compilers).  For example, the back-ends gets very little in the way of type information (as you note w.r. to CARDINAL).  In any case, I suggest that you not obsess about performance right now but simply concentrate on correctness in your backend.
> 
> Antony Hosking | Associate Professor | Computer Science | Purdue University
> 305 N. University Street | West Lafayette | IN 47907 | USA
> Office +1 765 494 6001 | Mobile +1 765 427 5484
> 
> 
> 
> 
> On 13 Mar 2010, at 05:19, Jay K wrote:
> 
> <*UNUSED*>PROCEDURE CardinalGE0(a:CARDINAL):BOOLEAN=BEGIN RETURN a>=0; END CardinalGE0;
> <*UNUSED*>PROCEDURE CardinalEQN1(a:CARDINAL):BOOLEAN=BEGIN RETURN a=-1; END CardinalEQN1;
> 
>  
> Seems to me, the front end should notice these.
> The first should always be TRUE.
>    And possibly, possibly warn.
> The second should always be FALSE.
>    And possibly, possibly warn.
>  
> "Generic" programming often hits this sort of thing though, a good reason not to warn.
> Programmer might also be working with existing code and have changed INTEGER to CARDINAL.
>   Or be defending against future maintainers changing CARDINAL to INTEGER.
>  
>  
> The backend isn't give enough information, because CARDINAL = INTEGER as far
> as it is told. Due to the half range of CARDINAL and LONGCARD, that isn't wrong.
> The only way to get unsigned types is to use ADDRESS from what I see.
>  
>  
>  - Jay
> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100313/9177f518/attachment-0002.html>