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