llvm dev - Apr 2007 - [LLVMdev] LLVM projects: Change framework

hi all,

I have used LLVM extensively over the last 2 years.
I have realized a so called change framework that based on the LLVM 
framework.

Basically it is a framework that augments the JIT to understand 
"changes", such that a mutator process can formulate changes in a
change
language (inspired by DTrace's D), which is too compiled to LLVM and 
sent to the application process.

The application process than transforms the IR and marks the functions 
as beeing dirty. After a detection period, the changes are detected and 
the functions in question get recompiled and relinked, such that the 
change is now applied within the application.

Every change can be undone. This is done by keeping an undo record of 
changes (allthough other approaches would seem fit also).

The thesis can be found on http://www.prahersoft.com/~jp/da.pdf.
Part of the thesis is an extensive documentation of the LLVM framework 
from a 10000 feet view. This might be interesting to new-comers.

The reason why I did not post information on this list, is that the my 
university rules did not allow me to.

I would be interested in hearing from you about it.

-- Jakob

Jakob,

What exactly can you describe in this change language?  There is a  
lot of research happening now on techniques to identify the best  
sequence of optimizations for a particular program, or just the best  
output form for the program.  There are no really good  
infrastructures for this kind of work, but we have been interested in  
making LLVM useful for such work.  (LLVM has been used by Keith  
Cooper's group at Rice for this purpose because it allows very easy  
pipelining of passes.)

I'm wondering if the change language can be used to describe a  
sequence of transformations more abstractly to make this kind of  
research easier and more systematic?

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org


On Apr 25, 2007, at 2:01 AM, Jakob Praher wrote:
> hi all,
>
> I have used LLVM extensively over the last 2 years.
> I have realized a so called change framework that based on the LLVM
> framework.
>
> Basically it is a framework that augments the JIT to understand
> "changes", such that a mutator process can formulate changes in a
> change
> language (inspired by DTrace's D), which is too compiled to LLVM and
> sent to the application process.
>
> The application process than transforms the IR and marks the functions
> as beeing dirty. After a detection period, the changes are detected  
> and
> the functions in question get recompiled and relinked, such that the
> change is now applied within the application.
>
> Every change can be undone. This is done by keeping an undo record of
> changes (allthough other approaches would seem fit also).
>
> The thesis can be found on http://www.prahersoft.com/~jp/da.pdf.
> Part of the thesis is an extensive documentation of the LLVM framework
> from a 10000 feet view. This might be interesting to new-comers.
>
> The reason why I did not post information on this list, is that the my
> university rules did not allow me to.
>
> I would be interested in hearing from you about it.
>
> -- Jakob
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

hi Vikram,

thanks for your interest.

Vikram S. Adve schrieb:
> Jakob,
> 
> What exactly can you describe in this change language?  
The language itself is based on so called providers. Providers run 
within the execution engine and export information (static) for fast 
evaulation. Every node in the representation is visited (at a certain 
scope). Providers declare their scope (such as function, basic bock, ...)

So you can write a provder and use it right away with the change 
language. The change language itself is simply a C like langauge that 
compiles to LLVM and gets loaded by the execution engine.

The change language is composed of a a predicate and some change 
statements (in a body) . The predicate gets translated to a LLVM 
function and get compiled to machine code at application time. Such that 
the predicate function can be called on any node visited in a static way.

If this function call evaluates to true, then the system knows to insert 
the changes at that point. Since the body of the change is also already 
in llvm representation the transformation is simply adding the nodes at 
that point into the graph and keeping an undo record.

What can be achieved really depends on how clever the provider is. For 
instance I sketched out a loopinfoProvider that works by DFS on the CFG 
to produce loop information points (such as LoopEnter, LoopExit, 
LoopHeaderEnter,...) The change language can use this provider and 
insert code at every LoopExit/LoopEnter,... points.

In order to express dynamic information (at run-time) a TLS object is 
introduced, that exports function pointers to set and get named values 
on TLS. These are pluggable too. Such that one can write her/his own 
magic value (io, thread, ...) that provide dynamic services. At this 
time the provider visits nodes and performs predicate checks based on 
the supplied change predicates.
> There is a  
> lot of research happening now on techniques to identify the best  
> sequence of optimizations for a particular program, or just the best  
> output form for the program.  There are no really good  
> infrastructures for this kind of work, but we have been interested in  
> making LLVM useful for such work.  (LLVM has been used by Keith  
> Cooper's group at Rice for this purpose because it allows very easy  
> pipelining of passes.)
That is interesting. I for instance have thought about using the change 
framework for hot spot analysis, since this is what basically could be 
done (using loop information... ). Thought the change framework has some 
problems transforming existing code. It merely inserts code at certain 
points at this time. One would have to identify how to express changing 
of the LLVM graph by transformation. For instance write a change that 
performs function inlining or loop unrolling ....
The framework is there.
> 
> I'm wondering if the change language can be used to describe a  
> sequence of transformations more abstractly to make this kind of  
> research easier and more systematic?
See above I think what is imissing now is how to transform existing 
instruction sequences, and not merely inserting them at points.


-- Jakob
> On Apr 25, 2007, at 2:01 AM, Jakob Praher wrote:
> 
>> hi all,
>>
>> I have used LLVM extensively over the last 2 years.
>> I have realized a so called change framework that based on the LLVM
>> framework.
>>
>> Basically it is a framework that augments the JIT to understand
>> "changes", such that a mutator process can formulate changes
in a
>> change
>> language (inspired by DTrace's D), which is too compiled to LLVM
and
>> sent to the application process.
>>
>> The application process than transforms the IR and marks the functions
>> as beeing dirty. After a detection period, the changes are detected  
>> and
>> the functions in question get recompiled and relinked, such that the
>> change is now applied within the application.
>>
>> Every change can be undone. This is done by keeping an undo record of
>> changes (allthough other approaches would seem fit also).
>>
>> The thesis can be found on http://www.prahersoft.com/~jp/da.pdf.
>> Part of the thesis is an extensive documentation of the LLVM framework
>> from a 10000 feet view. This might be interesting to new-comers.
>>
>> The reason why I did not post information on this list, is that the my
>> university rules did not allow me to.
>>
>> I would be interested in hearing from you about it.
>>
>> -- Jakob
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Wed, 25 Apr 2007, Jakob Praher wrote:
> I have used LLVM extensively over the last 2 years.
> I have realized a so called change framework that based on the LLVM
> framework.
I am just now getting a chance to read through your thesis.  It looks like 
excellent work.  Do you mind if we add it to llvm.org/pubs ?

-Chris
> Basically it is a framework that augments the JIT to understand
> "changes", such that a mutator process can formulate changes in a
change
> language (inspired by DTrace's D), which is too compiled to LLVM and
> sent to the application process.
>
> The application process than transforms the IR and marks the functions
> as beeing dirty. After a detection period, the changes are detected and
> the functions in question get recompiled and relinked, such that the
> change is now applied within the application.
>
> Every change can be undone. This is done by keeping an undo record of
> changes (allthough other approaches would seem fit also).
>
> The thesis can be found on http://www.prahersoft.com/~jp/da.pdf.
> Part of the thesis is an extensive documentation of the LLVM framework
> from a 10000 feet view. This might be interesting to new-comers.
>
> The reason why I did not post information on this list, is that the my
> university rules did not allow me to.
>
> I would be interested in hearing from you about it.
>
> -- Jakob
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

Hi Chris,

Chris Lattner wrote:
> On Wed, 25 Apr 2007, Jakob Praher wrote:
>> I have used LLVM extensively over the last 2 years.
>> I have realized a so called change framework that based on the LLVM
>> framework.
> 
> I am just now getting a chance to read through your thesis.  It looks like 
> excellent work.  Do you mind if we add it to llvm.org/pubs ?
> 
> -Chris
it would be an honor. thank you very much.

-- Jakob
> 
>> Basically it is a framework that augments the JIT to understand
>> "changes", such that a mutator process can formulate changes
in a change
>> language (inspired by DTrace's D), which is too compiled to LLVM
and
>> sent to the application process.
>>
>> The application process than transforms the IR and marks the functions
>> as beeing dirty. After a detection period, the changes are detected and
>> the functions in question get recompiled and relinked, such that the
>> change is now applied within the application.
>>
>> Every change can be undone. This is done by keeping an undo record of
>> changes (allthough other approaches would seem fit also).
>>
>> The thesis can be found on http://www.prahersoft.com/~jp/da.pdf.
>> Part of the thesis is an extensive documentation of the LLVM framework
>> from a 10000 feet view. This might be interesting to new-comers.
>>
>> The reason why I did not post information on this list, is that the my
>> university rules did not allow me to.
>>
>> I would be interested in hearing from you about it.
>>
>> -- Jakob
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
> 
> -Chris
>