[M3devel] small set comparisons understood, now just to understand the front end code..

[Tony Hosking]

Premature optimization is usually time wasted and results in  
unnecessary complexity.

On Apr 14, 2008, at 1:55 PM, Jay wrote:

> If they fit in an INT32, use an INT32.
> But if they fit in an INT64, that's still probably more efficient  
> than an otherwise "big set".
>    Well, of course, there's always the inline vs. non-inline size  
> vs. speed.
> And here I teeter toward hypocricy in taking advantage of two  
> "natural" integer types.
> Heck, generalize it to a list of efficient sizes: 8, 16, 32, 64,  
> pick the smallest that fits, and in the future when otherwise there  
> would have been LONGLONGINT, add 128 to the list.
>
>  - Jay
>
>
> CC: m3devel at elegosoft.com
> From: hosking at cs.purdue.edu
> To: jayk123 at hotmail.com
> Subject: Re: [M3devel] small set comparisons understood, now just to  
> understand the front end code..
> Date: Mon, 14 Apr 2008 11:22:35 -0400
>
> I would hesitate to implement small sets as LONGINT instead of  
> INTEGER, since there is no guarantee that LONGINT is necessarily  
> efficient, whereas INTEGER is intended to be the same as the natural  
> word size of the target.
>
> I could take a look at this but not anytime soon, since I have  
> several other things I need to work on.
>
> On Apr 14, 2008, at 10:51 AM, Jay wrote:
>
> currently set <,>,<=,>= are implemented merely as
> integer <,>,<=,>=
>
> Yes, that seems quite wrong.  I can't imagine things ever worked  
> properly if that is how they are implemented.
>
>
>
> This is wrong.
>
> I believe it should be:
>
> a < b => (a & b) == a
> a <= b => (a & b) == a (same as <=)
> a > b => (a & b) == b
> a >= b => (a & b) == b (same as >)
>
> Probably should be:
>
> a <= b => (a & b) == a
> a < b => (a # b) && ((a & b) == a)
> a >= b => (a & b) == b
> a > b => (a # b) && ((a & b) == b)
>
>
>
> The bug is in the frontend.
>
> m3-sys\m3front\src\misc\CG.m3.
>
> The code should be /something/ like:
>
> PROCEDURE Set_compare (s: Size; op: Cmp) =
> VAR tmp: Val;
>   swap := FALSE;
> BEGIN
>   (* a op b => BOOLEAN *)
>   IF Force_pair (commute := TRUE) THEN
>     op := M3CG.SwappedCompare [op];
>   END;
>   IF (s <= Target.Integer.size) THEN
>     IF (op = Cmp.EQ) OR (op = Cmp.NE) THEN
>       cg.compare (Target.Word.cg_type, Target.Integer.cg_type, op);
>     ELSE
>       (* set a is less than or equal to set b, if all of set a's  
> members are in set b. *)
>       IF (op = Cmp.LT) OR (op = Cmp.LE) THEN
>         swap := TRUE;
>         Swap ();
>       END;
>       tmp := Pop ();
>       Push (tmp);
>       IF swap THEN
>         Swap ();
>       END;
>        cg.and (Target.Integer.cg_type);
>        Push (tmp);
>       SimpleIndirectLoad (tmp^, Target.Word.cg_type);
>       EVAL Force_pair (commute := TRUE);
>        cg.compare (Target.Word.cg_type, Target.Integer.cg_type,  
> Cmp.EQ);
>       SPop (1, "Set_compare");
>       Free (tmp);
>     END;
>   ELSE
>     cg.set_compare (AsBytes (s), op, Target.Integer.cg_type);
>   END;
>   SPop (2, "Set_compare");
>   SPush (Type.Int32);
> END Set_compare;
>
> though this doesn't quite drive all the machinery correctly, since  
> it yields assertion failures in the compiler due to an unbalanced  
> software stack.
> upgrade works, but the test case (p155) fails assertions in the  
> integrated backend.
>
> I'd love to figure this out but have to do other stuff for now.
> Anyone (if there is anyone) familiar with what all is being pushed  
> and popped around here should be able to figure it out easily from  
> this mail.
> Otherwise I'll stare at more later.
>
> ps: "small" sets should probably be anything up to the number of  
> bits in longint, rather than int or pointer, since that is probably  
> efficient enough at the next level down. This is tangential.
>
> - Jay
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20080414/a26ae804/attachment-0002.html>