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.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 }