Mercurial > hg > truffle

comparison truffle/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/parser/SpecializationGroup.java @ 21951:9c8c0937da41

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moving all sources into truffle subdirectory
author Jaroslav Tulach <jaroslav.tulach@oracle.com>
date Wed, 17 Jun 2015 10:58:08 +0200
parents graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/parser/SpecializationGroup.java@18c0f02fa4d2
children dc83cc1f94f2
comparison
equal deleted inserted replaced
21950:2a5011c7e641 21951:9c8c0937da41
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.parser;
24
25 import java.util.*;
26
27 import javax.lang.model.type.*;
28
29 import com.oracle.truffle.dsl.processor.model.*;
30 import com.oracle.truffle.dsl.processor.model.TemplateMethod.TypeSignature;
31
32 /**
33 * Class creates groups of specializations to optimize the layout of generated executeAndSpecialize
34 * and generic execute methods.
35 */
36 public final class SpecializationGroup {
37
38 private final List<TypeGuard> typeGuards;
39 private final List<GuardExpression> guards;
40
41 private final NodeData node;
42 private final SpecializationData specialization;
43 private final List<SpecializationGroup> children = new ArrayList<>();
44
45 private SpecializationGroup parent;
46
47 private SpecializationGroup(SpecializationData data) {
48 this.node = data.getNode();
49 this.typeGuards = new ArrayList<>();
50 this.guards = new ArrayList<>();
51 this.specialization = data;
52
53 TypeSignature sig = data.getTypeSignature();
54 for (int i = 1; i < sig.size(); i++) {
55 typeGuards.add(new TypeGuard(sig.get(i), i - 1));
56 }
57 this.guards.addAll(data.getGuards());
58 }
59
60 public SpecializationGroup(List<SpecializationGroup> children, List<TypeGuard> typeGuardsMatches, List<GuardExpression> guardMatches) {
61 assert !children.isEmpty() : "children must not be empty";
62 this.typeGuards = typeGuardsMatches;
63 this.guards = guardMatches;
64 this.node = children.get(0).node;
65 this.specialization = null;
66 updateChildren(children);
67 }
68
69 public List<TypeGuard> getAllGuards() {
70 List<TypeGuard> collectedGuards = new ArrayList<>();
71 collectedGuards.addAll(typeGuards);
72 if (parent != null) {
73 collectedGuards.addAll(parent.getAllGuards());
74 }
75 return collectedGuards;
76 }
77
78 public List<GuardExpression> findElseConnectableGuards() {
79 if (!getTypeGuards().isEmpty()) {
80 return Collections.emptyList();
81 }
82
83 if (getGuards().isEmpty()) {
84 return Collections.emptyList();
85 }
86
87 List<GuardExpression> elseConnectableGuards = new ArrayList<>();
88 int guardIndex = 0;
89 while (guardIndex < getGuards().size() && findNegatedGuardInPrevious(getGuards().get(guardIndex)) != null) {
90 elseConnectableGuards.add(getGuards().get(guardIndex));
91 guardIndex++;
92 }
93
94 return elseConnectableGuards;
95 }
96
97 private GuardExpression findNegatedGuardInPrevious(GuardExpression guard) {
98 SpecializationGroup previous = this.getPreviousGroup();
99 if (previous == null) {
100 return null;
101 }
102 List<GuardExpression> elseConnectedGuards = previous.findElseConnectableGuards();
103
104 if (previous == null || previous.getGuards().size() != elseConnectedGuards.size() + 1) {
105 return null;
106 }
107
108 /* Guard is else branch can be connected in previous specialization. */
109 if (elseConnectedGuards.contains(guard)) {
110 return guard;
111 }
112
113 GuardExpression previousGuard = previous.getGuards().get(elseConnectedGuards.size());
114 if (guard.equalsNegated(previousGuard)) {
115 return guard;
116 }
117 return null;
118 }
119
120 private void updateChildren(List<SpecializationGroup> childs) {
121 if (!children.isEmpty()) {
122 children.clear();
123 }
124 this.children.addAll(childs);
125 for (SpecializationGroup child : childs) {
126 child.parent = this;
127 }
128 }
129
130 public SpecializationGroup getParent() {
131 return parent;
132 }
133
134 public List<TypeGuard> getTypeGuards() {
135 return typeGuards;
136 }
137
138 public List<GuardExpression> getGuards() {
139 return guards;
140 }
141
142 public List<SpecializationGroup> getChildren() {
143 return children;
144 }
145
146 public SpecializationData getSpecialization() {
147 return specialization;
148 }
149
150 private static SpecializationGroup combine(List<SpecializationGroup> groups) {
151 if (groups.isEmpty()) {
152 throw new IllegalArgumentException("empty combinations");
153 }
154 if (groups.size() == 1) {
155 return null;
156 }
157
158 List<TypeGuard> typeGuardsMatches = new ArrayList<>();
159 List<GuardExpression> guardMatches = new ArrayList<>();
160
161 SpecializationGroup first = groups.get(0);
162 List<SpecializationGroup> others = groups.subList(1, groups.size());
163
164 outer: for (TypeGuard typeGuard : first.typeGuards) {
165 for (SpecializationGroup other : others) {
166 if (!other.typeGuards.contains(typeGuard)) {
167 // type guards can be combined unordered
168 continue outer;
169 }
170 }
171 typeGuardsMatches.add(typeGuard);
172 }
173
174 outer: for (GuardExpression guard : first.guards) {
175 for (SpecializationGroup other : others) {
176 if (!other.guards.contains(guard)) {
177 // we must break here. One guard may depend on the other.
178 break outer;
179 }
180 }
181 guardMatches.add(guard);
182 }
183
184 // check for guards for required type casts
185 for (Iterator<GuardExpression> iterator = guardMatches.iterator(); iterator.hasNext();) {
186 GuardExpression guardMatch = iterator.next();
187 if (!guardMatch.getExpression().findBoundVariables().isEmpty()) {
188 iterator.remove();
189 }
190 // TODO we need to be smarter here with bound parameters.
191 }
192
193 if (typeGuardsMatches.isEmpty() && guardMatches.isEmpty()) {
194 return null;
195 }
196
197 for (SpecializationGroup group : groups) {
198 group.typeGuards.removeAll(typeGuardsMatches);
199 group.guards.removeAll(guardMatches);
200 }
201
202 List<SpecializationGroup> newChildren = new ArrayList<>(groups);
203 return new SpecializationGroup(newChildren, typeGuardsMatches, guardMatches);
204 }
205
206 public static SpecializationGroup create(SpecializationData specialization) {
207 return new SpecializationGroup(specialization);
208 }
209
210 public static SpecializationGroup create(List<SpecializationData> specializations) {
211 List<SpecializationGroup> groups = new ArrayList<>();
212 for (SpecializationData specialization : specializations) {
213 groups.add(new SpecializationGroup(specialization));
214 }
215 return new SpecializationGroup(createCombinationalGroups(groups), Collections.<TypeGuard> emptyList(), Collections.<GuardExpression> emptyList());
216 }
217
218 @Override
219 public String toString() {
220 return "SpecializationGroup [typeGuards=" + typeGuards + ", guards=" + guards + "]";
221 }
222
223 private static List<SpecializationGroup> createCombinationalGroups(List<SpecializationGroup> groups) {
224 if (groups.size() <= 1) {
225 return groups;
226 }
227 List<SpecializationGroup> newGroups = new ArrayList<>();
228
229 int i = 0;
230 for (i = 0; i < groups.size();) {
231 SpecializationGroup combined = null;
232 for (int j = groups.size(); j > i + 1; j--) {
233 combined = combine(groups.subList(i, j));
234 if (combined != null) {
235 break;
236 }
237 }
238 SpecializationGroup newGroup;
239 if (combined == null) {
240 newGroup = groups.get(i);
241 i++;
242 } else {
243 newGroup = combined;
244 List<SpecializationGroup> originalGroups = new ArrayList<>(combined.children);
245 combined.updateChildren(createCombinationalGroups(originalGroups));
246 i += originalGroups.size();
247 }
248
249 newGroups.add(newGroup);
250
251 }
252
253 return newGroups;
254 }
255
256 public SpecializationGroup getPreviousGroup() {
257 if (parent == null || parent.children.isEmpty()) {
258 return null;
259 }
260 int index = parent.children.indexOf(this);
261 if (index <= 0) {
262 return null;
263 }
264 return parent.children.get(index - 1);
265 }
266
267 public int getUncheckedSpecializationIndex() {
268 int groupMaxIndex = getMaxSpecializationIndex();
269
270 int genericIndex = node.getSpecializations().indexOf(node.getGenericSpecialization());
271 if (groupMaxIndex >= genericIndex) {
272 // no minimum state check for an generic index
273 groupMaxIndex = -1;
274 }
275
276 if (groupMaxIndex > -1) {
277 // no minimum state check if already checked by parent group
278 int parentMaxIndex = -1;
279 if (getParent() != null) {
280 parentMaxIndex = getParent().getMaxSpecializationIndex();
281 }
282 if (groupMaxIndex == parentMaxIndex) {
283 groupMaxIndex = -1;
284 }
285 }
286 return groupMaxIndex;
287 }
288
289 public int getMaxSpecializationIndex() {
290 if (specialization != null) {
291 return specialization.getNode().getSpecializations().indexOf(specialization);
292 } else {
293 int max = Integer.MIN_VALUE;
294 for (SpecializationGroup childGroup : getChildren()) {
295 max = Math.max(max, childGroup.getMaxSpecializationIndex());
296 }
297 return max;
298 }
299 }
300
301 public static final class TypeGuard {
302
303 private final int signatureIndex;
304 private final TypeMirror type;
305
306 public TypeGuard(TypeMirror type, int signatureIndex) {
307 this.type = type;
308 this.signatureIndex = signatureIndex;
309 }
310
311 @Override
312 public int hashCode() {
313 final int prime = 31;
314 int result = 1;
315 result = prime * result + signatureIndex;
316 result = prime * result + type.hashCode();
317 return result;
318 }
319
320 @Override
321 public boolean equals(Object obj) {
322 if (this == obj) {
323 return true;
324 } else if (obj == null) {
325 return false;
326 } else if (getClass() != obj.getClass()) {
327 return false;
328 }
329
330 TypeGuard other = (TypeGuard) obj;
331 if (signatureIndex != other.signatureIndex) {
332 return false;
333 } else if (!type.equals(other.type)) {
334 return false;
335 }
336 return true;
337 }
338
339 public int getSignatureIndex() {
340 return signatureIndex;
341 }
342
343 public TypeMirror getType() {
344 return type;
345 }
346 }
347
348 public SpecializationGroup getPrevious() {
349 if (getParent() == null) {
350 return null;
351 }
352
353 List<SpecializationGroup> parentChildren = getParent().getChildren();
354 int index = parentChildren.indexOf(this);
355 if (index <= 0) {
356 return null;
357 }
358 return parentChildren.get(index - 1);
359 }
360 }