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 */
023
024package com.oracle.graal.lir.ssa;
025
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import com.oracle.graal.debug.*;
031import com.oracle.graal.debug.Debug.*;
032import jdk.internal.jvmci.meta.*;
033
034import com.oracle.graal.compiler.common.cfg.*;
035import com.oracle.graal.lir.*;
036import com.oracle.graal.lir.LIRInstruction.OperandFlag;
037import com.oracle.graal.lir.LIRInstruction.OperandMode;
038
039final class SSAVerifier {
040    private static class Entry {
041        private final LIRInstruction inst;
042        private final AbstractBlockBase<?> block;
043
044        Entry(LIRInstruction inst, AbstractBlockBase<?> block) {
045            this.inst = inst;
046            this.block = block;
047        }
048    }
049
050    private final LIR lir;
051    private final BitSet visited;
052    private final HashMap<Value, Entry> defined;
053    private AbstractBlockBase<?> currentBlock;
054
055    SSAVerifier(LIR lir) {
056        this.lir = lir;
057        this.visited = new BitSet(lir.getControlFlowGraph().getBlocks().size());
058        this.defined = new HashMap<>();
059    }
060
061    public boolean verify() {
062        try (Scope s = Debug.scope("SSAVerifier", lir)) {
063            for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
064                doBlock(block);
065            }
066        } catch (Throwable e) {
067            throw Debug.handle(e);
068        }
069        return true;
070    }
071
072    private void doBlock(AbstractBlockBase<?> b) {
073        if (visited.get(b.getId())) {
074            return;
075        }
076        for (AbstractBlockBase<?> pred : b.getPredecessors()) {
077            if (!b.isLoopHeader() || !pred.isLoopEnd()) {
078                doBlock(pred);
079            }
080        }
081        try (Indent indent = Debug.logAndIndent("handle block %s", b)) {
082            assert verifyBlock(b);
083        }
084    }
085
086    private boolean verifyBlock(AbstractBlockBase<?> block) {
087        currentBlock = block;
088        assert !visited.get(block.getId()) : "Block already visited: " + block;
089        visited.set(block.getId());
090        for (LIRInstruction op : lir.getLIRforBlock(block)) {
091            op.visitEachAlive(this::useConsumer);
092            op.visitEachState(this::useConsumer);
093            op.visitEachInput(this::useConsumer);
094
095            op.visitEachTemp(this::defConsumer);
096            op.visitEachOutput(this::defConsumer);
097
098        }
099        currentBlock = null;
100        return true;
101    }
102
103    /**
104     * @see InstructionValueConsumer
105     * @param mode
106     * @param flags
107     */
108    private void useConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
109        if (shouldProcess(value)) {
110            assert defined.keySet().contains(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s used at instruction %s in block %s but never defined", value, inst,
111                            currentBlock);
112        }
113    }
114
115    /**
116     * @see InstructionValueConsumer
117     * @param mode
118     * @param flags
119     */
120    private void defConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
121        if (shouldProcess(value)) {
122            assert !defined.keySet().contains(value) : String.format("Value %s redefined at %s but never defined (previous definition %s in block %s)", value, inst, defined.get(value).inst,
123                            defined.get(value).block);
124            defined.put(value, new Entry(inst, currentBlock));
125        }
126    }
127
128    private static boolean shouldProcess(Value value) {
129        return !value.equals(Value.ILLEGAL) && !isConstant(value) && !isRegister(value) && !isStackSlotValue(value);
130    }
131
132}