1 /*
2 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.dfa;
24
25 import static jdk.vm.ci.code.ValueUtil.isIllegal;
26
27 import java.util.ArrayList;
28 import java.util.EnumSet;
29
30 import org.graalvm.compiler.core.common.LIRKind;
31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32 import org.graalvm.compiler.core.common.cfg.BlockMap;
33 import org.graalvm.compiler.debug.Debug;
34 import org.graalvm.compiler.debug.Indent;
35 import org.graalvm.compiler.lir.InstructionStateProcedure;
36 import org.graalvm.compiler.lir.LIR;
37 import org.graalvm.compiler.lir.LIRFrameState;
38 import org.graalvm.compiler.lir.LIRInstruction;
39 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
40 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
41 import org.graalvm.compiler.lir.ValueConsumer;
42 import org.graalvm.compiler.lir.framemap.FrameMap;
43 import org.graalvm.compiler.lir.util.ValueSet;
44
45 import jdk.vm.ci.code.Register;
46 import jdk.vm.ci.meta.PlatformKind;
47 import jdk.vm.ci.meta.Value;
48
49 public abstract class LocationMarker<S extends ValueSet<S>> {
50
51 private final LIR lir;
52 private final BlockMap<S> liveInMap;
53 private final BlockMap<S> liveOutMap;
54
55 protected final FrameMap frameMap;
56
57 protected LocationMarker(LIR lir, FrameMap frameMap) {
58 this.lir = lir;
59 this.frameMap = frameMap;
60 liveInMap = new BlockMap<>(lir.getControlFlowGraph());
61 liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
62 }
63
64 protected abstract S newLiveValueSet();
65
66 protected abstract boolean shouldProcessValue(Value operand);
67
68 protected abstract void processState(LIRInstruction op, LIRFrameState info, S values);
69
70 void build() {
71 AbstractBlockBase<?>[] blocks = lir.getControlFlowGraph().getBlocks();
72 UniqueWorkList worklist = new UniqueWorkList(blocks.length);
73 for (int i = blocks.length - 1; i >= 0; i--) {
74 worklist.add(blocks[i]);
75 }
76 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
77 liveInMap.put(block, newLiveValueSet());
78 }
79 while (!worklist.isEmpty()) {
80 AbstractBlockBase<?> block = worklist.poll();
81 processBlock(block, worklist);
82 }
83 }
84
85 /**
86 * Merge outSet with in-set of successors.
87 */
88 private boolean updateOutBlock(AbstractBlockBase<?> block) {
89 S union = newLiveValueSet();
90 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
91 union.putAll(liveInMap.get(succ));
92 }
93 S outSet = liveOutMap.get(block);
94 // check if changed
95 if (outSet == null || !union.equals(outSet)) {
96 liveOutMap.put(block, union);
97 return true;
98 }
99 return false;
100 }
101
102 @SuppressWarnings("try")
103 private void processBlock(AbstractBlockBase<?> block, UniqueWorkList worklist) {
104 if (updateOutBlock(block)) {
105 try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
106 currentSet = liveOutMap.get(block).copy();
107 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
108 for (int i = instructions.size() - 1; i >= 0; i--) {
109 LIRInstruction inst = instructions.get(i);
110 processInstructionBottomUp(inst);
111 }
112 liveInMap.put(block, currentSet);
113 currentSet = null;
114 for (AbstractBlockBase<?> b : block.getPredecessors()) {
115 worklist.add(b);
116 }
117 }
118 }
119 }
120
121 private static final EnumSet<OperandFlag> REGISTER_FLAG_SET = EnumSet.of(OperandFlag.REG);
122
123 private S currentSet;
124
125 /**
126 * Process all values of an instruction bottom-up, i.e. definitions before usages. Values that
127 * start or end at the current operation are not included.
128 */
129 @SuppressWarnings("try")
130 private void processInstructionBottomUp(LIRInstruction op) {
131 try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
132 // kills
133
134 op.visitEachTemp(defConsumer);
135 op.visitEachOutput(defConsumer);
136 if (frameMap != null && op.destroysCallerSavedRegisters()) {
137 for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
138 PlatformKind kind = frameMap.getTarget().arch.getLargestStorableKind(reg.getRegisterCategory());
139 defConsumer.visitValue(reg.asValue(LIRKind.value(kind)), OperandMode.TEMP, REGISTER_FLAG_SET);
140 }
141 }
142
143 // gen - values that are considered alive for this state
144 op.visitEachAlive(useConsumer);
145 op.visitEachState(useConsumer);
146 // mark locations
147 op.forEachState(stateConsumer);
148 // gen
149 op.visitEachInput(useConsumer);
150 }
151 }
152
153 InstructionStateProcedure stateConsumer = new InstructionStateProcedure() {
154 @Override
155 public void doState(LIRInstruction inst, LIRFrameState info) {
156 processState(inst, info, currentSet);
157 }
158 };
159
160 ValueConsumer useConsumer = new ValueConsumer() {
161 @Override
162 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
163 if (shouldProcessValue(operand)) {
164 // no need to insert values and derived reference
165 if (Debug.isLogEnabled()) {
166 Debug.log("set operand: %s", operand);
167 }
168 currentSet.put(operand);
169 }
170 }
171 };
172
173 ValueConsumer defConsumer = new ValueConsumer() {
174 @Override
175 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
176 if (shouldProcessValue(operand)) {
177 if (Debug.isLogEnabled()) {
178 Debug.log("clear operand: %s", operand);
179 }
180 currentSet.remove(operand);
181 } else {
182 assert isIllegal(operand) || !operand.getValueKind().equals(LIRKind.Illegal) || mode == OperandMode.TEMP : String.format("Illegal PlatformKind is only allowed for TEMP mode: %s, %s",
183 operand, mode);
184 }
185 }
186 };
187 }