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