[M3devel] range analysis?
Jay K
jay.krell at cornell.edu
Mon May 23 01:18:02 CEST 2011
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/20110522/dcae5da4/attachment-0002.html>
More information about the M3devel
mailing list