001/*
002 * Copyright (c) 2014, 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.dfa;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030
031import com.oracle.graal.debug.*;
032
033import jdk.internal.jvmci.meta.*;
034
035import com.oracle.graal.compiler.common.cfg.*;
036import com.oracle.graal.lir.*;
037import com.oracle.graal.lir.LIRInstruction.OperandFlag;
038import com.oracle.graal.lir.LIRInstruction.OperandMode;
039import com.oracle.graal.lir.framemap.*;
040import com.oracle.graal.lir.util.*;
041
042public abstract class LocationMarker<T extends AbstractBlockBase<T>, S extends ValueSet<S>> {
043
044    private final LIR lir;
045    private final BlockMap<S> liveInMap;
046    private final BlockMap<S> liveOutMap;
047
048    protected final FrameMap frameMap;
049
050    protected LocationMarker(LIR lir, FrameMap frameMap) {
051        this.lir = lir;
052        this.frameMap = frameMap;
053        liveInMap = new BlockMap<>(lir.getControlFlowGraph());
054        liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
055    }
056
057    protected abstract S newLiveValueSet();
058
059    protected abstract boolean shouldProcessValue(Value operand);
060
061    protected abstract void processState(LIRInstruction op, LIRFrameState info, S values);
062
063    @SuppressWarnings("unchecked")
064    void build() {
065        UniqueWorkList<T> worklist = new UniqueWorkList<>(lir.getControlFlowGraph().getBlocks().size());
066        for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
067            worklist.add((T) lir.getControlFlowGraph().getBlocks().get(i));
068        }
069        for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
070            liveInMap.put(block, newLiveValueSet());
071        }
072        while (!worklist.isEmpty()) {
073            AbstractBlockBase<T> block = worklist.poll();
074            processBlock(block, worklist);
075        }
076    }
077
078    /**
079     * Merge outSet with in-set of successors.
080     */
081    private boolean updateOutBlock(AbstractBlockBase<T> block) {
082        S union = newLiveValueSet();
083        for (T succ : block.getSuccessors()) {
084            union.putAll(liveInMap.get(succ));
085        }
086        S outSet = liveOutMap.get(block);
087        // check if changed
088        if (outSet == null || !union.equals(outSet)) {
089            liveOutMap.put(block, union);
090            return true;
091        }
092        return false;
093    }
094
095    private void processBlock(AbstractBlockBase<T> block, UniqueWorkList<T> worklist) {
096        if (updateOutBlock(block)) {
097            try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
098                currentSet = liveOutMap.get(block).copy();
099                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
100                for (int i = instructions.size() - 1; i >= 0; i--) {
101                    LIRInstruction inst = instructions.get(i);
102                    processInstructionBottomUp(inst);
103                }
104                liveInMap.put(block, currentSet);
105                currentSet = null;
106                worklist.addAll(block.getPredecessors());
107            }
108        }
109    }
110
111    private static final EnumSet<OperandFlag> REGISTER_FLAG_SET = EnumSet.of(OperandFlag.REG);
112    private static final LIRKind REFERENCE_KIND = LIRKind.reference(Kind.Object);
113
114    private S currentSet;
115
116    /**
117     * Process all values of an instruction bottom-up, i.e. definitions before usages. Values that
118     * start or end at the current operation are not included.
119     */
120    private void processInstructionBottomUp(LIRInstruction op) {
121        try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
122            // kills
123
124            op.visitEachTemp(defConsumer);
125            op.visitEachOutput(defConsumer);
126            if (frameMap != null && op.destroysCallerSavedRegisters()) {
127                for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
128                    defConsumer.visitValue(reg.asValue(REFERENCE_KIND), OperandMode.TEMP, REGISTER_FLAG_SET);
129                }
130            }
131
132            // gen - values that are considered alive for this state
133            op.visitEachAlive(useConsumer);
134            op.visitEachState(useConsumer);
135            // mark locations
136            op.forEachState(stateConsumer);
137            // gen
138            op.visitEachInput(useConsumer);
139        }
140    }
141
142    InstructionStateProcedure stateConsumer = new InstructionStateProcedure() {
143        public void doState(LIRInstruction inst, LIRFrameState info) {
144            processState(inst, info, currentSet);
145        }
146    };
147
148    ValueConsumer useConsumer = new ValueConsumer() {
149        public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
150            if (shouldProcessValue(operand)) {
151                // no need to insert values and derived reference
152                if (Debug.isLogEnabled()) {
153                    Debug.log("set operand: %s", operand);
154                }
155                currentSet.put(operand);
156            }
157        }
158    };
159
160    ValueConsumer defConsumer = new ValueConsumer() {
161        public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
162            if (shouldProcessValue(operand)) {
163                if (Debug.isLogEnabled()) {
164                    Debug.log("clear operand: %s", operand);
165                }
166                currentSet.remove(operand);
167            } else {
168                assert isIllegal(operand) || operand.getPlatformKind() != Kind.Illegal || mode == OperandMode.TEMP : String.format("Illegal PlatformKind is only allowed for TEMP mode: %s, %s",
169                                operand, mode);
170            }
171        }
172    };
173}