<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Tahoma
}
--></style>
</head>
<body class='hmmessage'>
Well, I can build the whole tree and see how many times it helps.<br>I think this is a pretty standard optimization technique.<br>Though it'd work better with compiler-derived additional information.<br><br>I initially happened upon this idea developing test cases.<br><br><span class="ecxApple-style-span" style="border-collapse:separate;font-family:Helvetica;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;orphans:2;text-indent:0px;text-transform:none;white-space:normal;widows:2;word-spacing:0px;font-size:medium"> > The code assumes the minimum of a type is less than or equal to its maximum.<br></span><br>I'll change it not have that problem -- to just fall back to usual pessimistic code for such types, I guess.<br><br> - Jay<br><br><br><hr id="stopSpelling">Subject: Re: range analysis?<br>From: hosking@cs.purdue.edu<br>Date: Sun, 22 May 2011 14:51:59 -0400<br>CC: m3devel@elegosoft.com<br>To: jay.krell@cornell.edu<br><br>
<meta http-equiv="Content-Type" content="text/html; charset=unicode">
<meta name="Generator" content="Microsoft SafeHTML"><base>So, one question is: what benefit does this really give? Your examples seem a little contrived.<div><br><div>
<br><div><div>On May 22, 2011, at 4:26 AM, Jay K wrote:</div><br class="ecxApple-interchange-newline"><blockquote><span class="ecxApple-style-span" style="border-collapse:separate;font-family:Helvetica;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;orphans:2;text-indent:0px;text-transform:none;white-space:normal;widows:2;word-spacing:0px;font-size:medium"><div class="ecxhmmessage" style="font-size:10pt;font-family:Tahoma">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>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><br>> always_true := FALSE;<br>> always_false := FALSE;<br>><span class="ecxApple-converted-space"> </span><br>> WITH left = stack [SCheck (2, "Compare-left")],<br>> right = stack [SCheck (1, "Compare-right")] DO<br>><span class="ecxApple-converted-space"> </span><br>> left_type := left.type;<br>> right_type := right.type;<br>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><br>> (* First handle types that match in signedness. *)<br>><span class="ecxApple-converted-space"> </span><br>> IF left_signed = right_signed THEN<br>><span class="ecxApple-converted-space"> </span><br>> (* Check for ranges with no overlap. *)<br>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><br>> (* Check for overlap just on the edge, e.g. [0..1] compared to [1..2]. *)<br>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><br>> (* Handle equal subranges with one element, not likely to occur. *)<br>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><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>><span class="ecxApple-converted-space"> </span><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>> <span class="ecxApple-converted-space"> </span><br>> <* ASSERT NOT (always_true AND always_false) *><br>><span class="ecxApple-converted-space"> </span><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></div></span></blockquote></div><br></div></div> </body>
</html>