1 /*
   2  * Copyright (c) 2015, 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 
  24 package org.graalvm.compiler.lir.ssa;
  25 
  26 import static org.graalvm.compiler.lir.LIRValueUtil.isJavaConstant;
  27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
  28 import static jdk.vm.ci.code.ValueUtil.isRegister;
  29 
  30 import java.util.BitSet;
  31 import java.util.EnumSet;
  32 import java.util.HashMap;
  33 
  34 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  35 import org.graalvm.compiler.debug.Debug;
  36 import org.graalvm.compiler.debug.Debug.Scope;
  37 import org.graalvm.compiler.debug.Indent;
  38 import org.graalvm.compiler.lir.InstructionValueConsumer;
  39 import org.graalvm.compiler.lir.LIR;
  40 import org.graalvm.compiler.lir.LIRInstruction;
  41 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
  42 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
  43 
  44 import jdk.vm.ci.meta.Value;
  45 
  46 final class SSAVerifier {
  47     private static class Entry {
  48         private final LIRInstruction inst;
  49         private final AbstractBlockBase<?> block;
  50 
  51         Entry(LIRInstruction inst, AbstractBlockBase<?> block) {
  52             this.inst = inst;
  53             this.block = block;
  54         }
  55     }
  56 
  57     private final LIR lir;
  58     private final BitSet visited;
  59     private final HashMap<Value, Entry> defined;
  60     private AbstractBlockBase<?> currentBlock;
  61 
  62     SSAVerifier(LIR lir) {
  63         this.lir = lir;
  64         this.visited = new BitSet(lir.getControlFlowGraph().getBlocks().length);
  65         this.defined = new HashMap<>();
  66     }
  67 
  68     @SuppressWarnings("try")
  69     public boolean verify() {
  70         try (Scope s = Debug.scope("SSAVerifier", lir)) {
  71             for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
  72                 doBlock(block);
  73             }
  74         } catch (Throwable e) {
  75             throw Debug.handle(e);
  76         }
  77         return true;
  78     }
  79 
  80     @SuppressWarnings("try")
  81     private void doBlock(AbstractBlockBase<?> b) {
  82         if (visited.get(b.getId())) {
  83             return;
  84         }
  85         for (AbstractBlockBase<?> pred : b.getPredecessors()) {
  86             if (!b.isLoopHeader() || !pred.isLoopEnd()) {
  87                 doBlock(pred);
  88             }
  89         }
  90         try (Indent indent = Debug.logAndIndent(Debug.INFO_LOG_LEVEL, "handle block %s", b)) {
  91             assert verifyBlock(b);
  92         }
  93     }
  94 
  95     private boolean verifyBlock(AbstractBlockBase<?> block) {
  96         currentBlock = block;
  97         assert !visited.get(block.getId()) : "Block already visited: " + block;
  98         visited.set(block.getId());
  99         for (LIRInstruction op : lir.getLIRforBlock(block)) {
 100             op.visitEachAlive(this::useConsumer);
 101             op.visitEachState(this::useConsumer);
 102             op.visitEachInput(this::useConsumer);
 103 
 104             op.visitEachTemp(this::defConsumer);
 105             op.visitEachOutput(this::defConsumer);
 106 
 107         }
 108         currentBlock = null;
 109         return true;
 110     }
 111 
 112     /**
 113      * @see InstructionValueConsumer
 114      * @param mode
 115      * @param flags
 116      */
 117     private void useConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
 118         if (shouldProcess(value)) {
 119             assert defined.containsKey(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s used at instruction %s in block %s but never defined", value, inst,
 120                             currentBlock);
 121         }
 122     }
 123 
 124     /**
 125      * @see InstructionValueConsumer
 126      * @param mode
 127      * @param flags
 128      */
 129     private void defConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
 130         if (shouldProcess(value)) {
 131             assert !defined.containsKey(value) : String.format("Value %s redefined at %s but never defined (previous definition %s in block %s)", value, inst, defined.get(value).inst,
 132                             defined.get(value).block);
 133             defined.put(value, new Entry(inst, currentBlock));
 134         }
 135     }
 136 
 137     private static boolean shouldProcess(Value value) {
 138         return !value.equals(Value.ILLEGAL) && !isJavaConstant(value) && !isRegister(value) && !isStackSlotValue(value);
 139     }
 140 
 141 }