[M3devel] comparisons vs. subranges

Sun Mar 14 06:15:22 CET 2010

> Prep vs. PrepBR vs. Compile

Expr.i3 documents it.

(*** phase 4 ****)

(* Expressions are compiled in two steps:
     Prep: emit any code that includes branchs or stores
     Compile: emit the rest of the code
*)

PROCEDURE Prep (t: T);
PROCEDURE Compile (t: T);
(* emits code to evaluate the expression onto the top of stack *)

PROCEDURE PrepLValue (t: T; traced: BOOLEAN);
PROCEDURE CompileLValue (t: T; traced: BOOLEAN);
(* emits code to evaluate 't's L-value into s0.A. *)

PROCEDURE CompileAddress (t: T; traced: BOOLEAN);
(* emits code to evaluate 't's byte address onto the top of stack.
   Use PrepLValue to prep these expressions. *)

PROCEDURE PrepBranch (t: T;  true, false: CG.Label;  freq: CG.Frequency);
PROCEDURE CompileBranch (t: T;  true, false: CG.Label;  freq: CG.Frequency);
(* emits code to evaluate the expression and conditionally branch to 'true'
   or 'false' depending on its boolean value.  'freq' is the estimated
   frequency that the specified branch will be taken. *)

 - Jay

From: jay.krell at cornell.edu
To: hosking at cs.purdue.edu
CC: m3devel at elegosoft.com
Subject: RE: [M3devel] comparisons vs. subranges
Date: Sun, 14 Mar 2010 05:01:24 +0000

Hm. How about elsewhere m3front?
Optimizing middle end not necessarily a different package?
  (esp. given that m3front is already big enough to afford being organized into directories: m3front/src/middle, m3front/src/target-independent-optimizations?)

Maybe elsewhere in the two files I changed? Prep or PrepBR or Compile instead of Fold?
  I don't understand this Prep vs. PrepBR business.
    I found out that "BR" stands for branch, but that doesn't explain it  me.
  Also PrepBR and Compile look very similar.
  I also noticed that Fold gets called twice (I had some RTIO in it) but didn't look into why.
  Surely doing it in PrepBR or Compile is correct or CG.m3 is correct, reasonable, efficient, maintainable?
  I can see why Fold would be wrong -- allowing code to compile, with a reasonable meaning, but that isn't supposed to.

Or in CG.m3, which is conceptually "the bottom" of m3front, any two adjacent pieces can be considered merged into one layer.
I'll look at both of those options later.

I think "subrange analysis" if done enough might yield efficiencies in real code.
Though m3front might already do enough of it -- e.g. the fact that you can't modify a FOR loop index affords some efficiencies, that are probably already taken into account.

 - Jay

From: jay.krell at cornell.edu
To: hosking at cs.purdue.edu
CC: m3devel at elegosoft.com
Subject: RE: [M3devel] comparisons vs. subranges
Date: Sun, 14 Mar 2010 03:52:15 +0000

Hm. You mean, like I'm not supposed to be able to say:

PROCEDURE F1(bool:BOOLEAN;a:[0..1];b:[2..3])=
 BEGIN
  CASE bool OF
    | (a < b) => IO.Put("true\n");
    | (a > b) => IO.Put("false\n");
  END;

but I can say:

PROCEDURE F1(bool:BOOLEAN;a:[0..1];b:[2..3])=
 BEGIN
  CASE bool OF
    | (LAST([0..1]) < FIRST([2..3]) => IO.Put("true\n");
    | (FIRST([0..1]) > LAST([2..3])=> IO.Put("false\n");
  END;

(I'd like to be able to say FIRST(a), etc., but I don't think it is allowed.)

"constants" kind of seem like an optimization themselves.
Other than efficiency concerns, they could all be variables
initialized by module initializers, that the frontend doesn't
let you write to. Including de-optimizations like runtime
allocation/sizing of arrays based on const/non-const sizes.

Look at how I changed const to var already in m3core/unix, and then
had to change CASE to if/elseif ladders.
It's a minor matter of what the language lets you say,
among various basically equivalent forms.
The compiler could allow case to target non-constants.
It'd just mainly be slower.
There is the matter of CASE arms can't overlap, where if/elseif ladders can.
  Because CASE is conceptually compared all at once where if/elseif
  is sequential.

Ok.

I see a few options at least.

m3middle could look basically like m3front, but with various checks like type checking removed
and assumed true. This would be an arduous task of duplication.

M3CG.i3 Var and Target.Int could gain the following fields (or methods):

 min_valid := FALSE;
 max_valid := FALSE;
 min := TInt.Zero;
 max := TInt.Zero;

m3front could fill them in a few cases.
 Initially none, but then a few as they are discovered to be easy, correct, efficient.
 For constants, min = max  value.
 For subranges, min/max come the type.
The backends could use them (if valid) and possibly transform them.
e.g. MIN(a,b) with valid min/max yields an expression
where min is the min of the two mins, max is the min of the two maxes.

MIN([0..1],[2..3]) < 2 => TRUE.

Probably more correct would be:

PROCEDURE declare_enum (xx: T;  t: TypeUID;  n_elts: INTEGER;  s: BitSize) =

PROCEDURE declare_subrange (xx: T; t, domain: TypeUID;
                            READONLY min, max: Target.Int;
                            s: BitSize)

 => already exist

and then 

PROCEDURE load (xx: T;  v: Var;  o: ByteOffset;  t: MType;  u: ZType) =
PROCEDURE load_indirect (xx: T;  o: ByteOffset;  t: MType;  u: ZType) =
PROCEDURE load_integer (xx: T;  t: IType;  READONLY i: Target.Int) =
PROCEDURE load_ordered (xx: T;  t: MType;  u: ZType;  order: MemoryOrder) =
etc.

should all take an optional TypeUID.

The second proposal I've thought a bit more about and it seems very easy.
The last idea seems cleaner, but with possibly signifiant downside
in that e.g. Word.T is not a subrange.

There's also some unclarity with respect to
 Word.LT(expression, -1);

-1 is a valid Word interpreted as a large number.
One would want to be careful not to break that.
I believe this is related to what you were saying, where operations 
are typed, not values.

It could be that every operation needs min/max or typeuid (pairs
of them for binary operations).

Can we take a stab at something like this?

This might also serve to replace some of what m3back does with constants already,
since constants would fall out of subranges of length 1.

Thanks,
 -Jay

From: hosking at cs.purdue.edu
Date: Sat, 13 Mar 2010 14:45:29 -0500
To: hosking at cs.purdue.edu
CC: m3devel at elegosoft.com; jay.krell at cornell.edu
Subject: Re: [M3devel] comparisons vs. subranges

Jay, 

I have reverted your commits because they violate the language definition.  Constant folding in the front-end is there only to support ha language definition of constant expressions.  Your changes violated that spec.  If you want such optimisations they should be performed in the back-end, or if we ever get one, in an optimising middle-end.

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 14:23, Tony Hosking wrote:

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/20100314/474d3389/attachment-0002.html>