[Issue 8431] New: [Optimizer] Merge equivalent jump tables for switch statements

[d-bugmail at puremagic.com]

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 at puremagic.com
        ReportedBy: dmitry.olsh at gmail.com


--- Comment #0 from Dmitry Olshansky <dmitry.olsh at 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: -------