1 /* 2 * Copyright (c) 2009, 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 package org.graalvm.compiler.nodes.cfg; 26 27 import java.util.ArrayList; 28 import java.util.Iterator; 29 30 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 31 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; 32 import org.graalvm.compiler.core.common.cfg.Loop; 33 import org.graalvm.compiler.graph.Node; 34 import org.graalvm.compiler.nodeinfo.Verbosity; 35 import org.graalvm.compiler.nodes.AbstractBeginNode; 36 import org.graalvm.compiler.nodes.FixedNode; 37 import org.graalvm.compiler.nodes.FixedWithNextNode; 38 import org.graalvm.compiler.nodes.InvokeWithExceptionNode; 39 import org.graalvm.compiler.nodes.LoopBeginNode; 40 import org.graalvm.compiler.nodes.LoopEndNode; 41 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint; 42 import jdk.internal.vm.compiler.word.LocationIdentity; 43 44 public final class Block extends AbstractBlockBase<Block> { 45 public static final Block[] EMPTY_ARRAY = new Block[0]; 46 47 protected final AbstractBeginNode beginNode; 48 49 protected FixedNode endNode; 50 51 protected double relativeFrequency; 52 private Loop<Block> loop; 53 54 protected Block postdominator; 55 private LocationSet killLocations; 56 private LocationSet killLocationsBetweenThisAndDominator; 57 58 public Block(AbstractBeginNode node) { 59 this.beginNode = node; 60 } 61 62 public AbstractBeginNode getBeginNode() { 63 return beginNode; 64 } 65 66 public FixedNode getEndNode() { 67 return endNode; 68 } 69 70 @Override 71 public Loop<Block> getLoop() { 72 return loop; 73 } 74 75 public void setLoop(Loop<Block> loop) { 76 this.loop = loop; 77 } 78 79 @Override 80 public int getLoopDepth() { 81 return loop == null ? 0 : loop.getDepth(); 82 } 83 84 @Override 85 public boolean isLoopHeader() { 86 return getBeginNode() instanceof LoopBeginNode; 87 } 88 89 @Override 90 public boolean isLoopEnd() { 91 return getEndNode() instanceof LoopEndNode; 92 } 93 94 @Override 95 public boolean isExceptionEntry() { 96 Node predecessor = getBeginNode().predecessor(); 97 return predecessor != null && predecessor instanceof InvokeWithExceptionNode && getBeginNode() == ((InvokeWithExceptionNode) predecessor).exceptionEdge(); 98 } 99 100 public Block getFirstPredecessor() { 101 return getPredecessors()[0]; 102 } 103 104 public Block getFirstSuccessor() { 105 return getSuccessors()[0]; 106 } 107 108 public Block getEarliestPostDominated() { 109 Block b = this; 110 while (true) { 111 Block dom = b.getDominator(); 112 if (dom != null && dom.getPostdominator() == b) { 113 b = dom; 114 } else { 115 break; 116 } 117 } 118 return b; 119 } 120 121 @Override 122 public Block getPostdominator() { 123 return postdominator; 124 } 125 126 private class NodeIterator implements Iterator<FixedNode> { 127 128 private FixedNode cur; 129 130 NodeIterator() { 131 cur = getBeginNode(); 132 } 133 134 @Override 135 public boolean hasNext() { 136 return cur != null; 137 } 138 139 @Override 140 public FixedNode next() { 141 FixedNode result = cur; 142 if (result instanceof FixedWithNextNode) { 143 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) result; 144 FixedNode next = fixedWithNextNode.next(); 145 if (next instanceof AbstractBeginNode) { 146 next = null; 147 } 148 cur = next; 149 } else { 150 cur = null; 151 } 152 assert !(cur instanceof AbstractBeginNode); 153 return result; 154 } 155 156 @Override 157 public void remove() { 158 throw new UnsupportedOperationException(); 159 } 160 } 161 162 public Iterable<FixedNode> getNodes() { 163 return new Iterable<FixedNode>() { 164 165 @Override 166 public Iterator<FixedNode> iterator() { 167 return new NodeIterator(); 168 } 169 170 @Override 171 public String toString() { 172 StringBuilder str = new StringBuilder().append('['); 173 for (FixedNode node : this) { 174 str.append(node).append(", "); 175 } 176 if (str.length() > 1) { 177 str.setLength(str.length() - 2); 178 } 179 return str.append(']').toString(); 180 } 181 }; 182 } 183 184 @Override 185 public String toString() { 186 return toString(Verbosity.Id); 187 } 188 189 public String toString(Verbosity verbosity) { 190 StringBuilder sb = new StringBuilder(); 191 sb.append('B').append(id); 192 if (verbosity != Verbosity.Id) { 193 if (isLoopHeader()) { 194 sb.append(" lh"); 195 } 196 197 if (getSuccessorCount() > 0) { 198 sb.append(" ->["); 199 for (int i = 0; i < getSuccessorCount(); ++i) { 200 if (i != 0) { 201 sb.append(','); 202 } 203 sb.append('B').append(getSuccessors()[i].getId()); 204 } 205 sb.append(']'); 206 } 207 208 if (getPredecessorCount() > 0) { 209 sb.append(" <-["); 210 for (int i = 0; i < getPredecessorCount(); ++i) { 211 if (i != 0) { 212 sb.append(','); 213 } 214 sb.append('B').append(getPredecessors()[i].getId()); 215 } 216 sb.append(']'); 217 } 218 } 219 return sb.toString(); 220 } 221 222 /** 223 * The execution frequency of this block relative to the start block as estimated by the 224 * profiling information. 225 */ 226 @Override 227 public double getRelativeFrequency() { 228 return relativeFrequency; 229 } 230 231 public void setRelativeFrequency(double relativeFrequency) { 232 assert relativeFrequency >= 0 && Double.isFinite(relativeFrequency); 233 this.relativeFrequency = relativeFrequency; 234 } 235 236 @Override 237 public Block getDominator(int distance) { 238 Block result = this; 239 for (int i = 0; i < distance; ++i) { 240 result = result.getDominator(); 241 } 242 return result; 243 } 244 245 public boolean canKill(LocationIdentity location) { 246 if (location.isImmutable()) { 247 return false; 248 } 249 return getKillLocations().contains(location); 250 } 251 252 public LocationSet getKillLocations() { 253 if (killLocations == null) { 254 killLocations = calcKillLocations(); 255 } 256 return killLocations; 257 } 258 259 private LocationSet calcKillLocations() { 260 LocationSet result = new LocationSet(); 261 for (FixedNode node : this.getNodes()) { 262 if (node instanceof MemoryCheckpoint.Single) { 263 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity(); 264 result.add(identity); 265 } else if (node instanceof MemoryCheckpoint.Multi) { 266 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) { 267 result.add(identity); 268 } 269 } 270 if (result.isAny()) { 271 break; 272 } 273 } 274 return result; 275 } 276 277 public boolean canKillBetweenThisAndDominator(LocationIdentity location) { 278 if (location.isImmutable()) { 279 return false; 280 } 281 return this.getKillLocationsBetweenThisAndDominator().contains(location); 282 } 283 284 private LocationSet getKillLocationsBetweenThisAndDominator() { 285 if (this.killLocationsBetweenThisAndDominator == null) { 286 LocationSet dominatorResult = new LocationSet(); 287 Block stopBlock = getDominator(); 288 if (this.isLoopHeader()) { 289 assert stopBlock.getLoopDepth() < this.getLoopDepth(); 290 dominatorResult.addAll(((HIRLoop) this.getLoop()).getKillLocations()); 291 } else { 292 for (Block b : this.getPredecessors()) { 293 assert !this.isLoopHeader(); 294 if (b != stopBlock) { 295 dominatorResult.addAll(b.getKillLocations()); 296 if (dominatorResult.isAny()) { 297 break; 298 } 299 b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock); 300 if (dominatorResult.isAny()) { 301 break; 302 } 303 } 304 } 305 } 306 this.killLocationsBetweenThisAndDominator = dominatorResult; 307 } 308 return this.killLocationsBetweenThisAndDominator; 309 } 310 311 private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) { 312 assert AbstractControlFlowGraph.dominates(stopBlock, this); 313 if (stopBlock == this || result.isAny()) { 314 // We reached the stop block => nothing to do. 315 return; 316 } else { 317 if (stopBlock == this.getDominator()) { 318 result.addAll(this.getKillLocationsBetweenThisAndDominator()); 319 } else { 320 // Divide and conquer: Aggregate kill locations from this to the dominator and then 321 // from the dominator onwards. 322 calcKillLocationsBetweenThisAndTarget(result, this.getDominator()); 323 result.addAll(this.getDominator().getKillLocations()); 324 if (result.isAny()) { 325 return; 326 } 327 this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock); 328 } 329 } 330 } 331 332 @Override 333 public void delete() { 334 335 // adjust successor and predecessor lists 336 Block next = getSuccessors()[0]; 337 for (Block pred : getPredecessors()) { 338 Block[] predSuccs = pred.successors; 339 Block[] newPredSuccs = new Block[predSuccs.length]; 340 for (int i = 0; i < predSuccs.length; ++i) { 341 if (predSuccs[i] == this) { 342 newPredSuccs[i] = next; 343 } else { 344 newPredSuccs[i] = predSuccs[i]; 345 } 346 } 347 pred.setSuccessors(newPredSuccs); 348 } 349 350 ArrayList<Block> newPreds = new ArrayList<>(); 351 for (int i = 0; i < next.getPredecessorCount(); i++) { 352 Block curPred = next.getPredecessors()[i]; 353 if (curPred == this) { 354 for (Block b : getPredecessors()) { 355 newPreds.add(b); 356 } 357 } else { 358 newPreds.add(curPred); 359 } 360 } 361 362 next.setPredecessors(newPreds.toArray(new Block[0])); 363 } 364 365 protected void setPostDominator(Block postdominator) { 366 this.postdominator = postdominator; 367 } 368 }