Source code

001/*
002 * Copyright (c) 2009, 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.lir;
024
025import static com.oracle.graal.lir.LIRValueUtil.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.common.*;
032import jdk.internal.jvmci.meta.*;
033
034import com.oracle.graal.compiler.common.cfg.*;
035import com.oracle.graal.debug.*;
036import com.oracle.graal.lir.LIRInstruction.OperandFlag;
037import com.oracle.graal.lir.LIRInstruction.OperandMode;
038import com.oracle.graal.lir.framemap.*;
039import com.oracle.graal.lir.ssa.*;
040
041public final class LIRVerifier {
042
043    private final LIR lir;
044    private final FrameMap frameMap;
045
046    private final boolean beforeRegisterAllocation;
047
048    private final BitSet[] blockLiveOut;
049    private final Object[] variableDefinitions;
050
051    private BitSet liveOutFor(AbstractBlockBase<?> block) {
052        return blockLiveOut[block.getId()];
053    }
054
055    private void setLiveOutFor(AbstractBlockBase<?> block, BitSet liveOut) {
056        blockLiveOut[block.getId()] = liveOut;
057    }
058
059    private int maxRegisterNum() {
060        return frameMap.getTarget().arch.getRegisters().length;
061    }
062
063    private boolean isAllocatableRegister(Value value) {
064        return isRegister(value) && frameMap.getRegisterConfig().getAttributesMap()[asRegister(value).number].isAllocatable();
065    }
066
067    public static boolean verify(final LIRInstruction op) {
068
069        op.visitEachInput(LIRVerifier::allowed);
070        op.visitEachAlive(LIRVerifier::allowed);
071        op.visitEachState(LIRVerifier::allowed);
072        op.visitEachTemp(LIRVerifier::allowed);
073        op.visitEachOutput(LIRVerifier::allowed);
074
075        op.verify();
076        return true;
077    }
078
079    public static boolean verify(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap) {
080        LIRVerifier verifier = new LIRVerifier(beforeRegisterAllocation, lir, frameMap);
081        verifier.verify();
082        return true;
083    }
084
085    private LIRVerifier(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap) {
086        this.beforeRegisterAllocation = beforeRegisterAllocation;
087        this.lir = lir;
088        this.frameMap = frameMap;
089        this.blockLiveOut = new BitSet[lir.linearScanOrder().size()];
090        this.variableDefinitions = new Object[lir.numVariables()];
091    }
092
093    private BitSet curVariablesLive;
094    private Value[] curRegistersLive;
095
096    private AbstractBlockBase<?> curBlock;
097    private Object curInstruction;
098    private BitSet curRegistersDefined;
099
100    private void verify() {
101        ValueConsumer useConsumer = new ValueConsumer() {
102
103            @Override
104            public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
105                use(value, mode, flags);
106            }
107        };
108        ValueConsumer defConsumer = new ValueConsumer() {
109
110            @Override
111            public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
112                def(value, mode, flags);
113            }
114        };
115
116        int maxRegisterNum = maxRegisterNum();
117        curRegistersDefined = new BitSet();
118        for (AbstractBlockBase<?> block : lir.linearScanOrder()) {
119            curBlock = block;
120            curVariablesLive = new BitSet();
121            curRegistersLive = new Value[maxRegisterNum];
122
123            if (block.getDominator() != null) {
124                curVariablesLive.or(liveOutFor(block.getDominator()));
125            }
126
127            assert lir.getLIRforBlock(block).get(0) instanceof StandardOp.LabelOp : "block must start with label";
128
129            if (block.getSuccessorCount() > 0) {
130                LIRInstruction last = lir.getLIRforBlock(block).get(lir.getLIRforBlock(block).size() - 1);
131                assert last instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
132            }
133            if (block.getPredecessorCount() > 1) {
134                SSAUtil.verifyPhi(lir, block);
135            }
136
137            for (LIRInstruction op : lir.getLIRforBlock(block)) {
138                curInstruction = op;
139
140                op.visitEachInput(useConsumer);
141                if (op.destroysCallerSavedRegisters()) {
142                    for (Register register : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
143                        curRegistersLive[register.number] = null;
144                    }
145                }
146                curRegistersDefined.clear();
147                op.visitEachAlive(useConsumer);
148                op.visitEachState(useConsumer);
149                op.visitEachTemp(defConsumer);
150                op.visitEachOutput(defConsumer);
151
152                curInstruction = null;
153            }
154
155            setLiveOutFor(block, curVariablesLive);
156        }
157    }
158
159    private void use(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
160        allowed(curInstruction, value, mode, flags);
161
162        if (isVariable(value)) {
163            assert beforeRegisterAllocation;
164
165            int variableIdx = asVariable(value).index;
166            if (!curVariablesLive.get(variableIdx)) {
167                TTY.println("block %s  instruction %s", curBlock, curInstruction);
168                TTY.println("live variables: %s", curVariablesLive);
169                if (variableDefinitions[variableIdx] != null) {
170                    TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
171                }
172                TTY.println("ERROR: Use of variable %s that is not defined in dominator", value);
173                throw JVMCIError.shouldNotReachHere();
174            }
175
176        } else if (isAllocatableRegister(value)) {
177            int regNum = asRegister(value).number;
178            if (mode == OperandMode.ALIVE) {
179                curRegistersDefined.set(regNum);
180            }
181
182            if (beforeRegisterAllocation && !curRegistersLive[regNum].equals(value)) {
183                TTY.println("block %s  instruction %s", curBlock, curInstruction);
184                TTY.println("live registers: %s", Arrays.toString(curRegistersLive));
185                TTY.println("ERROR: Use of fixed register %s that is not defined in this block", value);
186                throw JVMCIError.shouldNotReachHere();
187            }
188        }
189    }
190
191    private void def(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
192        allowed(curInstruction, value, mode, flags);
193
194        if (isVariable(value)) {
195            assert beforeRegisterAllocation;
196
197            int variableIdx = asVariable(value).index;
198            if (variableDefinitions[variableIdx] != null) {
199                TTY.println("block %s  instruction %s", curBlock, curInstruction);
200                TTY.println("live variables: %s", curVariablesLive);
201                TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
202                TTY.println("ERROR: Variable %s defined multiple times", value);
203                throw JVMCIError.shouldNotReachHere();
204            }
205            assert curInstruction != null;
206            variableDefinitions[variableIdx] = curInstruction;
207            assert !curVariablesLive.get(variableIdx);
208            if (mode == OperandMode.DEF) {
209                curVariablesLive.set(variableIdx);
210            }
211
212        } else if (isAllocatableRegister(value)) {
213            int regNum = asRegister(value).number;
214            if (curRegistersDefined.get(regNum)) {
215                TTY.println("block %s  instruction %s", curBlock, curInstruction);
216                TTY.println("ERROR: Same register defined twice in the same instruction: %s", value);
217                throw JVMCIError.shouldNotReachHere();
218            }
219            curRegistersDefined.set(regNum);
220
221            if (beforeRegisterAllocation) {
222                if (mode == OperandMode.DEF) {
223                    curRegistersLive[regNum] = value;
224                } else {
225                    curRegistersLive[regNum] = null;
226                }
227            }
228        }
229    }
230
231    // @formatter:off
232    private static void allowed(Object op, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
233        if ((isVariable(value) && flags.contains(OperandFlag.REG)) ||
234            (isRegister(value) && flags.contains(OperandFlag.REG)) ||
235            (isStackSlotValue(value) && flags.contains(OperandFlag.STACK)) ||
236            (isConstant(value) && flags.contains(OperandFlag.CONST) && mode != OperandMode.DEF) ||
237            (isIllegal(value) && flags.contains(OperandFlag.ILLEGAL))) {
238            return;
239        }
240        throw new JVMCIError("Invalid LIR%n  Instruction: %s%n  Mode: %s%n  Flags: %s%n  Unexpected value: %s %s",
241                        op, mode, flags, value.getClass().getSimpleName(), value);
242    }
243    // @formatter:on
244}