optimial inlining algo?
 skaller
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20070823 (16:22) 
From:  skaller <skaller@u...> 
Subject:  optimial inlining algo? 
I am trying to reduce a set of routines, with certain routines deemed roots, to an optimal configuration by inlining. A configuration is optimal if, apart from the roots, the only routines left are selfrecursive. You can easily extend this to nontailrecursive. For the purpose of the discussion functional values don't exist (although the real algorithm also tries to eliminate closures, and should ensure this is the case if an argument is an anonymous function). The inlining process consists of making a copy of a function and all its children, except its parameters. The copies are then type specialised based on the call, and parameter specialised by replacing parameters with arguments (the real algorithm also permits copying the parameter and assigning the argument to it). The application is then replaced by a fresh variable, which is initialised by inlining the modified function body, replacing return statements with initialisation of this variable. The code to do the mechanics of inlining isn't the issue here, the problem is deciding whether to inline the application. In principle, this problem just involves two related graphs: the call graph and child graph. The problem is that the graphs are subject to both reduction (removing functions by inlining them) and also expansion (adding specialised copies of children). My actual algorithm does this: before optimising a function, optimise its children. Before inlining a function, optimise that function. Optimisation is a mutator: functional code would be hopelessly inefficient. The difficulty is ensuring recursions like A has child B has child C A calls B calls C calls C are flattened by inlining C into B, then B into A. A call to A, however, must not be inlined. I'm trying to build a rule based on three properties: a) the call in A to B is recursive b) the function F is recursive (equivalent to F contains a recursive call) c) A is the parent of B together with an ordering of optimisations. I can't find a rule that actually works (it either fails to produce optimal results, or clones children infinitely) Anyone have any ideas?  John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net