Mercurial > hg > truffle
view graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java @ 10672:e7d07c9bb779
Removed priority compilation queue.
Fixed another race condition in the compilation queue.
Removed Graal-specific compilation policy.
author | Christian Haeubl <haeubl@ssw.jku.at> |
---|---|
date | Tue, 09 Jul 2013 17:53:58 +0200 |
parents | 50f02c7d1cec |
children | 96bb07a5d667 |
line wrap: on
line source
/* * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package com.oracle.graal.nodes.util; import java.util.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; public final class ComputeImmediateDominator { private final MergeNode dominated; private final Queue<FixedNode> toExplore; private final Queue<FixedNode> speculativeExplore; private final NodeMap<DominatorInfo> infoMap; private final DominatorInfo fullInfo; private FixedNode dominator; private int nextBit = 1; public ComputeImmediateDominator(MergeNode dominated) { this.dominated = dominated; this.toExplore = new LinkedList<>(); this.speculativeExplore = new LinkedList<>(); this.infoMap = dominated.graph().createNodeMap(); fullInfo = new DominatorInfo(dominated, true); this.processMerge(dominated, fullInfo); if (toExplore.size() == 1) { dominator = toExplore.remove(); } } public FixedNode compute() { try { while (dominator == null && (!toExplore.isEmpty() || !speculativeExplore.isEmpty())) { while (!toExplore.isEmpty()) { exploreUp(toExplore.remove()); if (dominator != null) { return dominator; } } exploreUp(speculativeExplore.remove()); } return dominator; } catch (Throwable t) { throw new GraalInternalError(t).addContext("Could not find a dominator").addContext(dominated); } } private void exploreUp(FixedNode from) { FixedNode p = from; DominatorInfo info = infoMap.get(from); if (info.isExplored()) { return; } // TTY.println("exploreUp(" + from + ") with " + info); info.setExplored(); while (p != null) { if (p instanceof MergeNode) { processMerge((MergeNode) p, info); p = null; } else if (p instanceof ControlSplitNode) { processControlSplit((ControlSplitNode) p, info); p = null; } else { p = (FixedNode) p.predecessor(); } } } private void processControlSplit(ControlSplitNode cs, DominatorInfo info) { // TTY.println("processControlSplit(" + cs + ", " + info + ")"); DominatorInfo csInfo = infoMap.get(cs); if (csInfo == null) { csInfo = new DominatorInfo(cs, false); infoMap.set(cs, csInfo); } csInfo.add(info); FixedNode next = (FixedNode) cs.predecessor(); if (checkControlSplitInfo(csInfo)) { return; } if (csInfo.isExplored()) { // TTY.println(" Already explored, propagate update"); propagateUpdate(csInfo); } else { if (csInfo.parentCount() == cs.successors().count()) { // all paths leading to this CS // have been explored // TTY.println(" All parents explored, Enqueue"); toExplore.add(next); speculativeExplore.remove(next); } else { // TTY.println(" Not all parents explored : Enqueue speculative"); speculativeExplore.add(next); } } infoMap.set(next, csInfo); } private boolean propagateUpdate(DominatorInfo di) { // TTY.println(" propagateUpdate(" + di + ")"); for (DominatorInfo child : di.children()) { // TTY.println(" add to child " + child); if (child.add(di, false)) { if (child.equals(fullInfo)) { // TTY.println(" Found DOM!"); dominator = child.node(); return true; } if (propagateUpdate(child)) { return true; } } } return false; } private boolean checkControlSplitInfo(DominatorInfo di) { // TTY.println(" checkControlSplitInfo(" + di + ")"); if (di.equals(fullInfo)) { dominator = di.node(); // TTY.println(" Found DOM!"); return true; } return false; } private void processMerge(MergeNode merge, DominatorInfo info) { // TTY.println("processMerge(" + merge + ", " + info + ")"); for (AbstractEndNode end : merge.cfgPredecessors()) { toExplore.add(end); infoMap.set(end, info.createChild(end)); // TTY.println(" Enqueue end : " + end + " with " + infoMap.get(end)); } } private class DominatorInfo { private final FixedNode node; private final BitSet bits; private final BitSet ownBits; private final Collection<DominatorInfo> children; private final Collection<DominatorInfo> parents; private boolean explored; public DominatorInfo(FixedNode node, boolean full) { this.node = node; this.bits = new BitSet(); this.ownBits = new BitSet(); this.children = new ArrayList<>(2); this.parents = new ArrayList<>(2); if (full) { addOwnBits(0); } } public boolean isExplored() { return explored; } public void setExplored() { explored = true; } public DominatorInfo createChild(FixedNode childNode) { DominatorInfo di = new DominatorInfo(childNode, false); di.bits.or(bits); di.ownBits.or(ownBits); if (!children.isEmpty() || di.ownBits.isEmpty()) { int newBit = nextBit++; di.bits.xor(ownBits); di.bits.set(newBit); di.ownBits.clear(); di.ownBits.set(newBit); addOwnBits(newBit); } children.add(di); di.parents.add(this); return di; } private void addOwnBits(int newBit) { if (!bits.get(newBit)) { ownBits.set(newBit); bits.set(newBit); for (DominatorInfo parent : parents) { parent.addOwnBits(newBit); } } } public boolean add(DominatorInfo i) { return add(i, true); } public boolean add(DominatorInfo i, boolean addParent) { boolean ret = true; if (addParent) { parents.add(i); i.children.add(this); bits.or(i.bits); } else { BitSet newBits = (BitSet) i.bits.clone(); newBits.andNot(bits); newBits.andNot(i.ownBits); ret = !newBits.isEmpty(); bits.or(newBits); } return ret; } public int parentCount() { return parents.size(); } public FixedNode node() { return node; } public Collection<DominatorInfo> children() { return children; } @Override public boolean equals(Object obj) { if (!(obj instanceof DominatorInfo)) { return false; } return ((DominatorInfo) obj).bits.equals(bits); } @Override public String toString() { return bits + " (o" + ownBits + ") " + node; } @Override public int hashCode() { return bits.hashCode(); } } }