1 /*
   2  * Copyright (c) 2017, 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.phases.common;
  26 
  27 import jdk.internal.vm.compiler.collections.EconomicMap;
  28 import jdk.internal.vm.compiler.collections.Equivalence;
  29 import jdk.internal.vm.compiler.collections.MapCursor;
  30 import org.graalvm.compiler.core.common.GraalOptions;
  31 import org.graalvm.compiler.core.common.cfg.BlockMap;
  32 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
  33 import org.graalvm.compiler.core.common.type.FloatStamp;
  34 import org.graalvm.compiler.core.common.type.Stamp;
  35 import org.graalvm.compiler.core.common.type.StampFactory;
  36 import org.graalvm.compiler.debug.CounterKey;
  37 import org.graalvm.compiler.debug.DebugContext;
  38 import org.graalvm.compiler.graph.Node;
  39 import org.graalvm.compiler.graph.NodeMap;
  40 import org.graalvm.compiler.graph.NodeStack;
  41 import org.graalvm.compiler.graph.Position;
  42 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
  43 import org.graalvm.compiler.nodeinfo.InputType;
  44 import org.graalvm.compiler.nodes.AbstractBeginNode;
  45 import org.graalvm.compiler.nodes.AbstractMergeNode;
  46 import org.graalvm.compiler.nodes.BinaryOpLogicNode;
  47 import org.graalvm.compiler.nodes.ConstantNode;
  48 import org.graalvm.compiler.nodes.EndNode;
  49 import org.graalvm.compiler.nodes.IfNode;
  50 import org.graalvm.compiler.nodes.LogicNode;
  51 import org.graalvm.compiler.nodes.MergeNode;
  52 import org.graalvm.compiler.nodes.NodeView;
  53 import org.graalvm.compiler.nodes.PhiNode;
  54 import org.graalvm.compiler.nodes.PiNode;
  55 import org.graalvm.compiler.nodes.StructuredGraph;
  56 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
  57 import org.graalvm.compiler.nodes.UnaryOpLogicNode;
  58 import org.graalvm.compiler.nodes.ValueNode;
  59 import org.graalvm.compiler.nodes.ValuePhiNode;
  60 import org.graalvm.compiler.nodes.calc.BinaryNode;
  61 import org.graalvm.compiler.nodes.calc.ConditionalNode;
  62 import org.graalvm.compiler.nodes.calc.UnaryNode;
  63 import org.graalvm.compiler.nodes.cfg.Block;
  64 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
  65 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph.RecursiveVisitor;
  66 import org.graalvm.compiler.nodes.extended.GuardingNode;
  67 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
  68 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
  69 import org.graalvm.compiler.nodes.memory.FloatingAccessNode;
  70 import org.graalvm.compiler.nodes.memory.FloatingReadNode;
  71 import org.graalvm.compiler.nodes.memory.MemoryAccess;
  72 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
  73 import org.graalvm.compiler.nodes.spi.CoreProviders;
  74 import org.graalvm.compiler.nodes.util.GraphUtil;
  75 import org.graalvm.compiler.options.OptionValues;
  76 import org.graalvm.compiler.phases.BasePhase;
  77 import org.graalvm.compiler.phases.Phase;
  78 import org.graalvm.compiler.phases.graph.ScheduledNodeIterator;
  79 import org.graalvm.compiler.phases.schedule.SchedulePhase;
  80 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
  81 import org.graalvm.compiler.phases.tiers.LowTierContext;
  82 
  83 import jdk.vm.ci.meta.Assumptions;
  84 import jdk.vm.ci.meta.Constant;
  85 import jdk.vm.ci.meta.ConstantReflectionProvider;
  86 import jdk.vm.ci.meta.MetaAccessProvider;
  87 import jdk.vm.ci.meta.TriState;
  88 
  89 /**
  90  * This phase lowers {@link FloatingReadNode FloatingReadNodes} into corresponding fixed reads.
  91  */
  92 public class FixReadsPhase extends BasePhase<LowTierContext> {
  93 
  94     private static final CounterKey counterStampsRegistered = DebugContext.counter("FixReads_StampsRegistered");
  95     private static final CounterKey counterIfsKilled = DebugContext.counter("FixReads_KilledIfs");
  96     private static final CounterKey counterConditionalsKilled = DebugContext.counter("FixReads_KilledConditionals");
  97     private static final CounterKey counterCanonicalizedSwitches = DebugContext.counter("FixReads_CanonicalizedSwitches");
  98     private static final CounterKey counterConstantReplacements = DebugContext.counter("FixReads_ConstantReplacement");
  99     private static final CounterKey counterConstantInputReplacements = DebugContext.counter("FixReads_ConstantInputReplacement");
 100     private static final CounterKey counterBetterMergedStamps = DebugContext.counter("FixReads_BetterMergedStamp");
 101 
 102     protected boolean replaceInputsWithConstants;
 103     protected Phase schedulePhase;
 104 
 105     @Override
 106     public float codeSizeIncrease() {
 107         return 2.0f;
 108     }
 109 
 110     private static class FixReadsClosure extends ScheduledNodeIterator {
 111 
 112         @Override
 113         protected void processNode(Node node) {
 114             if (node instanceof AbstractMergeNode) {
 115                 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
 116                 for (MemoryPhiNode memoryPhi : mergeNode.memoryPhis().snapshot()) {
 117                     // Memory phi nodes are no longer necessary at this point.
 118                     memoryPhi.replaceAtUsages(null);
 119                     memoryPhi.safeDelete();
 120                 }
 121             } else if (node instanceof FloatingAccessNode) {
 122                 FloatingAccessNode floatingAccessNode = (FloatingAccessNode) node;
 123                 floatingAccessNode.setLastLocationAccess(null);
 124                 GuardingNode guard = floatingAccessNode.getGuard();
 125                 if (guard != null) {
 126                     floatingAccessNode.setGuard(null);
 127                     GraphUtil.tryKillUnused(guard.asNode());
 128                 }
 129                 FixedAccessNode fixedAccess = floatingAccessNode.asFixedNode();
 130                 replaceCurrent(fixedAccess);
 131             } else if (node instanceof PiNode) {
 132                 PiNode piNode = (PiNode) node;
 133                 if (piNode.stamp(NodeView.DEFAULT).isCompatible(piNode.getOriginalNode().stamp(NodeView.DEFAULT))) {
 134                     // Pi nodes are no longer necessary at this point.
 135                     piNode.replaceAndDelete(piNode.getOriginalNode());
 136                 }
 137             } else if (node instanceof MemoryAccess) {
 138                 MemoryAccess memoryAccess = (MemoryAccess) node;
 139                 memoryAccess.setLastLocationAccess(null);
 140             }
 141         }
 142 
 143     }
 144 
 145     public static class RawConditionalEliminationVisitor implements RecursiveVisitor<Integer> {
 146 
 147         protected final NodeMap<StampElement> stampMap;
 148         protected final NodeStack undoOperations;
 149         private final ScheduleResult schedule;
 150         private final StructuredGraph graph;
 151         private final MetaAccessProvider metaAccess;
 152         private final boolean replaceConstantInputs;
 153         private final BlockMap<Integer> blockActionStart;
 154         private final EconomicMap<MergeNode, EconomicMap<ValueNode, Stamp>> endMaps;
 155         private final DebugContext debug;
 156         private final RawCanonicalizerTool rawCanonicalizerTool = new RawCanonicalizerTool();
 157 
 158         private class RawCanonicalizerTool implements NodeView, CanonicalizerTool {
 159 
 160             @Override
 161             public Assumptions getAssumptions() {
 162                 return graph.getAssumptions();
 163             }
 164 
 165             @Override
 166             public MetaAccessProvider getMetaAccess() {
 167                 return metaAccess;
 168             }
 169 
 170             @Override
 171             public ConstantReflectionProvider getConstantReflection() {
 172                 return null;
 173             }
 174 
 175             @Override
 176             public ConstantFieldProvider getConstantFieldProvider() {
 177                 return null;
 178             }
 179 
 180             @Override
 181             public boolean canonicalizeReads() {
 182                 return false;
 183             }
 184 
 185             @Override
 186             public boolean allUsagesAvailable() {
 187                 return true;
 188             }
 189 
 190             @Override
 191             public Integer smallestCompareWidth() {
 192                 return null;
 193             }
 194 
 195             @Override
 196             public OptionValues getOptions() {
 197                 return graph.getOptions();
 198             }
 199 
 200             @Override
 201             public Stamp stamp(ValueNode node) {
 202                 return getBestStamp(node);
 203             }
 204 
 205         }
 206 
 207         public RawConditionalEliminationVisitor(StructuredGraph graph, ScheduleResult schedule, MetaAccessProvider metaAccess, boolean replaceInputsWithConstants) {
 208             this.graph = graph;
 209             this.debug = graph.getDebug();
 210             this.schedule = schedule;
 211             this.metaAccess = metaAccess;
 212             blockActionStart = new BlockMap<>(schedule.getCFG());
 213             endMaps = EconomicMap.create(Equivalence.IDENTITY);
 214             stampMap = graph.createNodeMap();
 215             undoOperations = new NodeStack();
 216             replaceConstantInputs = replaceInputsWithConstants && GraalOptions.ReplaceInputsWithConstantsBasedOnStamps.getValue(graph.getOptions());
 217         }
 218 
 219         protected void replaceInput(Position p, Node oldInput, Node newConstantInput) {
 220             p.set(oldInput, newConstantInput);
 221         }
 222 
 223         protected int replaceConstantInputs(Node node) {
 224             int replacements = 0;
 225             // Check if we can replace any of the inputs with a constant.
 226             for (Position p : node.inputPositions()) {
 227                 Node input = p.get(node);
 228                 if (p.getInputType() == InputType.Value) {
 229                     if (input instanceof ValueNode) {
 230                         ValueNode valueNode = (ValueNode) input;
 231                         if (valueNode instanceof ConstantNode) {
 232                             // Input already is a constant.
 233                         } else {
 234                             Stamp bestStamp = getBestStamp(valueNode);
 235                             Constant constant = bestStamp.asConstant();
 236                             if (constant != null) {
 237                                 if (bestStamp instanceof FloatStamp) {
 238                                     FloatStamp floatStamp = (FloatStamp) bestStamp;
 239                                     if (floatStamp.contains(0.0d)) {
 240                                         // Could also be -0.0d.
 241                                         continue;
 242                                     }
 243                                 }
 244                                 counterConstantInputReplacements.increment(node.getDebug());
 245                                 ConstantNode stampConstant = ConstantNode.forConstant(bestStamp, constant, metaAccess, graph);
 246                                 assert stampConstant.stamp(NodeView.DEFAULT).isCompatible(valueNode.stamp(NodeView.DEFAULT));
 247                                 replaceInput(p, node, stampConstant);
 248                                 replacements++;
 249                             }
 250                         }
 251                     }
 252                 }
 253             }
 254             return replacements;
 255         }
 256 
 257         protected void processNode(Node node) {
 258             assert node.isAlive();
 259 
 260             if (replaceConstantInputs) {
 261                 replaceConstantInputs(node);
 262             }
 263 
 264             if (node instanceof MergeNode) {
 265                 registerCombinedStamps((MergeNode) node);
 266             }
 267 
 268             if (node instanceof AbstractBeginNode) {
 269                 processAbstractBegin((AbstractBeginNode) node);
 270             } else if (node instanceof IfNode) {
 271                 processIf((IfNode) node);
 272             } else if (node instanceof IntegerSwitchNode) {
 273                 processIntegerSwitch((IntegerSwitchNode) node);
 274             } else if (node instanceof BinaryNode) {
 275                 processBinary((BinaryNode) node);
 276             } else if (node instanceof ConditionalNode) {
 277                 processConditional((ConditionalNode) node);
 278             } else if (node instanceof UnaryNode) {
 279                 processUnary((UnaryNode) node);
 280             } else if (node instanceof EndNode) {
 281                 processEnd((EndNode) node);
 282             }
 283         }
 284 
 285         protected void registerCombinedStamps(MergeNode node) {
 286             EconomicMap<ValueNode, Stamp> endMap = endMaps.get(node);
 287             MapCursor<ValueNode, Stamp> entries = endMap.getEntries();
 288             while (entries.advance()) {
 289                 ValueNode value = entries.getKey();
 290                 if (value.isDeleted()) {
 291                     // nodes from this map can be deleted when a loop dies
 292                     continue;
 293                 }
 294                 if (registerNewValueStamp(value, entries.getValue())) {
 295                     counterBetterMergedStamps.increment(debug);
 296                 }
 297             }
 298         }
 299 
 300         protected void processEnd(EndNode node) {
 301             AbstractMergeNode abstractMerge = node.merge();
 302             if (abstractMerge instanceof MergeNode) {
 303                 MergeNode merge = (MergeNode) abstractMerge;
 304 
 305                 NodeMap<Block> blockToNodeMap = this.schedule.getNodeToBlockMap();
 306                 Block mergeBlock = blockToNodeMap.get(merge);
 307                 Block mergeBlockDominator = mergeBlock.getDominator();
 308                 Block currentBlock = blockToNodeMap.get(node);
 309 
 310                 EconomicMap<ValueNode, Stamp> currentEndMap = endMaps.get(merge);
 311 
 312                 if (currentEndMap == null || !currentEndMap.isEmpty()) {
 313 
 314                     EconomicMap<ValueNode, Stamp> endMap = EconomicMap.create(Equivalence.IDENTITY);
 315 
 316                     // Process phis
 317                     for (ValuePhiNode phi : merge.valuePhis()) {
 318                         if (currentEndMap == null || currentEndMap.containsKey(phi)) {
 319                             ValueNode valueAt = phi.valueAt(node);
 320                             Stamp bestStamp = getBestStamp(valueAt);
 321 
 322                             if (currentEndMap != null) {
 323                                 bestStamp = bestStamp.meet(currentEndMap.get(phi));
 324                             }
 325 
 326                             if (!bestStamp.equals(phi.stamp(NodeView.DEFAULT))) {
 327                                 endMap.put(phi, bestStamp);
 328                             }
 329                         }
 330                     }
 331 
 332                     int lastMark = undoOperations.size();
 333                     while (currentBlock != mergeBlockDominator) {
 334                         int mark = blockActionStart.get(currentBlock);
 335                         for (int i = lastMark - 1; i >= mark; --i) {
 336                             ValueNode nodeWithNewStamp = (ValueNode) undoOperations.get(i);
 337 
 338                             if (nodeWithNewStamp.isDeleted() || nodeWithNewStamp instanceof LogicNode || nodeWithNewStamp instanceof ConstantNode || blockToNodeMap.isNew(nodeWithNewStamp)) {
 339                                 continue;
 340                             }
 341 
 342                             Block block = getBlock(nodeWithNewStamp, blockToNodeMap);
 343                             if (block == null || block.getId() <= mergeBlockDominator.getId()) {
 344                                 // Node with new stamp in path to the merge block dominator and that
 345                                 // at the same time was defined at least in the merge block
 346                                 // dominator (i.e., therefore can be used after the merge.)
 347 
 348                                 Stamp bestStamp = getBestStamp(nodeWithNewStamp);
 349                                 assert bestStamp != null;
 350 
 351                                 if (currentEndMap != null) {
 352                                     Stamp otherEndsStamp = currentEndMap.get(nodeWithNewStamp);
 353                                     if (otherEndsStamp == null) {
 354                                         // No stamp registered in one of the previously processed
 355                                         // ends => skip.
 356                                         continue;
 357                                     }
 358                                     bestStamp = bestStamp.meet(otherEndsStamp);
 359                                 }
 360 
 361                                 if (nodeWithNewStamp.stamp(NodeView.DEFAULT).tryImproveWith(bestStamp) == null) {
 362                                     // No point in registering the stamp.
 363                                 } else {
 364                                     endMap.put(nodeWithNewStamp, bestStamp);
 365                                 }
 366                             }
 367                         }
 368                         currentBlock = currentBlock.getDominator();
 369                     }
 370 
 371                     endMaps.put(merge, endMap);
 372                 }
 373             }
 374         }
 375 
 376         private static Block getBlock(ValueNode node, NodeMap<Block> blockToNodeMap) {
 377             if (node instanceof PhiNode) {
 378                 PhiNode phiNode = (PhiNode) node;
 379                 return blockToNodeMap.get(phiNode.merge());
 380             }
 381             return blockToNodeMap.get(node);
 382         }
 383 
 384         protected void processUnary(UnaryNode node) {
 385             ValueNode value = node.getValue();
 386             Stamp bestStamp = getBestStamp(value);
 387             Stamp newStamp = node.foldStamp(bestStamp);
 388             if (!checkReplaceWithConstant(newStamp, node)) {
 389                 if (!bestStamp.equals(value.stamp(NodeView.DEFAULT))) {
 390                     ValueNode newNode = node.canonical(rawCanonicalizerTool);
 391                     if (newNode != node) {
 392                         // Canonicalization successfully triggered.
 393                         if (newNode != null && !newNode.isAlive()) {
 394                             newNode = graph.addWithoutUniqueWithInputs(newNode);
 395                         }
 396                         node.replaceAndDelete(newNode);
 397                         GraphUtil.tryKillUnused(value);
 398                         return;
 399                     }
 400                 }
 401                 registerNewValueStamp(node, newStamp);
 402             }
 403         }
 404 
 405         protected boolean checkReplaceWithConstant(Stamp newStamp, ValueNode node) {
 406             Constant constant = newStamp.asConstant();
 407             if (constant != null && !(node instanceof ConstantNode)) {
 408                 ConstantNode stampConstant = ConstantNode.forConstant(newStamp, constant, metaAccess, graph);
 409                 debug.log("RawConditionElimination: constant stamp replaces %1s with %1s", node, stampConstant);
 410                 counterConstantReplacements.increment(debug);
 411                 node.replaceAtUsages(InputType.Value, stampConstant);
 412                 GraphUtil.tryKillUnused(node);
 413                 return true;
 414             }
 415             return false;
 416         }
 417 
 418         protected void processBinary(BinaryNode node) {
 419 
 420             ValueNode x = node.getX();
 421             ValueNode y = node.getY();
 422 
 423             Stamp xStamp = getBestStamp(x);
 424             Stamp yStamp = getBestStamp(y);
 425             Stamp newStamp = node.foldStamp(xStamp, yStamp);
 426             if (!checkReplaceWithConstant(newStamp, node)) {
 427 
 428                 if (!xStamp.equals(x.stamp(NodeView.DEFAULT)) || !yStamp.equals(y.stamp(NodeView.DEFAULT))) {
 429                     // At least one of the inputs has an improved stamp => attempt to canonicalize
 430                     // based on that improvement.
 431                     ValueNode newNode = node.canonical(rawCanonicalizerTool);
 432                     if (newNode != node) {
 433                         // Canonicalization successfully triggered.
 434                         if (newNode != null && !newNode.isAlive()) {
 435                             newNode = graph.addWithoutUniqueWithInputs(newNode);
 436                         }
 437                         node.replaceAndDelete(newNode);
 438                         GraphUtil.tryKillUnused(x);
 439                         GraphUtil.tryKillUnused(y);
 440                         return;
 441                     }
 442                 }
 443 
 444                 registerNewValueStamp(node, newStamp);
 445             }
 446         }
 447 
 448         protected void processIntegerSwitch(IntegerSwitchNode node) {
 449             Stamp bestStamp = getBestStamp(node.value());
 450             if (node.tryRemoveUnreachableKeys(null, bestStamp)) {
 451                 debug.log("\t Canonicalized integer switch %s for value %s and stamp %s", node, node.value(), bestStamp);
 452                 counterCanonicalizedSwitches.increment(debug);
 453             }
 454         }
 455 
 456         protected void processIf(IfNode node) {
 457             TriState result = tryProveCondition(node.condition());
 458             if (result != TriState.UNKNOWN) {
 459                 boolean isTrue = (result == TriState.TRUE);
 460                 AbstractBeginNode survivingSuccessor = node.getSuccessor(isTrue);
 461                 survivingSuccessor.replaceAtUsages(null);
 462                 survivingSuccessor.replaceAtPredecessor(null);
 463                 node.replaceAtPredecessor(survivingSuccessor);
 464                 GraphUtil.killCFG(node);
 465 
 466                 counterIfsKilled.increment(debug);
 467             }
 468         }
 469 
 470         protected void processConditional(ConditionalNode node) {
 471             TriState result = tryProveCondition(node.condition());
 472             if (result != TriState.UNKNOWN) {
 473                 boolean isTrue = (result == TriState.TRUE);
 474                 counterConditionalsKilled.increment(debug);
 475                 node.replaceAndDelete(isTrue ? node.trueValue() : node.falseValue());
 476             } else {
 477                 Stamp trueStamp = getBestStamp(node.trueValue());
 478                 Stamp falseStamp = getBestStamp(node.falseValue());
 479                 registerNewStamp(node, trueStamp.meet(falseStamp));
 480             }
 481         }
 482 
 483         protected TriState tryProveCondition(LogicNode condition) {
 484             Stamp conditionStamp = this.getBestStamp(condition);
 485             if (conditionStamp == StampFactory.tautology()) {
 486                 return TriState.TRUE;
 487             } else if (conditionStamp == StampFactory.contradiction()) {
 488                 return TriState.FALSE;
 489             }
 490 
 491             if (condition instanceof UnaryOpLogicNode) {
 492                 UnaryOpLogicNode unaryOpLogicNode = (UnaryOpLogicNode) condition;
 493                 return unaryOpLogicNode.tryFold(this.getBestStamp(unaryOpLogicNode.getValue()));
 494             } else if (condition instanceof BinaryOpLogicNode) {
 495                 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
 496                 return binaryOpLogicNode.tryFold(this.getBestStamp(binaryOpLogicNode.getX()), this.getBestStamp(binaryOpLogicNode.getY()));
 497             }
 498 
 499             return TriState.UNKNOWN;
 500         }
 501 
 502         protected void processAbstractBegin(AbstractBeginNode beginNode) {
 503             Node predecessor = beginNode.predecessor();
 504             if (predecessor instanceof IfNode) {
 505                 IfNode ifNode = (IfNode) predecessor;
 506                 boolean negated = (ifNode.falseSuccessor() == beginNode);
 507                 LogicNode condition = ifNode.condition();
 508                 registerNewCondition(condition, negated);
 509             } else if (predecessor instanceof IntegerSwitchNode) {
 510                 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
 511                 registerIntegerSwitch(beginNode, integerSwitchNode);
 512             }
 513         }
 514 
 515         private void registerIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
 516             registerNewValueStamp(integerSwitchNode.value(), integerSwitchNode.getValueStampForSuccessor(beginNode));
 517         }
 518 
 519         protected void registerNewCondition(LogicNode condition, boolean negated) {
 520             if (condition instanceof UnaryOpLogicNode) {
 521                 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
 522                 ValueNode value = unaryLogicNode.getValue();
 523                 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
 524                 registerNewValueStamp(value, newStamp);
 525             } else if (condition instanceof BinaryOpLogicNode) {
 526                 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
 527                 ValueNode x = binaryOpLogicNode.getX();
 528                 ValueNode y = binaryOpLogicNode.getY();
 529                 Stamp xStamp = getBestStamp(x);
 530                 Stamp yStamp = getBestStamp(y);
 531                 registerNewValueStamp(x, binaryOpLogicNode.getSucceedingStampForX(negated, xStamp, yStamp));
 532                 registerNewValueStamp(y, binaryOpLogicNode.getSucceedingStampForY(negated, xStamp, yStamp));
 533             }
 534             registerCondition(condition, negated);
 535         }
 536 
 537         protected void registerCondition(LogicNode condition, boolean negated) {
 538             registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology());
 539         }
 540 
 541         protected boolean registerNewValueStamp(ValueNode value, Stamp newStamp) {
 542             if (newStamp != null && !value.isConstant()) {
 543                 Stamp currentStamp = getBestStamp(value);
 544                 Stamp betterStamp = currentStamp.tryImproveWith(newStamp);
 545                 if (betterStamp != null) {
 546                     registerNewStamp(value, betterStamp);
 547                     return true;
 548                 }
 549             }
 550             return false;
 551         }
 552 
 553         protected void registerNewStamp(ValueNode value, Stamp newStamp) {
 554             counterStampsRegistered.increment(debug);
 555             debug.log("\t Saving stamp for node %s stamp %s", value, newStamp);
 556             ValueNode originalNode = value;
 557             stampMap.setAndGrow(originalNode, new StampElement(newStamp, stampMap.getAndGrow(originalNode)));
 558             undoOperations.push(originalNode);
 559         }
 560 
 561         protected Stamp getBestStamp(ValueNode value) {
 562             ValueNode originalNode = value;
 563             if (!value.isAlive()) {
 564                 return value.stamp(NodeView.DEFAULT);
 565             }
 566 
 567             StampElement currentStamp = stampMap.getAndGrow(originalNode);
 568             if (currentStamp == null) {
 569                 return value.stamp(NodeView.DEFAULT);
 570             }
 571             return currentStamp.getStamp();
 572         }
 573 
 574         @Override
 575         public Integer enter(Block b) {
 576             int mark = undoOperations.size();
 577             blockActionStart.put(b, mark);
 578             for (Node n : schedule.getBlockToNodesMap().get(b)) {
 579                 if (n.isAlive()) {
 580                     processNode(n);
 581                 }
 582             }
 583             return mark;
 584         }
 585 
 586         @Override
 587         public void exit(Block b, Integer state) {
 588             int mark = state;
 589             while (undoOperations.size() > mark) {
 590                 Node node = undoOperations.pop();
 591                 if (node.isAlive()) {
 592                     stampMap.set(node, stampMap.get(node).getParent());
 593                 }
 594             }
 595         }
 596 
 597     }
 598 
 599     public FixReadsPhase(boolean replaceInputsWithConstants, Phase schedulePhase) {
 600         this.replaceInputsWithConstants = replaceInputsWithConstants;
 601         this.schedulePhase = schedulePhase;
 602     }
 603 
 604     @Override
 605     protected void run(StructuredGraph graph, LowTierContext context) {
 606         schedulePhase.apply(graph);
 607         ScheduleResult schedule = graph.getLastSchedule();
 608         FixReadsClosure fixReadsClosure = new FixReadsClosure();
 609         for (Block block : schedule.getCFG().getBlocks()) {
 610             fixReadsClosure.processNodes(block, schedule);
 611         }
 612         if (GraalOptions.RawConditionalElimination.getValue(graph.getOptions())) {
 613             schedule.getCFG().visitDominatorTree(createVisitor(graph, schedule, context), false);
 614         }
 615         graph.setAfterFixReadPhase(true);
 616     }
 617 
 618     public static class RawCEPhase extends BasePhase<LowTierContext> {
 619 
 620         private final boolean replaceInputsWithConstants;
 621 
 622         public RawCEPhase(boolean replaceInputsWithConstants) {
 623             this.replaceInputsWithConstants = replaceInputsWithConstants;
 624         }
 625 
 626         @Override
 627         protected CharSequence getName() {
 628             return "RawCEPhase";
 629         }
 630 
 631         @Override
 632         protected void run(StructuredGraph graph, LowTierContext context) {
 633             if (GraalOptions.RawConditionalElimination.getValue(graph.getOptions())) {
 634                 SchedulePhase schedulePhase = new SchedulePhase(SchedulingStrategy.LATEST, true);
 635                 schedulePhase.apply(graph);
 636                 ScheduleResult schedule = graph.getLastSchedule();
 637                 schedule.getCFG().visitDominatorTree(new RawConditionalEliminationVisitor(graph, schedule, context.getMetaAccess(), replaceInputsWithConstants), false);
 638             }
 639         }
 640     }
 641 
 642     protected ControlFlowGraph.RecursiveVisitor<?> createVisitor(StructuredGraph graph, ScheduleResult schedule, CoreProviders context) {
 643         return new RawConditionalEliminationVisitor(graph, schedule, context.getMetaAccess(), replaceInputsWithConstants);
 644     }
 645 
 646     protected static final class StampElement {
 647         private final Stamp stamp;
 648         private final StampElement parent;
 649 
 650         public StampElement(Stamp stamp, StampElement parent) {
 651             this.stamp = stamp;
 652             this.parent = parent;
 653         }
 654 
 655         public StampElement getParent() {
 656             return parent;
 657         }
 658 
 659         public Stamp getStamp() {
 660             return stamp;
 661         }
 662 
 663         @Override
 664         public String toString() {
 665             StringBuilder result = new StringBuilder();
 666             result.append(stamp);
 667             if (this.parent != null) {
 668                 result.append(" (");
 669                 result.append(this.parent.toString());
 670                 result.append(")");
 671             }
 672             return result.toString();
 673         }
 674     }
 675 
 676     public void setReplaceInputsWithConstants(boolean replaceInputsWithConstants) {
 677         this.replaceInputsWithConstants = replaceInputsWithConstants;
 678     }
 679 }