Source code

001/*
002 * Copyright (c) 2011, 2012, 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.virtual.phases.ea;
024
025import java.util.*;
026
027import jdk.internal.jvmci.common.*;
028import com.oracle.graal.debug.*;
029
030import com.oracle.graal.compiler.common.*;
031import com.oracle.graal.compiler.common.cfg.*;
032import com.oracle.graal.compiler.common.type.*;
033import com.oracle.graal.graph.*;
034import com.oracle.graal.graph.iterators.*;
035import com.oracle.graal.nodes.*;
036import com.oracle.graal.nodes.cfg.*;
037import com.oracle.graal.nodes.extended.*;
038import com.oracle.graal.nodes.util.*;
039import com.oracle.graal.nodes.virtual.*;
040import com.oracle.graal.phases.graph.*;
041import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
042import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
043import com.oracle.graal.phases.schedule.*;
044
045public abstract class EffectsClosure<BlockT extends EffectsBlockState<BlockT>> extends EffectsPhase.Closure<BlockT> {
046
047    protected final ControlFlowGraph cfg;
048    protected final SchedulePhase schedule;
049
050    protected final NodeMap<ValueNode> aliases;
051    protected final BlockMap<GraphEffectList> blockEffects;
052    private final Map<Loop<Block>, GraphEffectList> loopMergeEffects = CollectionsFactory.newIdentityMap();
053    private final Map<LoopBeginNode, BlockT> loopEntryStates = Node.newIdentityMap();
054    private final NodeBitMap hasScalarReplacedInputs;
055
056    protected boolean changed;
057
058    public EffectsClosure(SchedulePhase schedule, ControlFlowGraph cfg) {
059        this.schedule = schedule;
060        this.cfg = cfg;
061        this.aliases = cfg.graph.createNodeMap();
062        this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap();
063        this.blockEffects = new BlockMap<>(cfg);
064        for (Block block : cfg.getBlocks()) {
065            blockEffects.put(block, new GraphEffectList());
066        }
067    }
068
069    @Override
070    public boolean hasChanged() {
071        return changed;
072    }
073
074    @Override
075    public final void applyEffects() {
076        final StructuredGraph graph = cfg.graph;
077        final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
078        final ArrayList<GraphEffectList> effectList = new ArrayList<>();
079        BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
080
081            @Override
082            protected Void getInitialState() {
083                return null;
084            }
085
086            private void apply(GraphEffectList effects) {
087                if (effects != null && !effects.isEmpty()) {
088                    effectList.add(effects);
089                }
090            }
091
092            @Override
093            protected Void processBlock(Block block, Void currentState) {
094                apply(blockEffects.get(block));
095                return currentState;
096            }
097
098            @Override
099            protected Void merge(Block merge, List<Void> states) {
100                return null;
101            }
102
103            @Override
104            protected Void cloneState(Void oldState) {
105                return oldState;
106            }
107
108            @Override
109            protected List<Void> processLoop(Loop<Block> loop, Void initialState) {
110                LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
111                apply(loopMergeEffects.get(loop));
112                return info.exitStates;
113            }
114        };
115        ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
116        for (GraphEffectList effects : effectList) {
117            Debug.log(" ==== effects");
118            effects.apply(graph, obsoleteNodes, false);
119        }
120        for (GraphEffectList effects : effectList) {
121            Debug.log(" ==== cfg kill effects");
122            effects.apply(graph, obsoleteNodes, true);
123        }
124        Debug.dump(4, graph, "After applying effects");
125        assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
126        for (Node node : obsoleteNodes) {
127            if (node.isAlive()) {
128                node.replaceAtUsages(null);
129                GraphUtil.killWithUnusedFloatingInputs(node);
130            }
131        }
132    }
133
134    @Override
135    protected BlockT processBlock(Block block, BlockT state) {
136        if (!state.isDead()) {
137            GraphEffectList effects = blockEffects.get(block);
138
139            if (block.getBeginNode().predecessor() instanceof IfNode) {
140                IfNode ifNode = (IfNode) block.getBeginNode().predecessor();
141                LogicNode condition = ifNode.condition();
142                Node alias = getScalarAlias(condition);
143                if (alias instanceof LogicConstantNode) {
144                    LogicConstantNode constant = (LogicConstantNode) alias;
145                    boolean deadBranch = constant.getValue() != (block.getBeginNode() == ifNode.trueSuccessor());
146
147                    if (deadBranch) {
148                        state.markAsDead();
149                        effects.killIfBranch(ifNode, constant.getValue());
150                        return state;
151                    }
152                }
153            }
154
155            VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
156
157            FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null;
158            Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
159            for (Node node : nodes) {
160                aliases.set(node, null);
161                if (node instanceof LoopExitNode) {
162                    LoopExitNode loopExit = (LoopExitNode) node;
163                    for (ProxyNode proxy : loopExit.proxies()) {
164                        changed |= processNode(proxy, state, effects, lastFixedNode) && isSignificantNode(node);
165                    }
166                    processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
167                }
168                changed |= processNode(node, state, effects, lastFixedNode) && isSignificantNode(node);
169                if (node instanceof FixedWithNextNode) {
170                    lastFixedNode = (FixedWithNextNode) node;
171                }
172                if (state.isDead()) {
173                    break;
174                }
175            }
176            VirtualUtil.trace(")\n    end state: %s\n", state);
177        }
178        return state;
179    }
180
181    private static boolean isSignificantNode(Node node) {
182        return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
183    }
184
185    /**
186     * Collects the effects of virtualizing the given node.
187     *
188     * @return {@code true} if the effects include removing the node, {@code false} otherwise.
189     */
190    protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
191
192    @Override
193    protected BlockT merge(Block merge, List<BlockT> states) {
194        assert blockEffects.get(merge).isEmpty();
195        MergeProcessor processor = createMergeProcessor(merge);
196        doMergeWithoutDead(processor, states);
197        processor.commitEnds(states);
198        blockEffects.get(merge).addAll(processor.mergeEffects);
199        blockEffects.get(merge).addAll(processor.afterMergeEffects);
200        return processor.newState;
201    }
202
203    @Override
204    protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
205        if (initialState.isDead()) {
206            ArrayList<BlockT> states = new ArrayList<>();
207            for (int i = 0; i < loop.getExits().size(); i++) {
208                states.add(initialState);
209            }
210            return states;
211        }
212
213        BlockT loopEntryState = initialState;
214        BlockT lastMergedState = cloneState(initialState);
215        processInitialLoopState(loop, lastMergedState);
216        MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader());
217        for (int iteration = 0; iteration < 10; iteration++) {
218            LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
219
220            List<BlockT> states = new ArrayList<>();
221            states.add(initialState);
222            states.addAll(info.endStates);
223            doMergeWithoutDead(mergeProcessor, states);
224
225            Debug.log("================== %s", loop.getHeader());
226            Debug.log("%s", mergeProcessor.newState);
227            Debug.log("===== vs.");
228            Debug.log("%s", lastMergedState);
229
230            if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
231                mergeProcessor.commitEnds(states);
232
233                blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
234                loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
235
236                assert info.exitStates.size() == loop.getExits().size();
237                loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
238                assert assertExitStatesNonEmpty(loop, info);
239
240                return info.exitStates;
241            } else {
242                lastMergedState = mergeProcessor.newState;
243                for (Block block : loop.getBlocks()) {
244                    blockEffects.get(block).clear();
245                }
246            }
247        }
248        throw new JVMCIError("too many iterations at %s", loop);
249    }
250
251    @SuppressWarnings("unused")
252    protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
253        // nothing to do
254    }
255
256    private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) {
257        int alive = 0;
258        for (BlockT state : states) {
259            if (!state.isDead()) {
260                alive++;
261            }
262        }
263        if (alive == 0) {
264            mergeProcessor.setNewState(states.get(0));
265        } else if (alive == states.size()) {
266            int[] stateIndexes = new int[states.size()];
267            for (int i = 0; i < stateIndexes.length; i++) {
268                stateIndexes[i] = i;
269            }
270            mergeProcessor.setStateIndexes(stateIndexes);
271            mergeProcessor.merge(states);
272        } else {
273            ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
274            int[] stateIndexes = new int[alive];
275            for (int i = 0; i < states.size(); i++) {
276                if (!states.get(i).isDead()) {
277                    stateIndexes[aliveStates.size()] = i;
278                    aliveStates.add(states.get(i));
279                }
280            }
281            mergeProcessor.setStateIndexes(stateIndexes);
282            mergeProcessor.merge(aliveStates);
283        }
284    }
285
286    private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
287        for (int i = 0; i < loop.getExits().size(); i++) {
288            assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader();
289        }
290        return true;
291    }
292
293    protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
294
295    protected abstract MergeProcessor createMergeProcessor(Block merge);
296
297    protected class MergeProcessor {
298
299        private final Block mergeBlock;
300        private final AbstractMergeNode merge;
301
302        protected final GraphEffectList mergeEffects;
303        protected final GraphEffectList afterMergeEffects;
304
305        private int[] stateIndexes;
306        protected BlockT newState;
307
308        public MergeProcessor(Block mergeBlock) {
309            this.mergeBlock = mergeBlock;
310            this.merge = (AbstractMergeNode) mergeBlock.getBeginNode();
311            this.mergeEffects = new GraphEffectList();
312            this.afterMergeEffects = new GraphEffectList();
313        }
314
315        /**
316         * @param states the states that should be merged.
317         */
318        protected void merge(List<BlockT> states) {
319            setNewState(getInitialState());
320        }
321
322        private void setNewState(BlockT state) {
323            newState = state;
324            mergeEffects.clear();
325            afterMergeEffects.clear();
326        }
327
328        private void setStateIndexes(int[] stateIndexes) {
329            this.stateIndexes = stateIndexes;
330        }
331
332        @SuppressWarnings("unused")
333        protected void commitEnds(List<BlockT> states) {
334        }
335
336        protected final Block getPredecessor(int index) {
337            return mergeBlock.getPredecessors().get(stateIndexes[index]);
338        }
339
340        protected final NodeIterable<PhiNode> getPhis() {
341            return merge.phis();
342        }
343
344        protected final ValueNode getPhiValueAt(PhiNode phi, int index) {
345            return phi.valueAt(stateIndexes[index]);
346        }
347
348        protected final ValuePhiNode createValuePhi(Stamp stamp) {
349            return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]);
350        }
351
352        protected final void setPhiInput(PhiNode phi, int index, ValueNode value) {
353            afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value);
354        }
355
356        protected final int getStateIndex(int i) {
357            return stateIndexes[i];
358        }
359
360        protected final StructuredGraph graph() {
361            return merge.graph();
362        }
363
364        @Override
365        public String toString() {
366            return "MergeProcessor@" + merge;
367        }
368    }
369
370    public void addScalarAlias(ValueNode node, ValueNode alias) {
371        assert !(alias instanceof VirtualObjectNode);
372        aliases.set(node, alias);
373        for (Node usage : node.usages()) {
374            if (!hasScalarReplacedInputs.isNew(usage)) {
375                hasScalarReplacedInputs.mark(usage);
376            }
377        }
378    }
379
380    protected final boolean hasScalarReplacedInputs(Node node) {
381        return hasScalarReplacedInputs.isMarked(node);
382    }
383
384    public ValueNode getScalarAlias(ValueNode node) {
385        assert !(node instanceof VirtualObjectNode);
386        if (node == null || !node.isAlive() || aliases.isNew(node)) {
387            return node;
388        }
389        ValueNode result = aliases.get(node);
390        return (result == null || result instanceof VirtualObjectNode) ? node : result;
391    }
392}