diff options
Diffstat (limited to 'org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi')
31 files changed, 2352 insertions, 0 deletions
diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Entries b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Entries new file mode 100644 index 0000000..2aa317c --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Entries @@ -0,0 +1 @@ +D/analysis//// diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Repository b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Repository new file mode 100644 index 0000000..fa76657 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.ptp/tools/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Root b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Tag b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Tag new file mode 100644 index 0000000..09d5efe --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/CVS/Tag @@ -0,0 +1 @@ +TPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Entries b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Entries new file mode 100644 index 0000000..e524915 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Entries @@ -0,0 +1 @@ +D/cdt//// diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Repository b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Repository new file mode 100644 index 0000000..85d81f6 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.ptp/tools/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Root b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Tag b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Tag new file mode 100644 index 0000000..09d5efe --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/CVS/Tag @@ -0,0 +1 @@ +TPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/Activator.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/Activator.java new file mode 100644 index 0000000..7b400e9 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/Activator.java @@ -0,0 +1,61 @@ +/********************************************************************** + * 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.cdt; + +import org.eclipse.ui.plugin.AbstractUIPlugin; +import org.osgi.framework.BundleContext; + +/** + * The activator class controls the plug-in life cycle + */ +public class Activator extends AbstractUIPlugin { + + // The plug-in ID + public static final String PLUGIN_ID = "org.eclipse.ptp.pldt.mpi.analysis.cdt"; + + // The shared instance + private static Activator plugin; + + /** + * The constructor + */ + public Activator() { + plugin = this; + } + + /* + * (non-Javadoc) + * @see org.eclipse.ui.plugin.AbstractUIPlugin#start(org.osgi.framework.BundleContext) + */ + public void start(BundleContext context) throws Exception { + super.start(context); + } + + /* + * (non-Javadoc) + * @see org.eclipse.ui.plugin.AbstractUIPlugin#stop(org.osgi.framework.BundleContext) + */ + public void stop(BundleContext context) throws Exception { + plugin = null; + super.stop(context); + } + + /** + * Returns the shared instance + * + * @return the shared instance + */ + public static Activator getDefault() { + return plugin; + } + +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Entries b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Entries new file mode 100644 index 0000000..efc3a2b --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Entries @@ -0,0 +1,2 @@ +/Activator.java/1.1/Thu Apr 19 17:00:13 2007//TPTP_2_1 +D/graphs//// diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Repository b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Repository new file mode 100644 index 0000000..0f016ee --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.ptp/tools/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Root b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Tag b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Tag new file mode 100644 index 0000000..a1f2841 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/CVS/Tag @@ -0,0 +1 @@ +NPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Entries b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Entries new file mode 100644 index 0000000..6790d78 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Entries @@ -0,0 +1,6 @@ +/GraphCreator.java/1.2/Thu Mar 13 04:04:38 2008//TPTP_2_1 +/IBlock.java/1.3/Sat Mar 15 04:08:30 2008//TPTP_2_1 +/ICallGraph.java/1.1/Thu Apr 19 17:00:12 2007//TPTP_2_1 +/ICallGraphNode.java/1.1/Thu Apr 19 17:00:12 2007//TPTP_2_1 +/IControlFlowGraph.java/1.1/Thu Apr 19 17:00:12 2007//TPTP_2_1 +D/impl//// diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Repository b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Repository new file mode 100644 index 0000000..1167f21 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.ptp/tools/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Root b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Tag b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Tag new file mode 100644 index 0000000..a1f2841 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/CVS/Tag @@ -0,0 +1 @@ +NPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/GraphCreator.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/GraphCreator.java new file mode 100644 index 0000000..1da923e --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/GraphCreator.java @@ -0,0 +1,192 @@ +/********************************************************************** + * Copyright (c) 2008 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.cdt.graphs; + +import java.util.Iterator; +import java.util.List; + +import org.eclipse.core.resources.IContainer; +import org.eclipse.core.resources.IFile; +import org.eclipse.core.resources.IResource; +import org.eclipse.core.runtime.CoreException; +import org.eclipse.core.runtime.IPath; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl.CallGraph; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl.ResourceCollector; + +/** + * Convenience class for constructing various graphs from C source files + * + * @author Beth Tibbitts + * + */ +public class GraphCreator { + /** + * Convenience method for initializing and computing the call graph in one place. + * <br>This is done in two steps: + * <br>(1) initCallGraph(): initialize call graph with function information + * <br>(2) computeCallGraph(): compute caller/callee/recursive etc. info on the graph + * @param resource + * @return + */ + public ICallGraph createCallGraph(IResource resource) { + ICallGraph cg = initCallGraph(resource); + computeCallGraph(cg); + return cg; + + } + /** + * Create call graph structure from resources (C source files) but caller/callee + * calculations are not done yet; will descend to children of a container if + * called with a folder or project argument. + * @param resource + * @return call graph initialized with basic function information + */ + public ICallGraph initCallGraph(IResource resource) { + ICallGraph callGraph = new CallGraph(); + callGraph = initCallGraph(resource, callGraph); + return callGraph; + + } + /** + * Add information to an existing call graph. + * <br>Will descend to children if this is a container (folder or project) + * + * @param resource contains source file(s) whose functions will be found and added to the call graph. + * @param callGraph + * @return + */ + public ICallGraph initCallGraph(IResource resource, ICallGraph callGraph) { + boolean foundError = resourceCollector(resource, callGraph); + if(foundError) { + System.out.println("Error occurred during call graph creation."); + } + return callGraph; + } + /** + * Create an empty call graph, ready to fill with function information + * later with subsequent calls to initCallGraph(resource, callGraph) + * @return + */ + public ICallGraph initCallGraph() { + return new CallGraph(); + } + /** + * Calculate the caller/callee and recursive properties of the call graph + * @return + */ + public ICallGraph computeCallGraph(ICallGraph callGraph) { + callGraph.buildCG(); + return callGraph; + } + + + /** + * Run analysis ("Resource collector") on a resource (e.g. File or Folder) + * and add the function information found in/under the given resource (file or container) + * to the given call graph + * <br>Will descend to members of folder + * + * @param resource + * the resource selected by the user + * @param callGraph the call graph to which the information will be appended + * @return + */ + public boolean resourceCollector(IResource resource, ICallGraph callGraph) { + + boolean foundError = false; + + // if it's a C file, collect info in the call graph for this file + if (resource instanceof IFile) { + IFile file = (IFile) resource; + String filename = file.getName(); + if (filename.endsWith(".c")) { + ResourceCollector rc = new ResourceCollector(callGraph, file); + rc.run(); + } + // if it's a container, run resourceCollector on each of its members + } else if (resource instanceof IContainer) { + IContainer container = (IContainer) resource; + try { + IResource[] mems = container.members(); + for (int i = 0; i < mems.length; i++) { + boolean err = resourceCollector(mems[i], callGraph); + foundError = foundError || err; + } + } catch (CoreException e) { + e.printStackTrace(); + foundError=true; + } + } else { + // ????? + String name = ""; + if (resource instanceof IResource) { + IResource res = (IResource) resource; + // name=res.getName(); // simple filename only, no path info + IPath path = res.getProjectRelativePath(); + name = path.toString(); + } + System.out.println("Cancelled by User, aborting analysis on subsequent files... " + + name); + } + + return foundError; + } + /** + * Print a call graph structure + * @param cg the call graph to print + */ + public void showCallGraph(ICallGraph cg) { + System.out.println("Show call graph"); + List<ICallGraphNode> nodes = cg.getAllNodes(); + for (Iterator<ICallGraphNode> iterator = nodes.iterator(); iterator.hasNext();) { + ICallGraphNode cgNode = iterator.next(); + printCGNode(cgNode, ""); + //System.out.println(" callers: ==>"); + + for (Iterator<ICallGraphNode> iterator2 = cgNode.getCallers().iterator(); iterator2.hasNext();) { + ICallGraphNode caller = iterator2.next(); + printCGNode(caller," caller: "); + } + //System.out.println(" <== callees:"); + for (Iterator<ICallGraphNode> iterator3 = cgNode.getCallees().iterator(); iterator3.hasNext();) { + ICallGraphNode callee = iterator3.next(); + printCGNode(callee," callee: "); + + } + System.out.println(" "); + + } + List<List<ICallGraphNode>>cycles = cg.getCycles(); + System.out.println("Recursive cycles:"); + for (List<ICallGraphNode> cycle : cycles) { + System.out.println("Cycle: "); + for (Iterator<ICallGraphNode> iterator = cycle.iterator(); iterator.hasNext();) { + ICallGraphNode fn = iterator.next(); + System.out.print(" "+fn.getFuncName()); + + } + System.out.println(" \n"); + } + List<String> vars= cg.getEnv(); + System.out.println("Global variables:"); + for (Iterator<String> varit= vars.iterator(); varit.hasNext();) { + String var = varit.next(); + System.out.println("Global var: "+var); + + } + + } + public void printCGNode(ICallGraphNode cgNode, String prefix) { + System.out.println(prefix+" "+cgNode.getFuncName()+" in "+cgNode.getFileName()); + cgNode.getCFG(); + } +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java new file mode 100644 index 0000000..f61b879 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java @@ -0,0 +1,145 @@ +/********************************************************************** + * 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.cdt.graphs; + +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTNode; +import org.eclipse.cdt.core.dom.ast.IASTStatement; + +/** + * A "Block" contains either a single statement or a predicate expression, + * and it can be entered only at the beginning and exited only at the end. + * + * @author Yuan Zhang + * + */ +public interface IBlock { + /** + * @return the unique ID + */ + public int getID(); + + /** + * @return the list of successors in the control flow graph + */ + public List<IBlock> getSuccs(); + + /** + * @return the list of predecessors in the control flow graph + */ + public List<IBlock> getPreds(); + + /** + * @return the next block in CFG according to the topological + * order (top-down order) + */ + public IBlock topNext(); + /** + * @return the next block in CFG according to the topological + * order (top-down order) + */ + public IBlock getTopNext(); + /** + * Set the next block in CFG according to the topological + * order (top-down order) + */ + public void setTopNext(IBlock b); + + /** + * Get the next block in CFG according to the reverse + * topological order (bottom-up order) + */ + public IBlock botNext(); + /** + * Get the next block in CFG according to the reverse + * topological order (bottom-up order) + */ + public IBlock getBotNext(); + /** + * Set the next block in CFG according to the reverse + * topological order (bottom-up order) + */ + public void setBotNext(IBlock b); + + /** + * @return the content (a predicate expression or a statement) + */ + public IASTNode getContent(); + + /** + * Search to determine if a block contains an expression + * @return true if this block contains expression expr + * which is the predicate of statement <parent>, false otherwise. + */ + public boolean search(IASTExpression expr, IASTStatement parent); + /** + * Search to determine if a block contains a statement + * @return true if this block contains statement stmt, + * false otherwise. + */ + public boolean search(IASTStatement stmt); + /** + * Search to determine if a block contains a given label + * @return true if this block contains label, false otherwise + */ + public boolean search(IASTName label); + + /** + * Get Dominators<br> + * Block A dominates another block B if every path from the entry that + * reaches block B has to pass through block A. + * The entry block dominates all blocks. + * @return list of dominator IBlocks + */ + public List<IBlock> getDOM(); + /** + * Set dominators + * @param set list of dominators + */ + public void setDOM(List<IBlock> set); + + /** + * Get post-dominators<br> + * Block A postdominates block B if every path from B to the exit has to pass through block A. + * The exit block postdominates all blocks. + * + * @return list of post-dominator IBlocks + */ + public List<IBlock> getPDOM(); + /** + * set post-dominators + * @param set + */ + public void setPDOM(List<IBlock> set); + + /** + * An attribute (identified by its name) of a block could be any + * property of it. + * @param name + * @param attr + */ + public void setAttr(String name, Object attr); + /** + * Get an attribute of a block + * @param name + * @return + */ + public Object getAttr(String name); + + /** + * Print IBlock information, include id, content, and successors + */ + public void print(); +}
\ No newline at end of file diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraph.java new file mode 100644 index 0000000..60a0391 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraph.java @@ -0,0 +1,88 @@ +/********************************************************************** + * 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.cdt.graphs; + +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; + +/** + * A call graph is a directed graph which represents the calling relation + * among subroutines in a program. In CDT, it is partially determined + * by static analysis. + * + * @author Yuan Zhang + * + */ +public interface ICallGraph { + + /** + * @return all functions in the call graph + */ + public List<ICallGraphNode> getAllNodes(); + + /** + * @return all global variables + */ + public List<String> getEnv(); + + /** + * @return one root function. A root function is never called by + * other functions. There may be multiple root functions in a call + * graph. + */ + public ICallGraphNode topEntry(); + public void setTopEntry(ICallGraphNode node); + + /** + * @return one leaf function. A leaf function never calls any other + * functions. There may be multiple leaf functions in a call graph. + */ + public ICallGraphNode botEntry(); + public void setBotEntry(ICallGraphNode node); + + /** + * @return list of recursive function calls + */ + public List<List<ICallGraphNode>> getCycles(); + + /** + * Search for a function according to its filename and function name. + * @param fileName + * @param funcName + * @return its call graph node if it is found; null otherwise. + */ + public ICallGraphNode getNode(String fileName, String funcName); + + /** + * Search for a function according to its declaration. + * @param fdef + * @return its call graph node if it is found; null otherwise. + */ + public ICallGraphNode getNode(IASTFunctionDefinition fdef); + + /** + * Add a function node to the call graph. Its calling relation + * is not constructed yet. + * @param node + */ + public void addNode(ICallGraphNode node); + + /** + * Build the calling relations. This method is not reponsible for + * collecting functions in a program. + */ + public void buildCG(); + + public void print(); + +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraphNode.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraphNode.java new file mode 100644 index 0000000..3574662 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/ICallGraphNode.java @@ -0,0 +1,80 @@ +/********************************************************************** + * 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.cdt.graphs; + +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; +import org.eclipse.core.resources.IResource; + +/** + * A call graph node corresponds to a user-defined function. + * + * @author Yuan Zhang + * + */ +public interface ICallGraphNode { + + /** + * @return the function name + */ + public String getFuncName(); + + /** + * @return the enclosing file name + */ + public String getFileName(); + + public IResource getResource(); + + /** + * @return the function declaration + */ + public IASTFunctionDefinition getFuncDef(); + + /** + * @return the set of functions that call this function + */ + public List<ICallGraphNode> getCallers(); + public void addCaller(ICallGraphNode caller); + + /** + * @return the set of functions that are called by this function + */ + public List<ICallGraphNode> getCallees(); + public void addCallee(ICallGraphNode callee); + + /** + * @return the control flow graph of this function + */ + public IControlFlowGraph getCFG(); + public void setCFG(IControlFlowGraph cfg); + + /** + * @return the next function according to the topological order + */ + public ICallGraphNode topNext(); + public void setTopNext(ICallGraphNode node); + + /** + * @return the next function according to the reverse topological order + */ + public ICallGraphNode botNext(); + public void setBotNext(ICallGraphNode node); + + public void setAttr(String name, Object attr); + public Object getAttr(String name); + public void removeAttr(String name); + + public void setRecursive(boolean val); + public boolean isRecursive(); +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java new file mode 100644 index 0000000..ecc4449 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java @@ -0,0 +1,63 @@ +/********************************************************************** + * 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.cdt.graphs; + +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTStatement; + +/** + * A control flow graph is directed graph. Each node is a block, and + * each edge represents the jump in the control flow. + * + * @author Yuan Zhang + * + */ + +public interface IControlFlowGraph { + + /** + * @return the entry block + */ + public IBlock getEntry(); + + /** + * @return the exit block + */ + public IBlock getExit(); + + + /** Search for the block which contains the statement <stmt> + */ + public IBlock getBlock(IASTStatement stmt); + /** + * Search for the block which contains the condition expression + * <expr>, and <expr> is the predicate of statement <parent> + * @return + */ + public IBlock getBlock(IASTExpression expr, IASTStatement parent); + + /** + * Search for the block which contains the <label> + * @return + */ + public IBlock getBlock(IASTName label); + + public void addBlock(IBlock bb); + + /** + * Build the control flow relation + */ + public void buildCFG(); + + public void print(); +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java new file mode 100644 index 0000000..db76c50 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java @@ -0,0 +1,246 @@ +/********************************************************************** + * 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.cdt.graphs.impl; + +import java.util.ArrayList; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTNode; +import org.eclipse.cdt.core.dom.ast.IASTStatement; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; + +/** + * + * @author Yuan Zhang + * + */ +public class Block implements IBlock { + protected List<IBlock> succs_; + protected List<IBlock> preds_; + protected IBlock topNext_ = null; + protected IBlock botNext_ = null; + protected List<IBlock> DOM_ = null; + protected List<IBlock> PDOM_ = null; + + protected static int counter = 0; + protected int id; + + /** "type" tells the type of the content in this block. + * A block with expr_type/stmt_type/label_type stores an + * expression/statement/labelname, respectively. A block + * with continue_join_type is an empty block in a loop + * joining regular flows and flows from continue statements. + * A block with exit_join_type is an empty block joining + * (1) two branches of an if statement (2) all leaving + * edges (through break or default statements) of a + * switch statement (3) the regular exit from a loop and + * irregular exits from break statements of this loop. + */ + protected int type; + public static final int expr_type = 1; + public static final int stmt_type = 2; + public static final int label_type = 3; + public static final int continue_join_type = 4; + public static final int exit_join_type = 5; + + protected IASTNode content_; + + /** The parent of a block storing a statement is the statement itself; + * The parent of a block with a predicate expression is the corresponding + * if/loop/switch statement; + * The parent of a block with a label is the label statement; + * The parent of a block with continue_join_type or exit_join_type + * is the corresponding if/loop/switch statement; + */ + protected IASTStatement parent_; + + protected Hashtable<String,Object> attrs_; + + int color; // white = 0, gray = 1, black = 2 + + public Block(){ + id = counter ++; + type = 0; + content_ = null; + parent_ = null; + blockInit(); + } + + public Block(IASTNode content, IASTStatement parent, int type){ + this(); + content_ = content; + parent_ = parent; + this.type = type; + blockInit(); + } + + /** Short-cut constructor for stmt_type block */ + public Block(IASTStatement stmt){ + this(stmt, stmt, stmt_type); + } + + /** Short-cut constructor for expr_type block */ + public Block(IASTExpression expr, IASTStatement parent){ + this(expr, parent, expr_type); + } + + /** Short-cut constructor for label_type block */ + public Block(IASTName label){ + this(label, null, label_type); + } + + protected void blockInit(){ + succs_ = new ArrayList<IBlock>(); + preds_ = new ArrayList<IBlock>(); + DOM_ = new ArrayList<IBlock>(); + PDOM_ = new ArrayList<IBlock>(); + attrs_ = new Hashtable<String,Object>(); + } + + public int getID(){ + return id; + } + + public IASTNode getContent(){ + return content_; + } + + public IASTStatement getParent(){ + return parent_; + } + public int getType() {return type;} + + public boolean search(IASTNode content, IASTStatement parent, int type){ + if(this.type != type) return false; + if(type == stmt_type){ + if(content == content_) return true; + else return false; + } + else if(type == label_type){ + if(content instanceof IASTName){ + IASTName name = (IASTName)content; + IASTName labelName = (IASTName)content_; + if(name.toString().equals(labelName.toString())) + return true; + else return false; + } + else return false; + } + else if(type == expr_type){ + if(content != null && content == content_) return true; + if(content == null && content_ == null && parent_ == parent) + return true; + else return false; + } + else if(type == continue_join_type || type == exit_join_type){ + if(content != null) return false; + if(parent == parent_) return true; + else return false; + } + else return false; + } + + public boolean search(IASTExpression expr, IASTStatement parent){ + return search(expr, parent, expr_type); + } + + public boolean search(IASTStatement stmt){ + return search(stmt, stmt, stmt_type); + } + + public boolean search(IASTName label){ + return search(label, null, label_type); + } + + public IBlock topNext() { + return topNext_; + } + public IBlock getTopNext() { + return topNext_; + } + public void setTopNext(IBlock b){ + topNext_ = b; + } + + public IBlock botNext() { + return botNext_; + } + public IBlock getBotNext() { + return botNext_; + } + public void setBotNext(IBlock b){ + botNext_ = b; + } + + public List<IBlock> getPreds() { + return preds_; + } + + public List<IBlock> getSuccs() { + return succs_; + } + + public List<IBlock> getDOM(){ + return DOM_; + } + + public void setDOM(List<IBlock> set){ + DOM_ = set; + } + + public List<IBlock> getPDOM(){ + return PDOM_; + } + + public void setPDOM(List<IBlock> set){ + PDOM_ = set; + } + + public void setAttr(String name, Object attr){ + attrs_.put(name, attr); + } + + public Object getAttr(String name){ + return attrs_.get(name); + } + + /** + * Print IBlock information, include id, content (type & raw signature), and successors + */ + public void print(){ + System.out.print("Block " + id + ": "); + IASTNode content = getContent(); + if(content != null) { + String type = content.getClass().getSimpleName(); + System.out.println(" "+type+" "+content.getRawSignature()); + } + else + System.out.println(" Empty block"); + System.out.print(" flows to: "); + for(Iterator<IBlock> i = succs_.iterator(); i.hasNext();){ + System.out.print(i.next().getID() + ", "); + } + System.out.println(" "); + /* + System.out.print("Dominator: "); + for(Iterator i = DOM_.iterator(); i.hasNext();){ + Block dom = (Block)i.next(); + System.out.print(dom.getID() + ", "); + } + System.out.println(" "); + */ + } +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Entries b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Entries new file mode 100644 index 0000000..77ea635 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Entries @@ -0,0 +1,5 @@ +/Block.java/1.3/Thu Mar 13 04:34:43 2008//TPTP_2_1 +/CallGraph.java/1.1/Thu Apr 19 17:00:12 2007//TPTP_2_1 +/CallGraphNode.java/1.2/Thu Mar 13 03:58:20 2008//TPTP_2_1 +/ControlFlowGraph.java/1.3/Thu Mar 13 18:54:10 2008//TPTP_2_1 +/ResourceCollector.java/1.3/Thu Mar 13 03:59:17 2008//TPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Repository b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Repository new file mode 100644 index 0000000..1f2b254 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.ptp/tools/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Root b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Tag b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Tag new file mode 100644 index 0000000..a1f2841 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CVS/Tag @@ -0,0 +1 @@ +NPTP_2_1 diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraph.java new file mode 100644 index 0000000..33a3af8 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraph.java @@ -0,0 +1,309 @@ +/********************************************************************** + * 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.cdt.graphs.impl; + +import java.util.ArrayList; +import java.util.Enumeration; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.List; +import java.util.Stack; + +import org.eclipse.cdt.core.dom.ast.ASTVisitor; +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTFunctionCallExpression; +import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; +import org.eclipse.cdt.core.dom.ast.IASTNode; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraph; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode; + +public class CallGraph implements ICallGraph { + /**list of call graph nodes */ + protected List<ICallGraphNode> nodes_; + /**list of global variable names*/ + protected List<String> env_; + + /** the entry node according to topological order */ + protected ICallGraphNode topEntry_; + /** the entry node according to the reverse topological order */ + protected ICallGraphNode botEntry_; + /** list of cycles in the call graph */ + protected List<List<ICallGraphNode>> cycles_; + + public CallGraph(){ + nodes_ = new ArrayList<ICallGraphNode>(); + env_ = new ArrayList<String>(); + topEntry_ = null; + botEntry_ = null; + cycles_ = new ArrayList<List<ICallGraphNode>>(); + } + + public void addNode(ICallGraphNode node) { + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode n = i.next(); + if(n.getFuncName().equals(node.getFuncName()) && + n.getFileName().equals(node.getFileName())) + return; + } + nodes_.add(node); + } + + public List<ICallGraphNode> getAllNodes() { + return nodes_; + } + + public ICallGraphNode botEntry() { + return botEntry_; + } + + public List<List<ICallGraphNode>> getCycles() { + return cycles_; + } + + /** @return the enclosing function of an AST node */ + protected ICallGraphNode getEnclosingFunc(IASTNode n) { + IASTNode parent = n.getParent(); + while(parent != null){ + if(parent instanceof IASTFunctionDefinition) + return getNode((IASTFunctionDefinition)parent); + parent = parent.getParent(); + } + return null; + } + + public List<String> getEnv() { + return env_; + } + + /** @return the call graph node with the function name "funcName". + * If there are more than one functions with the same name (but + * with different scopes), and there is one such function in the + * file "fileName", then return this function node */ + public ICallGraphNode getNode(String fileName, String funcName) { + ICallGraphNode tmp = null; + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + if(node.getFuncName().equals(funcName)){ + tmp = node; + if(node.getFileName().equals(fileName)) + return node; + } + } + return tmp; + } + + public ICallGraphNode getNode(IASTFunctionDefinition fdef) { + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + if(node.getFuncDef() == fdef) + return node; + } + return null; + } + + public ICallGraphNode topEntry() { + return topEntry_; + } + + public void setBotEntry(ICallGraphNode node) { + botEntry_ = node; + } + + public void setTopEntry(ICallGraphNode node) { + topEntry_ = node; + } + + /** Constructing the call graph consists of three steps: + * (1) calculating caller and callee relations among functions. + * Note that call graph nodes have been collected before + * constructing the call graph + * (2) check the recursive function calls and collecting all cycles + * (3) other options for future extension + */ + public void buildCG(){ + CGBuilder builder = new CGBuilder(); + builder.run(); + checkRecursive(); + otherOP(); + } + + class CGBuilder extends ASTVisitor{ + ICallGraphNode currentNode_; + + public void run() + { + this.shouldVisitExpressions = true; + this.shouldVisitStatements = true; + this.shouldVisitDeclarations = true; + + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + currentNode_ = i.next(); + IASTFunctionDefinition func = currentNode_.getFuncDef(); + func.accept(this); + ICallGraphNode enclosingFuncNode = getEnclosingFunc(func); + if(enclosingFuncNode != null){ + // fd is nested declared function + enclosingFuncNode.addCallee(currentNode_); + currentNode_.addCaller(enclosingFuncNode); + } + } + } + + public int visit(IASTExpression expression) + { + if (expression instanceof IASTFunctionCallExpression) { + IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression)expression; + IASTExpression funcname = funcExpr.getFunctionNameExpression(); + String signature = funcname.getRawSignature(); + //System.out.println(signature); + ICallGraphNode fnode = getNode(currentNode_.getFileName(), signature); + if (fnode != null){ + /* This is a user-defined function call */ + currentNode_.addCallee(fnode); + fnode.addCaller(currentNode_); + } + } + return PROCESS_CONTINUE; + } + } + + protected Stack<ICallGraphNode> order; + + public void checkRecursive(){ + order = new Stack<ICallGraphNode>(); + DFS(); + RV_DFS(); + + Hashtable<ICallGraphNode,List<ICallGraphNode>> recursions = + new Hashtable<ICallGraphNode,List<ICallGraphNode>>(); + for(ICallGraphNode node = botEntry_; node != null; node = node.botNext()){ + ICallGraphNode pi = (ICallGraphNode)node.getAttr("pi"); + if(pi != null){ + if(recursions.containsKey(pi)){ + List<ICallGraphNode> list = recursions.get(pi); + list.add(node); + } else { + List<ICallGraphNode> list = new ArrayList<ICallGraphNode>(); + list.add(node); + recursions.put(pi, list); + } + } + } + for(Enumeration<ICallGraphNode> e = recursions.keys(); e.hasMoreElements();){ + ICallGraphNode root = e.nextElement(); + List<ICallGraphNode> list = recursions.get(root); + if(!list.contains(root)) + list.add(root); + cycles_.add(list); + for(Iterator<ICallGraphNode> i = list.iterator(); i.hasNext();){ + i.next().setRecursive(true); + } + } + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + if(node.getCallees().contains(node)){ //self-recursion + List<ICallGraphNode> list = new ArrayList<ICallGraphNode>(); + list.add(node); + cycles_.add(list); + node.setRecursive(true); + } + } + } + + protected void DFS(){ + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + node.setAttr("color", new Integer(0)); + node.removeAttr("pi"); + } + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + int color = ((Integer)node.getAttr("color")).intValue(); + if(color == 0) + DFSVisit(node); + } + } + + protected void DFSVisit(ICallGraphNode node){ + node.setAttr("color", new Integer(1)); + for(Iterator<ICallGraphNode> i = node.getCallees().iterator(); i.hasNext();){ + ICallGraphNode callee = i.next(); + int color = ((Integer)callee.getAttr("color")).intValue(); + if(color == 0){ //white + callee.setAttr("pi", node); + DFSVisit(callee); + } + } + order.push(node); + } + + protected void RV_DFS(){ + for(Iterator<ICallGraphNode> i = nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + node.setAttr("color", new Integer(0)); + node.removeAttr("pi"); + } + + ICallGraphNode n = null; + ICallGraphNode m = null; + topEntry_ = order.peek(); + while(!order.empty()){ + n = order.pop(); + n.setBotNext(m); + if(m != null) m.setTopNext(n); + m = n; + int color = ((Integer)n.getAttr("color")).intValue(); + if(color == 0){ + RV_DFSVisit(n); + } + } + botEntry_ = m; + + for(n = botEntry_; n != null; n = n.botNext()){ + ICallGraphNode pred = (ICallGraphNode)n.getAttr("pi"); + ICallGraphNode temp = null; + while(pred != null){ + temp = pred; + pred = (ICallGraphNode)pred.getAttr("pi"); + } + if(temp != null) n.setAttr("pi", temp); + } + } + + protected void RV_DFSVisit(ICallGraphNode node){ + node.setAttr("color", new Integer(1)); + for(Iterator<ICallGraphNode> i = node.getCallers().iterator(); i.hasNext();){ + ICallGraphNode caller = i.next(); + int color = ((Integer)caller.getAttr("color")).intValue(); + if(color == 0){ //white + caller.setAttr("pi", node); + RV_DFSVisit(caller); + } + } + } + + public void otherOP(){ + } + + public void print(){ + for(Iterator<ICallGraphNode> i=nodes_.iterator(); i.hasNext();){ + ICallGraphNode node = i.next(); + System.out.print(node.getFuncName() + " calls: "); + for(Iterator<ICallGraphNode> ii = node.getCallees().iterator(); ii.hasNext();){ + ICallGraphNode callee = ii.next(); + System.out.println(callee.getFuncName() + ", "); + } + System.out.println(""); + System.out.println(""); + } + } +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraphNode.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraphNode.java new file mode 100644 index 0000000..11bf50d --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/CallGraphNode.java @@ -0,0 +1,163 @@ +/********************************************************************** + * Copyright (c) 2007, 2008 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.cdt.graphs.impl; + +import java.util.ArrayList; +import java.util.Hashtable; +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTDeclarator; +import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.core.resources.IResource; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph; + +/** + * Implementation of a call graph node, which represents a user-defined + * function + * + */ +public class CallGraphNode implements ICallGraphNode { + protected IResource resource_; + protected String fileName_; + protected String funcName_; + protected IASTFunctionDefinition fdef_; + protected List<ICallGraphNode> callers_; + protected List<ICallGraphNode> callees_; + protected boolean nested; //nested function declaration? + protected IControlFlowGraph CFG_; + + /** next node in reverse-topological (bottom-up) order */ + protected ICallGraphNode botNext_; + /** next node in topological (top-down) order */ + protected ICallGraphNode topNext_; + protected Hashtable<String,Object> attrs_; + + protected boolean recursive; + + public CallGraphNode(IResource resource, String filename, + String funcname, IASTFunctionDefinition fdef){ + resource_ = resource; + fileName_ = filename; + funcName_ = funcname; + fdef_ = fdef; + init(); + } + + public CallGraphNode(IResource resource, String filename, + IASTFunctionDefinition fdef){ + resource_ = resource; + fileName_ = filename; + fdef_ = fdef; + funcName_ = getFuncName(fdef); + init(); + } + + private void init(){ + callers_ = new ArrayList<ICallGraphNode>(); + callees_ = new ArrayList<ICallGraphNode>(); + nested = false; + CFG_ = null; + topNext_ = null; + botNext_ = null; + attrs_ = new Hashtable<String,Object>(); + recursive = false; + } + + private String getFuncName(IASTFunctionDefinition fdef){ + IASTDeclarator fdecl = (IASTDeclarator)fdef.getDeclarator(); + return new String(((IASTName)fdecl.getName()).toCharArray()); + } + + public String getFuncName(){ + return funcName_; + } + + public String getFileName(){ + return fileName_; + } + + public IResource getResource(){ + return resource_; + } + + public IASTFunctionDefinition getFuncDef(){ + return fdef_; + } + + public boolean isNested(){ + return nested; + } + + public List<ICallGraphNode> getCallers(){ + return callers_; + } + + public void addCaller(ICallGraphNode caller){ + if(!callers_.contains(caller)) + callers_.add(caller); + } + + public List<ICallGraphNode> getCallees(){ + return callees_; + } + + public void addCallee(ICallGraphNode callee){ + if(!callees_.contains(callee)) + callees_.add(callee); + } + /** Returns next node in reverse-topological (bottom-up) order */ + public ICallGraphNode botNext() { + return botNext_; + } + + public void setBotNext(ICallGraphNode node){ + botNext_ = node; + } + + public IControlFlowGraph getCFG() { + return CFG_; + } + /** Returns next node in topological (top-down) order */ + public ICallGraphNode topNext() { + return topNext_; + } + + public void setTopNext(ICallGraphNode node){ + topNext_ = node; + } + + public void setCFG(IControlFlowGraph cfg) { + CFG_ = cfg; + } + + public void setAttr(String name, Object attr){ + attrs_.put(name, attr); + } + public Object getAttr(String name){ + return attrs_.get(name); + } + + public void removeAttr(String name){ + attrs_.remove(name); + } + + public void setRecursive(boolean val){ + recursive = val; + } + + public boolean isRecursive(){ + return recursive; + } + +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java new file mode 100644 index 0000000..3ee0072 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java @@ -0,0 +1,820 @@ +/********************************************************************** + * Copyright (c) 2007,2008 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.cdt.graphs.impl; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.Stack; + +import org.eclipse.cdt.core.dom.ast.ASTVisitor; +import org.eclipse.cdt.core.dom.ast.IASTBreakStatement; +import org.eclipse.cdt.core.dom.ast.IASTCaseStatement; +import org.eclipse.cdt.core.dom.ast.IASTCompoundStatement; +import org.eclipse.cdt.core.dom.ast.IASTContinueStatement; +import org.eclipse.cdt.core.dom.ast.IASTDeclarationStatement; +import org.eclipse.cdt.core.dom.ast.IASTDefaultStatement; +import org.eclipse.cdt.core.dom.ast.IASTDoStatement; +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTExpressionStatement; +import org.eclipse.cdt.core.dom.ast.IASTForStatement; +import org.eclipse.cdt.core.dom.ast.IASTFunctionCallExpression; +import org.eclipse.cdt.core.dom.ast.IASTGotoStatement; +import org.eclipse.cdt.core.dom.ast.IASTIfStatement; +import org.eclipse.cdt.core.dom.ast.IASTLabelStatement; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTNode; +import org.eclipse.cdt.core.dom.ast.IASTNullStatement; +import org.eclipse.cdt.core.dom.ast.IASTProblemStatement; +import org.eclipse.cdt.core.dom.ast.IASTReturnStatement; +import org.eclipse.cdt.core.dom.ast.IASTStatement; +import org.eclipse.cdt.core.dom.ast.IASTSwitchStatement; +import org.eclipse.cdt.core.dom.ast.IASTWhileStatement; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph; + +/** + * Control Flow Graph implementation + * + * @author Yuan Zhang + * + */ + +public class ControlFlowGraph implements IControlFlowGraph { + protected IASTStatement prog_; + protected List<IBlock> BBs_; + protected IBlock entry_; + protected IBlock exit_; + private static final boolean traceOn = false; + + public ControlFlowGraph(IASTStatement prog){ + this.prog_ = prog; + BBs_ = new ArrayList<IBlock>(); + } + + /** Constructing a CFG consists of several steps: + * Step 1: collecting all blocks in a function + * Step 2: calculating control flows among blocks + * Step 3: calculating dominator and post-dominator relations + * Step 4: Sort all blocks according to the topological order + * Step 5: Other additional operations + */ + public void buildCFG(){ + collectBlocks(); + setBlockFlow(); + buildDOM(); + buildPDOM(); + sort(); + otherOPs(); + } + + /** Collecting all blocks in a function */ + protected void collectBlocks(){ + entry_ = new Block(); + exit_ = new Block(); + BasicBlockCollector bc = new BasicBlockCollector(); + bc.run(); + } + + /** Calculating control flows among blocks */ + protected void setBlockFlow(){ + FlowBuilder flowBuilder = new FlowBuilder(); + flowBuilder.run(); + } + + class BasicBlockCollector extends ASTVisitor{ + + public void run(){ + this.shouldVisitStatements = true; + this.shouldVisitDeclarations = true; + prog_.accept(this); + } + + public int visit(IASTStatement stmt) + { + IBlock block; + if(stmt instanceof IASTBreakStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTCaseStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTCompoundStatement){ + } + else if(stmt instanceof IASTContinueStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTDeclarationStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTDefaultStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTDoStatement){ + IASTDoStatement doStmt = (IASTDoStatement)stmt; + block = new Block(doStmt.getCondition(), stmt); + addBlock(block); + IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); + addBlock(exitjoin); + IBlock continuejoin = new Block(null, stmt, Block.continue_join_type); + addBlock(continuejoin); + } + else if(stmt instanceof IASTExpressionStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTForStatement){ + IASTForStatement forStmt = (IASTForStatement)stmt; + /* The initialization is a statement, and will be added later */ + block = new Block(forStmt.getConditionExpression(), stmt); + addBlock(block); + if(forStmt.getIterationExpression() != null){ + block = new Block(forStmt.getIterationExpression(), stmt); + addBlock(block); + } + IBlock continuejoin = new Block(null, stmt, Block.continue_join_type); + addBlock(continuejoin); + IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); + addBlock(exitjoin); + } + else if(stmt instanceof IASTGotoStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTIfStatement){ + IASTIfStatement ifStmt = (IASTIfStatement)stmt; + block = new Block(ifStmt.getConditionExpression(), stmt); + addBlock(block); + IBlock join = new Block(null, stmt, Block.exit_join_type); + addBlock(join); + } + else if(stmt instanceof IASTLabelStatement){ + IASTLabelStatement labelS = (IASTLabelStatement)stmt; + block = new Block(labelS.getName(), stmt, Block.label_type); + addBlock(block); + } + else if(stmt instanceof IASTNullStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTProblemStatement){ + block = new Block(stmt); + addBlock(block); + } + else if(stmt instanceof IASTReturnStatement){ + IASTReturnStatement rtStmt = (IASTReturnStatement)stmt; + block = new Block(rtStmt.getReturnValue(), stmt); + addBlock(block); + } + else if(stmt instanceof IASTSwitchStatement){ + IASTSwitchStatement swStmt = (IASTSwitchStatement)stmt; + block = new Block(swStmt.getControllerExpression(), stmt); + addBlock(block); + IBlock join = new Block(null, stmt, Block.exit_join_type); + addBlock(join); + } + else if(stmt instanceof IASTWhileStatement){ + IASTWhileStatement whStmt = (IASTWhileStatement)stmt; + block = new Block(whStmt.getCondition(), stmt); + addBlock(block); + IBlock join = new Block(null, stmt, Block.continue_join_type); + addBlock(join); + IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); + addBlock(exitjoin); + } + return PROCESS_CONTINUE; + } + } + + public class FlowBuilder extends ASTVisitor{ + private boolean exitBlock = false; + + public void run(){ + this.shouldVisitStatements = true; + this.shouldVisitDeclarations = true; + this.shouldVisitTranslationUnit = true; + this.shouldVisitExpressions = true; + IBlock first = firstBlock(prog_); + ControlFlowEdge(entry_, first); + prog_.accept(this); + } + + public int visit(IASTStatement stmt){ + if(stmt instanceof IASTBreakStatement){ + /** A break statement flows to a block with exit_join_type */ + if(traceOn) System.out.println("BreakStatement"); + IBlock block = getBlock(stmt); + IASTNode parent = stmt.getParent(); + while(true){ + if(parent instanceof IASTDoStatement || + parent instanceof IASTForStatement || + parent instanceof IASTWhileStatement || + parent instanceof IASTSwitchStatement){ + IBlock exitjoin = getBlock(null, (IASTStatement)parent, + Block.exit_join_type); + ControlFlowEdge(block, exitjoin); + break; + } + else{ + parent = parent.getParent(); + } + } + } + else if(stmt instanceof IASTCaseStatement || + stmt instanceof IASTDefaultStatement){ + /** A case(default) statement flows from the switch + * condition block or the previous case statement, and + * flows to the first statement in the case(default) body. + */ + if(traceOn) System.out.println("CaseStatement / DefaultStatement"); + IASTNode parent = stmt.getParent(); + while(true){ + if(parent instanceof IASTSwitchStatement) break; + else parent = parent.getParent(); + } + IASTSwitchStatement swStmt = (IASTSwitchStatement)parent; + IBlock swblock = getBlock(swStmt.getControllerExpression(), + (IASTStatement)parent); + IBlock caseblock = getBlock(stmt); + ControlFlowEdge(swblock, caseblock); + IBlock next = nextBlock(stmt); + ControlFlowEdge(caseblock, next); + } + else if(stmt instanceof IASTCompoundStatement){ + } + else if(stmt instanceof IASTContinueStatement){ + /** A continue statement flows to the continue_join_type block */ + if(traceOn) System.out.println("ContinueStatement"); + IBlock block = getBlock(stmt); + IASTNode parent = stmt.getParent(); + while(true){ + if(parent instanceof IASTDoStatement || + parent instanceof IASTForStatement || + parent instanceof IASTWhileStatement){ + IBlock continuejoin = getBlock(null, (IASTStatement)parent, + Block.continue_join_type); + ControlFlowEdge(block, continuejoin); + break; + } + else{ + parent = parent.getParent(); + } + } + } + else if(stmt instanceof IASTDeclarationStatement){ + /** Except the regular variable declaration statements, the + * initializer of a for statement could also be a + * declaration statement. In the latter case, the flow + * relation is already calculated and therefore nothing + * is done here. */ + if(traceOn) System.out.println("DeclarationStatement"); + IASTNode parent = stmt.getParent(); + if(parent instanceof IASTForStatement){ + IASTForStatement forStmt = (IASTForStatement)parent; + if(forStmt.getInitializerStatement() == stmt) + return PROCESS_CONTINUE; + } + IBlock block = getBlock(stmt); + IBlock next = nextBlock(stmt); + ControlFlowEdge(block, next); + } + else if(stmt instanceof IASTDoStatement){ + /** We calculate four types of control flows here: + * (1) the condition block flows to the first block of the loop body + * (2) the condition block flows to the exit_join_type block + * (3) the continue_join_type block flows to the condition block + * (4) the exit_join_type block flows to the next statement after + * this do loop + */ + if(traceOn) System.out.println("DoStatement"); + IASTDoStatement doStmt = (IASTDoStatement)stmt; + IBlock cond = getBlock(doStmt.getCondition(), stmt); + if(doStmt.getBody() == null){ + ControlFlowEdge(cond, cond); + } else { + IBlock first = firstBlock(doStmt.getBody()); + ControlFlowEdge(cond, first); + IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); + ControlFlowEdge(continuejoin, cond); + } + IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); + ControlFlowEdge(cond, exitjoin); + IBlock next = nextBlock(stmt); + ControlFlowEdge(exitjoin, next); + } + else if(stmt instanceof IASTExpressionStatement){ + /** If the expression statement is the initializer of a for + * loop, do nothing here. If this statement contains an + * "exit" function call, it flows to the exit block of the + * current function */ + if(traceOn) System.out.println("ExpressionSatement"); + IASTNode parent = stmt.getParent(); + if(parent instanceof IASTForStatement){ + IASTForStatement forStmt = (IASTForStatement)parent; + if(forStmt.getInitializerStatement() == stmt) + return PROCESS_CONTINUE; + } + IBlock block = getBlock(stmt); + IASTExpressionStatement exprStmt = (IASTExpressionStatement)stmt; + exitBlock = false; + exprStmt.getExpression().accept(this); + if(exitBlock){ + ControlFlowEdge(block, exit_); + } + else { + IBlock next = nextBlock(stmt); + ControlFlowEdge(block, next); + } + } + else if(stmt instanceof IASTForStatement){ + /** In a for loop, the initializer flows to the loop condition, + * the loop condition flows to the first statement in the loop + * body and the block with exit_join_type. The continue_join_type + * block flows to the iterator, and the iterator flows to the + * condition block */ + if(traceOn) System.out.println("ForStatement"); + IASTForStatement forStmt = (IASTForStatement)stmt; + IASTStatement initStmt = forStmt.getInitializerStatement(); + IBlock init = getBlock(initStmt); + IBlock cond = getBlock(forStmt.getConditionExpression(), stmt); + IBlock iter = null; + IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); + IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); + + if(forStmt.getIterationExpression() != null) + iter = getBlock(forStmt.getIterationExpression(), stmt); + + /* The empty initialization will be a Null statement */ + ControlFlowEdge(init, cond); + + if(forStmt.getBody() != null){ + IBlock first = firstBlock(forStmt.getBody()); + ControlFlowEdge(cond, first); + if(iter != null){ + ControlFlowEdge(continuejoin, iter); + ControlFlowEdge(iter, cond); + } else + ControlFlowEdge(continuejoin, cond); + } else { + if(iter != null){ + ControlFlowEdge(cond, iter); + ControlFlowEdge(iter, cond); + } else { + ControlFlowEdge(cond, cond); + } + } + ControlFlowEdge(cond, exitjoin); + IBlock next = nextBlock(stmt); + ControlFlowEdge(exitjoin, next); + } + else if(stmt instanceof IASTGotoStatement){ + /** Goto statement flows to the corresponding label statement */ + if(traceOn) System.out.println("GotoStatement"); + IASTGotoStatement gotoStmt = (IASTGotoStatement)stmt; + IBlock label = getBlock(gotoStmt.getName(), gotoStmt, Block.label_type); + if(label == null){ + System.out.println("Null Label Error"); + } + IBlock block = getBlock(gotoStmt); + ControlFlowEdge(block, label); + } + else if(stmt instanceof IASTIfStatement){ + /** The if condition block flows to the first block of the + * then(else) clause if it is not empty, the exit_join_type + * block otherwise */ + if(traceOn) System.out.println("IfStatement"); + IASTIfStatement ifStmt = (IASTIfStatement)stmt; + IBlock condb = getBlock(ifStmt.getConditionExpression(), stmt); + IBlock join = getBlock(null, stmt, Block.exit_join_type); + if(ifStmt.getThenClause() != null){ + IBlock thenb = firstBlock(ifStmt.getThenClause()); + ControlFlowEdge(condb, thenb); + } else { + ControlFlowEdge(condb, join); + } + + if(ifStmt.getElseClause() != null){ + IBlock elseb = firstBlock(ifStmt.getElseClause()); + ControlFlowEdge(condb, elseb); + } else { + ControlFlowEdge(condb, join); + } + IBlock next = nextBlock(stmt); + ControlFlowEdge(join, next); + } + else if(stmt instanceof IASTLabelStatement){ + /** If there is a nested statement, the label statement flows + * to the first block of the nested statement + */ + if(traceOn) System.out.println("LabelStatement"); + IASTLabelStatement label = (IASTLabelStatement)stmt; + IBlock block = getBlock(label.getName(), stmt, Block.label_type); + if(label.getNestedStatement() == null){ + IBlock next = nextBlock(stmt); + ControlFlowEdge(block, next); + } else { + IBlock next = firstBlock(label.getNestedStatement()); + ControlFlowEdge(block, next); + } + } + else if(stmt instanceof IASTNullStatement){ + if(traceOn) System.out.println("NullStatement"); + IASTNode parent = stmt.getParent(); + if(parent instanceof IASTForStatement){ + IASTForStatement forStmt = (IASTForStatement)parent; + if(forStmt.getInitializerStatement() == stmt) + return PROCESS_CONTINUE; + } + IBlock block = getBlock(stmt); + IBlock next = nextBlock(stmt); + ControlFlowEdge(block, next); + } + else if(stmt instanceof IASTProblemStatement){ + if(traceOn) System.out.println("ProblemStatement"); + IBlock block = getBlock(stmt); + IBlock next = nextBlock(stmt); + ControlFlowEdge(block, next); + } + else if(stmt instanceof IASTReturnStatement){ + /* The return statement flows to the exit block */ + if(traceOn) System.out.println("ReturnStatement"); + IASTReturnStatement rtStmt = (IASTReturnStatement)stmt; + IBlock rv = getBlock(rtStmt.getReturnValue(), stmt); + ControlFlowEdge(rv, exit_); + } + else if(stmt instanceof IASTSwitchStatement){ + /** The exit_join block of a switch statement flows to the + * first block of the next statement + */ + if(traceOn) System.out.println("SwitchStatement"); + IBlock join = getBlock(null, stmt, Block.exit_join_type); + IBlock next = nextBlock(stmt); + ControlFlowEdge(join, next); + } + else if(stmt instanceof IASTWhileStatement){ + /** The condition block of a while loop flows to the first + * statement in the loop body and the exit_join block. + * The condition_join block flows to the condition block. + */ + if(traceOn) System.out.println("WhileStatement"); + IASTWhileStatement whStmt = (IASTWhileStatement)stmt; + IBlock cond = getBlock(whStmt.getCondition(), stmt); + IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); + IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); + if(whStmt.getBody() == null){ + ControlFlowEdge(cond, cond); + } else { + IBlock first = firstBlock(whStmt.getBody()); + ControlFlowEdge(cond, first); + ControlFlowEdge(continuejoin, cond); + } + IBlock next = nextBlock(stmt); + ControlFlowEdge(cond, exitjoin); + ControlFlowEdge(exitjoin, next); + } + return PROCESS_CONTINUE; + } + + /* + * @return the first block of stmt + */ + public IBlock firstBlock(IASTStatement stmt){ + + if(stmt instanceof IASTBreakStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTCaseStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTCompoundStatement){ + IASTCompoundStatement cmpStmt = (IASTCompoundStatement)stmt; + IASTStatement[] stmts = cmpStmt.getStatements(); + for(int i=0; i<stmts.length; i++){ + if(stmts[i] != null) return firstBlock(stmts[i]); + } + /* The compound statement is empty. Return the first block + * of the next Statement. + */ + return nextBlock(stmt); + } + else if(stmt instanceof IASTContinueStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTDeclarationStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTDefaultStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTDoStatement){ + IASTDoStatement doStmt = (IASTDoStatement)stmt; + if(doStmt.getBody() != null) + return firstBlock(doStmt.getBody()); + else + return getBlock(doStmt.getCondition(), stmt); + } + else if(stmt instanceof IASTExpressionStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTForStatement){ + IASTForStatement forStmt = (IASTForStatement)stmt; + IASTStatement initS = forStmt.getInitializerStatement(); + if(initS != null) + return getBlock(initS); + else + return getBlock(forStmt.getConditionExpression(), stmt); + } + else if(stmt instanceof IASTGotoStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTIfStatement){ + IASTIfStatement ifStmt = (IASTIfStatement)stmt; + return getBlock(ifStmt.getConditionExpression(), stmt); + } + else if(stmt instanceof IASTLabelStatement){ + IASTLabelStatement label = (IASTLabelStatement)stmt; + return getBlock(label.getName(), stmt, Block.label_type); + } + else if(stmt instanceof IASTNullStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTProblemStatement){ + return getBlock(stmt); + } + else if(stmt instanceof IASTReturnStatement){ + IASTReturnStatement rtStmt = (IASTReturnStatement)stmt; + return getBlock(rtStmt.getReturnValue(), stmt); + } + else if(stmt instanceof IASTSwitchStatement){ + IASTSwitchStatement swStmt = (IASTSwitchStatement)stmt; + return getBlock(swStmt.getControllerExpression(), stmt); + } + else if(stmt instanceof IASTWhileStatement){ + IASTWhileStatement whStmt = (IASTWhileStatement)stmt; + return getBlock(whStmt.getCondition(), stmt); + } + return null; + } + + + /* + * @return + */ + public IBlock nextBlock(IASTStatement stmt){ + + IASTNode node = stmt.getParent(); + if(!(node instanceof IASTStatement)){ + /* empty return statement for void-typed functions */ + return exit_; + } + + IASTStatement parent = (IASTStatement)node; + if(parent instanceof IASTCompoundStatement){ + IASTCompoundStatement cmpStmt = (IASTCompoundStatement)parent; + IASTStatement[] stmts = cmpStmt.getStatements(); + int i; + for(i=0; i<stmts.length; i++){ + if(stmts[i] == stmt) break; + } + for(i=i+1; i<stmts.length; i++){ + if(stmts[i] != null) return firstBlock(stmts[i]); + } + /*stmt is the last one in compound statement */ + return nextBlock(parent); + } + else if(parent instanceof IASTDeclarationStatement){ + return nextBlock(parent); + } + else if(parent instanceof IASTDoStatement){ + /* "stmt" is the body of Do statement, control flows to + * the continue join block + */ + return getBlock(null, parent, Block.continue_join_type); + } + else if(parent instanceof IASTForStatement){ + /* control flows to the for loop continue join block */ + return getBlock(null, parent, Block.continue_join_type); + } + else if(parent instanceof IASTIfStatement){ + return getBlock(null, parent, Block.exit_join_type); + } + else if(parent instanceof IASTLabelStatement){ + return nextBlock(parent); + } + else if(parent instanceof IASTSwitchStatement){ + return getBlock(null, parent, Block.exit_join_type); + } + else if(parent instanceof IASTWhileStatement){ + return getBlock(null, parent, Block.continue_join_type); + } + else + return nextBlock(parent); + } + + private void ControlFlowEdge(IBlock from, IBlock to){ + if(!from.getSuccs().contains(to)) + from.getSuccs().add(to); + if(!to.getPreds().contains(from)) + to.getPreds().add(from); + } + + public int visit(IASTExpression expr){ + if (expr instanceof IASTFunctionCallExpression) { + IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression)expr; + IASTExpression funcname = funcExpr.getFunctionNameExpression(); + String signature = funcname.getRawSignature(); + if(signature.equals("exit")){ + exitBlock = true; + } + return PROCESS_SKIP; + } + return PROCESS_CONTINUE; + } + } + + + protected void addBasicBlock(IBlock block){ + if(!BBs_.contains(block)) + BBs_.add(block); + } + + public IBlock getBlock(IASTExpression expr, IASTStatement parent) { + for(Iterator<IBlock> i = BBs_.iterator(); i.hasNext();){ + IBlock bb = i.next(); + if(bb.search(expr, parent)) return bb; + } + return null; + } + + public IBlock getBlock(IASTStatement stmt){ + for(Iterator<IBlock> i = BBs_.iterator(); i.hasNext();){ + IBlock bb = i.next(); + if(bb.search(stmt)) return bb; + } + return null; + } + + public IBlock getBlock(IASTName label){ + for(Iterator<IBlock> i = BBs_.iterator(); i.hasNext();){ + IBlock bb = i.next(); + if(bb.search(label)) return bb; + } + return null; + } + + public IBlock getBlock(IASTNode content, IASTStatement parent, int type){ + for(Iterator<IBlock> i = BBs_.iterator(); i.hasNext();){ + Block bb = (Block)i.next(); + if(bb.search(content, parent, type)) return bb; + } + return null; + } + + public IBlock getEntry() { + return entry_; + } + + public IBlock getExit() { + return exit_; + } + + public void addBlock(IBlock bb){ + if(!BBs_.contains(bb)) + BBs_.add(bb); + } + + @SuppressWarnings("unchecked") + public void buildDOM(){ + List<IBlock> all = new ArrayList<IBlock>(); + all.add(entry_); + all.addAll(BBs_); + all.add(exit_); + + entry_.getDOM().add(entry_); + + Iterator<IBlock> i; + for(i = BBs_.iterator(); i.hasNext();){ + i.next().setDOM(all); + } + exit_.setDOM(all); + + boolean change = true; + while(change){ + change = false; + for(i = all.iterator(); i.hasNext();){ + IBlock block = i.next(); + if(block == entry_) continue; + List<IBlock> temp = new ArrayList<IBlock>(all); + for(Iterator<IBlock> ii = block.getPreds().iterator(); ii.hasNext();){ + IBlock pred = ii.next(); + temp = intersect(temp, pred.getDOM()); + } + List<IBlock> D = new ArrayList<IBlock>(temp); + if(!D.contains(block)) D.add(block); + if(!equals(D, block.getDOM())){ + change = true; + block.setDOM(D); + } + } + } + } + + public void buildPDOM(){ + /* TODO */ + } + + @SuppressWarnings("unchecked") + public List intersect(List A, List B){ + if(A == null || B == null) return null; + List list = new ArrayList(); + for(Iterator i = A.iterator(); i.hasNext();){ + Object o = i.next(); + if(B.contains(o)) list.add(o); + } + return list; + } + @SuppressWarnings("unchecked") + public boolean equals(List A, List B){ + if(A == null && B == null) return true; + if(A == null && B != null) return false; + if(A != null && B == null) return false; + if(A.size() != B.size()) return false; + for(Iterator i = A.iterator(); i.hasNext();){ + if(!B.contains(i.next())) return false; + } + return true; + } + + /** + * Sort Blocks in topological order + */ + private Stack<IBlock> order; + protected void sort(){ + List<IBlock> all = new ArrayList<IBlock>(); + all.add(entry_); + all.addAll(BBs_); + all.add(exit_); + for(Iterator<IBlock> i = all.iterator(); i.hasNext();){ + IBlock block = i.next(); + block.setAttr("color", new Integer(0)); + } + order = new Stack<IBlock>(); + for(Iterator<IBlock> i = all.iterator(); i.hasNext();){ + IBlock block = (IBlock)i.next(); + int color = ((Integer)block.getAttr("color")).intValue(); + if(color == 0) + DFSVisit(block); + } + + IBlock b1 = order.pop(); + IBlock b2 = null; + while(!order.empty()){ + b2 = order.pop(); + b1.setTopNext(b2); + b1 = b2; + } + } + + protected void DFSVisit(IBlock block){ + block.setAttr("color", new Integer(1)); //gray + for(Iterator<IBlock> i = block.getSuccs().iterator(); i.hasNext();){ + IBlock succ = i.next(); + if(isBackEdgeSucc(block, succ)) continue; + int color = ((Integer)succ.getAttr("color")).intValue(); + if(color == 0) //white + DFSVisit(succ); + } + order.push(block); + } + + /** + * @return "true" if edge (from, to) is a back edge. + */ + protected boolean isBackEdgeSucc(IBlock from, IBlock to){ + return from.getSuccs().contains(to) && from.getDOM().contains(to); + } + + protected void otherOPs(){ + /* Empty method for future extensions */ + } + + public void print(){ + for(IBlock b = entry_; b != null; b = b.topNext()) + b.print(); + } + +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ResourceCollector.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ResourceCollector.java new file mode 100644 index 0000000..a91d798 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ResourceCollector.java @@ -0,0 +1,155 @@ +/********************************************************************** + * Copyright (c) 2007,2008 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.cdt.graphs.impl; + +import java.util.List; + +import org.eclipse.cdt.core.dom.CDOM; +import org.eclipse.cdt.core.dom.IASTServiceProvider; +import org.eclipse.cdt.core.dom.ast.ASTVisitor; +import org.eclipse.cdt.core.dom.ast.IASTCompositeTypeSpecifier; +import org.eclipse.cdt.core.dom.ast.IASTDeclSpecifier; +import org.eclipse.cdt.core.dom.ast.IASTDeclaration; +import org.eclipse.cdt.core.dom.ast.IASTDeclarator; +import org.eclipse.cdt.core.dom.ast.IASTElaboratedTypeSpecifier; +import org.eclipse.cdt.core.dom.ast.IASTEnumerationSpecifier; +import org.eclipse.cdt.core.dom.ast.IASTFunctionDeclarator; +import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTSimpleDeclaration; +import org.eclipse.cdt.core.dom.ast.IASTTranslationUnit; +import org.eclipse.core.resources.IFile; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraph; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode; + +/** + * The resource collector collects all functions for the call graph, but does not + * calculate the caller and callee relations. + * + * @author Yuan Zhang, Beth Tibbitts + * + */ +public class ResourceCollector extends ASTVisitor { + protected ICallGraph CG_; + protected IFile file_; + protected int depth; + + /** + * Resource collector finds all functions in a given source file, + * and adds them to the given call graph + * @param cg call graph that will have this information added to it + * @param file source file whose functions will be discovered and catalogued + */ + public ResourceCollector(ICallGraph cg, IFile file){ + CG_ = cg; + file_ = file; + } + + /** + * Use an ASTVisitor to discover the functions in the the given source and add them to the call graph + */ + public void run(){ + this.shouldVisitDeclarations = true; + this.shouldVisitTranslationUnit = true; + IASTTranslationUnit ast_ = null; + try { + ast_ = CDOM.getInstance().getASTService().getTranslationUnit(file_, + CDOM.getInstance().getCodeReaderFactory(CDOM.PARSE_SAVED_RESOURCES)); + } catch (IASTServiceProvider.UnsupportedDialectException e) { + } + depth = 0; + ast_.accept(this); + } + + /** + * visits declaration nodes to catalog the function declarations + */ + public int visit(IASTDeclaration declaration) { + String filename = declaration.getContainingFilename(); + // if(!filename.endsWith(".c") || !filename.endsWith(".C")) + if (filename.endsWith(".h")) + return PROCESS_SKIP; + + if (declaration instanceof IASTFunctionDefinition) { + depth++; + IASTFunctionDefinition fd = (IASTFunctionDefinition) declaration; + ICallGraphNode node = addCallGraphNode(file_, filename, fd); + CG_.addNode(node); + return PROCESS_SKIP; + } else if (declaration instanceof IASTSimpleDeclaration) { + if (depth > 0) + return PROCESS_SKIP; // not global + IASTSimpleDeclaration sdecl = (IASTSimpleDeclaration) declaration; + /* if the declarator is null, then it is a structure specifier */ + if (sdecl.getDeclarators() == null) + return PROCESS_CONTINUE; + IASTDeclSpecifier spec = sdecl.getDeclSpecifier(); + if (spec instanceof IASTCompositeTypeSpecifier + || spec instanceof IASTElaboratedTypeSpecifier + || spec instanceof IASTEnumerationSpecifier) + return PROCESS_SKIP; + + List<String> env = CG_.getEnv(); + IASTDeclarator[] declarators = sdecl.getDeclarators(); + for (int j = 0; j < declarators.length; j++) { + if (declarators[j] instanceof IASTFunctionDeclarator) + continue; + IASTName n = declarators[j].getName(); + String var = n.toString(); + if (doQuickOptionalTest(var)) + continue; + if (!env.contains(var)) + env.add(var); + doOtherDeClaratorStuff(declarators[j]); + } + } + return PROCESS_CONTINUE; + } + + + public int leave(IASTDeclaration declaration) + { + String filename = declaration.getContainingFilename(); + //if(!filename.endsWith(".c") || !filename.endsWith(".C")) + if(filename.endsWith(".h")) + return PROCESS_SKIP; + + if (declaration instanceof IASTFunctionDefinition) { + depth --; + return PROCESS_SKIP; + } + return PROCESS_CONTINUE; + } + /** + * Can be overridden by subclasses to create a specific kind of call graph + * node if required + * + * @return call graph node created + */ + protected ICallGraphNode addCallGraphNode(IFile file, String filename, + IASTFunctionDefinition fd) { + ICallGraphNode cgnode = new CallGraphNode(file, filename, fd); + return cgnode; + } + /** + * extra optional test that derived class can do + */ + protected boolean doQuickOptionalTest(String var){ + return true; + } + + /** + * optional stuff that derived class may want to do at this point + * @param declarator + */ + protected void doOtherDeClaratorStuff(IASTDeclarator declarator){} +} |