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.Debug; 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 Effect[] effects = EMPTY_ARRAY; 66 private String[] names = EMPTY_STRING_ARRAY; 67 private int size; 68 69 private void enlarge(int elements) { 70 int length = effects.length; 71 if (size + elements > length) { 72 while (size + elements > length) { 73 length = Math.max(length * 2, 4); 74 } 75 effects = Arrays.copyOf(effects, length); 76 if (Debug.isEnabled()) { 77 names = Arrays.copyOf(names, length); 78 } 79 } 80 } 81 82 public void add(String name, SimpleEffect effect) { 83 add(name, (Effect) effect); 84 } 85 86 public void add(String name, Effect effect) { 87 assert effect != null; 88 enlarge(1); 89 if (Debug.isEnabled()) { 90 names[size] = name; 91 } 92 effects[size++] = effect; 93 } 94 95 public void addAll(EffectList list) { 96 enlarge(list.size); 97 System.arraycopy(list.effects, 0, effects, size, list.size); 98 if (Debug.isEnabled()) { 99 System.arraycopy(list.names, 0, names, size, list.size); 100 } 101 size += list.size; 102 } 103 104 public void insertAll(EffectList list, int position) { 105 assert position >= 0 && position <= size; 106 enlarge(list.size); 107 System.arraycopy(effects, position, effects, position + list.size, size - position); 108 System.arraycopy(list.effects, 0, effects, position, list.size); 109 if (Debug.isEnabled()) { 110 System.arraycopy(names, position, names, position + list.size, size - position); 111 System.arraycopy(list.names, 0, names, position, list.size); 112 } 113 size += list.size; 114 } 115 116 public int checkpoint() { 117 return size; 118 } 119 120 public int size() { 121 return size; 122 } 123 124 public void backtrack(int checkpoint) { 125 assert checkpoint <= size; 126 size = checkpoint; 127 } 128 129 @Override 130 public Iterator<Effect> iterator() { 131 return new Iterator<Effect>() { 132 133 int index; 134 final int listSize = EffectList.this.size; 135 136 @Override 137 public boolean hasNext() { 138 return index < listSize; 139 } 140 141 @Override 142 public Effect next() { 143 return effects[index++]; 144 } 145 146 @Override 147 public void remove() { 148 throw new UnsupportedOperationException(); 149 } 150 }; 151 } 152 153 public Effect get(int index) { 154 if (index >= size) { 155 throw new IndexOutOfBoundsException(); 156 } 157 return effects[index]; 158 } 159 160 public void clear() { 161 size = 0; 162 } 163 164 public boolean isEmpty() { 165 return size == 0; 166 } 167 168 public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes, boolean cfgKills) { 169 for (int i = 0; i < size(); i++) { 170 Effect effect = effects[i]; 171 if (effect.isCfgKill() == cfgKills) { 172 try { 173 effect.apply(graph, obsoleteNodes); 174 } catch (Throwable t) { 175 StringBuilder str = new StringBuilder(); 176 toString(str, i); 177 throw new GraalError(t).addContext("effect", str); 178 } 179 if (effect.isVisible() && Debug.isLogEnabled()) { 180 StringBuilder str = new StringBuilder(); 181 toString(str, i); 182 Debug.log(" %s", str); 183 } 184 } 185 } 186 } 187 188 private void toString(StringBuilder str, int i) { 189 Effect effect = effects[i]; 190 str.append(getName(i)).append(" ["); 191 boolean first = true; 192 for (Field field : effect.getClass().getDeclaredFields()) { 193 try { 194 field.setAccessible(true); 195 Object object = field.get(effect); 196 if (object == this) { 197 // Inner classes could capture the EffectList itself. 198 continue; 199 } 200 str.append(first ? "" : ", ").append(format(object)); 201 first = false; 202 } catch (SecurityException | IllegalAccessException e) { 203 throw new RuntimeException(e); 204 } 205 } 206 str.append(']'); 207 } 208 209 private static String format(Object object) { 210 if (object != null && Object[].class.isAssignableFrom(object.getClass())) { 211 return Arrays.toString((Object[]) object); 212 } 213 return "" + object; 214 } 215 216 @Override 217 public String toString() { 218 StringBuilder str = new StringBuilder(); 219 for (int i = 0; i < size(); i++) { 220 Effect effect = get(i); 221 if (effect.isVisible()) { 222 toString(str, i); 223 str.append('\n'); 224 } 225 } 226 return str.toString(); 227 } 228 229 private String getName(int i) { 230 if (Debug.isEnabled()) { 231 return names[i]; 232 } else { 233 return ""; 234 } 235 } 236 }