Source code

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.ssi;
024
025import static com.oracle.graal.lir.LIRValueUtil.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.meta.*;
031
032import com.oracle.graal.compiler.common.cfg.*;
033import com.oracle.graal.debug.*;
034import com.oracle.graal.lir.*;
035import com.oracle.graal.lir.LIRInstruction.OperandMode;
036import com.oracle.graal.lir.StandardOp.BlockEndOp;
037import com.oracle.graal.lir.StandardOp.LabelOp;
038import com.oracle.graal.lir.gen.*;
039import com.oracle.graal.lir.util.*;
040
041public final class SSIBlockValueMapImpl implements BlockValueMap {
042
043    private static final class BlockData {
044
045        /** Mapping from value to index into {@link #incoming}. */
046        private final ValueMap<Value, Integer> valueIndexMap;
047        private final ArrayList<Value> incoming;
048        private final ArrayList<Value> outgoing;
049
050        private BlockData(int initialVariableCapacity, int initialStackSlotCapacity) {
051            valueIndexMap = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity);
052            incoming = new ArrayList<>();
053            outgoing = new ArrayList<>();
054        }
055
056        public Integer getIndex(Value operand) {
057            return valueIndexMap.get(operand);
058        }
059
060        public Value getIncoming(int index) {
061            return incoming.get(index);
062        }
063
064        public void setIncoming(int index, Value value) {
065            incoming.set(index, value);
066        }
067
068        public int addIncoming(Value operand) {
069            assert isVariable(operand) || isVirtualStackSlot(operand) : "Not a variable or vstack: " + operand;
070            int index = incoming.size();
071            incoming.add(Value.ILLEGAL);
072            valueIndexMap.put(operand, index);
073            return index;
074        }
075
076        public boolean contains(Value operand) {
077            return getIndex(operand) != null;
078        }
079
080        public int addOutgoing(Value operand) {
081            int index = outgoing.size();
082            outgoing.add(operand);
083            return index;
084        }
085
086    }
087
088    /** Mapping from value to definition block. */
089    private final ValueMap<Value, AbstractBlockBase<?>> valueToDefBlock;
090    private final BlockMap<BlockData> blockData;
091    private final int initialVariableCapacity;
092    private final int initialStackSlotCapacity;
093
094    public SSIBlockValueMapImpl(AbstractControlFlowGraph<?> cfg, int initialVariableCapacity, int initialStackSlotCapacity) {
095        this.initialVariableCapacity = initialVariableCapacity;
096        this.initialStackSlotCapacity = initialStackSlotCapacity;
097        valueToDefBlock = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity);
098        blockData = new BlockMap<>(cfg);
099    }
100
101    @Override
102    public void accessOperand(Value operand, AbstractBlockBase<?> block) {
103        assert block != null : "block is null";
104        if (operand instanceof CompositeValue) {
105            ((CompositeValue) operand).forEachComponent(null, OperandMode.USE, (op, value, mode, flag) -> {
106                accessOperand(value, block);
107                return value;
108            });
109        } else if (processValue(operand)) {
110            AbstractBlockBase<?> defBlock = getDefinitionBlock(operand);
111            assert defBlock != null : "Value is not defined: " + operand;
112            assert AbstractControlFlowGraph.dominates(defBlock, block) : "Block " + defBlock + " does not dominate " + block;
113            accessRecursive(operand, defBlock, block);
114        }
115    }
116
117    @Override
118    public void defineOperand(Value operand, AbstractBlockBase<?> block) {
119        assert block != null : "block is null";
120        if (processValue(operand)) {
121            AbstractBlockBase<?> defBlock = getDefinitionBlock(operand);
122            if (defBlock == null) {
123                setDefinitionBlock(operand, block);
124            } else {
125                /*
126                 * Redefinition: this can happen for nodes that do not produce a new value but proxy
127                 * another one (PiNode, reinterpret).
128                 */
129                assert AbstractControlFlowGraph.dominates(defBlock, block) : String.format("Definition of %s in %s does not dominate the redefinition %s", operand, defBlock, block);
130            }
131        }
132    }
133
134    private static boolean processValue(Value operand) {
135        return isVariable(operand) || isVirtualStackSlot(operand);
136    }
137
138    // setter getter for internal data structures
139
140    private AbstractBlockBase<?> getDefinitionBlock(Value operand) {
141        return valueToDefBlock.get(operand);
142    }
143
144    private void setDefinitionBlock(Value operand, AbstractBlockBase<?> block) {
145        valueToDefBlock.put(operand, block);
146    }
147
148    private BlockData getOrInit(AbstractBlockBase<?> block) {
149        BlockData data = blockData.get(block);
150        if (data == null) {
151            data = new BlockData(initialVariableCapacity, initialStackSlotCapacity);
152            blockData.put(block, data);
153        }
154        return data;
155    }
156
157    // implementation
158
159    private void accessRecursive(Value operand, AbstractBlockBase<?> defBlock, AbstractBlockBase<?> block) {
160        Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
161        worklist.add(block);
162
163        while (!worklist.isEmpty()) {
164            accessRecursive(operand, defBlock, worklist.pollLast(), worklist);
165        }
166    }
167
168    private void accessRecursive(Value operand, AbstractBlockBase<?> defBlock, AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) {
169        try (Indent indent = Debug.logAndIndent("get operand %s in block %s", operand, block)) {
170            if (block.equals(defBlock)) {
171                Debug.log("found definition!");
172                return;
173            }
174            BlockData data = getOrInit(block);
175            Integer index = data.getIndex(operand);
176            if (index != null) {
177                // value is live at block begin but might not be initialized
178                Value in = data.getIncoming(index);
179                if (Value.ILLEGAL.equals(in)) {
180                    data.setIncoming(index, operand);
181                    Debug.log("uninitialized incoming value -> initialize!");
182                } else {
183                    Debug.log("incoming value already initialized!");
184                }
185                return;
186            }
187
188            // the value is not yet live a current block
189            int idx = addLiveValueToBlock(operand, block);
190            data.setIncoming(idx, operand);
191
192            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
193                worklist.addLast(pred);
194            }
195        }
196    }
197
198    private int addLiveValueToBlock(Value operand, AbstractBlockBase<?> block) {
199        try (Indent indent = Debug.logAndIndent("add incoming value!")) {
200            int index = -1;
201            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
202                try (Indent indent1 = Debug.logAndIndent("Add outgoing operand to %s", pred)) {
203                    BlockData predData = getOrInit(pred);
204                    int predIndex = predData.addOutgoing(operand);
205
206                    if (index == -1) {
207                        index = predIndex;
208                    } else {
209                        assert predIndex == index;
210                    }
211
212                    for (AbstractBlockBase<?> succ : pred.getSuccessors()) {
213                        Debug.log("Add incoming operand to %s", succ);
214                        BlockData succData = getOrInit(succ);
215                        if (!succData.contains(operand)) {
216                            int succIndex = succData.addIncoming(operand);
217                            assert succIndex == predIndex;
218                        }
219                    }
220                }
221            }
222            Debug.log("new index: %d", index);
223            return index;
224        }
225    }
226
227    // finish
228
229    public void finish(LIRGeneratorTool gen) {
230        Debug.dump(gen.getResult().getLIR(), "Before SSI operands");
231        AbstractControlFlowGraph<?> cfg = gen.getResult().getLIR().getControlFlowGraph();
232        for (AbstractBlockBase<?> block : cfg.getBlocks()) {
233            // set label
234            BlockData data = blockData.get(block);
235            if (data != null) {
236                if (data.incoming != null && data.incoming.size() > 0) {
237                    LabelOp label = getLabel(gen, block);
238                    label.addIncomingValues(data.incoming.toArray(new Value[data.incoming.size()]));
239                }
240                // set block end
241                if (data.outgoing != null && data.outgoing.size() > 0) {
242                    BlockEndOp blockEndOp = getBlockEnd(gen, block);
243                    blockEndOp.addOutgoingValues(data.outgoing.toArray(new Value[data.outgoing.size()]));
244                }
245            }
246        }
247    }
248
249    private static List<LIRInstruction> getLIRforBlock(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
250        return gen.getResult().getLIR().getLIRforBlock(block);
251    }
252
253    private static LabelOp getLabel(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
254        return (LabelOp) getLIRforBlock(gen, block).get(0);
255    }
256
257    private static BlockEndOp getBlockEnd(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
258        List<LIRInstruction> instructions = getLIRforBlock(gen, block);
259        return (BlockEndOp) instructions.get(instructions.size() - 1);
260    }
261}