llvm dev - Apr 2008 - [LLVMdev] Being able to know the jitted code-size before emitting

In general, it is not possible to know jitted code size without
emitting. You can suppress the actual write of the instructions
themselves, but you have to do all of the work prior to that point.

The reason is that on many architectures there are span-dependent
branches. The final instruction size depends on the branch span. The
span depends on the code size, and the code size depends on the
representation of the span. It really is a cyclical dependency, and it
is usually solved by doing the best you can and then breaking cycles in
the span dependency graph by picking one of the offending spans
arbitrarily and fixing it to the max representation length (after which
the rest of the dependency loop can be resolved).

But the point is that you have to actually generate the code (at least
in memory) to do this analysis.

You can get a conservative upper bound on those architectures by
assuming that all spans will use the maximal sized representation, but
you cannot get a precise size without emitting the code.


shap

On Apr 4, 2008, at 11:58 AM, Jonathan S. Shapiro wrote:
> In general, it is not possible to know jitted code size without
> emitting. You can suppress the actual write of the instructions
> themselves, but you have to do all of the work prior to that point.
That's not true. llvm targets which support JIT have all the  
information necessary to calculate the size of every instructions.  
It's possible to compute instruction length without having to compute  
what bits are going to be emitted.
>
> The reason is that on many architectures there are span-dependent
> branches. The final instruction size depends on the branch span. The
> span depends on the code size, and the code size depends on the
> representation of the span. It really is a cyclical dependency, and it
> is usually solved by doing the best you can and then breaking cycles  
> in
> the span dependency graph by picking one of the offending spans
> arbitrarily and fixing it to the max representation length (after  
> which
> the rest of the dependency loop can be resolved).
>
>
> But the point is that you have to actually generate the code (at least
> in memory) to do this analysis.
JIT is responsible for relocation. It knows everything, including the  
distance between the source and destination. Codegen needs to resolve  
all this before jitting so it's always possible to compute the size of  
every instruction before actually code emission.

Evan
>
>
> You can get a conservative upper bound on those architectures by
> assuming that all spans will use the maximal sized representation, but
> you cannot get a precise size without emitting the code.
>
>
> shap
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Fri, 2008-04-04 at 12:15 -0700, Evan Cheng wrote:
> On Apr 4, 2008, at 11:58 AM, Jonathan S. Shapiro wrote:
> 
> > In general, it is not possible to know jitted code size without
> > emitting. You can suppress the actual write of the instructions
> > themselves, but you have to do all of the work prior to that point.
> 
> That's not true. llvm targets which support JIT have all the  
> information necessary to calculate the size of every instructions.  
> It's possible to compute instruction length without having to compute  
> what bits are going to be emitted.
Evan: please explain how span-dependent branches are resolved in your
method. You don't need to compute the bits that will be emitted, but you
do need to compute the length of those bits. In most real
implementations, the two steps are therefore inseparable.
> > But the point is that you have to actually generate the code (at least
> > in memory) to do this analysis.
> 
> JIT is responsible for relocation. It knows everything, including the  
> distance between the source and destination. Codegen needs to resolve  
> all this before jitting so it's always possible to compute the size of
> every instruction before actually code emission.
This is basically repeating what I already said. You can suppress the
actual write of the instructions, but you need to run all of the steps
of code generation up to (but excluding) emission if you need to resolve
span dependent branches.

Meta-observation: if you cared how big the jitted code was, presumably
there was some question about whether/where you had the space for the
code. Codegen will require at least that much space in order to answer
the question. Given which, the simplest approach is to go ahead and
generate the code provisionally and either (a) keep it or (b) discard
it.


shap