[LLVMbugs] [Bug 884] NEW: Optimize repetitive case/return and case/=/break sequences to array access

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=884

           Summary: Optimize repetitive case/return and case/=/break
                    sequences to array access
           Product: tools
           Version: trunk
          Platform: Macintosh
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: opt
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: ggreif at gmail.com


Here is a short IRC transcript:

gabor: sabre: I had an optimization idea the other day
[00:26] gabor: kind of
[00:26] apinski: it make RA O(n) 
[00:26] gabor: switch (enum)
[00:26] apinski: if the processor has PHIs 
[00:26] sabre: is away (bb in 30 mins)
[00:27] apinski: gabor: isn't that just VRP?
[00:27] gabor: { case 1: return "one"; case 2: return "two"; etc. }
[00:27] gabor: surely this gets optimized to a jump table
[00:27] apinski: gabor: oh, switch to an array?
[00:27] gabor: but ome could automatically buils a value array
[00:27] gabor: apinski: yes
[00:28] apinski: gabor: yes this is something which could be done  (it has been mentioned a couple of 
times on #gcc and on gcc@ and maybe even implemented in LLVM)
[00:28] gabor: there are definitely a win for many leaf routines
[00:29] gabor: such an LLVM pass should be easy to come up with
[00:41] tonic_ hat den Chatroom verlassen. (Quit: My damn controlling terminal disappeared!)
[01:07] ZabaQ hat den Chatroom verlassen. (Quit: Leaving.)
[01:16] sabre: gabor: that optzn would be very easy to do
[01:16] sabre: if you find some realistic testcases that would benefit form it, I'll implement it
[01:16] gabor: at least the code I inherited at work is full of it
[01:17]

and later...

gabor: _sabre_: some material for switch/return:
[08:20] gabor: gabor: here is one typical, that noone can rewrite as a table, because the indices are 
configuration dependent: http://lists.freestandards.org/pipermail/lsb-discuss/2002-February/
001168.html
[08:20] gabor: [07:57] gabor: one Samba link: http://lists.samba.org/archive/samba-cvs/2006-
February/065220.html
[08:20] gabor: [08:01] gabor: people seem to like code like this. http://gcc.gnu.org/ml/java-prs/2002-
q4/msg00107.html
[08:20] gabor: [08:04] gabor: this one is more involved because it needs "default:" handling http://
search.cpan.org/src/KJALB/OpenGL-0.5/gl_util.c
[08:20] gabor: [08:06] gabor: heh: http://www.calvin.edu/~jdfrens/Research/ProgLang/Switch/
[08:21] _sabre_: gabor: nice
[08:22] _sabre_: gabor: can you put those links in a bugzilla bug?
[08:22] gabor: I guess these things are not in tight loops, though
[08:23] _sabre_: *shrug* just having the examples is all I needed
[08:23] _sabre_: just to make sure the xform was general enough
[08:23] gabor: but I can imagine that some enum-based state machines may well profit
[08:24] _sabre_: so here's another fun thing
[08:24] _sabre_: you don't want to turn:
[08:24] _sabre_: case 1: X = "foo"; break;
[08:24] _sabre_: case 2: X = "bar"; break;
[08:24] _sabre_: into:
[08:24] _sabre_: arr[] = { .., "foo", "bar" };
[08:25] _sabre_: because then you now have lots of relocations in the "arr" array
[08:25] _sabre_: you'd much rather have:
[08:25] _sabre_: char arr[] = "..foo\0bar\0";
[08:25] _sabre_: or something
[08:25] gabor: coolness
[08:25] Reid: good idea
[08:25] _sabre_: 'course then you need another array with the right indices
[08:25] _sabre_: anyway, gotta run
[08:25] _sabre_: 'night all
[08:25] Reid: fwiw: I write code like this all the time .. HLVM has several examples .. typical usage: 
conversion of one enum to another
[08:25] gabor: goes and opens an optimization bug



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.