Mercurial > hg > truffle

comparison graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/SpecializationGroup.java @ 11195:4f52b08bd2f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Truffle-DSL: Implemented specialization grouping for generic cases.
author Christian Humer <christian.humer@gmail.com>
date Thu, 01 Aug 2013 20:53:54 +0200
parents
children 7fc3e1fb3965
comparison
equal deleted inserted replaced
11194:14d5ff4683e0 11195:4f52b08bd2f9
1 /*
2 * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package com.oracle.truffle.dsl.processor.node;
24
25 import java.util.*;
26
27 import com.oracle.truffle.dsl.processor.template.TemplateMethod.Signature;
28 import com.oracle.truffle.dsl.processor.typesystem.*;
29
30 /**
31 * Class creates groups of specializations to optimize the layout of generated executeAndSpecialize
32 * and generic execute methods.
33 */
34 public final class SpecializationGroup {
35
36 private final List<String> assumptions;
37 private final List<TypeData> typeGuards;
38 private final List<GuardData> guards;
39
40 private final SpecializationData specialization;
41 private final List<SpecializationGroup> children = new ArrayList<>();
42
43 private SpecializationGroup parent;
44
45 private SpecializationGroup(SpecializationData data) {
46 this.assumptions = new ArrayList<>();
47 this.typeGuards = new ArrayList<>();
48 this.guards = new ArrayList<>();
49 this.specialization = data;
50
51 this.assumptions.addAll(data.getAssumptions());
52 Signature sig = data.getSignature();
53 for (int i = 1; i < sig.size(); i++) {
54 typeGuards.add(sig.get(i));
55 }
56 this.guards.addAll(data.getGuards());
57 }
58
59 public SpecializationGroup(List<SpecializationGroup> children, List<String> assumptionMatches, List<TypeData> typeGuardsMatches, List<GuardData> guardMatches) {
60 this.assumptions = assumptionMatches;
61 this.typeGuards = typeGuardsMatches;
62 this.guards = guardMatches;
63 this.specialization = null;
64 updateChildren(children);
65 }
66
67 private void updateChildren(List<SpecializationGroup> childs) {
68 if (!children.isEmpty()) {
69 children.clear();
70 }
71 this.children.addAll(childs);
72 for (SpecializationGroup child : childs) {
73 child.parent = this;
74 }
75 }
76
77 public int getTypeGuardOffset() {
78 return (parent != null ? parent.getTypeGuardOffsetRec() : 0);
79 }
80
81 private int getTypeGuardOffsetRec() {
82 return typeGuards.size() + (parent != null ? parent.getTypeGuardOffsetRec() : 0);
83 }
84
85 public SpecializationGroup getParent() {
86 return parent;
87 }
88
89 public List<String> getAssumptions() {
90 return assumptions;
91 }
92
93 public List<TypeData> getTypeGuards() {
94 return typeGuards;
95 }
96
97 public List<GuardData> getGuards() {
98 return guards;
99 }
100
101 public List<SpecializationGroup> getChildren() {
102 return children;
103 }
104
105 public SpecializationData getSpecialization() {
106 return specialization;
107 }
108
109 private static SpecializationGroup combine(List<SpecializationGroup> groups) {
110 if (groups.isEmpty()) {
111 throw new IllegalArgumentException("empty combinations");
112 }
113 if (groups.size() == 1) {
114 return null;
115 }
116
117 List<String> assumptionMatches = new ArrayList<>();
118 List<TypeData> typeGuardsMatches = new ArrayList<>();
119 List<GuardData> guardMatches = new ArrayList<>();
120
121 SpecializationGroup first = groups.get(0);
122 List<SpecializationGroup> others = groups.subList(1, groups.size());
123
124 outer: for (String assumption : first.assumptions) {
125 for (SpecializationGroup other : others) {
126 if (!other.assumptions.contains(assumption)) {
127 // assumptions can be combined unordered
128 continue outer;
129 }
130 }
131 assumptionMatches.add(assumption);
132 }
133
134 int typeGuardIndex = 0;
135 outer: for (TypeData typeGuard : first.typeGuards) {
136 for (SpecializationGroup other : others) {
137 if (typeGuardIndex >= other.typeGuards.size()) {
138 break outer;
139 }
140
141 if (!other.typeGuards.get(typeGuardIndex).equals(typeGuard)) {
142 break outer;
143 }
144 }
145 typeGuardsMatches.add(typeGuard);
146 typeGuardIndex++;
147 }
148
149 outer: for (GuardData guard : first.guards) {
150 for (SpecializationGroup other : others) {
151 if (!other.guards.contains(guard)) {
152 // we must break here. One guard may depend on the other.
153 break outer;
154 }
155 }
156 guardMatches.add(guard);
157 }
158
159 if (assumptionMatches.isEmpty() && typeGuardsMatches.isEmpty() && guardMatches.isEmpty()) {
160 return null;
161 }
162
163 for (SpecializationGroup group : groups) {
164 group.assumptions.removeAll(assumptionMatches);
165 group.typeGuards.subList(0, typeGuardIndex).clear();
166 group.guards.removeAll(guardMatches);
167 }
168
169 List<SpecializationGroup> newChildren = new ArrayList<>(groups);
170 return new SpecializationGroup(newChildren, assumptionMatches, typeGuardsMatches, guardMatches);
171 }
172
173 public static List<SpecializationGroup> create(List<SpecializationData> specializations) {
174 List<SpecializationGroup> groups = new ArrayList<>();
175 for (SpecializationData specialization : specializations) {
176 groups.add(new SpecializationGroup(specialization));
177 }
178 return createCombinationalGroups(groups);
179 }
180
181 @Override
182 public String toString() {
183 return "SpecializationGroup [assumptions=" + assumptions + ", typeGuards=" + typeGuards + ", guards=" + guards + "]";
184 }
185
186 private static List<SpecializationGroup> createCombinationalGroups(List<SpecializationGroup> groups) {
187 if (groups.size() <= 1) {
188 return groups;
189 }
190 List<SpecializationGroup> newGroups = new ArrayList<>();
191
192 int i = 0;
193 for (i = 0; i < groups.size();) {
194 SpecializationGroup combined = null;
195 for (int j = groups.size(); j > i + 1; j--) {
196 combined = combine(groups.subList(i, j));
197 if (combined != null) {
198 break;
199 }
200 }
201 SpecializationGroup newGroup;
202 if (combined == null) {
203 newGroup = groups.get(i);
204 i++;
205 } else {
206 newGroup = combined;
207 List<SpecializationGroup> originalGroups = new ArrayList<>(combined.children);
208 combined.updateChildren(createCombinationalGroups(originalGroups));
209 i += originalGroups.size();
210 }
211
212 newGroups.add(newGroup);
213
214 }
215
216 return newGroups;
217 }
218
219 public SpecializationGroup getPreviousGroup() {
220 if (parent == null || parent.children.isEmpty()) {
221 return null;
222 }
223 int index = parent.children.indexOf(this);
224 if (index <= 0) {
225 return null;
226 }
227 return parent.children.get(index - 1);
228 }
229
230 public int getMaxSpecializationIndex() {
231 if (specialization != null) {
232 return specialization.getNode().getSpecializations().indexOf(specialization);
233 } else {
234 int max = Integer.MIN_VALUE;
235 for (SpecializationGroup childGroup : getChildren()) {
236 max = Math.max(max, childGroup.getMaxSpecializationIndex());
237 }
238 return max;
239 }
240 }
241 }