Mercurial > hg > graal-compiler
comparison graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/parser/SpecializationGroup.java @ 16759:23415229349b
Truffle-DSL: new package structure.
author | Christian Humer <christian.humer@gmail.com> |
---|---|
date | Mon, 11 Aug 2014 15:57:14 +0200 |
parents | graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/SpecializationGroup.java@bd28da642eea |
children | 2db61eddcb97 |
comparison
equal
deleted
inserted
replaced
16758:c5f8eeb3cbc8 | 16759:23415229349b |
---|---|
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.*; | |
30 import com.oracle.truffle.dsl.processor.java.*; | |
31 import com.oracle.truffle.dsl.processor.model.*; | |
32 import com.oracle.truffle.dsl.processor.model.TemplateMethod.TypeSignature; | |
33 | |
34 /** | |
35 * Class creates groups of specializations to optimize the layout of generated executeAndSpecialize | |
36 * and generic execute methods. | |
37 */ | |
38 public final class SpecializationGroup { | |
39 | |
40 private final List<String> assumptions; | |
41 private final List<TypeGuard> typeGuards; | |
42 private final List<GuardExpression> guards; | |
43 | |
44 private final NodeData node; | |
45 private final SpecializationData specialization; | |
46 private final List<SpecializationGroup> children = new ArrayList<>(); | |
47 | |
48 private SpecializationGroup parent; | |
49 | |
50 private SpecializationGroup(SpecializationData data) { | |
51 this.node = data.getNode(); | |
52 this.assumptions = new ArrayList<>(); | |
53 this.typeGuards = new ArrayList<>(); | |
54 this.guards = new ArrayList<>(); | |
55 this.specialization = data; | |
56 | |
57 this.assumptions.addAll(data.getAssumptions()); | |
58 TypeSignature sig = data.getTypeSignature(); | |
59 for (int i = 1; i < sig.size(); i++) { | |
60 typeGuards.add(new TypeGuard(sig.get(i), i - 1)); | |
61 } | |
62 this.guards.addAll(data.getGuards()); | |
63 } | |
64 | |
65 public SpecializationGroup(List<SpecializationGroup> children, List<String> assumptionMatches, List<TypeGuard> typeGuardsMatches, List<GuardExpression> guardMatches) { | |
66 assert !children.isEmpty() : "children must not be empty"; | |
67 this.assumptions = assumptionMatches; | |
68 this.typeGuards = typeGuardsMatches; | |
69 this.guards = guardMatches; | |
70 this.node = children.get(0).node; | |
71 this.specialization = null; | |
72 updateChildren(children); | |
73 } | |
74 | |
75 public List<TypeGuard> getAllGuards() { | |
76 List<TypeGuard> collectedGuards = new ArrayList<>(); | |
77 collectedGuards.addAll(typeGuards); | |
78 if (parent != null) { | |
79 collectedGuards.addAll(parent.getAllGuards()); | |
80 } | |
81 return collectedGuards; | |
82 } | |
83 | |
84 public TypeGuard findTypeGuard(int signatureIndex) { | |
85 for (TypeGuard guard : typeGuards) { | |
86 if (guard.getSignatureIndex() == signatureIndex) { | |
87 return guard; | |
88 } | |
89 } | |
90 return null; | |
91 } | |
92 | |
93 public List<GuardExpression> findElseConnectableGuards() { | |
94 if (!getTypeGuards().isEmpty() || !getAssumptions().isEmpty()) { | |
95 return Collections.emptyList(); | |
96 } | |
97 | |
98 if (getGuards().isEmpty()) { | |
99 return Collections.emptyList(); | |
100 } | |
101 | |
102 List<GuardExpression> elseConnectableGuards = new ArrayList<>(); | |
103 int guardIndex = 0; | |
104 while (guardIndex < getGuards().size() && findNegatedGuardInPrevious(getGuards().get(guardIndex)) != null) { | |
105 elseConnectableGuards.add(getGuards().get(guardIndex)); | |
106 guardIndex++; | |
107 } | |
108 | |
109 return elseConnectableGuards; | |
110 } | |
111 | |
112 private GuardExpression findNegatedGuardInPrevious(GuardExpression guard) { | |
113 SpecializationGroup previous = this.getPreviousGroup(); | |
114 if (previous == null) { | |
115 return null; | |
116 } | |
117 List<GuardExpression> elseConnectedGuards = previous.findElseConnectableGuards(); | |
118 | |
119 if (previous == null || previous.getGuards().size() != elseConnectedGuards.size() + 1) { | |
120 return null; | |
121 } | |
122 | |
123 /* Guard is else branch can be connected in previous specialization. */ | |
124 if (elseConnectedGuards.contains(guard)) { | |
125 return guard; | |
126 } | |
127 | |
128 GuardExpression previousGuard = previous.getGuards().get(elseConnectedGuards.size()); | |
129 if (guard.getResolvedGuard().getMethod().equals(previousGuard.getResolvedGuard().getMethod()) && guard.isNegated() != previousGuard.isNegated()) { | |
130 return guard; | |
131 } | |
132 return null; | |
133 } | |
134 | |
135 private void updateChildren(List<SpecializationGroup> childs) { | |
136 if (!children.isEmpty()) { | |
137 children.clear(); | |
138 } | |
139 this.children.addAll(childs); | |
140 for (SpecializationGroup child : childs) { | |
141 child.parent = this; | |
142 } | |
143 } | |
144 | |
145 public SpecializationGroup getParent() { | |
146 return parent; | |
147 } | |
148 | |
149 public List<String> getAssumptions() { | |
150 return assumptions; | |
151 } | |
152 | |
153 public List<TypeGuard> getTypeGuards() { | |
154 return typeGuards; | |
155 } | |
156 | |
157 public List<GuardExpression> getGuards() { | |
158 return guards; | |
159 } | |
160 | |
161 public List<SpecializationGroup> getChildren() { | |
162 return children; | |
163 } | |
164 | |
165 public SpecializationData getSpecialization() { | |
166 return specialization; | |
167 } | |
168 | |
169 private static SpecializationGroup combine(List<SpecializationGroup> groups) { | |
170 if (groups.isEmpty()) { | |
171 throw new IllegalArgumentException("empty combinations"); | |
172 } | |
173 if (groups.size() == 1) { | |
174 return null; | |
175 } | |
176 | |
177 List<String> assumptionMatches = new ArrayList<>(); | |
178 List<TypeGuard> typeGuardsMatches = new ArrayList<>(); | |
179 List<GuardExpression> guardMatches = new ArrayList<>(); | |
180 | |
181 SpecializationGroup first = groups.get(0); | |
182 List<SpecializationGroup> others = groups.subList(1, groups.size()); | |
183 | |
184 outer: for (String assumption : first.assumptions) { | |
185 for (SpecializationGroup other : others) { | |
186 if (!other.assumptions.contains(assumption)) { | |
187 // assumptions can be combined unordered | |
188 continue outer; | |
189 } | |
190 } | |
191 assumptionMatches.add(assumption); | |
192 } | |
193 | |
194 outer: for (TypeGuard typeGuard : first.typeGuards) { | |
195 for (SpecializationGroup other : others) { | |
196 if (!other.typeGuards.contains(typeGuard)) { | |
197 // type guards can be combined unordered | |
198 continue outer; | |
199 } | |
200 } | |
201 typeGuardsMatches.add(typeGuard); | |
202 } | |
203 | |
204 outer: for (GuardExpression guard : first.guards) { | |
205 for (SpecializationGroup other : others) { | |
206 if (!other.guards.contains(guard)) { | |
207 // we must break here. One guard may depend on the other. | |
208 break outer; | |
209 } | |
210 } | |
211 guardMatches.add(guard); | |
212 } | |
213 | |
214 // check for guards for required type casts | |
215 for (Iterator<GuardExpression> iterator = guardMatches.iterator(); iterator.hasNext();) { | |
216 GuardExpression guardMatch = iterator.next(); | |
217 | |
218 int signatureIndex = 0; | |
219 for (Parameter parameter : guardMatch.getResolvedGuard().getParameters()) { | |
220 signatureIndex++; | |
221 if (!parameter.getSpecification().isSignature()) { | |
222 continue; | |
223 } | |
224 | |
225 TypeMirror guardType = parameter.getType(); | |
226 | |
227 // object guards can be safely moved up | |
228 if (ElementUtils.isObject(guardType)) { | |
229 continue; | |
230 } | |
231 | |
232 // generic guards can be safely moved up | |
233 SpecializationData generic = first.node.getGenericSpecialization(); | |
234 if (generic != null) { | |
235 Parameter genericParameter = generic.findParameter(parameter.getLocalName()); | |
236 if (genericParameter != null && ElementUtils.typeEquals(genericParameter.getType(), guardType)) { | |
237 continue; | |
238 } | |
239 } | |
240 | |
241 // signature index required for moving up guards | |
242 if (containsIndex(typeGuardsMatches, signatureIndex) || (first.getParent() != null && first.getParent().containsTypeGuardIndex(signatureIndex))) { | |
243 continue; | |
244 } | |
245 | |
246 iterator.remove(); | |
247 break; | |
248 } | |
249 } | |
250 | |
251 if (assumptionMatches.isEmpty() && typeGuardsMatches.isEmpty() && guardMatches.isEmpty()) { | |
252 return null; | |
253 } | |
254 | |
255 for (SpecializationGroup group : groups) { | |
256 group.assumptions.removeAll(assumptionMatches); | |
257 group.typeGuards.removeAll(typeGuardsMatches); | |
258 group.guards.removeAll(guardMatches); | |
259 } | |
260 | |
261 List<SpecializationGroup> newChildren = new ArrayList<>(groups); | |
262 return new SpecializationGroup(newChildren, assumptionMatches, typeGuardsMatches, guardMatches); | |
263 } | |
264 | |
265 private boolean containsTypeGuardIndex(int index) { | |
266 if (containsIndex(typeGuards, index)) { | |
267 return true; | |
268 } | |
269 if (parent != null) { | |
270 return parent.containsTypeGuardIndex(index); | |
271 } | |
272 return false; | |
273 } | |
274 | |
275 private static boolean containsIndex(List<TypeGuard> typeGuards, int signatureIndex) { | |
276 for (TypeGuard guard : typeGuards) { | |
277 if (guard.signatureIndex == signatureIndex) { | |
278 return true; | |
279 } | |
280 } | |
281 return false; | |
282 } | |
283 | |
284 public static SpecializationGroup create(SpecializationData specialization) { | |
285 return new SpecializationGroup(specialization); | |
286 } | |
287 | |
288 public static SpecializationGroup create(List<SpecializationData> specializations) { | |
289 List<SpecializationGroup> groups = new ArrayList<>(); | |
290 for (SpecializationData specialization : specializations) { | |
291 groups.add(new SpecializationGroup(specialization)); | |
292 } | |
293 return new SpecializationGroup(createCombinationalGroups(groups), Collections.<String> emptyList(), Collections.<TypeGuard> emptyList(), Collections.<GuardExpression> emptyList()); | |
294 } | |
295 | |
296 @Override | |
297 public String toString() { | |
298 return "SpecializationGroup [assumptions=" + assumptions + ", typeGuards=" + typeGuards + ", guards=" + guards + "]"; | |
299 } | |
300 | |
301 private static List<SpecializationGroup> createCombinationalGroups(List<SpecializationGroup> groups) { | |
302 if (groups.size() <= 1) { | |
303 return groups; | |
304 } | |
305 List<SpecializationGroup> newGroups = new ArrayList<>(); | |
306 | |
307 int i = 0; | |
308 for (i = 0; i < groups.size();) { | |
309 SpecializationGroup combined = null; | |
310 for (int j = groups.size(); j > i + 1; j--) { | |
311 combined = combine(groups.subList(i, j)); | |
312 if (combined != null) { | |
313 break; | |
314 } | |
315 } | |
316 SpecializationGroup newGroup; | |
317 if (combined == null) { | |
318 newGroup = groups.get(i); | |
319 i++; | |
320 } else { | |
321 newGroup = combined; | |
322 List<SpecializationGroup> originalGroups = new ArrayList<>(combined.children); | |
323 combined.updateChildren(createCombinationalGroups(originalGroups)); | |
324 i += originalGroups.size(); | |
325 } | |
326 | |
327 newGroups.add(newGroup); | |
328 | |
329 } | |
330 | |
331 return newGroups; | |
332 } | |
333 | |
334 public SpecializationGroup getPreviousGroup() { | |
335 if (parent == null || parent.children.isEmpty()) { | |
336 return null; | |
337 } | |
338 int index = parent.children.indexOf(this); | |
339 if (index <= 0) { | |
340 return null; | |
341 } | |
342 return parent.children.get(index - 1); | |
343 } | |
344 | |
345 public int getUncheckedSpecializationIndex() { | |
346 int groupMaxIndex = getMaxSpecializationIndex(); | |
347 | |
348 int genericIndex = node.getSpecializations().indexOf(node.getGenericSpecialization()); | |
349 if (groupMaxIndex >= genericIndex) { | |
350 // no minimum state check for an generic index | |
351 groupMaxIndex = -1; | |
352 } | |
353 | |
354 if (groupMaxIndex > -1) { | |
355 // no minimum state check if already checked by parent group | |
356 int parentMaxIndex = -1; | |
357 if (getParent() != null) { | |
358 parentMaxIndex = getParent().getMaxSpecializationIndex(); | |
359 } | |
360 if (groupMaxIndex == parentMaxIndex) { | |
361 groupMaxIndex = -1; | |
362 } | |
363 } | |
364 return groupMaxIndex; | |
365 } | |
366 | |
367 public int getMaxSpecializationIndex() { | |
368 if (specialization != null) { | |
369 return specialization.getNode().getSpecializations().indexOf(specialization); | |
370 } else { | |
371 int max = Integer.MIN_VALUE; | |
372 for (SpecializationGroup childGroup : getChildren()) { | |
373 max = Math.max(max, childGroup.getMaxSpecializationIndex()); | |
374 } | |
375 return max; | |
376 } | |
377 } | |
378 | |
379 public static final class TypeGuard { | |
380 | |
381 private final int signatureIndex; | |
382 private final TypeData type; | |
383 | |
384 public TypeGuard(TypeData type, int signatureIndex) { | |
385 this.type = type; | |
386 this.signatureIndex = signatureIndex; | |
387 } | |
388 | |
389 @Override | |
390 public int hashCode() { | |
391 final int prime = 31; | |
392 int result = 1; | |
393 result = prime * result + signatureIndex; | |
394 result = prime * result + type.hashCode(); | |
395 return result; | |
396 } | |
397 | |
398 @Override | |
399 public boolean equals(Object obj) { | |
400 if (this == obj) { | |
401 return true; | |
402 } else if (obj == null) { | |
403 return false; | |
404 } else if (getClass() != obj.getClass()) { | |
405 return false; | |
406 } | |
407 | |
408 TypeGuard other = (TypeGuard) obj; | |
409 if (signatureIndex != other.signatureIndex) { | |
410 return false; | |
411 } else if (!type.equals(other.type)) { | |
412 return false; | |
413 } | |
414 return true; | |
415 } | |
416 | |
417 public int getSignatureIndex() { | |
418 return signatureIndex; | |
419 } | |
420 | |
421 public TypeData getType() { | |
422 return type; | |
423 } | |
424 } | |
425 | |
426 public boolean isTypeGuardUsedInAnyGuardBelow(ProcessorContext context, SpecializationData source, TypeGuard typeGuard) { | |
427 | |
428 for (GuardExpression guard : guards) { | |
429 Parameter guardParameter = guard.getResolvedGuard().getSignatureParameter(typeGuard.getSignatureIndex()); | |
430 if (guardParameter == null) { | |
431 // guardParameters are optional | |
432 continue; | |
433 } | |
434 Parameter sourceParameter = source.getSignatureParameter(typeGuard.getSignatureIndex()); | |
435 if (sourceParameter.getTypeSystemType().needsCastTo(guardParameter.getType())) { | |
436 return true; | |
437 } | |
438 } | |
439 | |
440 for (SpecializationGroup group : getChildren()) { | |
441 if (group.isTypeGuardUsedInAnyGuardBelow(context, source, typeGuard)) { | |
442 return true; | |
443 } | |
444 } | |
445 | |
446 return false; | |
447 } | |
448 } |