tools/pldt/org.eclipse.ptp.pldt.mpi.analysis/src/org/eclipse/ptp/pldt/mpi/analysis/analysis/MPICallGraph.java

/**********************************************************************
 * Copyright (c) 2007 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.mpi.analysis.analysis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

import org.eclipse.cdt.core.dom.ast.*;
import org.eclipse.ptp.pldt.mpi.analysis.analysis.BarrierTable.BarrierInfo;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl.CallGraph;

public class MPICallGraph extends CallGraph{
	/** Is the global variable pointer type? */
	protected List<Boolean> gvPointer_;
	protected BarrierTable btable_;
	protected int count;
	private static final boolean traceOn=false;
	
	public MPICallGraph()
	{
		super();
		btable_ = new BarrierTable();
		count = 4; // 0-3 are types in BarrierExpression
		gvPointer_ = new ArrayList<Boolean>();
	}
	
	public List<Boolean> getGVPointer(){return gvPointer_;}
	
	public BarrierTable getBarrierTable(){return btable_;}
	
	public void otherOP(){
		//FunctionPointerChecker fpc = new FunctionPointerChecker();
		//fpc.run();
		FunctionMarker fm = new FunctionMarker();
		fm.run();
		checkBarrierRelatedCycles();
		if(traceOn)System.out.println((btable_.commCounter + 1) + " communicators "); //$NON-NLS-1$
	}	
	
	class FunctionPointerChecker extends ASTVisitor{
		protected ICallGraphNode currentFunc_;
		protected boolean funcPointer = false;
		
		public boolean hasFuncPointer(){return funcPointer;}
		
		public void run(){
			this.shouldVisitDeclarations = true;
			this.shouldVisitStatements = true;
			this.shouldVisitExpressions = true;
			for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){
				currentFunc_ = i.next();
				currentFunc_.getFuncDef().accept(this);
			}
		}
		
		protected Stack<String> funcCall = new Stack<String>();
		
		public int visit(IASTExpression expr){
			if(expr instanceof IASTFunctionCallExpression){
				IASTFunctionCallExpression funcE = (IASTFunctionCallExpression)expr;
				IASTExpression funcname = funcE.getFunctionNameExpression();
				String signature = funcname.getRawSignature();
				funcCall.push(signature);
			} 
			else if(expr instanceof IASTIdExpression){
				IASTIdExpression idE = (IASTIdExpression)expr;
				String name = idE.getName().toString();
				if(!funcCall.empty() && name.equals(funcCall.peek())){
					funcCall.pop();
				} else {
					ICallGraphNode node = getNode(currentFunc_.getFileName(), name);
					if(node != null){
						funcPointer = true;
						System.out.println("Function Pointer " + name + " in " +  //$NON-NLS-1$ //$NON-NLS-2$
								currentFunc_.getFuncName() + "(" + currentFunc_.getFileName() + ")"); //$NON-NLS-1$ //$NON-NLS-2$
					}
				}
			}
			return PROCESS_CONTINUE;
		}
	}
	
	class FunctionMarker extends ASTVisitor{
		protected MPICallGraphNode currentNode_ = null;
		
		public void run()
		{
			this.shouldVisitExpressions = true;
			this.shouldVisitStatements = true;
			this.shouldVisitDeclarations = true;
			
			for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){
				currentNode_ = (MPICallGraphNode)i.next();
				//System.out.println(currentNode_.getFuncName());
				currentNode_.getFuncDef().accept(this);
			}
			
			for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){
				currentNode_ = (MPICallGraphNode)i.next();
				//System.out.println(currentNode_.getFuncName());
				markBarrierRelated(currentNode_);
			}
			for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){
				currentNode_  = (MPICallGraphNode)i.next();
				markMPIInit(currentNode_);
			}
			
			markFunction();
			count = count -4;
		}
		
		public int visit(IASTExpression expression) 
		{
			if (expression instanceof IASTFunctionCallExpression) {
				IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression)expression;
				IASTExpression funcname = funcExpr.getFunctionNameExpression();
				String signature = funcname.getRawSignature();
				if(signature.equals("MPI_Barrier")){ //$NON-NLS-1$
					count ++;
					BarrierInfo newbar = btable_.addBarrier(funcExpr, count, 
							currentNode_.getResource(), currentNode_.getFuncName());
					currentNode_.setBarrierRelated(true);
					currentNode_.getAllBarriers().add(newbar);
				}
				else if(signature.equals("MPI_Init")){ //$NON-NLS-1$
					currentNode_.mpiInit = true;
				}
			}
			return PROCESS_CONTINUE;
		}
		
		/* Functions that directly call barriers (MPI_Barrier()) and their
		 * ancestors are barrier-related
		 */
		protected void markBarrierRelated(MPICallGraphNode node){
			if(node.barrierRelated()){
				//System.out.println(node.getName());
				for(Iterator<ICallGraphNode> ii = node.getCallers().iterator(); ii.hasNext();){
					MPICallGraphNode caller = (MPICallGraphNode)ii.next();
					if(!caller.barrierRelated()){
						caller.setBarrierRelated(true);
						markBarrierRelated(caller);
					}
				}
			}
		}
		protected void markMPIInit(MPICallGraphNode node){
			if(node.mpiInit){
				for(Iterator<ICallGraphNode> ii = node.getCallers().iterator(); ii.hasNext();){
					MPICallGraphNode caller = (MPICallGraphNode)ii.next();
					if(!caller.mpiInit){
						caller.mpiInit = true;
						markMPIInit(caller);
					}
				}
			}
		}
		
		/** A function is marked if:<br>
		 * (1) It is a barrier-related function<br>
		 * (2) It is called by (1)<br>
		 * (3) It is an MPI Initialization function (call MPI_Init)<br>
		 * (4) It is an ancestor of (3)<br>
		 * (5) It is called by (4)
		 */
		protected void markFunction(){
			int total = nodes_.size();
			int marked = 0;
			
			for(ICallGraphNode node = topEntry_; node != null; node = node.topNext()){
				currentNode_ = (MPICallGraphNode)node;
				if(currentNode_.barrierRelated() || currentNode_.mpiInit){
					currentNode_.marked = true;
					marked ++;
				}
			}
			
			boolean changed = true;
			while(changed){
				changed = false;
				for(ICallGraphNode node = topEntry_; node != null; node = node.topNext()){
					currentNode_ = (MPICallGraphNode)node;
					if(currentNode_.marked){
						for(Iterator<ICallGraphNode> i = currentNode_.getCallees().iterator(); i.hasNext();){
							MPICallGraphNode callee = (MPICallGraphNode)i.next();
							if(!callee.marked){
								callee.marked = true;
								marked ++;
								changed = true;
							}
						}
					}
				}
			}
			if(traceOn)System.out.println(marked + " out of " + total + " functions are marked"); //$NON-NLS-1$ //$NON-NLS-2$
		}
	}
	
	protected void checkBarrierRelatedCycles(){

		for(Iterator<List<ICallGraphNode>> i=cycles_.iterator(); i.hasNext();){
			List<ICallGraphNode> cycle = i.next();
			boolean barrierRelated = false;
			for(Iterator<ICallGraphNode> ii = cycle.iterator(); ii.hasNext();){
				MPICallGraphNode node = (MPICallGraphNode)ii.next();
				if(node.barrierRelated){
					barrierRelated = true;
					break;
				}
			}
			if(!barrierRelated) continue;
			String errorMsg = new String("Barrier related recursive function calls on: "); //$NON-NLS-1$
			for(Iterator<ICallGraphNode> ii = cycle.iterator(); ii.hasNext();){
				ICallGraphNode func = ii.next();
				errorMsg = errorMsg + func.getFuncName() + "(" + func.getFileName() + "), "; //$NON-NLS-1$ //$NON-NLS-2$
			}
			System.out.println(errorMsg);
		}
	}
}