1 /*
2
3 This file is part of the Maude 2 interpreter.
4
5 Copyright 1997-2003 SRI International, Menlo Park, CA 94025, USA.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
20
21 */
22
23 //
24 // Implementation for class VariableInfo.
25 //
26
27 #include "macros.hh"
28 #include "vector.hh"
29 #include "graph.hh"
30
31 // forward declarations
32 #include "interface.hh"
33 #include "core.hh"
34 #include "variable.hh"
35
36 // core class definitions
37 #include "substitution.hh"
38 #include "variableInfo.hh"
39
VariableInfo()40 VariableInfo::VariableInfo()
41 {
42 nrProtectedVariables = 0;
43 fragmentNumber = 0;
44 }
45
46 int
variable2Index(VariableTerm * variable)47 VariableInfo::variable2Index(VariableTerm* variable)
48 {
49 Assert(variable != 0, "null term");
50 int nrRealVariables = variables.length();
51 Assert(nrRealVariables == nrProtectedVariables,
52 "can't add new real variables at this stage");
53 for (int i = 0; i < nrRealVariables; i++)
54 {
55 if (variable->equal(variables[i]))
56 return i;
57 }
58 variables.append(variable);
59 ++nrProtectedVariables;
60 return nrRealVariables;
61 }
62
63 int
makeConstructionIndex()64 VariableInfo::makeConstructionIndex()
65 {
66 int nrConstructionIndices = constructionIndices.length();
67 constructionIndices.expandBy(1);
68 constructionIndices[nrConstructionIndices].assignedFragment = fragmentNumber;
69 constructionIndices[nrConstructionIndices].lastUseFragment = fragmentNumber;
70 return MAX_NR_PROTECTED_VARIABLES + nrConstructionIndices;
71 }
72
73 int
computeIndexRemapping()74 VariableInfo::computeIndexRemapping()
75 {
76 int nrConstructionIndices = constructionIndices.length();
77 /*
78 cerr << "dumping constructionIndices\n";
79 for (int i = 0; i < nrConstructionIndices; i++)
80 {
81 cerr << i << '\t' <<
82 constructionIndices[i].assignedFragment << '\t' <<
83 constructionIndices[i].lastUseFragment << '\t' <<
84 constructionIndices[i].lastUseTime << endl;
85 }
86 */
87
88 //
89 // All construction indices that need to be protected between different fragments
90 // get remapped to a new protected variable.
91 //
92 for (int i = 0; i < nrConstructionIndices; i++)
93 {
94 if (constructionIndices[i].assignedFragment != constructionIndices[i].lastUseFragment)
95 constructionIndices[i].newIndex = makeProtectedVariable();
96 }
97 //
98 // We now build a graph of conflicts between remaining construction indices.
99 //
100 DebugAdvisoryCheck(nrConstructionIndices < 100, "nrConstructionIndices = " << nrConstructionIndices);
101 Graph conflicts(nrConstructionIndices);
102 Vector<int> conflictCandidates;
103 Vector<int> nextConflictCandidates;
104 for (int i = 0; i < nrConstructionIndices; i++)
105 {
106 if (constructionIndices[i].assignedFragment ==
107 constructionIndices[i].lastUseFragment)
108 {
109 //
110 // A remaining construction index i conflicts with any earlier
111 // remaining construction index j whose last use is after the
112 // allocation of construction index i. To speed things up
113 // when the number of construction indices is huge we keep track
114 // a smaller pool of candidates.
115 //
116 nextConflictCandidates.clear();
117 FOR_EACH_CONST(j, Vector<int>, conflictCandidates)
118 {
119 int c = *j;
120 if (constructionIndices[c].lastUseTime > i)
121 {
122 conflicts.insertEdge(i, c);
123 nextConflictCandidates.append(c);
124 }
125 }
126 nextConflictCandidates.append(i);
127 conflictCandidates.swap(nextConflictCandidates);
128 }
129 }
130 //
131 // We now use graph coloring to remap the remaining construction indices.
132 //
133 Vector<int> coloring;
134 int nrColors = conflicts.color(coloring);
135 for (int i = 0; i < nrConstructionIndices; i++)
136 {
137 if (constructionIndices[i].assignedFragment ==
138 constructionIndices[i].lastUseFragment)
139 constructionIndices[i].newIndex = nrProtectedVariables + coloring[i];
140 }
141 //
142 // Finally, we need return the minimum size of substitution needed.
143 //
144 return nrProtectedVariables + nrColors;
145 /*
146 DebugAdvisory("nrProtectedVariables = " << nrProtectedVariables <<
147 "\tnrColors = " << nrColors);
148 */
149 }
150