interpreter/preprocessor/faust-0.9.47mr3/compiler/tlib/shlysis.cpp

   1 /************************************************************************
   2  ************************************************************************
   3     FAUST compiler
   4         Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
   5     ---------------------------------------------------------------------
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  ************************************************************************
  20  ************************************************************************/
  21
  22
  23
  24 /*****************************************************************************
  25 ******************************************************************************
  26                                                                 Tree Sharing Analysis
  27                                                 Y. Orlarey, (c) Grame 2002
  28 ------------------------------------------------------------------------------
  29 The sharing analysis of tree t is the annotation of all its subtrees t'
  30 with their number of occurences in t. As this annotation of t' depends of
  31 a context (the tree t for which t' is a subtree) a specific property key
  32 unique to each sharing analysis must be generated.
  33
  34  API:
  35  ----
  36
  37         shprkey(t) -> k         = unique sharing property key of t
  38         shcount(k,t') -> n      = returns the number of occurences of t' in t (where k = shprkey(t))
  39         shlysis(t)      -> k    = annotated the subtrees of t with prop (key sharing-count)
  40                                                   (0 if t' is not a subtree of t)
  41
  42  History :
  43  ---------
  44         2002-04-08 : First version
  45     2006-03-25 : Modifications for new symbolic rec trees
  46
  47 ******************************************************************************
  48 *****************************************************************************/
  49
  50  /**
  51  * @file shlysis.cpp
  52  * The sharing analysis of tree t is the annotation of all its subtrees t'
  53  * with their number of occurences in t. As this annotation of t' depends of
  54  * a context (the tree t for which t' is a subtree) a specific property key
  55  * unique to each sharing analysis must be generated.
  56  */
  57
  58 #include    <string.h>
  59 #include    <stdlib.h>
  60 #include    <stdio.h>
  61
  62 #include        "shlysis.hh"
  63 #include "compatibility.hh"
  64
  65 /**
  66  * Create a specific property key for the sharing count of subtrees of t
  67  */
  68
  69 Tree shprkey(Tree t)
  70 {
  71         char    name[256];
  72         snprintf(name, 256, "SHARED IN %p : ", (CTree*)t);
  73         return tree(unique(name));
  74 }
  75
  76
  77 /**
  78  * Return the value of sharing count or 0
  79  */
  80
  81 int shcount(Tree key, Tree t)
  82 {
  83         Tree c;
  84         if (getProperty(t, key, c)) {
  85                 return c->node().getInt();
  86         } else {
  87                 return 0;
  88         }
  89 }
  90
  91
  92
  93 //------------------------------------------------------------------------------
  94 // Create a specific property key for the sharing count of subtrees of t
  95 //------------------------------------------------------------------------------
  96
  97 static void annotate(Tree k, Tree t, barrier foo);
  98
  99 static bool nobarrier (const Tree& t) { return false; }
 100
 101 /**
 102  * Do a sharing analysis : annotates all the subtrees of t
 103  * with there occurences
 104  */
 105 Tree shlysis(Tree t, barrier foo)
 106 {
 107         Tree k = shprkey(t);
 108         annotate(k, t, foo);
 109         return k;
 110 }
 111
 112
 113 /**
 114  * Do a sharing analysis : annotates all the subtrees of t
 115  * with there occurences
 116  */
 117 Tree shlysis(Tree t)
 118 {
 119         Tree k = shprkey(t);
 120         annotate(k, t, nobarrier);
 121         return k;
 122 }
 123
 124
 125 /**
 126  * Recursively increment the occurences count
 127  * of t and its subtrees
 128  */
 129 static void annotate(Tree k, Tree t, barrier foo)
 130 {
 131         cerr << "Annotate " << *t << endl;
 132         int c = shcount(k,t);
 133         if (c==0) {
 134                 // First visit
 135                 Tree var, body;
 136                 if (isRec(t, var, body)) {
 137                         // special case for recursive trees
 138                         setProperty(t, k, tree(1));
 139                         annotate(k, body, foo);
 140                         return;
 141                 } else {
 142                         int n = t->arity();
 143                         if (n>0 && ! foo(t)) {
 144                                 for (int i=0; i<n; i++) annotate(k, t->branch(i), foo);
 145                         }
 146                 }
 147         } else {
 148                 //printf(" annotate %p with %d\n", (CTree*)t, c+1);
 149         }
 150         setProperty(t, k, tree(c+1));
 151 }