From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id A8DA9BC69 for ; Thu, 23 Aug 2007 18:22:59 +0200 (CEST) Received: from ipmail01.adl2.internode.on.net (ipmail01.adl2.internode.on.net [203.16.214.140]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l7NGMvIE014661 for ; Thu, 23 Aug 2007 18:22:58 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAI5QzUY7pw2h/2dsb2JhbAAM X-IronPort-AV: E=Sophos;i="4.19,301,1183300200"; d="scan'208";a="178189371" Received: from ppp59-167-13-161.lns2.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.13.161]) by ipmail01.adl2.internode.on.net with ESMTP; 24 Aug 2007 01:52:53 +0930 Subject: optimial inlining algo? From: skaller To: caml-list@yquem.inria.fr Content-Type: text/plain Date: Fri, 24 Aug 2007 02:22:51 +1000 Message-Id: <1187886171.6375.26.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 46CDB461.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; inlining:01 inlining:01 optimising:01 optimise:01 optimise:01 recursions:01 inlined:01 recursive:01 recursive:01 clones:98 sourceforge:01 closures:01 graph:01 graph:01 inline:01 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 self-recursive. You can easily extend this to non-tail-recursive. 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 Felix, successor to C++: http://felix.sf.net