1 /*
   2  * Copyright (c) 2012, 2017, 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 package org.graalvm.compiler.virtual.phases.ea;
  24 
  25 import java.lang.reflect.Field;
  26 import java.util.ArrayList;
  27 import java.util.Arrays;
  28 import java.util.Iterator;
  29 
  30 import org.graalvm.compiler.debug.DebugContext;
  31 import org.graalvm.compiler.debug.GraalError;
  32 import org.graalvm.compiler.graph.Node;
  33 import org.graalvm.compiler.nodes.StructuredGraph;
  34 
  35 /**
  36  * An {@link EffectList} can be used to maintain a list of {@link Effect}s and backtrack to a
  37  * previous state by truncating the list.
  38  */
  39 public class EffectList implements Iterable<EffectList.Effect> {
  40 
  41     public interface Effect {
  42         default boolean isVisible() {
  43             return true;
  44         }
  45 
  46         default boolean isCfgKill() {
  47             return false;
  48         }
  49 
  50         void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes);
  51     }
  52 
  53     public interface SimpleEffect extends Effect {
  54         @Override
  55         default void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
  56             apply(graph);
  57         }
  58 
  59         void apply(StructuredGraph graph);
  60     }
  61 
  62     private static final Effect[] EMPTY_ARRAY = new Effect[0];
  63     private static final String[] EMPTY_STRING_ARRAY = new String[0];
  64 
  65     private final DebugContext debug;
  66     private Effect[] effects = EMPTY_ARRAY;
  67     private String[] names = EMPTY_STRING_ARRAY;
  68     private int size;
  69 
  70     public EffectList(DebugContext debug) {
  71         this.debug = debug;
  72     }
  73 
  74     private void enlarge(int elements) {
  75         int length = effects.length;
  76         if (size + elements > length) {
  77             while (size + elements > length) {
  78                 length = Math.max(length * 2, 4);
  79             }
  80             effects = Arrays.copyOf(effects, length);
  81             if (debug.isLogEnabled()) {
  82                 names = Arrays.copyOf(names, length);
  83             }
  84         }
  85     }
  86 
  87     public void add(String name, SimpleEffect effect) {
  88         add(name, (Effect) effect);
  89     }
  90 
  91     public void add(String name, Effect effect) {
  92         assert effect != null;
  93         enlarge(1);
  94         if (debug.isLogEnabled()) {
  95             names[size] = name;
  96         }
  97         effects[size++] = effect;
  98     }
  99 
 100     public void addAll(EffectList list) {
 101         enlarge(list.size);
 102         System.arraycopy(list.effects, 0, effects, size, list.size);
 103         if (debug.isLogEnabled()) {
 104             System.arraycopy(list.names, 0, names, size, list.size);
 105         }
 106         size += list.size;
 107     }
 108 
 109     public void insertAll(EffectList list, int position) {
 110         assert position >= 0 && position <= size;
 111         enlarge(list.size);
 112         System.arraycopy(effects, position, effects, position + list.size, size - position);
 113         System.arraycopy(list.effects, 0, effects, position, list.size);
 114         if (debug.isLogEnabled()) {
 115             System.arraycopy(names, position, names, position + list.size, size - position);
 116             System.arraycopy(list.names, 0, names, position, list.size);
 117         }
 118         size += list.size;
 119     }
 120 
 121     public int checkpoint() {
 122         return size;
 123     }
 124 
 125     public int size() {
 126         return size;
 127     }
 128 
 129     public void backtrack(int checkpoint) {
 130         assert checkpoint <= size;
 131         size = checkpoint;
 132     }
 133 
 134     @Override
 135     public Iterator<Effect> iterator() {
 136         return new Iterator<Effect>() {
 137 
 138             int index;
 139             final int listSize = EffectList.this.size;
 140 
 141             @Override
 142             public boolean hasNext() {
 143                 return index < listSize;
 144             }
 145 
 146             @Override
 147             public Effect next() {
 148                 return effects[index++];
 149             }
 150 
 151             @Override
 152             public void remove() {
 153                 throw new UnsupportedOperationException();
 154             }
 155         };
 156     }
 157 
 158     public Effect get(int index) {
 159         if (index >= size) {
 160             throw new IndexOutOfBoundsException();
 161         }
 162         return effects[index];
 163     }
 164 
 165     public void clear() {
 166         size = 0;
 167     }
 168 
 169     public boolean isEmpty() {
 170         return size == 0;
 171     }
 172 
 173     public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes, boolean cfgKills) {
 174         for (int i = 0; i < size(); i++) {
 175             Effect effect = effects[i];
 176             if (effect.isCfgKill() == cfgKills) {
 177                 try {
 178                     effect.apply(graph, obsoleteNodes);
 179                 } catch (Throwable t) {
 180                     StringBuilder str = new StringBuilder();
 181                     toString(str, i);
 182                     throw new GraalError(t).addContext("effect", str);
 183                 }
 184                 if (effect.isVisible() && debug.isLogEnabled()) {
 185                     StringBuilder str = new StringBuilder();
 186                     toString(str, i);
 187                     debug.log("    %s", str);
 188                 }
 189             }
 190         }
 191     }
 192 
 193     private void toString(StringBuilder str, int i) {
 194         Effect effect = effects[i];
 195         str.append(getName(i)).append(" [");
 196         boolean first = true;
 197         for (Field field : effect.getClass().getDeclaredFields()) {
 198             try {
 199                 field.setAccessible(true);
 200                 Object object = field.get(effect);
 201                 if (object == this) {
 202                     // Inner classes could capture the EffectList itself.
 203                     continue;
 204                 }
 205                 str.append(first ? "" : ", ").append(format(object));
 206                 first = false;
 207             } catch (SecurityException | IllegalAccessException e) {
 208                 throw new RuntimeException(e);
 209             }
 210         }
 211         str.append(']');
 212     }
 213 
 214     private static String format(Object object) {
 215         if (object != null && Object[].class.isAssignableFrom(object.getClass())) {
 216             return Arrays.toString((Object[]) object);
 217         }
 218         return "" + object;
 219     }
 220 
 221     @Override
 222     public String toString() {
 223         StringBuilder str = new StringBuilder();
 224         for (int i = 0; i < size(); i++) {
 225             Effect effect = get(i);
 226             if (effect.isVisible()) {
 227                 toString(str, i);
 228                 str.append('\n');
 229             }
 230         }
 231         return str.toString();
 232     }
 233 
 234     private String getName(int i) {
 235         if (debug.isLogEnabled()) {
 236             return names[i];
 237         } else {
 238             return "";
 239         }
 240     }
 241 }