1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 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 Tree Sharing Analysis
25 Y. Orlarey, (c) Grame 2002
26 ------------------------------------------------------------------------------
27 The sharing analysis of tree t is the annotation of all its subtrees t'
28 with their number of occurences in t. As this annotation of t' depends of
29 a context (the tree t for which t' is a subtree) a specific property key
30 unique to each sharing analysis must be generated.
31
32 API:
33 ----
34
35 shprkey(t) -> k = unique sharing property key of t
36 shcount(k,t') -> n = returns the number of occurences of t' in t (where k = shprkey(t))
37 shlysis(t) -> k = annotated the subtrees of t with prop (key sharing-count)
38 (0 if t' is not a subtree of t)
39
40 History :
41 ---------
42 2002-04-08 : First version
43 2006-03-25 : Modifications for new symbolic rec trees
44
45 ******************************************************************************
46 *****************************************************************************/
47
48 /**
49 * @file shlysis.cpp
50 * The sharing analysis of tree t is the annotation of all its subtrees t'
51 * with their number of occurences in t. As this annotation of t' depends of
52 * a context (the tree t for which t' is a subtree) a specific property key
53 * unique to each sharing analysis must be generated.
54 */
55
56 #include <stdio.h>
57 #include <stdlib.h>
58 #include <string.h>
59
60 #include "compatibility.hh"
61 #include "shlysis.hh"
62
63 /**
64 * Create a specific property key for the sharing count of subtrees of t
65 */
66
shprkey(Tree t)67 Tree shprkey(Tree t)
68 {
69 char name[256];
70 snprintf(name, 256, "SHARED IN %p : ", (void*)(CTree*)t);
71 return tree(unique(name));
72 }
73
74 /**
75 * Return the value of sharing count or 0
76 */
77
shcount(Tree key,Tree t)78 int shcount(Tree key, Tree t)
79 {
80 Tree c;
81 if (getProperty(t, key, c)) {
82 return c->node().getInt();
83 } else {
84 return 0;
85 }
86 }
87
88 //------------------------------------------------------------------------------
89 // Create a specific property key for the sharing count of subtrees of t
90 //------------------------------------------------------------------------------
91
92 static void annotate(Tree k, Tree t, barrier foo);
93
nobarrier(const Tree & t)94 static bool nobarrier(const Tree& t)
95 {
96 return false;
97 }
98
99 /**
100 * Do a sharing analysis : annotates all the subtrees of t
101 * with there occurences
102 */
shlysis(Tree t,barrier foo)103 Tree shlysis(Tree t, barrier foo)
104 {
105 Tree k = shprkey(t);
106 annotate(k, t, foo);
107 return k;
108 }
109
110 /**
111 * Do a sharing analysis : annotates all the subtrees of t
112 * with there occurences
113 */
shlysis(Tree t)114 Tree shlysis(Tree t)
115 {
116 Tree k = shprkey(t);
117 annotate(k, t, nobarrier);
118 return k;
119 }
120
121 /**
122 * Recursively increment the occurences count
123 * of t and its subtrees
124 */
annotate(Tree k,Tree t,barrier foo)125 static void annotate(Tree k, Tree t, barrier foo)
126 {
127 // cerr << "Annotate " << *t << endl;
128 int c = shcount(k, t);
129 if (c == 0) {
130 // First visit
131 Tree var, body;
132 if (isRec(t, var, body)) {
133 // special case for recursive trees
134 setProperty(t, k, tree(1));
135 annotate(k, body, foo);
136 return;
137 } else {
138 int n = t->arity();
139 if (n > 0 && !foo(t)) {
140 for (int i = 0; i < n; i++) annotate(k, t->branch(i), foo);
141 }
142 }
143 } else {
144 // printf(" annotate %p with %d\n", (CTree*)t, c+1);
145 }
146 setProperty(t, k, tree(c + 1));
147 }
148