<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Hi all:<br>in one process it might be good to check for those optimization, but then you might want to abstract them all to allow to be pessimistic or to analyze them in ESC.<br>This should require some good knowledge of the compiler though, which is maybe a harder task than just build a VCG but perhaps is too slow for m3cg, maybe for native backends, is more justifiable if so. Perhaps there is enough good trade off to do so.<br><br>Thanks in advance<br><br>--- El <b>dom, 22/5/11, Jay K <i><jay.krell@cornell.edu></i></b> escribió:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>De: Jay K <jay.krell@cornell.edu><br>Asunto: Re: [M3devel] range analysis?<br>Para: "Tony" <hosking@cs.purdue.edu><br>CC: "m3devel" <m3devel@elegosoft.com><br>Fecha: domingo, 22 de mayo, 2011
18:18<br><br><div id="yiv1984867628">
<style><!--
#yiv1984867628 .yiv1984867628hmmessage P
{
margin:0px;padding:0px;}
#yiv1984867628 .yiv1984867628hmmessage
{
font-size:10pt;font-family:Tahoma;}
--></style>
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="yiv1984867628ecxApple-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="yiv1984867628stopSpelling">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>
<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="yiv1984867628ecxApple-interchange-newline"><blockquote><span class="yiv1984867628ecxApple-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="yiv1984867628ecxhmmessage" 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="yiv1984867628ecxApple-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="yiv1984867628ecxApple-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="yiv1984867628ecxApple-converted-space"> </span><br>> always_true := FALSE;<br>> always_false := FALSE;<br>><span class="yiv1984867628ecxApple-converted-space"> </span><br>> WITH left = stack [SCheck (2, "Compare-left")],<br>> right = stack [SCheck (1, "Compare-right")] DO<br>><span class="yiv1984867628ecxApple-converted-space"> </span><br>> left_type := left.type;<br>> right_type := right.type;<br>><span class="yiv1984867628ecxApple-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="yiv1984867628ecxApple-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="yiv1984867628ecxApple-converted-space"> </span><br>> (* First handle types that match in signedness. *)<br>><span class="yiv1984867628ecxApple-converted-space"> </span><br>> IF left_signed = right_signed THEN<br>><span class="yiv1984867628ecxApple-converted-space"> </span><br>> (* Check for ranges with no overlap. *)<br>><span class="yiv1984867628ecxApple-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="yiv1984867628ecxApple-converted-space"> </span><br>> (* Check for overlap just on the edge, e.g. [0..1] compared to [1..2]. *)<br>><span class="yiv1984867628ecxApple-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="yiv1984867628ecxApple-converted-space"> </span><br>> (* Handle equal subranges with one element, not likely to occur. *)<br>><span class="yiv1984867628ecxApple-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="yiv1984867628ecxApple-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="yiv1984867628ecxApple-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="yiv1984867628ecxApple-converted-space"> </span><br>> <* ASSERT NOT (always_true AND always_false) *><br>><span class="yiv1984867628ecxApple-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>
</div></blockquote></td></tr></table>