00001 /************************************************************************ 00002 ************************************************************************ 00003 FAUST compiler 00004 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale 00005 --------------------------------------------------------------------- 00006 This program is free software; you can redistribute it and/or modify 00007 it under the terms of the GNU General Public License as published by 00008 the Free Software Foundation; either version 2 of the License, or 00009 (at your option) any later version. 00010 00011 This program is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 GNU General Public License for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software 00018 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 ************************************************************************ 00020 ************************************************************************/ 00021 00022 00023 00024 /***************************************************************************** 00025 ****************************************************************************** 00026 Tree Sharing Analysis 00027 Y. Orlarey, (c) Grame 2002 00028 ------------------------------------------------------------------------------ 00029 The sharing analysis of tree t is the annotation of all its subtrees t' 00030 with their number of occurences in t. As this annotation of t' depends of 00031 a context (the tree t for which t' is a subtree) a specific property key 00032 unique to each sharing analysis must be generated. 00033 00034 API: 00035 ---- 00036 00037 shprkey(t) -> k = unique sharing property key of t 00038 shcount(k,t') -> n = returns the number of occurences of t' in t (where k = shprkey(t)) 00039 shlysis(t) -> k = annotated the subtrees of t with prop (key sharing-count) 00040 (0 if t' is not a subtree of t) 00041 00042 History : 00043 --------- 00044 2002-04-08 : First version 00045 2006-03-25 : Modifications for new symbolic rec trees 00046 00047 ****************************************************************************** 00048 *****************************************************************************/ 00049 00058 #include <string.h> 00059 #include <stdlib.h> 00060 #include <stdio.h> 00061 00062 #include "shlysis.hh" 00063 #include "compatibility.hh" 00064 00069 Tree shprkey(Tree t) 00070 { 00071 char name[256]; 00072 snprintf(name, 256, "SHARED IN %p : ", (CTree*)t); 00073 return tree(unique(name)); 00074 } 00075 00076 00081 int shcount(Tree key, Tree t) 00082 { 00083 Tree c; 00084 if (getProperty(t, key, c)) { 00085 return c->node().getInt(); 00086 } else { 00087 return 0; 00088 } 00089 } 00090 00091 00092 00093 //------------------------------------------------------------------------------ 00094 // Create a specific property key for the sharing count of subtrees of t 00095 //------------------------------------------------------------------------------ 00096 00097 static void annotate(Tree k, Tree t, barrier foo); 00098 00099 static bool nobarrier (const Tree& t) { return false; } 00100 00105 Tree shlysis(Tree t, barrier foo) 00106 { 00107 Tree k = shprkey(t); 00108 annotate(k, t, foo); 00109 return k; 00110 } 00111 00112 00117 Tree shlysis(Tree t) 00118 { 00119 Tree k = shprkey(t); 00120 annotate(k, t, nobarrier); 00121 return k; 00122 } 00123 00124 00129 static void annotate(Tree k, Tree t, barrier foo) 00130 { 00131 cerr << "Annotate " << *t << endl; 00132 int c = shcount(k,t); 00133 if (c==0) { 00134 // First visit 00135 Tree var, body; 00136 if (isRec(t, var, body)) { 00137 // special case for recursive trees 00138 setProperty(t, k, tree(1)); 00139 annotate(k, body, foo); 00140 return; 00141 } else { 00142 int n = t->arity(); 00143 if (n>0 && ! foo(t)) { 00144 for (int i=0; i<n; i++) annotate(k, t->branch(i), foo); 00145 } 00146 } 00147 } else { 00148 //printf(" annotate %p with %d\n", (CTree*)t, c+1); 00149 } 00150 setProperty(t, k, tree(c+1)); 00151 }