Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java @ 21226:2f2fac20c446

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LIRVerifier: verify PHIs.
author Josef Eisl <josef.eisl@jku.at>
date Thu, 23 Apr 2015 11:30:36 +0200
parents f226f63af996
children f85711ac631c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21220
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
1 /*
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
2 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
4 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
7 * published by the Free Software Foundation.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
8 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
13 * accompanied this code).
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
14 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
18 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
21 * questions.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
22 */
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
23 package com.oracle.graal.lir.ssa;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
24
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
25 import java.util.*;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
26
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
27 import com.oracle.graal.api.meta.*;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
28 import com.oracle.graal.compiler.common.cfg.*;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
29 import com.oracle.graal.lir.*;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
30 import com.oracle.graal.lir.StandardOp.BlockEndOp;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
31 import com.oracle.graal.lir.StandardOp.JumpOp;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
32 import com.oracle.graal.lir.StandardOp.LabelOp;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
33
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
34 /**
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
35 * Utilities for working with Static-Single-Assignment LIR form.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
36 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
37 * <h2>Representation of <code>PHI</code>s</h2>
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
38 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
39 * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
40 * as parallel copy that span across a control-flow edge.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
41 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
42 * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
43 * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
44 * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
45 * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
46 * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
47 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
48 * <h3>Example:</h3>
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
49 *
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
50 * <pre>
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
51 * B0 -> B1
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
52 * ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
53 * v0|i = ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
54 * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
55 * ________________________________________________
21222
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
56 *
21220
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
57 * B2 -> B1
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
58 * ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
59 * v1|i = ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
60 * v2|i = ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
61 * JUMP ~[v1|i, v2|i] destination: B2 -> B1
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
62 * ________________________________________________
21222
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
63 *
21220
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
64 * B1 <- B0,B2
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
65 * [v3|i, v4|i] = LABEL
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
66 * ...
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
67 * </pre>
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
68 */
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
69 public final class SSAUtils {
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
70
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
71 public interface PhiValueVisitor {
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
72 /**
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
73 * @param phiIn the incoming value at the merge block
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
74 * @param phiOut the outgoing value from the predecessor block
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
75 */
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
76 void visit(Value phiIn, Value phiOut);
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
77 }
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
78
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
79 /**
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
80 * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
81 * incoming value to the merge block.
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
82 */
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
83 public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
84 if (merge.getPredecessorCount() < 2) {
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
85 return;
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
86 }
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
87 assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors());
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
88 assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors());
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
89 assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge);
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
90
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
91 List<LIRInstruction> instructions = lir.getLIRforBlock(pred);
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
92 JumpOp jump = (JumpOp) instructions.get(instructions.size() - 1);
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
93 LabelOp label = (LabelOp) lir.getLIRforBlock(merge).get(0);
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
94
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
95 assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize());
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
96
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
97 for (int i = 0; i < label.getIncomingSize(); i++) {
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
98 visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
99 }
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
100 }
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
101
21222
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
102 public static boolean verifySSAForm(LIR lir) {
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
103 return new SSAVerifier(lir).verify();
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
104 }
f226f63af996 Add SSAVerifier.
Josef Eisl <josef.eisl@jku.at>
parents: 21220
diff changeset
105
21226
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
106 public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
107 assert merge.getPredecessorCount() > 1;
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
108 for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
109 forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
110 assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) ||
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
111 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isDerivedReference() && phiOut.getLIRKind().isValue());
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
112 });
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
113 }
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
114 }
2f2fac20c446 LIRVerifier: verify PHIs.
Josef Eisl <josef.eisl@jku.at>
parents: 21222
diff changeset
115
21220
e02ae54e6a44 Introduce c.o.g.lir.ssa.SSAUtils.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
116 }