[M3devel] range analysis?
Daniel Alejandro Benavides D.
dabenavidesd at yahoo.es
Mon May 23 22:44:11 CEST 2011
Hi all:
in one process it might be good to check for those optimization, but then you might want to abstract them all to allow to be pessimistic or to analyze them in ESC.
This should require some good knowledge of the compiler though, which is maybe a harder task than just build a VCG but perhaps is too slow for m3cg, maybe for native backends, is more justifiable if so. Perhaps there is enough good trade off to do so.
Thanks in advance
--- El dom, 22/5/11, Jay K <jay.krell at cornell.edu> escribió:
De: Jay K <jay.krell at cornell.edu>
Asunto: Re: [M3devel] range analysis?
Para: "Tony" <hosking at cs.purdue.edu>
CC: "m3devel" <m3devel at elegosoft.com>
Fecha: domingo, 22 de mayo, 2011 18:18
Well, I can build the whole tree and see how many times it helps.
I think this is a pretty standard optimization technique.
Though it'd work better with compiler-derived additional information.
I initially happened upon this idea developing test cases.
> The code assumes the minimum of a type is less than or equal to its maximum.
I'll change it not have that problem -- to just fall back to usual pessimistic code for such types, I guess.
- Jay
Subject: Re: range analysis?
From: hosking at cs.purdue.edu
Date: Sun, 22 May 2011 14:51:59 -0400
CC: m3devel at elegosoft.com
To: jay.krell at cornell.edu
So, one question is: what benefit does this really give? Your examples seem a little contrived.
On May 22, 2011, at 4:26 AM, Jay K wrote:
I've been sitting on this diff a long while.
In some places the frontend knows the bounds of a type/value and
will optimize away range checks. I'm pretty sure.
This makes it do that more.
I haven't looked at or tested this in ages.
But the basic idea seems sound, simple, easy enough to get a few small wins from.
For example if you have:
a: [-10..-1];
b: [1..10];
then all comparisons between a and b are compile-time constant.
Comparisons of cardinals to negative numbers, likewise.
One thing maybe missing below is handling of empty ranges like
a: [1..-1];
The code assumes the minimum of a type is less than or equal to its maximum.
Index: m3-sys/m3front/src/misc/CG.i3
===================================================================
RCS file: /usr/cvs/cm3/m3-sys/m3front/src/misc/CG.i3,v
retrieving revision 1.15
diff -r1.15 CG.i3
11c11
< IMPORT Target, M3CG, M3;
---
> IMPORT Target, M3CG, M3, TInt;
402c402,406
< PROCEDURE Load (v: Var; o: Offset; s: Size; a: Alignment; t: Type);
---
> PROCEDURE Load (v: Var; o: Offset; s: Size; a: Alignment; t: Type;
> min_valid: BOOLEAN := FALSE;
> max_valid: BOOLEAN := FALSE;
> min: Target.Int := TInt.Zero;
> max: Target.Int := TInt.Zero);
414,415c418,423
< PROCEDURE Load_int (t: IType; v: Var; o: Offset := 0);
< (* == Load (v, o, t.size, t.align, t) *)
---
> PROCEDURE Load_int (t: IType; v: Var; o: Offset := 0;
> min_valid: BOOLEAN := FALSE;
> max_valid: BOOLEAN := FALSE;
> min: Target.Int := TInt.Zero;
> max: Target.Int := TInt.Zero);
> (* == Load (v, o, t.size, t.align, t, min/max...) *)
Index: m3-sys/m3front/src/misc/CG.m3
===================================================================
RCS file: /usr/cvs/cm3/m3-sys/m3front/src/misc/CG.m3,v
retrieving revision 1.40
diff -r1.40 CG.m3
13c13
< IMPORT M3, M3CG, M3CG_Ops, M3CG_Check;
---
> IMPORT M3, M3CG, M3CG_Ops, M3CG_Check, RTIO, RTParams;
45a46,49
> min_valid : BOOLEAN := FALSE; (* whether or not min is valid *)
> max_valid : BOOLEAN := FALSE; (* whether or not max is valid *)
> min : Target.Int := TInt.Zero; (* the minimum possible value *)
> max : Target.Int := TInt.Zero; (* the maximum possible value *)
80c84,85
< VAR
---
> VAR
> debug := FALSE;
604a610,614
> v.min := TInt.Zero;
> v.max := TInt.Zero;
> v.min_valid := FALSE;
> v.max_valid := FALSE;
>
766a777,780
> x.min := TInt.Zero;
> x.max := TInt.Zero;
> x.min_valid := FALSE;
> x.max_valid := FALSE;
978a993,995
> IF debug THEN
> RTIO.PutText("m3front:cg:Init_int:NOT in_init: o: " & Fmt.Int(o) & " s:" & Fmt.Int(s) & " value:" & TInt.ToText(value) & "\n"); RTIO.Flush();
> END;
980a998,1001
> END;
>
> IF debug THEN
> RTIO.PutText("m3front:cg:Init_int:in_init: o: " & Fmt.Int(o) & " s:" & Fmt.Int(s) & " value:" & TInt.ToText(value) & "\n"); RTIO.Flush();
1266c1287,1291
< PROCEDURE Load (v: Var; o: Offset; s: Size; a: Alignment; t: Type) =
---
> PROCEDURE Load (v: Var; o: Offset; s: Size; a: Alignment; t: Type;
> min_valid: BOOLEAN := FALSE;
> max_valid: BOOLEAN := FALSE;
> min: Target.Int := TInt.Zero;
> max: Target.Int := TInt.Zero) =
1276c1301
< SimpleLoad (v, o, t);
---
> SimpleLoad (v, o, t, min_valid, max_valid, min, max);
1291c1316
< SimpleLoad (v, o, best_type);
---
> SimpleLoad (v, o, best_type, min_valid, max_valid, min, max);
1312c1337,1341
< PROCEDURE SimpleLoad (v: Var; o: Offset; t: Type) =
---
> PROCEDURE SimpleLoad (v: Var; o: Offset; t: Type;
> min_valid: BOOLEAN := FALSE;
> max_valid: BOOLEAN := FALSE;
> min: Target.Int := TInt.Zero;
> max: Target.Int := TInt.Zero) =
1323a1353,1356
> x.min_valid := min_valid;
> x.max_valid := max_valid;
> x.min := min;
> x.max := max;
1339a1373,1376
> x.min := TInt.Zero;
> x.max := TInt.Zero;
> x.min_valid := FALSE;
> x.max_valid := FALSE;
1347a1385,1388
> stack[tos-1].min := TInt.Zero;
> stack[tos-1].max := TInt.Zero;
> stack[tos-1].min_valid := FALSE;
> stack[tos-1].max_valid := FALSE;
1350c1391,1395
< PROCEDURE Load_int (t: IType; v: Var; o: Offset := 0) =
---
> PROCEDURE Load_int (t: IType; v: Var; o: Offset := 0;
> min_valid: BOOLEAN := FALSE;
> max_valid: BOOLEAN := FALSE;
> min: Target.Int := TInt.Zero;
> max: Target.Int := TInt.Zero) =
1352c1397
< SimpleLoad (v, o, t);
---
> SimpleLoad (v, o, t, min_valid, max_valid, min, max);
1815a1861,1864
> x.min_valid := TRUE;
> x.max_valid := TRUE;
> x.min := i;
> x.max := i;
1832,1834c1881,2007
< BEGIN
< IF Force_pair (commute := TRUE) THEN
< op := M3CG.SwappedCompare [op];
---
> VAR always_true: BOOLEAN;
> always_false: BOOLEAN;
> left_type: Type;
> right_type: Type;
> left_min: Target.Int;
> left_max: Target.Int;
> right_min: Target.Int;
> right_max: Target.Int;
> left_signed: BOOLEAN;
> right_signed: BOOLEAN;
> BEGIN
>
> always_true := FALSE;
> always_false := FALSE;
>
> WITH left = stack [SCheck (2, "Compare-left")],
> right = stack [SCheck (1, "Compare-right")] DO
>
> left_type := left.type;
> right_type := right.type;
>
> IF left.min_valid
> AND left.max_valid
> AND right.min_valid
> AND right.max_valid
> AND Target.OrdinalType[left_type]
> AND Target.OrdinalType[right_type] THEN
>
> left_min := left.min;
> left_max := left.max;
> right_min := right.min;
> right_max := right.max;
> left_signed := Target.SignedType[left_type];
> right_signed := Target.SignedType[right_type];
>
> (* First handle types that match in signedness. *)
>
> IF left_signed = right_signed THEN
>
> (* Check for ranges with no overlap. *)
>
> IF left_signed (* and right_signed *) THEN
> IF TInt.LT(left_max, right_min) THEN
> always_true := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};
> ELSIF TInt.GT(left_min, right_max) THEN
> always_true := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};
> END;
> ELSE (* left_signed and right_signed both false *)
> IF TWord.LT(left_max, right_min) THEN
> always_true := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};
> ELSIF TWord.GT(left_min, right_max) THEN
> always_true := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};
> END;
> END;
>
> (* Check for overlap just on the edge, e.g. [0..1] compared to [1..2]. *)
>
> IF NOT (always_true OR always_false) THEN
> IF TInt.EQ(left_max, right_min) THEN
> always_true := op = Cmp.LE;
> always_false := op = Cmp.GT;
> ELSIF TInt.EQ(left_min, right_max) THEN
> always_true := op = Cmp.GE;
> always_false := op = Cmp.LT;
> END;
> END;
>
> (* Handle equal subranges with one element, not likely to occur. *)
>
> IF NOT (always_true OR always_false) THEN
> IF TInt.EQ(left_max, left_min)
> AND TInt.EQ(left_max, right_max)
> AND TInt.EQ(left_max, right_min) THEN
> always_true := op IN SET OF Cmp{Cmp.GE, Cmp.LE, Cmp.EQ};
> always_false := op IN SET OF Cmp{Cmp.LT, Cmp.GT, Cmp.NE};
> END;
> END;
> ELSE
>
> (* Now deal with mixed up types (signed compared to unsigned).
> * We may be able to merge these by setting some min/max
> * to zero. That is, the minimum of an unsigned type is zero.
> * However we want to be sure not to interpret unsigned min/max
> * as signed.
> *)
>
> IF left_signed THEN
> IF TInt.LT(left_max, TInt.Zero) THEN
> always_true := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};
> ELSIF TInt.EQ(left_max, TInt.Zero) THEN
> always_true := op = Cmp.LE;
> always_false := op = Cmp.GT;
> END;
> ELSE (* right is signed *)
> IF TInt.LT(right_max, TInt.Zero) THEN
> always_true := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};
> always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};
> ELSIF TInt.EQ(right_max, TInt.Zero) THEN
> always_true := op = Cmp.GE;
> always_false := op = Cmp.LT;
> END;
> END;
> END;
> END;
>
> <* ASSERT NOT (always_true AND always_false) *>
>
> IF always_true OR always_false THEN
> Discard(right_type);
> Discard(left_type);
> IF always_true THEN
> cg.load_integer (Target.Integer.cg_type, TInt.One);
> ELSE
> cg.load_integer (Target.Integer.cg_type, TInt.Zero);
> END
> ELSE
> IF Force_pair (commute := TRUE) THEN
> op := M3CG.SwappedCompare [op];
> END;
> cg.compare (t, Target.Integer.cg_type, op);
> SPop (2, "Compare");
> END;
1836,1837d2008
< cg.compare (t, Target.Integer.cg_type, op);
< SPop (2, "Compare");
2880a3052,3055
> x.min := TInt.Zero;
> x.max := TInt.Zero;
> x.min_valid := FALSE;
> x.max_valid := FALSE;
2977c3152,3153
< BEGIN
---
> BEGIN
> debug := debug OR RTParams.IsPresent ("m3front_cg_debug");
Index: m3-sys/m3front/src/values/Variable.m3
===================================================================
RCS file: /usr/cvs/cm3/m3-sys/m3front/src/values/Variable.m3,v
retrieving revision 1.13
diff -r1.13 Variable.m3
362a363,365
> VAR min: Target.Int;
> max: Target.Int;
> bounds_valid: BOOLEAN;
395c398,401
< CG.Load (t.cg_var, t.offset, t.size, t.cg_align, t.stk_type);
---
> (*GetBounds (t, min, max);
> bounds_valid := TInt.LE(min, max);*)
> bounds_valid := t.tipe # NIL AND Type.GetBounds(t.tipe, min, max) AND TInt.LE(min, max);
> CG.Load (t.cg_var, t.offset, t.size, t.cg_align, t.stk_type, bounds_valid, bounds_valid, min, max);
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20110523/1ac117a0/attachment-0002.html>
More information about the M3devel
mailing list