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 java.util.*;
026
027import jdk.internal.jvmci.code.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.debug.*;
031import com.oracle.graal.lir.*;
032import com.oracle.graal.lir.LIRInstruction.OperandFlag;
033import com.oracle.graal.lir.framemap.*;
034import com.oracle.graal.lir.gen.*;
035import com.oracle.graal.lir.phases.*;
036import com.oracle.graal.lir.ssa.*;
037
038public final class SSIConstructionPhase extends PreAllocationOptimizationPhase {
039
040    @Override
041    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) {
042        assert SSAUtil.verifySSAForm(lirGenRes.getLIR());
043        LIR lir = lirGenRes.getLIR();
044        new SSIBuilder(lir, lirGenRes.getFrameMapBuilder()).build(lirGen);
045    }
046
047    private static final class SSIBuilder {
048        private final SSIBlockValueMapImpl valueMap;
049        private final LIR lir;
050        private final BitSet processed;
051
052        private SSIBuilder(LIR lir, FrameMapBuilder frameMapBuilder) {
053            this.lir = lir;
054            valueMap = new SSIBlockValueMapImpl(lir.getControlFlowGraph(), lir.nextVariable(), ((FrameMapBuilderTool) frameMapBuilder).getNumberOfStackSlots());
055            processed = new BitSet(lir.getControlFlowGraph().getBlocks().size());
056        }
057
058        private void build(LIRGeneratorTool lirGen) {
059            Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(lir.getControlFlowGraph().getBlocks());
060            while (!worklist.isEmpty()) {
061                AbstractBlockBase<?> block = worklist.poll();
062                if (!processed.get(block.getId())) {
063                    try (Indent indent = Debug.logAndIndent("Try processing Block %s", block)) {
064                        // check predecessors
065                        boolean reschedule = false;
066                        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
067                            if (!processed.get(pred.getId()) && !isLoopBackEdge(pred, block)) {
068                                Debug.log("Schedule predecessor: %s", pred);
069                                worklist.addLast(pred);
070                                reschedule = true;
071                            }
072                        }
073                        if (reschedule) {
074                            Debug.log("Reschedule block %s", block);
075                            worklist.addLast(block);
076                        } else {
077                            processBlock(block);
078                        }
079                    }
080                }
081            }
082            valueMap.finish(lirGen);
083        }
084
085        public void processBlock(AbstractBlockBase<?> block) {
086            assert !processed.get(block.getId()) : "Block already processed " + block;
087            try (Indent indent = Debug.logAndIndent("Process Block %s", block)) {
088                // track values
089                ValueConsumer useConsumer = (value, mode, flags) -> {
090                    if (flags.contains(OperandFlag.UNINITIALIZED)) {
091                        AbstractBlockBase<?> startBlock = lir.getControlFlowGraph().getStartBlock();
092                        Debug.log("Set definition of %s in block %s", value, startBlock);
093                        valueMap.defineOperand(value, startBlock);
094                    } else {
095                        Debug.log("Access %s in block %s", value, block);
096                        valueMap.accessOperand(value, block);
097                    }
098                };
099                ValueConsumer defConsumer = (value, mode, flags) -> {
100                    Debug.log("Set definition of %s in block %s", value, block);
101                    valueMap.defineOperand(value, block);
102                };
103                for (LIRInstruction op : lir.getLIRforBlock(block)) {
104                    // use
105                    op.visitEachInput(useConsumer);
106                    op.visitEachAlive(useConsumer);
107                    op.visitEachState(useConsumer);
108                    // def
109                    op.visitEachTemp(defConsumer);
110                    op.visitEachOutput(defConsumer);
111                }
112                processed.set(block.getId());
113            }
114        }
115
116        private static boolean isLoopBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
117            return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop());
118        }
119    }
120}