Patching jump tables at run-time

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Patching jump tables at run-time

Riyaz Puthiyapurayil
I am looking for guidance on how to:                                                                                                                                                                                                                                                                                        
                                                                               
1. At compile time: ensure that a jump table is generated for a *specific* switch instruction
2. At runtime: get hold of the jump table entries for a specific pair of values and swap them.
                                                                               
Let's say I have:                                                              
                                                                               
     switch i32 %2, label %7 [                                                  
       i32 0, label %3                                                          
       i32 1, label %4                                                          
       i32 2, label %5                                                          
       i32 3, label %6                                                          
     ]                                                                          
       :                                                                        
       :                                                                        
for which the following assembly code gets generated:                          
    jmpq    *.LJTI0_0(,%rdi,8)                                                  
       :                                                                        
   .LJTI0_0:                                                                    
    .quad   .LBB0_2                                                            
    .quad   .LBB0_3                                                            
    .quad   .LBB0_4                                                            
    .quad   .LBB0_5                                                            
                                                                               
Based on some run-time conditions, I may want to change the behavior of the switch instruction by swapping the jump table entries for 0 and 2 at runtime. My jump table should then become:
                                                                               
   .LJTI0_0:                                                                    
    .quad   .LBB0_4                                                            
    .quad   .LBB0_3                                                            
    .quad   .LBB0_2                                                            
    .quad   .LBB0_5                                                            
                                                                               
As this is a very simple transformation, I don't want to incur the overhead of recompiling the entire function at run-time.
                                                                               
My target architectures are x86 and x86_64. I understand that the above transformation may not be safe in general, but I know that for the specific switch instructions that I am targeting, it is safe. I am not very familiar with the LLVM code generator and so any advice on how to do this will be appreciated. I don't want to touch the code generator but if there is a way to tag the switch instruction and somehow get the jump table corresponding to that switch at run-time, that's all I need. If I can use intrinsics to achieve this, that would be great. Also is there a way to guarantee the generation of jump table for a switch instruction? My switch labels correspond to a continuous range of values [0..N].
                                                                               
One approach is not to use the switch instruction to lower my switch statement to LLVM. Instead, implement the jump table myself and use the indirectbr instruction. Then I have full control over the jump table. Is this feasible? How would I initialize my global array representing the jump table with the local labels in a function?


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Patching jump tables at run-time

Sean Silva-2



On Tue, Aug 6, 2013 at 2:07 PM, Riyaz Puthiyapurayil <[hidden email]> wrote:
One approach is not to use the switch instruction to lower my switch statement to LLVM. Instead, implement the jump table myself and use the indirectbr instruction. Then I have full control over the jump table. Is this feasible? How would I initialize my global array representing the jump table with the local labels in a function?


Another option is to use indirect tail calls and a table of function pointers. E.g.

typedef uint32_t opcode;
typedef void dispatch_f(opcode *, long, long, long);
dispatch_f *jump_tab[256] = {
...
};
void add(opcode *pc, long r1, long r2) {
  return jump_tab[*pc & 0xFF](pc + 1, r1 + r2, r2);
}
void sub(opcode *pc, long r1, long r2) {
  return jump_tab[*pc & 0xFF](pc + 1, r1 - r2, r2);
}

This has the advantage that you can be sure that you get get a fixed register assignment (which depends on the calling convention), which is typically one of the most difficult things for the compiler to get right for "interpreter-like" code in switches or with indirect branches.

To achieve what you want with this approach, you can just modify jump_tab. Alternatively, you can swap out the jump table itself (e.g. to switch into a tracing mode for a tracing jit).

-- Sean Silva



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev