www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8431] New: [Optimizer] Merge equivalent jump tables for switch statements

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8431

           Summary: [Optimizer] Merge equivalent jump tables for switch
                    statements
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: dmitry.olsh gmail.com


--- Comment #0 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-07-24
23:45:11 PDT ---
An optimization that would enable a common idiom used to speed up
VM interpretters.

See also, for in-depth study:
http://www.complang.tuwien.ac.at/anton/lvas/sem06w/revucky.pdf 
and NG discussion: 
http://forum.dlang.org/thread/gltqflqrvsxggarxjkde forum.dlang.org?page=3

Example code, currently creates N+1 jump tables 
whereas 1 should be optimal:

//GLOBALS
size_t[] bytecode = firstPassCompile("my_source.ds"); //say it's DMDscript

void run(size_t pc)
{
    //here we don't JIT to real addresses beforehand
    //as jump tables somehow should be good enough
    // Okay...

    //interpret:
    switch(bytecode[pc])
    {
    L_op1:
    case 0:
        //do my op1 thing
        pc += x;
    //DISPATCH:
    //here comes trouble - 1st of N nearly identical tables??
        switch(bytecode[pc])
        {
        case 0:    goto L_op1;
        case 1: goto L_op2;
        ...
        }
    L_op2:
    case 1:
        //do some other thing
        pc += y;
    //DISPATCH:
    //here comes trouble - 2nd table?
        switch(bytecode[pc])
        {
        case 0:    goto L_op1;
        case 1: goto L_op2;
        ...
        }
    L_op3:
    case 2:
        //my other op, jumps back
        pc -= ...;
    //DISPATCH:
    //here comes trouble - 3rd table?
        switch(bytecode[pc])
        {
        case 0:    goto L_op1;
        case 1: goto L_op2;
        ...
        }
...
    L_opN:
    case N-1:
    ...
    //DISPATCH:
    //here comes trouble Nth table ... time to count overhead
        switch(bytecode[pc])
        {
        case 0:    goto L_op1;
        case 1: goto L_op2;
        ...
        }
    }//end of giant switch
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 24 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8431


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #1 from bearophile_hugs eml.cc 2012-07-25 01:45:56 PDT ---
No need for "final switch"?

The presence of this optimization covers one use case of computed gotos
(assuming the programmer is careful in defining the inner switch() with all the
cases of the outer switch).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8431



--- Comment #2 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-07-25
01:50:03 PDT ---
(In reply to comment #1)

 No need for "final switch"?
 


Why would it? Final allows  system code to omit bounds check that's all.


 The presence of this optimization covers one use case of computed gotos
 (assuming the programmer is careful in defining the inner switch() with all the
 cases of the outer switch).


I bet there could be other use cases.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2012