[M3devel] range analysis?
Tony Hosking
hosking at cs.purdue.edu
Sun May 22 20:51:59 CEST 2011
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/bd123818/attachment-0002.html>
More information about the M3devel
mailing list