001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.ssa;
024
025import java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.lir.*;
031import com.oracle.graal.lir.LIRInstruction.OperandMode;
032import com.oracle.graal.lir.StandardOp.BlockEndOp;
033import com.oracle.graal.lir.StandardOp.JumpOp;
034import com.oracle.graal.lir.StandardOp.LabelOp;
035
036/**
037 * Utilities for working with Static-Single-Assignment LIR form.
038 *
039 * <h2>Representation of <code>PHI</code>s</h2>
040 *
041 * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
042 * as parallel copy that span across a control-flow edge.
043 *
044 * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
045 * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
046 * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the
047 * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
048 * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
049 *
050 * <h3>Example:</h3>
051 *
052 * <pre>
053 * B0 -> B1
054 *   ...
055 *   v0|i = ...
056 *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
057 * ________________________________________________
058 * 
059 * B2 -> B1
060 *   ...
061 *   v1|i = ...
062 *   v2|i = ...
063 *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
064 * ________________________________________________
065 * 
066 * B1 <- B0,B2
067 *   [v3|i, v4|i] = LABEL
068 *   ...
069 * </pre>
070 */
071public final class SSAUtil {
072
073    public interface PhiValueVisitor {
074        /**
075         * @param phiIn the incoming value at the merge block
076         * @param phiOut the outgoing value from the predecessor block
077         */
078        void visit(Value phiIn, Value phiOut);
079    }
080
081    /**
082     * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
083     * incoming value to the merge block.
084     */
085    public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
086        if (merge.getPredecessorCount() < 2) {
087            return;
088        }
089        assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors());
090        assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors());
091        assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge);
092
093        JumpOp jump = phiOut(lir, pred);
094        LabelOp label = phiIn(lir, merge);
095
096        assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize());
097
098        for (int i = 0; i < label.getIncomingSize(); i++) {
099            visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
100        }
101    }
102
103    private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
104        assert block.getSuccessorCount() == 1;
105        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
106        int index = instructions.size() - 1;
107        LIRInstruction op = instructions.get(index);
108        return (JumpOp) op;
109    }
110
111    public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
112        assert block.getSuccessorCount() == 1;
113        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
114        int index = instructions.size() - 1;
115        assert instructions.get(index) instanceof JumpOp;
116        return index;
117    }
118
119    private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
120        assert block.getPredecessorCount() > 1;
121        LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
122        return label;
123    }
124
125    public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
126        JumpOp jump = phiOut(lir, block);
127        jump.clearOutgoingValues();
128    }
129
130    public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
131        LabelOp label = phiIn(lir, block);
132        label.clearIncomingValues();
133    }
134
135    public static boolean verifySSAForm(LIR lir) {
136        return new SSAVerifier(lir).verify();
137    }
138
139    public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
140        assert merge.getPredecessorCount() > 1;
141        for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
142            forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
143                assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) ||
144                                (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isUnknownReference() && phiOut.getLIRKind().isValue());
145            });
146        }
147    }
148
149    public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
150        assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
151        assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
152
153        if (!label.isPhiIn()) {
154            return;
155        }
156        int idx = indexOfValue(label, targetValue);
157        assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
158
159        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
160            JumpOp jump = phiOut(lir, pred);
161            Value sourceValue = jump.getOutgoingValue(idx);
162            valueConsumer.visitValue(jump, sourceValue, null, null);
163        }
164
165    }
166
167    private static int indexOfValue(LabelOp label, Value value) {
168        for (int i = 0; i < label.getIncomingSize(); i++) {
169            if (label.getIncomingValue(i).equals(value)) {
170                return i;
171            }
172        }
173        return -1;
174    }
175
176}