[M3devel] range analysis?

Jay K jay.krell at cornell.edu
Sun May 22 10:26:30 CEST 2011


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/e2bf291a/attachment-0001.html>


More information about the M3devel mailing list