1/*
2 * Copyright (c) 2009, 2012, 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 */
23package org.graalvm.compiler.lir.alloc.trace.lsra;
24
25import static org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.isVariableOrRegister;
26import static jdk.vm.ci.code.ValueUtil.asRegister;
27import static jdk.vm.ci.code.ValueUtil.isRegister;
28
29import java.util.ArrayList;
30import java.util.EnumSet;
31import java.util.List;
32
33import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
34import org.graalvm.compiler.core.common.util.ArrayMap;
35import org.graalvm.compiler.debug.Debug;
36import org.graalvm.compiler.debug.Debug.Scope;
37import org.graalvm.compiler.debug.GraalError;
38import org.graalvm.compiler.debug.Indent;
39import org.graalvm.compiler.lir.InstructionValueConsumer;
40import org.graalvm.compiler.lir.LIRInstruction;
41import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
42import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
43import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
44
45import jdk.vm.ci.code.Register;
46import jdk.vm.ci.meta.Value;
47
48/**
49 */
50final class RegisterVerifier {
51
52    TraceLinearScan allocator;
53    List<AbstractBlockBase<?>> workList; // all blocks that must be processed
54    ArrayMap<TraceInterval[]> savedStates; // saved information of previous check
55
56    // simplified access to methods of LinearScan
57    TraceInterval intervalAt(Value operand) {
58        return allocator.intervalFor(operand);
59    }
60
61    // currently, only registers are processed
62    int stateSize() {
63        return allocator.numRegisters();
64    }
65
66    // accessors
67    TraceInterval[] stateForBlock(AbstractBlockBase<?> block) {
68        return savedStates.get(block.getId());
69    }
70
71    void setStateForBlock(AbstractBlockBase<?> block, TraceInterval[] savedState) {
72        savedStates.put(block.getId(), savedState);
73    }
74
75    void addToWorkList(AbstractBlockBase<?> block) {
76        if (!workList.contains(block)) {
77            workList.add(block);
78        }
79    }
80
81    RegisterVerifier(TraceLinearScan allocator) {
82        this.allocator = allocator;
83        workList = new ArrayList<>(16);
84        this.savedStates = new ArrayMap<>();
85
86    }
87
88    @SuppressWarnings("try")
89    void verify(AbstractBlockBase<?> start) {
90        try (Scope s = Debug.scope("RegisterVerifier")) {
91            // setup input registers (method arguments) for first block
92            TraceInterval[] inputState = new TraceInterval[stateSize()];
93            setStateForBlock(start, inputState);
94            addToWorkList(start);
95
96            // main loop for verification
97            do {
98                AbstractBlockBase<?> block = workList.get(0);
99                workList.remove(0);
100
101                processBlock(block);
102            } while (!workList.isEmpty());
103        }
104    }
105
106    @SuppressWarnings("try")
107    private void processBlock(AbstractBlockBase<?> block) {
108        try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) {
109            // must copy state because it is modified
110            TraceInterval[] inputState = copy(stateForBlock(block));
111
112            try (Indent indent2 = Debug.logAndIndent("Input-State of intervals:")) {
113                printState(inputState);
114            }
115
116            // process all operations of the block
117            processOperations(block, inputState);
118
119            try (Indent indent2 = Debug.logAndIndent("Output-State of intervals:")) {
120                printState(inputState);
121            }
122
123            // iterate all successors
124            for (AbstractBlockBase<?> succ : block.getSuccessors()) {
125                processSuccessor(succ, inputState);
126            }
127        }
128    }
129
130    protected void printState(TraceInterval[] inputState) {
131        for (int i = 0; i < stateSize(); i++) {
132            Register reg = allocator.getRegisters().get(i);
133            assert reg.number == i;
134            if (inputState[i] != null) {
135                Debug.log(" %6s %4d  --  %s", reg, inputState[i].operandNumber, inputState[i]);
136            } else {
137                Debug.log(" %6s   __", reg);
138            }
139        }
140    }
141
142    private void processSuccessor(AbstractBlockBase<?> block, TraceInterval[] inputState) {
143        TraceInterval[] savedState = stateForBlock(block);
144
145        if (savedState != null) {
146            // this block was already processed before.
147            // check if new inputState is consistent with savedState
148
149            boolean savedStateCorrect = true;
150            for (int i = 0; i < stateSize(); i++) {
151                if (inputState[i] != savedState[i]) {
152                    // current inputState and previous savedState assume a different
153                    // interval in this register . assume that this register is invalid
154                    if (savedState[i] != null) {
155                        // invalidate old calculation only if it assumed that
156                        // register was valid. when the register was already invalid,
157                        // then the old calculation was correct.
158                        savedStateCorrect = false;
159                        savedState[i] = null;
160
161                        Debug.log("processSuccessor B%d: invalidating slot %d", block.getId(), i);
162                    }
163                }
164            }
165
166            if (savedStateCorrect) {
167                // already processed block with correct inputState
168                Debug.log("processSuccessor B%d: previous visit already correct", block.getId());
169            } else {
170                // must re-visit this block
171                Debug.log("processSuccessor B%d: must re-visit because input state changed", block.getId());
172                addToWorkList(block);
173            }
174
175        } else {
176            // block was not processed before, so set initial inputState
177            Debug.log("processSuccessor B%d: initial visit", block.getId());
178
179            setStateForBlock(block, copy(inputState));
180            addToWorkList(block);
181        }
182    }
183
184    static TraceInterval[] copy(TraceInterval[] inputState) {
185        return inputState.clone();
186    }
187
188    static void statePut(TraceInterval[] inputState, Value location, TraceInterval interval) {
189        if (location != null && isRegister(location)) {
190            Register reg = asRegister(location);
191            int regNum = reg.number;
192            if (interval != null) {
193                Debug.log("%s = %s", reg, interval.operand);
194            } else if (inputState[regNum] != null) {
195                Debug.log("%s = null", reg);
196            }
197
198            inputState[regNum] = interval;
199        }
200    }
201
202    static boolean checkState(AbstractBlockBase<?> block, LIRInstruction op, TraceInterval[] inputState, Value operand, Value reg, TraceInterval interval) {
203        if (reg != null && isRegister(reg)) {
204            if (inputState[asRegister(reg).number] != interval) {
205                throw new GraalError(
206                                "Error in register allocation: operation (%s) in block %s expected register %s (operand %s) to contain the value of interval %s but data-flow says it contains interval %s",
207                                op, block, reg, operand, interval, inputState[asRegister(reg).number]);
208            }
209        }
210        return true;
211    }
212
213    void processOperations(AbstractBlockBase<?> block, final TraceInterval[] inputState) {
214        List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block);
215        InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
216
217            @Override
218            public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
219                // we skip spill moves inserted by the spill position optimization
220                if (isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != TraceLinearScanPhase.DOMINATOR_SPILL_MOVE_ID) {
221                    TraceInterval interval = intervalAt(operand);
222                    if (op.id() != -1) {
223                        interval = interval.getSplitChildAtOpId(op.id(), mode);
224                    }
225
226                    assert checkState(block, op, inputState, interval.operand, interval.location(), interval.splitParent());
227                }
228            }
229        };
230
231        InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> {
232            if (isVariableOrRegister(operand) && allocator.isProcessed(operand)) {
233                TraceInterval interval = intervalAt(operand);
234                if (op.id() != -1) {
235                    interval = interval.getSplitChildAtOpId(op.id(), mode);
236                }
237
238                statePut(inputState, interval.location(), interval.splitParent());
239            }
240        };
241
242        // visit all instructions of the block
243        for (int i = 0; i < ops.size(); i++) {
244            final LIRInstruction op = ops.get(i);
245
246            if (Debug.isLogEnabled()) {
247                Debug.log("%s", op.toStringWithIdPrefix());
248            }
249
250            // check if input operands are correct
251            op.visitEachInput(useConsumer);
252            // invalidate all caller save registers at calls
253            if (op.destroysCallerSavedRegisters()) {
254                for (Register r : allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters()) {
255                    statePut(inputState, r.asValue(), null);
256                }
257            }
258            op.visitEachAlive(useConsumer);
259            // set temp operands (some operations use temp operands also as output operands, so
260            // can't set them null)
261            op.visitEachTemp(defConsumer);
262            // set output operands
263            op.visitEachOutput(defConsumer);
264        }
265    }
266}
267