<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Tahoma
}
--></style>
</head>
<body class='hmmessage'>
I've been sitting on this diff a long while.<br><br>In some places the frontend knows the bounds of a type/value and<br>will optimize away range checks. I'm pretty sure.<br><br><br><br>This makes it do that more.<br><br><br>I haven't looked at or tested this in ages.<br>But the basic idea seems sound, simple, easy enough to get a few small wins from.<br><br>For example if you have:<br><br>a: [-10..-1];<br>b: [1..10];<br><br>then all comparisons between a and b are compile-time constant.<br><br>Comparisons of cardinals to negative numbers, likewise.<br><br>One thing maybe missing below is handling of empty ranges like<br>a: [1..-1];<br><br>The code assumes the minimum of a type is less than or equal to its maximum.<br><br><br>Index: m3-sys/m3front/src/misc/CG.i3<br>===================================================================<br>RCS file: /usr/cvs/cm3/m3-sys/m3front/src/misc/CG.i3,v<br>retrieving revision 1.15<br>diff -r1.15 CG.i3<br>11c11<br>< IMPORT Target, M3CG, M3;<br>---<br>> IMPORT Target, M3CG, M3, TInt;<br>402c402,406<br>< PROCEDURE Load (v: Var;  o: Offset;  s: Size;  a: Alignment;  t: Type);<br>---<br>> PROCEDURE Load (v: Var;  o: Offset;  s: Size;  a: Alignment;  t: Type;<br>>                 min_valid: BOOLEAN := FALSE;<br>>                 max_valid: BOOLEAN := FALSE;<br>>                 min: Target.Int := TInt.Zero;<br>>                 max: Target.Int := TInt.Zero);<br>414,415c418,423<br>< PROCEDURE Load_int (t: IType;  v: Var;  o: Offset := 0);<br>< (* == Load (v, o, t.size, t.align, t) *)<br>---<br>> PROCEDURE Load_int (t: IType;  v: Var;  o: Offset := 0;<br>>                     min_valid: BOOLEAN := FALSE;<br>>                     max_valid: BOOLEAN := FALSE;<br>>                     min: Target.Int := TInt.Zero;<br>>                     max: Target.Int := TInt.Zero);<br>> (* == Load (v, o, t.size, t.align, t, min/max...) *)<br>Index: m3-sys/m3front/src/misc/CG.m3<br>===================================================================<br>RCS file: /usr/cvs/cm3/m3-sys/m3front/src/misc/CG.m3,v<br>retrieving revision 1.40<br>diff -r1.40 CG.m3<br>13c13<br>< IMPORT M3, M3CG, M3CG_Ops, M3CG_Check;<br>---<br>> IMPORT M3, M3CG, M3CG_Ops, M3CG_Check, RTIO, RTParams;<br>45a46,49<br>>     min_valid : BOOLEAN := FALSE; (* whether or not min is valid *)<br>>     max_valid : BOOLEAN := FALSE; (* whether or not max is valid *)<br>>     min       : Target.Int := TInt.Zero; (* the minimum possible value *)<br>>     max       : Target.Int := TInt.Zero; (* the maximum possible value *)<br>80c84,85<br>< VAR<br>---<br>> VAR<br>>   debug := FALSE;<br>604a610,614<br>>     v.min       := TInt.Zero;<br>>     v.max       := TInt.Zero;<br>>     v.min_valid := FALSE;<br>>     v.max_valid := FALSE;<br>> <br>766a777,780<br>>     x.min       := TInt.Zero;<br>>     x.max       := TInt.Zero;<br>>     x.min_valid := FALSE;<br>>     x.max_valid := FALSE;<br>978a993,995<br>>       IF debug THEN<br>>         RTIO.PutText("m3front:cg:Init_int:NOT in_init: o: " & Fmt.Int(o) & " s:" & Fmt.Int(s) & " value:" & TInt.ToText(value) & "\n"); RTIO.Flush();<br>>       END;<br>980a998,1001<br>>     END;<br>> <br>>     IF debug THEN<br>>       RTIO.PutText("m3front:cg:Init_int:in_init: o: " & Fmt.Int(o) & " s:" & Fmt.Int(s) & " value:" & TInt.ToText(value) & "\n"); RTIO.Flush();<br>1266c1287,1291<br>< PROCEDURE Load (v: Var;  o: Offset;  s: Size;  a: Alignment;  t: Type) =<br>---<br>> PROCEDURE Load (v: Var;  o: Offset;  s: Size;  a: Alignment;  t: Type;<br>>                 min_valid: BOOLEAN := FALSE;<br>>                 max_valid: BOOLEAN := FALSE;<br>>                 min: Target.Int := TInt.Zero;<br>>                 max: Target.Int := TInt.Zero) =<br>1276c1301<br><       SimpleLoad (v, o, t);<br>---<br>>       SimpleLoad (v, o, t, min_valid, max_valid, min, max);<br>1291c1316<br><         SimpleLoad (v, o, best_type);<br>---<br>>         SimpleLoad (v, o, best_type, min_valid, max_valid, min, max);<br>1312c1337,1341<br>< PROCEDURE SimpleLoad (v: Var;  o: Offset;  t: Type) =<br>---<br>> PROCEDURE SimpleLoad (v: Var;  o: Offset;  t: Type;<br>>                       min_valid: BOOLEAN := FALSE;<br>>                       max_valid: BOOLEAN := FALSE;<br>>                       min: Target.Int := TInt.Zero;<br>>                       max: Target.Int := TInt.Zero) =<br>1323a1353,1356<br>>       x.min_valid := min_valid;<br>>       x.max_valid := max_valid;<br>>       x.min       := min;<br>>       x.max       := max;<br>1339a1373,1376<br>>       x.min       := TInt.Zero;<br>>       x.max       := TInt.Zero;<br>>       x.min_valid := FALSE;<br>>       x.max_valid := FALSE;<br>1347a1385,1388<br>>     stack[tos-1].min       := TInt.Zero;<br>>     stack[tos-1].max       := TInt.Zero;<br>>     stack[tos-1].min_valid := FALSE;<br>>     stack[tos-1].max_valid := FALSE;<br>1350c1391,1395<br>< PROCEDURE Load_int (t: IType;  v: Var;  o: Offset := 0) =<br>---<br>> PROCEDURE Load_int (t: IType;  v: Var;  o: Offset := 0;<br>>                     min_valid: BOOLEAN := FALSE;<br>>                     max_valid: BOOLEAN := FALSE;<br>>                     min: Target.Int := TInt.Zero;<br>>                     max: Target.Int := TInt.Zero) =<br>1352c1397<br><     SimpleLoad (v, o, t);<br>---<br>>     SimpleLoad (v, o, t, min_valid, max_valid, min, max);<br>1815a1861,1864<br>>       x.min_valid := TRUE;<br>>       x.max_valid := TRUE;<br>>       x.min := i;<br>>       x.max := i;<br>1832,1834c1881,2007<br><   BEGIN<br><     IF Force_pair (commute := TRUE) THEN<br><       op := M3CG.SwappedCompare [op];<br>---<br>>   VAR always_true: BOOLEAN;<br>>       always_false: BOOLEAN;<br>>       left_type: Type;<br>>       right_type: Type;<br>>       left_min: Target.Int;<br>>       left_max: Target.Int;<br>>       right_min: Target.Int;<br>>       right_max: Target.Int;<br>>       left_signed: BOOLEAN;<br>>       right_signed: BOOLEAN;<br>>   BEGIN<br>> <br>>     always_true := FALSE;<br>>     always_false := FALSE;<br>> <br>>     WITH left  = stack [SCheck (2, "Compare-left")],<br>>          right = stack [SCheck (1, "Compare-right")] DO<br>> <br>>       left_type := left.type;<br>>       right_type := right.type;<br>> <br>>       IF      left.min_valid<br>>           AND left.max_valid<br>>           AND right.min_valid<br>>           AND right.max_valid<br>>           AND Target.OrdinalType[left_type]<br>>           AND Target.OrdinalType[right_type] THEN<br>> <br>>         left_min := left.min;<br>>         left_max := left.max;<br>>         right_min := right.min;<br>>         right_max := right.max;<br>>         left_signed := Target.SignedType[left_type];<br>>         right_signed := Target.SignedType[right_type];<br>> <br>>         (* First handle types that match in signedness. *)<br>> <br>>         IF left_signed = right_signed THEN<br>> <br>>           (* Check for ranges with no overlap. *)<br>> <br>>           IF left_signed (* and right_signed *) THEN<br>>             IF TInt.LT(left_max, right_min) THEN<br>>               always_true := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};<br>>             ELSIF TInt.GT(left_min, right_max) THEN<br>>               always_true := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};<br>>             END;<br>>           ELSE (* left_signed and right_signed both false *)<br>>             IF TWord.LT(left_max, right_min) THEN<br>>               always_true := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};<br>>             ELSIF TWord.GT(left_min, right_max) THEN<br>>               always_true := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};<br>>             END;<br>>           END;<br>> <br>>           (* Check for overlap just on the edge, e.g. [0..1] compared to [1..2]. *)<br>> <br>>           IF NOT (always_true OR always_false) THEN<br>>             IF TInt.EQ(left_max, right_min) THEN<br>>               always_true := op = Cmp.LE;<br>>               always_false := op = Cmp.GT;<br>>             ELSIF TInt.EQ(left_min, right_max) THEN<br>>               always_true := op = Cmp.GE;<br>>               always_false := op = Cmp.LT;<br>>             END;<br>>           END;<br>> <br>>           (* Handle equal subranges with one element, not likely to occur. *)<br>> <br>>           IF NOT (always_true OR always_false) THEN<br>>             IF      TInt.EQ(left_max, left_min)<br>>                 AND TInt.EQ(left_max, right_max)<br>>                 AND TInt.EQ(left_max, right_min) THEN<br>>               always_true  := op IN SET OF Cmp{Cmp.GE, Cmp.LE, Cmp.EQ};<br>>               always_false := op IN SET OF Cmp{Cmp.LT, Cmp.GT, Cmp.NE};<br>>             END;<br>>           END;<br>>         ELSE<br>> <br>>           (* Now deal with mixed up types (signed compared to unsigned).<br>>            * We may be able to merge these by setting some min/max<br>>            * to zero. That is, the minimum of an unsigned type is zero.<br>>            * However we want to be sure not to interpret unsigned min/max<br>>            * as signed.<br>>            *)<br>> <br>>           IF left_signed THEN<br>>             IF TInt.LT(left_max, TInt.Zero) THEN<br>>               always_true  := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.EQ};<br>>             ELSIF TInt.EQ(left_max, TInt.Zero) THEN<br>>               always_true  := op = Cmp.LE;<br>>               always_false := op = Cmp.GT;<br>>             END;<br>>           ELSE (* right is signed *)<br>>             IF TInt.LT(right_max, TInt.Zero) THEN<br>>               always_true  := op IN SET OF Cmp{Cmp.GT, Cmp.GE, Cmp.NE};<br>>               always_false := op IN SET OF Cmp{Cmp.LT, Cmp.LE, Cmp.EQ};<br>>             ELSIF TInt.EQ(right_max, TInt.Zero) THEN<br>>               always_true := op = Cmp.GE;<br>>               always_false := op = Cmp.LT;<br>>             END;<br>>           END;<br>>         END;<br>>       END;<br>>  <br>>       <* ASSERT NOT (always_true AND always_false) *><br>> <br>>       IF always_true OR always_false THEN<br>>         Discard(right_type);<br>>         Discard(left_type);<br>>         IF always_true THEN<br>>           cg.load_integer (Target.Integer.cg_type, TInt.One);<br>>         ELSE<br>>           cg.load_integer (Target.Integer.cg_type, TInt.Zero);<br>>         END<br>>       ELSE<br>>         IF Force_pair (commute := TRUE) THEN<br>>           op := M3CG.SwappedCompare [op];<br>>         END;<br>>         cg.compare (t, Target.Integer.cg_type, op);<br>>         SPop (2, "Compare");<br>>       END;<br>1836,1837d2008<br><     cg.compare (t, Target.Integer.cg_type, op);<br><     SPop (2, "Compare");<br>2880a3052,3055<br>>       x.min       := TInt.Zero;<br>>       x.max       := TInt.Zero;<br>>       x.min_valid := FALSE;<br>>       x.max_valid := FALSE;<br>2977c3152,3153<br>< BEGIN<br>---<br>> BEGIN<br>>   debug := debug OR RTParams.IsPresent ("m3front_cg_debug");<br>Index: m3-sys/m3front/src/values/Variable.m3<br>===================================================================<br>RCS file: /usr/cvs/cm3/m3-sys/m3front/src/values/Variable.m3,v<br>retrieving revision 1.13<br>diff -r1.13 Variable.m3<br>362a363,365<br>>   VAR min: Target.Int;<br>>       max: Target.Int;<br>>       bounds_valid: BOOLEAN;<br>395c398,401<br><         CG.Load (t.cg_var, t.offset, t.size, t.cg_align, t.stk_type);<br>---<br>>         (*GetBounds (t, min, max);<br>>         bounds_valid := TInt.LE(min, max);*)<br>>         bounds_valid := t.tipe # NIL AND Type.GetBounds(t.tipe, min, max) AND TInt.LE(min, max);<br>>         CG.Load (t.cg_var, t.offset, t.size, t.cg_align, t.stk_type, bounds_valid, bounds_valid, min, max);<br><br><br><br><br><br>                                     </body>
</html>