tools/pldt/org.eclipse.ptp.pldt.openmp.analysis/src/org/eclipse/ptp/pldt/openmp/analysis/ompcfg/factory/PhaseAnalysisFactory.java - ptp/org.eclipse.ptp - Git at Google

 /**********************************************************************
  * Copyright (c) 2006 IBM Corporation.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *******************************************************************************/

 package org.eclipse.ptp.pldt.openmp.analysis.ompcfg.factory;

 import java.util.HashSet;
 import java.util.Hashtable;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.Stack;

 import org.eclipse.ptp.pldt.openmp.analysis.PAST.PASTOMPPragma;
 import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFG;
 import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFGNode;
 import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPDFS;
 import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPPragmaNode;

 /**
  * Main Algorithm -
  *
  * Given: the start node of a control flow graph (OMPCFG)
  * Output: a set of barrier phases
  *
  * 1) Start the algorithm using the start node of the cfg
  * 2) For each barrier reached by a DFS, said barrier neither prior processed
  * nor on the stack, push onto stack, and start fresh DFS on new barrier
  * 3) For each node encountered
  * a) if node is in a phase having its initial barrier match with top barrier
  * on the stack, add all nodes after that top barrier to that phase.
  * b) if node is a barrier, build phase, add nodes on stack from penultimate
  * barrier
  * 4) When a DFS completes, pop the stack
  * 5) Terminate when the stack is empty
  *
  */

 public class PhaseAnalysisFactory
 {
 	protected OMPCFG cfg_ = null;
 	protected OMPCFGNode termNode_ = null;

 	protected Stack barrierStack_ = new Stack(); // of DFSWalk's
 	protected HashSet finishedBarriers_ = new HashSet(); // of barriers that are finished being
 															// traversed from
 	protected LinkedList phases_ = new LinkedList(); // of PhaseConcurrencyAnalysis's

 	// A common search we do is, for a given node, and a given barrier, find all
 	// phases that
 	// a) contain that node
 	// b) have that barrier as the starting barrier of the phase
 	// Solution: map each node to a list of phases to which it belongs.
 	// The list should be sparse, for filtering out the phases that
 	// begin with a particular barrier should be inexpensive.
 	protected Hashtable nodeToPhases_ = new Hashtable();

 	/**
 	 * PhaseAnalysisFactory - Constructor
 	 *
 	 * @param cfg
 	 *            - OMPCFG
 	 */
 	public PhaseAnalysisFactory(OMPCFG cfg)
 	{
 		cfg_ = cfg;
 		termNode_ = cfg_.getTermNode();
 	}

 	public void buildPhases()
 	{
 		// Set up the first statement
 		OMPCFGNode node = cfg_.getRoot();
 		if (!(node instanceof OMPPragmaNode))
 			return; // required
 		DFSWalk pc = new DFSWalk((OMPPragmaNode) node);
 		barrierStack_.push(pc);
 		pc.trigger();
 	}

 	/**
 	 * findPhase - find a specified phase and add it
 	 *
 	 * @param bNode
 	 *            - OMPPragmaNode
 	 * @param eNode
 	 *            - OMPPragmaNode
 	 * @param addNew
 	 *            - boolean
 	 * @return PhaseConcurrencyAnalysis
 	 */
 	protected PhaseConcurrencyAnalysis findPhase(OMPPragmaNode bNode, OMPPragmaNode eNode, boolean addNew)
 	{
 		// Find the phase that starts and ends with these TODO: make more efficient
 		for (Iterator i = phases_.iterator(); i.hasNext();) {
 			PhaseConcurrencyAnalysis phase = (PhaseConcurrencyAnalysis) i.next();
 			if (phase.getBeginNode() == bNode && phase.getEndNode() == eNode)
 				return phase;
 		}
 		if (!addNew)
 			return null;

 		PhaseConcurrencyAnalysis phase = new PhaseConcurrencyAnalysis(bNode, eNode);
 		phases_.add(phase);
 		return phase;
 	}

 	/**
 	 * addNodesToPhase - add a list of nodes to a specific phase
 	 *
 	 * @param phase
 	 *            - PhaseConcurrencyAnalysis
 	 * @param nodes
 	 *            - OMPCFGNode []
 	 */
 	protected void addNodesToPhase(PhaseConcurrencyAnalysis phase, OMPCFGNode[] nodes)
 	{
 		for (int i = 0; i < nodes.length; i++) {
 			phase.add(nodes[i]);
 			mapNodeToPhase(nodes[i], phase);
 		}
 	}

 	protected boolean isFinished(OMPPragmaNode pNode)
 	{
 		return finishedBarriers_.contains(pNode);
 	}

 	protected boolean isOnBarrierStack(OMPPragmaNode pNode)
 	{
 		for (Iterator i = barrierStack_.iterator(); i.hasNext();) {
 			DFSWalk dw = (DFSWalk) i.next();
 			if (dw.getPragmaNode() == pNode)
 				return true;
 		}
 		return false;
 	}

 	protected LinkedList memberPhases(OMPCFGNode node)
 	{
 		return (LinkedList) nodeToPhases_.get(node);
 	}

 	/**
 	 * mapNodeToPhase - map a given node to a given phase in the node-phase map
 	 *
 	 * @param node
 	 *            - OMPCFGNode
 	 * @param phase
 	 *            - PhaseConcurrencyAnalysis
 	 */
 	protected void mapNodeToPhase(OMPCFGNode node, PhaseConcurrencyAnalysis phase)
 	{
 		LinkedList l = (LinkedList) nodeToPhases_.get(node);
 		if (l == null) {
 			l = new LinkedList();
 			nodeToPhases_.put(node, l);
 		}
 		if (!l.contains(phase))
 			l.add(phase);
 	}

 	/**
 	 * getPhases - produce a list of all phases produced from this analysis
 	 *
 	 * @return PhaseConcurrencyAnalysis []
 	 */
 	public PhaseConcurrencyAnalysis[] getPhases()
 	{
 		PhaseConcurrencyAnalysis[] l = new PhaseConcurrencyAnalysis[phases_.size()];
 		int count = 0;
 		for (Iterator i = phases_.iterator(); i.hasNext();)
 			l[count++] = (PhaseConcurrencyAnalysis) i.next();
 		return l;
 	}

 	// *************************************************************************
 	// DFSWalk
 	// *************************************************************************
 	protected class DFSWalk extends OMPDFS
 	{
 		protected OMPPragmaNode phaseBeginNode_ = null;

 		public DFSWalk(OMPPragmaNode phaseBeginNode)
 		{
 			super(phaseBeginNode);
 			phaseBeginNode_ = phaseBeginNode;
 		}

 		public OMPPragmaNode getPragmaNode()
 		{
 			return phaseBeginNode_;
 		}

 		/**
 		 * trigger - begin the process of walking the graph
 		 *
 		 */
 		public void trigger()
 		{
 			this.startWalking();
 		}

 		/**
 		 * visit - visit method - what the user usually overrides
 		 *
 		 * @param node
 		 *            - OMPCFGNode
 		 * @return int (see OMPDFS codes)
 		 */
 		public int visit(OMPCFGNode node)
 		{
 			if (node instanceof OMPPragmaNode) {
 				OMPPragmaNode pragmaNode = (OMPPragmaNode) node;
 				if (pragmaNode.getPragma() != null && pragmaNode.getPragma().getOMPType() != PASTOMPPragma.OmpBarrier)
 					return OMPDFS.CONTINUE;
 				// If at beginning of stack again, keep moving on
 				if (getNodeStackSize() == 1)
 					return OMPDFS.CONTINUE;
 				// If necessary, create a new phase and add to list of phases
 				PhaseConcurrencyAnalysis phase = findPhase(phaseBeginNode_, pragmaNode, true);
 				addNodesToPhase(phase, getNodeStack());
 				// If barrier is completed or is on stack, we skip searching forward
 				if (isFinished(pragmaNode) || isOnBarrierStack(pragmaNode))
 					return OMPDFS.SKIP;
 				// Create a new walk to the next segments - increase the stack
 				// NOTE: we may have to skip the followin for implict barrier
 				DFSWalk pc = new DFSWalk(pragmaNode);
 				barrierStack_.push(pc);
 				pc.trigger();
 				// above finished walking, pop the stack, and skip on this level
 				barrierStack_.pop();
 				return OMPDFS.SKIP;
 			}
 			else if (node == termNode_) { // this is an implicit barrier, but not further dfs
 				if (getNodeStackSize() == 1)
 					return OMPDFS.CONTINUE;
 				return OMPDFS.CONTINUE;
 			}

 			// For each visited successor node, add node stack to all phases the successor
 			// belongs to, said successor phase beginning with phaseBeginNode_
 			// Note: we should not bother with phases that begin with other than phaseBeginNode_ -
 			// as then we would have to account for partial paths from other such phases,
 			// which we do not have (we glom all nodes together, no paths). That was why
 			// we do fresh searches starting at new barriers.
 			OMPCFGNode[] nodes = node.getOutNodes();
 			for (int i = 0; i < nodes.length; i++) {
 				if (isVisited(nodes[i])) {
 					LinkedList l = memberPhases(nodes[i]);
 					OMPCFGNode[] nodeStack = getNodeStack();
 					Object[] listArray = l.toArray(); // safer to use this, l may get modified
 					for (int j = 0; j < listArray.length; j++) {
 						PhaseConcurrencyAnalysis phase = (PhaseConcurrencyAnalysis) listArray[j];
 						if (phase.getBeginNode() == phaseBeginNode_)
 							addNodesToPhase(phase, nodeStack);
 					}
 				}
 			}

 			return OMPDFS.CONTINUE;
 		}

 		/**
 		 * atStartNode - check if we are at the 1st node of the search
 		 *
 		 * @param node
 		 * @return
 		 */
 		protected boolean atStartNode(OMPCFGNode node)
 		{
 			return (node == phaseBeginNode_ && getNodeStackSize() == 1);
 		}

 	}
 }
	/**********************************************************************
	* Copyright (c) 2006 IBM Corporation.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	*******************************************************************************/

	package org.eclipse.ptp.pldt.openmp.analysis.ompcfg.factory;

	import java.util.HashSet;
	import java.util.Hashtable;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.Stack;

	import org.eclipse.ptp.pldt.openmp.analysis.PAST.PASTOMPPragma;
	import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFG;
	import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFGNode;
	import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPDFS;
	import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPPragmaNode;

	/**
	* Main Algorithm -
	*
	* Given: the start node of a control flow graph (OMPCFG)
	* Output: a set of barrier phases
	*
	* 1) Start the algorithm using the start node of the cfg
	* 2) For each barrier reached by a DFS, said barrier neither prior processed
	* nor on the stack, push onto stack, and start fresh DFS on new barrier
	* 3) For each node encountered
	* a) if node is in a phase having its initial barrier match with top barrier
	* on the stack, add all nodes after that top barrier to that phase.
	* b) if node is a barrier, build phase, add nodes on stack from penultimate
	* barrier
	* 4) When a DFS completes, pop the stack
	* 5) Terminate when the stack is empty
	*
	*/

	public class PhaseAnalysisFactory
	{
	protected OMPCFG cfg_ = null;
	protected OMPCFGNode termNode_ = null;

	protected Stack barrierStack_ = new Stack(); // of DFSWalk's
	protected HashSet finishedBarriers_ = new HashSet(); // of barriers that are finished being
	// traversed from
	protected LinkedList phases_ = new LinkedList(); // of PhaseConcurrencyAnalysis's

	// A common search we do is, for a given node, and a given barrier, find all
	// phases that
	// a) contain that node
	// b) have that barrier as the starting barrier of the phase
	// Solution: map each node to a list of phases to which it belongs.
	// The list should be sparse, for filtering out the phases that
	// begin with a particular barrier should be inexpensive.
	protected Hashtable nodeToPhases_ = new Hashtable();

	/**
	* PhaseAnalysisFactory - Constructor
	*
	* @param cfg
	* - OMPCFG
	*/
	public PhaseAnalysisFactory(OMPCFG cfg)
	{
	cfg_ = cfg;
	termNode_ = cfg_.getTermNode();
	}

	public void buildPhases()
	{
	// Set up the first statement
	OMPCFGNode node = cfg_.getRoot();
	if (!(node instanceof OMPPragmaNode))
	return; // required
	DFSWalk pc = new DFSWalk((OMPPragmaNode) node);
	barrierStack_.push(pc);
	pc.trigger();
	}

	/**
	* findPhase - find a specified phase and add it
	*
	* @param bNode
	* - OMPPragmaNode
	* @param eNode
	* - OMPPragmaNode
	* @param addNew
	* - boolean
	* @return PhaseConcurrencyAnalysis
	*/
	protected PhaseConcurrencyAnalysis findPhase(OMPPragmaNode bNode, OMPPragmaNode eNode, boolean addNew)
	{
	// Find the phase that starts and ends with these TODO: make more efficient
	for (Iterator i = phases_.iterator(); i.hasNext();) {
	PhaseConcurrencyAnalysis phase = (PhaseConcurrencyAnalysis) i.next();
	if (phase.getBeginNode() == bNode && phase.getEndNode() == eNode)
	return phase;
	}
	if (!addNew)
	return null;

	PhaseConcurrencyAnalysis phase = new PhaseConcurrencyAnalysis(bNode, eNode);
	phases_.add(phase);
	return phase;
	}

	/**
	* addNodesToPhase - add a list of nodes to a specific phase
	*
	* @param phase
	* - PhaseConcurrencyAnalysis
	* @param nodes
	* - OMPCFGNode []
	*/
	protected void addNodesToPhase(PhaseConcurrencyAnalysis phase, OMPCFGNode[] nodes)
	{
	for (int i = 0; i < nodes.length; i++) {
	phase.add(nodes[i]);
	mapNodeToPhase(nodes[i], phase);
	}
	}

	protected boolean isFinished(OMPPragmaNode pNode)
	{
	return finishedBarriers_.contains(pNode);
	}

	protected boolean isOnBarrierStack(OMPPragmaNode pNode)
	{
	for (Iterator i = barrierStack_.iterator(); i.hasNext();) {
	DFSWalk dw = (DFSWalk) i.next();
	if (dw.getPragmaNode() == pNode)
	return true;
	}
	return false;
	}

	protected LinkedList memberPhases(OMPCFGNode node)
	{
	return (LinkedList) nodeToPhases_.get(node);
	}

	/**
	* mapNodeToPhase - map a given node to a given phase in the node-phase map
	*
	* @param node
	* - OMPCFGNode
	* @param phase
	* - PhaseConcurrencyAnalysis
	*/
	protected void mapNodeToPhase(OMPCFGNode node, PhaseConcurrencyAnalysis phase)
	{
	LinkedList l = (LinkedList) nodeToPhases_.get(node);
	if (l == null) {
	l = new LinkedList();
	nodeToPhases_.put(node, l);
	}
	if (!l.contains(phase))
	l.add(phase);
	}

	/**
	* getPhases - produce a list of all phases produced from this analysis
	*
	* @return PhaseConcurrencyAnalysis []
	*/
	public PhaseConcurrencyAnalysis[] getPhases()
	{
	PhaseConcurrencyAnalysis[] l = new PhaseConcurrencyAnalysis[phases_.size()];
	int count = 0;
	for (Iterator i = phases_.iterator(); i.hasNext();)
	l[count++] = (PhaseConcurrencyAnalysis) i.next();
	return l;
	}

	// *************************************************************************
	// DFSWalk
	// *************************************************************************
	protected class DFSWalk extends OMPDFS
	{
	protected OMPPragmaNode phaseBeginNode_ = null;

	public DFSWalk(OMPPragmaNode phaseBeginNode)
	{
	super(phaseBeginNode);
	phaseBeginNode_ = phaseBeginNode;
	}

	public OMPPragmaNode getPragmaNode()
	{
	return phaseBeginNode_;
	}

	/**
	* trigger - begin the process of walking the graph
	*
	*/
	public void trigger()
	{
	this.startWalking();
	}

	/**
	* visit - visit method - what the user usually overrides
	*
	* @param node
	* - OMPCFGNode
	* @return int (see OMPDFS codes)
	*/
	public int visit(OMPCFGNode node)
	{
	if (node instanceof OMPPragmaNode) {
	OMPPragmaNode pragmaNode = (OMPPragmaNode) node;
	if (pragmaNode.getPragma() != null && pragmaNode.getPragma().getOMPType() != PASTOMPPragma.OmpBarrier)
	return OMPDFS.CONTINUE;
	// If at beginning of stack again, keep moving on
	if (getNodeStackSize() == 1)
	return OMPDFS.CONTINUE;
	// If necessary, create a new phase and add to list of phases
	PhaseConcurrencyAnalysis phase = findPhase(phaseBeginNode_, pragmaNode, true);
	addNodesToPhase(phase, getNodeStack());
	// If barrier is completed or is on stack, we skip searching forward
	if (isFinished(pragmaNode) \|\| isOnBarrierStack(pragmaNode))
	return OMPDFS.SKIP;
	// Create a new walk to the next segments - increase the stack
	// NOTE: we may have to skip the followin for implict barrier
	DFSWalk pc = new DFSWalk(pragmaNode);
	barrierStack_.push(pc);
	pc.trigger();
	// above finished walking, pop the stack, and skip on this level
	barrierStack_.pop();
	return OMPDFS.SKIP;
	}
	else if (node == termNode_) { // this is an implicit barrier, but not further dfs
	if (getNodeStackSize() == 1)
	return OMPDFS.CONTINUE;
	return OMPDFS.CONTINUE;
	}

	// For each visited successor node, add node stack to all phases the successor
	// belongs to, said successor phase beginning with phaseBeginNode_
	// Note: we should not bother with phases that begin with other than phaseBeginNode_ -
	// as then we would have to account for partial paths from other such phases,
	// which we do not have (we glom all nodes together, no paths). That was why
	// we do fresh searches starting at new barriers.
	OMPCFGNode[] nodes = node.getOutNodes();
	for (int i = 0; i < nodes.length; i++) {
	if (isVisited(nodes[i])) {
	LinkedList l = memberPhases(nodes[i]);
	OMPCFGNode[] nodeStack = getNodeStack();
	Object[] listArray = l.toArray(); // safer to use this, l may get modified
	for (int j = 0; j < listArray.length; j++) {
	PhaseConcurrencyAnalysis phase = (PhaseConcurrencyAnalysis) listArray[j];
	if (phase.getBeginNode() == phaseBeginNode_)
	addNodesToPhase(phase, nodeStack);
	}
	}
	}

	return OMPDFS.CONTINUE;
	}

	/**
	* atStartNode - check if we are at the 1st node of the search
	*
	* @param node
	* @return
	*/
	protected boolean atStartNode(OMPCFGNode node)
	{
	return (node == phaseBeginNode_ && getNodeStackSize() == 1);
	}

	}
	}