| /********************************************************************** |
| * Copyright (c) 2007,2010 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.Enumeration; |
| import java.util.Hashtable; |
| import java.util.Iterator; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Stack; |
| |
| import org.eclipse.cdt.core.dom.ast.ASTVisitor; |
| import org.eclipse.cdt.core.dom.ast.IASTArraySubscriptExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTBinaryExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTCastExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTConditionalExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTDeclaration; |
| import org.eclipse.cdt.core.dom.ast.IASTDeclarationStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTDeclarator; |
| import org.eclipse.cdt.core.dom.ast.IASTDoStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTExpressionList; |
| import org.eclipse.cdt.core.dom.ast.IASTExpressionStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTFieldReference; |
| import org.eclipse.cdt.core.dom.ast.IASTForStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTFunctionCallExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTFunctionDeclarator; |
| import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition; |
| import org.eclipse.cdt.core.dom.ast.IASTIdExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTIfStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTInitializer; |
| import org.eclipse.cdt.core.dom.ast.IASTInitializerClause; |
| import org.eclipse.cdt.core.dom.ast.IASTInitializerExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTInitializerList; |
| import org.eclipse.cdt.core.dom.ast.IASTLiteralExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTName; |
| import org.eclipse.cdt.core.dom.ast.IASTNode; |
| import org.eclipse.cdt.core.dom.ast.IASTParameterDeclaration; |
| import org.eclipse.cdt.core.dom.ast.IASTProblemExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTSimpleDeclaration; |
| import org.eclipse.cdt.core.dom.ast.IASTStandardFunctionDeclarator; |
| import org.eclipse.cdt.core.dom.ast.IASTStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTSwitchStatement; |
| import org.eclipse.cdt.core.dom.ast.IASTTypeIdExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTUnaryExpression; |
| import org.eclipse.cdt.core.dom.ast.IASTWhileStatement; |
| import org.eclipse.cdt.core.dom.ast.c.ICASTTypeIdInitializerExpression; |
| import org.eclipse.cdt.core.dom.ast.gnu.c.ICASTKnRFunctionDeclarator; |
| import org.eclipse.cdt.internal.core.dom.parser.IASTAmbiguousExpression; |
| import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; |
| import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraph; |
| import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode; |
| import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph; |
| |
| /** |
| * MPI Multi-Valued analysis |
| * |
| * @author zhangyua |
| * |
| */ |
| public class MPIMVAnalysis { |
| class BroadCastAnalyzer extends ASTVisitor { |
| private final IBlock block_; |
| private String var; |
| |
| public BroadCastAnalyzer(IBlock block) { |
| block_ = block; |
| var = null; |
| } |
| |
| public String getBCdata() { |
| return var; |
| } |
| |
| public void run() { |
| this.shouldVisitStatements = true; |
| this.shouldVisitExpressions = true; |
| IASTNode content = block_.getContent(); |
| if (content != null) { |
| content.accept(this); |
| } |
| } |
| |
| @Override |
| public int visit(IASTExpression expr) { |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcE = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcE.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| if (signature.equals("MPI_Bcast")) { //$NON-NLS-1$ |
| IASTInitializerClause[] arguments = funcE.getArguments(); |
| if (arguments.length > 0 && arguments[0] instanceof IASTExpression) { |
| IASTExpression dataE = (IASTExpression) arguments[0]; |
| if (dataE instanceof IASTIdExpression) { |
| IASTIdExpression ID = (IASTIdExpression) dataE; |
| var = ID.getName().toString(); |
| } else if (dataE instanceof IASTUnaryExpression) { |
| IASTUnaryExpression uE = (IASTUnaryExpression) dataE; |
| if (uE.getOperator() == IASTUnaryExpression.op_amper && uE.getOperand() instanceof IASTIdExpression) { |
| IASTIdExpression ID = (IASTIdExpression) uE.getOperand(); |
| var = ID.getName().toString(); |
| } |
| } |
| } |
| } |
| return PROCESS_SKIP; |
| } |
| return PROCESS_CONTINUE; |
| } |
| |
| } |
| |
| /** |
| * Expression Multi-valued Analyzer |
| * |
| */ |
| class ExprMVAnalyzer { |
| private IASTStatement stmt_; |
| private IASTExpression expr_; |
| private final List<String> context_; |
| private final MPIBlock currentBlock_; |
| |
| private final List<String> MVvar_; |
| private final Stack<boolean[]> exprListMVContext_; |
| |
| private boolean value; |
| |
| public ExprMVAnalyzer(IASTExpression expr, List<String> context, MPIBlock block) { |
| stmt_ = null; |
| expr_ = expr; |
| context_ = context; |
| currentBlock_ = block; |
| MVvar_ = new ArrayList<String>(); |
| exprListMVContext_ = new Stack<boolean[]>(); |
| value = false; |
| } |
| |
| public ExprMVAnalyzer(IASTNode node, List<String> context, MPIBlock block) {// BRT |
| // this |
| // one |
| // is |
| // called |
| if (node instanceof IASTExpression) { |
| stmt_ = null; |
| expr_ = (IASTExpression) node; |
| } else if (node instanceof IASTStatement) { |
| stmt_ = (IASTStatement) node; |
| expr_ = null; |
| } |
| context_ = context; |
| currentBlock_ = block; |
| MVvar_ = new ArrayList<String>(); |
| exprListMVContext_ = new Stack<boolean[]>(); |
| value = false; |
| } |
| |
| public ExprMVAnalyzer(IASTStatement stmt, List<String> context, MPIBlock block) { |
| stmt_ = stmt; |
| expr_ = null; |
| context_ = context; |
| currentBlock_ = block; |
| MVvar_ = new ArrayList<String>(); |
| exprListMVContext_ = new Stack<boolean[]>(); |
| value = false; |
| } |
| |
| public List<String> getMVList() { |
| return MVvar_; |
| } |
| |
| public boolean isMV() { |
| return value; |
| } |
| |
| public void run() { |
| if (stmt_ != null) { |
| value = useDefMVMapping(stmt_); |
| } else if (expr_ != null) { |
| List<String> defset = new ArrayList<String>(); |
| value = useDefMVMapping(expr_, rhs, null, defset); |
| } |
| } |
| |
| /** |
| * Returns true if multi-valued? //BRT |
| * |
| * @param init |
| * @return |
| */ |
| // BRT make sure this gets called, but will it be with these args? |
| // / not in a tree walk; perhaps with args gleaned from fn call |
| private boolean handleInitializer(IASTInitializer init) { |
| if (init instanceof IASTInitializerExpression) { |
| IASTInitializerExpression initE = (IASTInitializerExpression) init; |
| IASTExpression expr = initE.getExpression(); |
| List<String> mvlist = new ArrayList<String>(); |
| return useDefMVMapping(expr, rhs, null, mvlist); |
| } else if (init instanceof IASTInitializerList) {// BRT |
| IASTInitializerList initList = (IASTInitializerList) init; |
| IASTInitializer[] list = initList.getInitializers(); |
| boolean listvalue = false; |
| for (int i = 0; i < list.length; i++) { |
| listvalue = listvalue | handleInitializer(list[i]); |
| } |
| return listvalue; |
| } |
| return false; |
| } |
| |
| /** |
| * @param side |
| * @param set |
| * @param v1 |
| * @param l1 |
| * @param funcE |
| * @param newParameterList |
| * @param n |
| * @param returnval |
| * @return |
| */ |
| private boolean newParameterUse(int side, List<String> set, boolean v1, List<String> l1, IASTFunctionCallExpression funcE, |
| IASTInitializerClause[] newParameterList, MPICallGraphNode n, boolean returnval) { |
| if (newParameterList != null) { |
| |
| // boolean[] newContext = new boolean[parameter2.length]; |
| boolean context; |
| for (int i = 0; i < newParameterList.length; i++) { |
| IASTInitializerClause ic = newParameterList[i]; |
| if (ic instanceof IASTExpression) { // BRT?? is it?? |
| ic.getRawSignature(); |
| IASTExpression iexpr = (IASTExpression) ic; |
| v1 = v1 | useDefMVMapping(iexpr, side, funcE, l1); |
| context = v1; |
| Util.addAll(set, l1); // BRT ????? |
| |
| // --- put this inside this loop, don't need another |
| // loop |
| if (context) { |
| String param = getFormalParamName(n, i); |
| if (param != null) { |
| List<String> mvlist = n.getMVSummary().get(param); |
| Util.addAll(MVvar_, mvlist); |
| if (mvlist.contains(n.getFuncName())) { // return |
| // MV |
| // value |
| MVvar_.remove(n.getFuncName()); |
| returnval = true; |
| } |
| } |
| } |
| // --- |
| } |
| // omit exprListMVContext_.push(newContext); |
| } |
| |
| } |
| return returnval; |
| } |
| |
| /** |
| * @param parameter |
| * @param cgNode |
| * @param returnval |
| * @return |
| */ |
| private boolean oldParameterUse(IASTExpression parameter, MPICallGraphNode cgNode, boolean returnval) { |
| if (parameter instanceof IASTExpressionList) { // >1 parameter |
| boolean[] paramContext = exprListMVContext_.pop(); |
| for (int i = 0; i < paramContext.length; i++) { |
| if (paramContext[i]) { |
| String param = getFormalParamName(cgNode, i); |
| if (param != null) { |
| List<String> mvlist = cgNode.getMVSummary().get(param); |
| Util.addAll(MVvar_, mvlist); |
| if (mvlist.contains(cgNode.getFuncName())) { // return |
| // MV |
| // value |
| MVvar_.remove(cgNode.getFuncName()); |
| returnval = true; |
| } |
| } |
| } |
| } |
| } else { // single parameter |
| String param = getFormalParamName(cgNode, 0); |
| if (param != null) { |
| List<String> mvlist = cgNode.getMVSummary().get(param); |
| Util.addAll(MVvar_, mvlist); |
| if (mvlist.contains(cgNode.getFuncName())) { // return MV |
| // value |
| MVvar_.remove(cgNode.getFuncName()); |
| returnval = true; |
| } |
| } |
| } |
| return returnval; |
| } |
| |
| /** |
| * Return true if "expr" is multi_valued. |
| * |
| * @param expr |
| * expression to determine if multi-valued |
| * @param side |
| * LHS or RHS |
| * @param func |
| * @param set |
| * contains all defined variables in "expr" through |
| * assignment |
| */ |
| private boolean useDefMVMapping(IASTExpression expr, int side, IASTFunctionCallExpression func, List<String> set) { |
| boolean v1 = false, v2 = false, v3 = false; |
| List<String> l1 = new ArrayList<String>(); |
| List<String> l2 = new ArrayList<String>(); |
| List<String> l3 = new ArrayList<String>(); |
| if (expr == null) { |
| return false; |
| } |
| if (expr instanceof IASTAmbiguousExpression) { |
| } else if (expr instanceof IASTArraySubscriptExpression) { |
| IASTArraySubscriptExpression asE = (IASTArraySubscriptExpression) expr; |
| if (side == rhs) { |
| // = a[index_expr] |
| v1 = useDefMVMapping(asE.getArrayExpression(), rhs, func, l1); |
| v2 = useDefMVMapping(asE.getSubscriptExpression(), rhs, func, l2); |
| } else { // lhs |
| // a[b[i]] = ... , a is defined, b and i are used |
| v1 = useDefMVMapping(asE.getSubscriptExpression(), rhs, func, l1); |
| v2 = useDefMVMapping(asE.getArrayExpression(), lhs, func, l2); |
| } |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| return v1 | v2; |
| } else if (expr instanceof IASTBinaryExpression) { |
| IASTBinaryExpression biE = (IASTBinaryExpression) expr; |
| int op = biE.getOperator(); |
| if (op == IASTBinaryExpression.op_assign) { |
| // x = y = z is right associative --> x = (y = z) |
| // So the "side" will be always rhs |
| v1 = useDefMVMapping(biE.getOperand1(), lhs, func, l1); |
| v2 = useDefMVMapping(biE.getOperand2(), rhs, func, l2); |
| if (v2) { |
| Util.addAll(MVvar_, l1); |
| } |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| } else if (op == IASTBinaryExpression.op_multiplyAssign || op == IASTBinaryExpression.op_divideAssign |
| || op == IASTBinaryExpression.op_moduloAssign || op == IASTBinaryExpression.op_plusAssign |
| || op == IASTBinaryExpression.op_minusAssign || op == IASTBinaryExpression.op_shiftLeftAssign |
| || op == IASTBinaryExpression.op_shiftRightAssign || op == IASTBinaryExpression.op_binaryAndAssign |
| || op == IASTBinaryExpression.op_binaryXorAssign || op == IASTBinaryExpression.op_binaryOrAssign) { |
| v1 = useDefMVMapping(biE.getOperand1(), rhs, func, l1); |
| v2 = useDefMVMapping(biE.getOperand2(), rhs, func, l2); |
| v3 = useDefMVMapping(biE.getOperand1(), lhs, func, l3); |
| if (v1 | v2) { |
| Util.addAll(MVvar_, l3); |
| } |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| Util.addAll(set, l3); |
| } else { |
| v1 = useDefMVMapping(biE.getOperand1(), rhs, func, l1);// BRT |
| // results |
| // are |
| // diff |
| // from |
| // 3.0! |
| v2 = useDefMVMapping(biE.getOperand2(), rhs, func, l2); |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| } |
| return v1 | v2 | v3; |
| } else if (expr instanceof IASTCastExpression) { |
| IASTCastExpression castE = (IASTCastExpression) expr; |
| v1 = useDefMVMapping(castE.getOperand(), side, func, l1); |
| Util.addAll(set, l1); |
| return v1; |
| } else if (expr instanceof IASTConditionalExpression) { |
| IASTConditionalExpression condE = (IASTConditionalExpression) expr; |
| if (side == rhs) { |
| v1 = useDefMVMapping(condE.getLogicalConditionExpression(), rhs, func, l1); |
| v2 = useDefMVMapping(condE.getPositiveResultExpression(), rhs, func, l2); |
| v3 = useDefMVMapping(condE.getNegativeResultExpression(), rhs, func, l3); |
| } else { |
| // eg. (x > y ? x : y) = 1 |
| v1 = useDefMVMapping(condE.getLogicalConditionExpression(), rhs, func, l1); |
| v2 = useDefMVMapping(condE.getPositiveResultExpression(), lhs, func, l2); |
| v3 = useDefMVMapping(condE.getNegativeResultExpression(), lhs, func, l3); |
| } |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| Util.addAll(set, l3); |
| return v1 | v2 | v3; |
| } else if (expr instanceof IASTExpressionList) {// BRT |
| // IASTExpressionList |
| // no longer in AST; |
| // see below |
| IASTExpressionList exprList = (IASTExpressionList) expr;// But |
| // this |
| // *DOES* |
| // get |
| // called. |
| // 3-deep |
| // recursive |
| // call |
| // of |
| // useDevMVMapping |
| IASTExpression[] exprs = exprList.getExpressions(); |
| boolean[] newContext_ = new boolean[exprs.length]; |
| for (int i = 0; i < exprs.length; i++) { |
| v1 = v1 | useDefMVMapping(exprs[i], side, func, l1); |
| newContext_[i] = v1; |
| Util.addAll(set, l1); |
| } |
| if (func != null) { |
| exprListMVContext_.push(newContext_);// BRT note this is NOT |
| // a field! local |
| // var only |
| } |
| return v1; |
| } else if (expr instanceof IASTFieldReference) { |
| IASTFieldReference frE = (IASTFieldReference) expr; |
| v1 = useDefMVMapping(frE.getFieldOwner(), side, func, l1); |
| Util.addAll(set, l1); |
| return v1; |
| } else if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcE = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcE.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| IASTInitializerClause[] arguments = funcE.getArguments(); |
| MPICallGraphNode cgNode = (MPICallGraphNode) cg_.getNode(currentNode_.getFileName(), signature); |
| if (cgNode != null) { // BRT always null on tiny.c. ?? |
| /* |
| * 1. Determine whether each parameter is MV or SV 2. Refer |
| * to the MVsummary, find the set of MV variables according |
| * to the parameter MV context, and find out whether the |
| * return value is MV or SV |
| */ |
| boolean returnval = false; |
| if (arguments.length > 0 && arguments[0] instanceof IASTExpression) { |
| IASTExpression parameter = (IASTExpression) arguments[0]; |
| v1 = useDefMVMapping(parameter, side, funcE, l1); |
| // BRT note with CDT 7.0 the IASTExpressionList is not |
| // encountered in the AST |
| // See bug |
| // https://bugs.eclipse.org/bugs/show_bug.cgi?id=306064 |
| // But since we get it from a method call |
| // IASTFunctionCallExpression.getParameterExpression() |
| // this probably still |
| // works ok here. |
| returnval = oldParameterUse(parameter, cgNode, returnval); |
| |
| // == end context old way |
| |
| // === new way |
| // returnval = newParameterUse(side, set, v1, l1, funcE, |
| // newParameterList, cgNode, returnval); |
| // === end new way |
| } |
| for (Iterator<String> i = cgNode.getGlobalUse().iterator(); i.hasNext();) { |
| String guse = i.next(); |
| if (context_.contains(guse)) { |
| List<String> mvlist = cgNode.getMVSummary().get(guse); |
| Util.addAll(MVvar_, mvlist); |
| if (mvlist.contains(cgNode.getFuncName())) { // return |
| // MV |
| // value |
| MVvar_.remove(cgNode.getFuncName()); |
| returnval = true; |
| } |
| } |
| } |
| if (cgNode.getMVSummary().size() == 1) {// no parameter, no |
| // global use |
| List<String> mvlist = cgNode.getMVSummary().get(cgNode.getFuncName()); |
| if (mvlist.size() == 1 && mvlist.contains(cgNode.getFuncName())) { |
| returnval = true; |
| } else { |
| returnval = false; |
| } |
| } |
| return returnval; |
| }// end if cgNode!=null |
| else { |
| if (arguments.length > 0 && arguments[0] instanceof IASTExpression) { |
| IASTExpression parameter = (IASTExpression) arguments[0]; |
| v1 = useDefMVMapping(parameter, side, funcE, l1); |
| if (parameter instanceof IASTExpressionList) { |
| exprListMVContext_.pop(); |
| } |
| Util.addAll(set, l1); |
| return v1; |
| } else { |
| return false; |
| } |
| } |
| } else if (expr instanceof IASTIdExpression) { |
| IASTIdExpression id = (IASTIdExpression) expr; |
| IASTName name = id.getName(); |
| String var = name.toString(); |
| if (var.startsWith("MPI_")) { |
| return false; //$NON-NLS-1$ |
| } |
| if (side == rhs) { |
| if (func != null) { // function parameter |
| IASTExpression funcname = func.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| ICallGraphNode n = cg_.getNode(currentNode_.getFileName(), signature); |
| if (n == null) { // library function call |
| if (currentBlock_.getDef().contains(var)) { |
| if (!set.contains(var)) { |
| set.add(var); |
| } |
| if (context_.contains(var) && !MVvar_.contains(var)) { |
| MVvar_.add(var); |
| } |
| } |
| } |
| } |
| if (context_.contains(var)) { |
| return true; |
| } |
| } else { // lhs |
| if (!set.contains(var)) { |
| set.add(var); |
| } |
| return false; |
| } |
| } else if (expr instanceof IASTLiteralExpression) { |
| } else if (expr instanceof IASTProblemExpression) { |
| } else if (expr instanceof IASTTypeIdExpression) { |
| } else if (expr instanceof IASTUnaryExpression) { |
| IASTUnaryExpression uE = (IASTUnaryExpression) expr; |
| int op = uE.getOperator(); |
| if (op == IASTUnaryExpression.op_prefixIncr || op == IASTUnaryExpression.op_prefixDecr |
| || op == IASTUnaryExpression.op_postFixIncr || op == IASTUnaryExpression.op_postFixDecr) { |
| v1 = useDefMVMapping(uE.getOperand(), rhs, func, l1); |
| v2 = useDefMVMapping(uE.getOperand(), lhs, func, l2); |
| if (v1) { |
| Util.addAll(MVvar_, l2); |
| } |
| Util.addAll(set, l1); |
| Util.addAll(set, l2); |
| } else { |
| v1 = useDefMVMapping(uE.getOperand(), side, func, l1); |
| Util.addAll(set, l1); |
| } |
| return v1 | v2; |
| } else if (expr instanceof ICASTTypeIdInitializerExpression) { |
| } else { |
| } |
| return false; |
| } |
| |
| /** |
| * Returns true if statement is multi_valued. |
| */ |
| private boolean useDefMVMapping(IASTStatement stmt) { |
| if (stmt instanceof IASTDeclarationStatement) { |
| boolean value = false; |
| IASTDeclarationStatement declStmt = (IASTDeclarationStatement) stmt; |
| IASTDeclaration decl = declStmt.getDeclaration(); |
| if (decl instanceof IASTSimpleDeclaration) { |
| IASTSimpleDeclaration simpleDecl = (IASTSimpleDeclaration) decl; |
| IASTDeclarator[] declarators = simpleDecl.getDeclarators(); |
| for (int i = 0; i < declarators.length; i++) { |
| boolean v1 = false; |
| IASTInitializer init = declarators[i].getInitializer(); |
| if (init != null) { |
| IASTName name = declarators[i].getName(); |
| v1 = handleInitializer(init); |
| if (v1) { |
| if (!MVvar_.contains(name.toString())) { |
| MVvar_.add(name.toString()); |
| } |
| } |
| } |
| value = value | v1; |
| } |
| } |
| return value; |
| } else if (stmt instanceof IASTExpressionStatement) { |
| IASTExpressionStatement exprS = (IASTExpressionStatement) stmt; |
| IASTExpression expr = exprS.getExpression(); |
| List<String> mvlist = new ArrayList<String>(); |
| value = useDefMVMapping(expr, rhs, null, mvlist); |
| } |
| return false; |
| } |
| } |
| |
| class FuncParamMVChecker extends ASTVisitor { |
| protected MPICallGraphNode currentNode_; |
| protected MPIBlock block_; |
| protected MPICallGraphNode func; |
| |
| public FuncParamMVChecker(MPICallGraphNode func, MPIBlock block) { |
| currentNode_ = func; |
| block_ = block; |
| func = null; |
| } |
| |
| @Override |
| public int leave(IASTExpression expr) { |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcExpr.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| if (cg_.getNode(currentNode_.getFileName(), signature) == func) { |
| func = null; |
| } |
| } |
| return PROCESS_CONTINUE; |
| } |
| |
| public void run() { |
| this.shouldVisitExpressions = true; |
| this.shouldVisitStatements = true; |
| |
| IASTNode content = block_.getContent(); |
| if (content != null) { |
| content.accept(this); |
| } |
| } |
| |
| @Override |
| public int visit(IASTExpression expr) { |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcExpr.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| func = (MPICallGraphNode) cg_.getNode(currentNode_.getFileName(), signature); |
| if (func != null) { |
| IASTInitializerClause[] arguments = funcExpr.getArguments(); |
| for (int i = 0; i < arguments.length; i++) { |
| if (arguments[i] instanceof IASTExpression) { |
| ExprMVAnalyzer ema = new ExprMVAnalyzer(arguments[i], block_.getMVvar(), block_); |
| ema.run(); |
| if (ema.isMV()) { |
| String paramName = getFormalParamName(func, i); |
| if (paramName != null) { |
| func.getParamMV().put(paramName, new Boolean(true)); |
| } |
| } |
| } |
| } |
| } |
| } |
| return PROCESS_CONTINUE; |
| } |
| } |
| |
| class PointerAnalyzer extends ASTVisitor { |
| protected IBlock block_; |
| protected List<String> deref_; |
| protected List<String> addr_; |
| |
| public PointerAnalyzer(IBlock b) { |
| block_ = b; |
| deref_ = new ArrayList<String>(); |
| addr_ = new ArrayList<String>(); |
| } |
| |
| public List<String> getAddr() { |
| return addr_; |
| } |
| |
| public List<String> getDeref() { |
| return deref_; |
| } |
| |
| public void run() { |
| this.shouldVisitExpressions = true; |
| this.shouldVisitStatements = true; |
| IASTNode content = block_.getContent(); |
| if (content != null) { |
| content.accept(this); |
| } |
| } |
| |
| @Override |
| public int visit(IASTExpression expr) { |
| visitor(expr, false, false); |
| return PROCESS_SKIP; |
| } |
| |
| private void visitor(IASTExpression expr, boolean inDeref, boolean inAddr) { |
| if (expr instanceof IASTArraySubscriptExpression) { |
| IASTArraySubscriptExpression arrayE = (IASTArraySubscriptExpression) expr; |
| visitor(arrayE.getArrayExpression(), inDeref, inAddr); |
| visitor(arrayE.getSubscriptExpression(), false, false); |
| } else if (expr instanceof IASTBinaryExpression) { |
| IASTBinaryExpression biE = (IASTBinaryExpression) expr; |
| visitor(biE.getOperand1(), inDeref, inAddr); |
| visitor(biE.getOperand2(), inDeref, inAddr); |
| } else if (expr instanceof IASTConditionalExpression) { |
| IASTConditionalExpression condE = (IASTConditionalExpression) expr; |
| visitor(condE.getLogicalConditionExpression(), inDeref, inAddr); |
| visitor(condE.getPositiveResultExpression(), inDeref, inAddr); |
| visitor(condE.getNegativeResultExpression(), inDeref, inAddr); |
| } else if (expr instanceof IASTExpressionList) { |
| IASTExpressionList listE = (IASTExpressionList) expr; |
| IASTExpression[] exprs = listE.getExpressions(); |
| for (int i = 0; i < exprs.length; i++) { |
| visitor(exprs[i], inDeref, inAddr); |
| } |
| } else if (expr instanceof IASTFieldReference) { |
| IASTFieldReference fr = (IASTFieldReference) expr; |
| visitor(fr.getFieldOwner(), inDeref, inAddr); |
| } else if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcE = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcE.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| ICallGraphNode n = cg_.getNode(currentNode_.getFileName(), signature); |
| if (n != null) { |
| return; |
| } |
| visitor(funcE.getFunctionNameExpression(), false, false); |
| for (IASTInitializerClause argument: funcE.getArguments()) { |
| if (argument instanceof IASTExpression) { |
| visitor((IASTExpression) argument, inDeref, inAddr); |
| } |
| } |
| } else if (expr instanceof IASTIdExpression) { |
| IASTIdExpression ID = (IASTIdExpression) expr; |
| String var = ID.getName().toString(); |
| if (inDeref) { |
| if (!deref_.contains(var)) { |
| deref_.add(var); |
| } |
| } |
| if (inAddr) { |
| if (!addr_.contains(var)) { |
| addr_.add(var); |
| } |
| } |
| } else if (expr instanceof IASTUnaryExpression) { |
| IASTUnaryExpression uE = (IASTUnaryExpression) expr; |
| int op = uE.getOperator(); |
| boolean addrflag = inAddr; |
| boolean derefflag = inDeref; |
| if (op == IASTUnaryExpression.op_amper) { // &E |
| addrflag = true; |
| } else if (op == IASTUnaryExpression.op_star) { // *E |
| derefflag = true; |
| } |
| visitor(uE.getOperand(), addrflag, derefflag); |
| } |
| } |
| } |
| |
| class SeedsCollector extends ASTVisitor { |
| private MPICallGraphNode currentFunc_; |
| |
| public void run() { |
| this.shouldVisitExpressions = true; |
| this.shouldVisitStatements = true; |
| |
| for (ICallGraphNode n = cg_.botEntry(); n != null; n = n.botNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| currentFunc_ = node; |
| IControlFlowGraph cfg = node.getCFG(); |
| for (IBlock b = cfg.getEntry(); b != null; b = b.topNext()) { |
| IASTNode content = b.getContent(); |
| if (content != null) { |
| content.accept(this); |
| } |
| } |
| } |
| for (ICallGraphNode n = cg_.botEntry(); n != null; n = n.botNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| if (node.hasSeed()) { |
| for (Iterator<ICallGraphNode> i = node.getCallers().iterator(); i.hasNext();) { |
| MPICallGraphNode caller = (MPICallGraphNode) i.next(); |
| caller.setSeed(true); |
| } |
| } |
| } |
| } |
| |
| @Override |
| public int visit(IASTExpression expr) { |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcExpr.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| if (signature.equals("MPI_Comm_rank")) { //$NON-NLS-1$ |
| currentFunc_.setSeed(true); |
| } |
| } |
| return PROCESS_CONTINUE; |
| } |
| } |
| |
| /** |
| * Work list contains two kinds of blocks:<br> |
| * (1) where MPI_Comm_rank() is directly or indirectly called; <br> |
| * (2) the entry block of a function that has some MV real parameters; |
| * <p> |
| * (1) is marked in SeedsCollector and collected in WorkListCollector <br> |
| * (2) is collected in the slicing function. |
| */ |
| class WorkListCollector extends ASTVisitor { |
| private final ICallGraphNode func_; |
| private boolean inRankFunc; |
| private IASTExpressionList paramsOLD; |
| private IASTInitializerClause[] params_;// BRT will perhaps replace |
| // IASTExpressionList |
| private final LinkedList<IBlock> wlist; |
| private MPIBlock currentBlock_; |
| |
| public WorkListCollector(ICallGraphNode func) { |
| func_ = func; |
| inRankFunc = false; |
| wlist = new LinkedList<IBlock>(); |
| } |
| |
| public LinkedList<IBlock> getWorkList() { |
| if (!((MPICallGraphNode) func_).hasSeed()) { |
| return wlist; |
| } |
| |
| this.shouldVisitExpressions = true; |
| this.shouldVisitStatements = true; |
| for (IBlock b = func_.getCFG().getEntry(); b != null; b = b.topNext()) { |
| currentBlock_ = (MPIBlock) b; |
| IASTNode content = b.getContent(); |
| if (content != null) { |
| content.accept(this); |
| } |
| } |
| return wlist; |
| } |
| |
| @Override |
| public int leave(IASTExpression expr) { |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcExpr.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| if (signature.equals("MPI_Comm_rank")) { //$NON-NLS-1$ |
| inRankFunc = false; |
| } |
| params_ = null; // BRT ???? do we do this here since no more |
| // IASTExpressionList below? |
| paramsOLD = null; |
| // BRT do we need to do paramsOLD=null instead? |
| // BRTnext IASTFunctionCallExpr is one level higher in the AST |
| // than the old IASTExpressionList was |
| |
| } else if (expr instanceof IASTExpressionList) { |
| paramsOLD = null;// BRT will never reach here, |
| // IASTExpressionLlist no longer in AST tree |
| } |
| return PROCESS_CONTINUE; |
| } |
| |
| // int visitDebugCount=0; |
| @Override |
| public int visit(IASTExpression expr) { |
| // System.out.println("visitDebugCount="+visitDebugCount+" expr="+expr+" "+expr.getRawSignature()); |
| // visitDebugCount++; |
| if (expr instanceof IASTFunctionCallExpression) { |
| IASTFunctionCallExpression funcExpr = (IASTFunctionCallExpression) expr; |
| IASTExpression funcname = funcExpr.getFunctionNameExpression(); |
| String signature = funcname.getRawSignature(); |
| if (signature.equals("MPI_Comm_rank")) { //$NON-NLS-1$ |
| inRankFunc = true; |
| } else { |
| MPICallGraphNode n = (MPICallGraphNode) cg_.getNode(currentNode_.getFileName(), signature); |
| if (n != null && n.hasSeed()) { |
| if (!wlist.contains(currentBlock_)) { |
| wlist.add(currentBlock_); |
| } |
| List<String> genMV = n.getMVSummary().get(signature); |
| Util.addAll(currentBlock_.getMVvar(), genMV); |
| if (currentBlock_.getMVvar().contains(n.getFuncName())) { |
| currentBlock_.getMVvar().remove(n.getFuncName()); |
| } |
| } |
| } |
| if (inRankFunc) { |
| // BRT do what was formerly done when we hit an |
| // IASTExpressionList node. |
| IASTInitializerClause[] initClause = funcExpr.getArguments(); |
| params_ = initClause; |
| } |
| |
| } else if (expr instanceof IASTIdExpression) { // BRT NOTE: most of |
| // changes (for CDT |
| // 7.0 change) are |
| // here |
| ((IASTIdExpression) expr).getName().toString(); |
| // BRT debug cond bkpt here: var2.equals("my_rank") |
| if (inRankFunc) { |
| IASTNode me = expr; |
| IASTNode parent = me.getParent(); |
| while (true) { |
| // if(parent == params) break; // BRT ptp40: params is |
| // null. not in ptp30; there is no longer an ASTnode for |
| // the parameters |
| // else |
| if (parent instanceof IASTFunctionCallExpression) { |
| break; |
| } else { |
| if (traceOn) { |
| System.out.println("MMVA: me=parent, parent=parent.getParent()"); //$NON-NLS-1$ |
| } |
| me = parent; |
| parent = parent.getParent(); |
| } |
| } |
| me.getRawSignature(); |
| boolean temp = false;// BRT never encountered now? |
| if (temp && !(parent instanceof IASTExpressionList /* |
| * new: |
| * || |
| * parent |
| * instanceof |
| * IASTFunctionCallExpression |
| */)) { |
| return PROCESS_CONTINUE; |
| // IASTExpression[] rankParams = |
| // params.getExpressions(); |
| } |
| |
| if (params_ != null) { |
| IASTInitializerClause cl = params_[0]; |
| if (cl instanceof IASTIdExpression) { |
| //System.out.println("IASTInitializerClause is IASTIdExpression"); //$NON-NLS-1$ |
| } |
| } |
| |
| int index; |
| for (index = 0; index < params_.length; index++) { |
| // if(me == rankParams[index]) break; |
| if (me == params_[index]) { |
| break; |
| } |
| } |
| // BRT The second arg of MPI_Comm_rank is the variable that |
| // is thus multi-valued. |
| if (index == 1) { |
| IASTIdExpression id = (IASTIdExpression) expr; |
| String var = id.getName().toString(); |
| // if(var.equals("MPI_Comm_rank")) return |
| // PROCESS_CONTINUE; |
| // BRT Add this variable to the list of multivalued |
| // variables in the current block, if not already there |
| if (!currentBlock_.getMVvar().contains(var)) { |
| currentBlock_.getMVvar().add(var); |
| } |
| if (!wlist.contains(currentBlock_)) { |
| wlist.add(currentBlock_); |
| } |
| } |
| } |
| } else if (expr instanceof IASTExpressionList) { |
| if (inRankFunc) { |
| paramsOLD = (IASTExpressionList) expr;// BRT investigate if |
| // ptp40 gets here |
| } |
| } |
| return PROCESS_CONTINUE; |
| } |
| } |
| |
| protected ICallGraph cg_; |
| |
| protected MPICallGraphNode currentNode_; |
| |
| protected final int lhs = 0; |
| |
| protected final int rhs = 1; |
| |
| protected boolean changed = false; |
| |
| private static final boolean traceOn = false; |
| |
| public MPIMVAnalysis(ICallGraph cg) { |
| cg_ = cg; |
| } |
| |
| public void run() { |
| init(); |
| SeedsCollector sc = new SeedsCollector(); |
| sc.run(); |
| functionMVSummary(); |
| functionSlicing(); |
| exprMVAnalysis(); |
| |
| for (ICallGraphNode n = cg_.topEntry(); n != null; n = n.topNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| IControlFlowGraph cfg = node.getCFG(); |
| for (IBlock b = cfg.getEntry(); b != null; b = b.topNext()) { |
| MPIBlock block = (MPIBlock) b; |
| if (block.getMV() && (block.withBreak || block.withContinue)) { |
| System.out.println("************ Multi-valued branch with Break/Continue in " + //$NON-NLS-1$ |
| node.getFuncName() + "(" + node.getFileName() + ")"); //$NON-NLS-1$ //$NON-NLS-2$ |
| } |
| } |
| } |
| } |
| |
| private void clean() { |
| for (IBlock b = currentNode_.getCFG().getEntry(); b != null; b = b.topNext()) { |
| MPIBlock block = (MPIBlock) b; |
| block.sliced = false; |
| block.setMVvar(new ArrayList<String>()); |
| } |
| } |
| |
| /** Determine whether an "EXPRESSION" is multi-valued */ |
| private void exprMVAnalysis() { |
| for (ICallGraphNode n = cg_.botEntry(); n != null; n = n.botNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| IControlFlowGraph cfg = node.getCFG(); |
| for (IBlock b = cfg.getEntry(); b != null; b = b.topNext()) { |
| MPIBlock block = (MPIBlock) b; |
| //System.out.println("expMVAnalysis(): Block " + block.getID()); //$NON-NLS-1$ |
| ExprMVAnalyzer EA = new ExprMVAnalyzer(block.getContent(), block.getMVvar(), block); |
| // ^^^ BRT isEmpty |
| EA.run(); |
| EA.isMV(); |
| block.setMV(EA.isMV()); |
| |
| } |
| } |
| } |
| |
| private void functionMVSummary() { |
| changed = true; |
| while (changed) { |
| changed = false; |
| for (ICallGraphNode n = cg_.botEntry(); n != null; n = n.botNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| currentNode_ = node; |
| for (Enumeration<String> e = node.getMVSummary().keys(); e.hasMoreElements();) { |
| String var = e.nextElement(); |
| singleVariableSlicing(var); |
| /* |
| * System.out.print("Summary: "); for(Iterator i = |
| * ((ArrayList)node.getMVSummary().get(var)).iterator(); |
| * i.hasNext();){ System.out.print((String)i.next() + ", "); |
| * } System.out.println(" "); |
| */ |
| clean(); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Determines a set of multi-valued "VARIABLES" (local and global) in each |
| * program point |
| */ |
| private void functionSlicing() { |
| for (ICallGraphNode n = cg_.topEntry(); n != null; n = n.topNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| currentNode_ = node; |
| // System.out.println(node.getFuncName()); |
| IControlFlowGraph cfg = node.getCFG(); |
| |
| /** |
| * The initial worklist contains seeds blocks in this function and |
| * the entry block if any of its parameters is multi-valued. |
| */ |
| WorkListCollector wlc = new WorkListCollector(currentNode_); |
| LinkedList<IBlock> seeds = wlc.getWorkList(); |
| boolean hasMVparam = false; |
| for (Enumeration<String> e = node.getParamMV().keys(); e.hasMoreElements();) { |
| String param = e.nextElement(); |
| boolean val = node.getParamMV().get(param).booleanValue(); |
| if (val) { // multi-valued parameter |
| ((MPIBlock) cfg.getEntry()).getMVvar().add(param); |
| hasMVparam = true; |
| } |
| } |
| if (hasMVparam) { |
| seeds.add(cfg.getEntry()); |
| } |
| |
| /** Slicing */ |
| while (!seeds.isEmpty()) { |
| MPIBlock block = (MPIBlock) seeds.remove(); |
| if (block.sliced) { |
| continue; |
| } |
| block.sliced = true; |
| |
| // System.out.println("current seed is " + block.getID()); |
| Hashtable<String, List<IBlock>> DUSucc = block.getDUSucc(); |
| List<String> mv = block.getMVvar(); |
| List<String> newMV = new ArrayList<String>(); |
| |
| handlePointers(block, mv); |
| |
| /* |
| * Intra-block slicing (Case #1) --- If there is a \phi function |
| * in this block, consider two cases: (1) If this block is a |
| * join block for If statement or Switch statement, or if this |
| * block is break exit join block of a loop, then all \phi |
| * variables in this block are multi-valued; (2) If this block |
| * is a join block (i.e., cond block) for For statement, While |
| * statement or Do statement, then its multi-valued \phi |
| * variables have been already marked through data dependences, |
| * and all used \phi variables are kept multi-valued. Note: a |
| * block falls into one and only one of these two cases. |
| */ |
| if (!block.getPhiVar().isEmpty()) { |
| List<IBlock> cond = block.getCond(); |
| int blockcase = 0; |
| for (Iterator<IBlock> i = cond.iterator(); i.hasNext();) { |
| if (blockcase == 2) { |
| break; |
| } |
| MPIBlock condblock = (MPIBlock) i.next(); |
| IASTStatement parent = condblock.getParent(); |
| if (parent instanceof IASTIfStatement || parent instanceof IASTSwitchStatement) { |
| blockcase = 1; |
| } else if (parent instanceof IASTForStatement || parent instanceof IASTDoStatement |
| || parent instanceof IASTWhileStatement) { |
| if (block.getType() == MPIBlock.exit_join_type) { |
| blockcase = 1; |
| } else if (block.getType() == MPIBlock.expr_type) { |
| blockcase = 2; |
| } |
| } |
| } |
| if (blockcase == 1) { |
| newMV = Util.Union(newMV, block.getPhiVar()); |
| } else if (blockcase == 2) { |
| for (Iterator<IBlock> i = cond.iterator(); i.hasNext();) { |
| MPIBlock condblock = (MPIBlock) i.next(); |
| for (Iterator<String> ii = condblock.getUsedPhiVar().iterator(); ii.hasNext();) { |
| String var = ii.next(); |
| if (mv.contains(var)) { |
| newMV.add(var); |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * Intra-block slicing (Case #1) --- Given MV/SV used variable, |
| * determine whether defined variables are MV or SV. |
| */ |
| |
| IASTNode content = block.getContent(); |
| ExprMVAnalyzer emva = new ExprMVAnalyzer(content, mv, block); |
| emva.run(); |
| newMV = Util.Union(newMV, emva.getMVList()); |
| |
| /** |
| * Intra-block slicing (Case #3) -- any used only multi-valued |
| * variable is still multi-valued |
| */ |
| for (Iterator<String> i = mv.iterator(); i.hasNext();) { |
| String var = i.next(); |
| if (block.getUse().contains(var) && !block.getDef().contains(var)) { |
| if (!newMV.contains(var)) { |
| newMV.add(var); |
| } |
| } |
| } |
| |
| handlePointers(block, newMV); |
| handleBroadCast(block, newMV); |
| block.setMVvar(newMV); |
| |
| /** Inter-block slicing based on data dependences */ |
| for (Iterator<String> i = newMV.iterator(); i.hasNext();) { |
| String MVvar = i.next(); |
| List<IBlock> DUnext = DUSucc.get(MVvar); |
| if (DUnext != null) { |
| for (Iterator<IBlock> ii = DUnext.iterator(); ii.hasNext();) { |
| MPIBlock b = (MPIBlock) ii.next(); |
| if (b.sliced == true) { |
| continue; |
| } |
| if (!seeds.contains(b)) { |
| seeds.add(b); |
| // System.out.println("block " + b.getID() + |
| // " is added to seeds"); |
| } |
| if (!b.getMVvar().contains(MVvar)) { |
| b.getMVvar().add(MVvar); |
| } |
| } |
| } |
| } |
| |
| /** Inter-block slicing based on \Phi edges */ |
| for (Iterator<IBlock> i = block.getJoin().iterator(); i.hasNext();) { |
| MPIBlock join = (MPIBlock) i.next(); |
| if (!seeds.contains(join) && !join.sliced) { |
| seeds.add(join); |
| } |
| } |
| } |
| |
| /* |
| * Function Multi-valued Summary --- (1) whether a function's REAL |
| * parameters are multi-valued (A real parameter of function foo is |
| * multi-valued if in any of foo's call sites the parameter is |
| * multi-valued) |
| */ |
| for (IBlock block = cfg.getEntry(); block != null; block = block.topNext()) { |
| FuncParamMVChecker fpc = new FuncParamMVChecker(node, (MPIBlock) block); |
| fpc.run(); |
| } |
| } |
| } |
| |
| private String getFormalParamName(ICallGraphNode func, int index) { |
| IASTFunctionDefinition fd = func.getFuncDef(); |
| IASTFunctionDeclarator fdecl = fd.getDeclarator(); |
| if (fdecl instanceof IASTStandardFunctionDeclarator) { |
| IASTStandardFunctionDeclarator sfunc = (IASTStandardFunctionDeclarator) fdecl; |
| IASTParameterDeclaration[] params = sfunc.getParameters(); |
| if (index >= params.length) { |
| return null; |
| } |
| IASTName param = params[index].getDeclarator().getName(); |
| return param.toString(); |
| } else { |
| ICASTKnRFunctionDeclarator krfunc = (ICASTKnRFunctionDeclarator) fdecl; |
| IASTName[] params = krfunc.getParameterNames(); |
| if (index >= params.length) { |
| return null; |
| } |
| return params[index].toString(); |
| } |
| } |
| |
| private void handleBroadCast(MPIBlock block, List<String> set) { |
| BroadCastAnalyzer bca = new BroadCastAnalyzer(block); |
| bca.run(); |
| String bcdata = bca.getBCdata(); |
| if (bcdata != null) { |
| if (set.contains(bcdata)) { |
| set.remove(bcdata); |
| } |
| } |
| block.setMVvar(set); |
| } |
| |
| private void handlePointers(MPIBlock block, List<String> set) { |
| PointerAnalyzer pa = new PointerAnalyzer(block); |
| pa.run(); |
| for (Iterator<String> i = pa.getAddr().iterator(); i.hasNext();) { |
| String var = i.next(); |
| if (block.getUse().contains(var)) { |
| if (!set.contains(var)) { |
| set.add(var); |
| } |
| } |
| } |
| for (Iterator<String> i = pa.getDeref().iterator(); i.hasNext();) { |
| String var = i.next(); |
| if (block.getUse().contains(var)) { |
| if (!set.contains(var)) { |
| set.add(var); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Initialize all parameters of a function as single-valued; Initialize its |
| * MV and SV summary as empty |
| */ |
| private void init() { |
| for (ICallGraphNode n = cg_.topEntry(); n != null; n = n.topNext()) { |
| MPICallGraphNode node = (MPICallGraphNode) n; |
| if (!node.marked) { |
| continue; |
| } |
| IASTFunctionDefinition fd = node.getFuncDef(); |
| IASTFunctionDeclarator fdecl = fd.getDeclarator(); |
| if (fdecl instanceof IASTStandardFunctionDeclarator) { |
| IASTStandardFunctionDeclarator sfunc = (IASTStandardFunctionDeclarator) fdecl; |
| IASTParameterDeclaration[] params = sfunc.getParameters(); |
| for (int i = 0; i < params.length; i++) { |
| IASTName param = params[i].getDeclarator().getName(); |
| if (param.toString().equals("")) { |
| continue; //void parameter //$NON-NLS-1$ |
| } |
| node.getParamMV().put(param.toString(), new Boolean(false)); |
| node.getMVSummary().put(param.toString(), new ArrayList<String>()); |
| } |
| } else { |
| ICASTKnRFunctionDeclarator krfunc = (ICASTKnRFunctionDeclarator) fdecl; |
| IASTName[] params = krfunc.getParameterNames(); |
| for (int i = 0; i < params.length; i++) { |
| node.getParamMV().put(params[i].toString(), new Boolean(false)); |
| node.getMVSummary().put(params[i].toString(), new ArrayList<String>()); |
| } |
| } |
| for (Iterator<String> i = node.getGlobalUse().iterator(); i.hasNext();) { |
| String var = i.next(); |
| node.getMVSummary().put(var, new ArrayList<String>()); |
| } |
| /* |
| * Another entry if (1) the function has no parameter and no global |
| * use; (2) all parameters and global uses are SV. (We call this |
| * function(context) as "empty MV input" function(context).) Use the |
| * function name as the key in these cases |
| */ |
| node.getMVSummary().put(node.getFuncName(), new ArrayList<String>()); |
| } |
| } |
| |
| /** |
| * The return value of a function is multi-valued if any of its return |
| * statement is multi-valued. |
| */ |
| private boolean returnMV() { |
| boolean returnmv = false; |
| for (Iterator<IBlock> i = ((MPIControlFlowGraph) currentNode_.getCFG()).getReturnBlocks().iterator(); i.hasNext();) { |
| MPIBlock returnBlock = (MPIBlock) i.next(); |
| ExprMVAnalyzer ema = new ExprMVAnalyzer(returnBlock.getContent(), returnBlock.getMVvar(), returnBlock); |
| ema.run(); |
| returnmv = returnmv | ema.isMV(); |
| returnBlock.setMV(false); // reset it |
| } |
| return returnmv; |
| } |
| |
| /** |
| * For each function, assume all parameters are MV, find out which global |
| * variables (and passable parameters) are MV |
| */ |
| private void singleVariableSlicing(String var) { |
| IControlFlowGraph cfg = currentNode_.getCFG(); |
| |
| WorkListCollector wlc = new WorkListCollector(currentNode_); |
| LinkedList<IBlock> seeds = wlc.getWorkList(); |
| if (!var.equals(currentNode_.getFuncName())) { |
| seeds.add(cfg.getEntry()); |
| ((MPIBlock) cfg.getEntry()).getMVvar().add(var); |
| } |
| |
| while (!seeds.isEmpty()) { |
| MPIBlock block = (MPIBlock) seeds.remove(); |
| if (block.sliced) { |
| continue; |
| } |
| block.sliced = true; |
| |
| if (block.getContent() == null) { |
| continue; |
| } |
| |
| Hashtable<String, List<IBlock>> DUSucc = block.getDUSucc(); |
| List<String> mv = block.getMVvar(); |
| List<String> newMV = new ArrayList<String>(); |
| |
| handlePointers(block, mv); |
| |
| if (!block.getPhiVar().isEmpty()) { |
| List<IBlock> cond = block.getCond(); |
| int blockcase = 0; |
| for (Iterator<IBlock> i = cond.iterator(); i.hasNext();) { |
| if (blockcase == 2) { |
| break; |
| } |
| MPIBlock condblock = (MPIBlock) i.next(); |
| IASTStatement parent = condblock.getParent(); |
| if (parent instanceof IASTIfStatement || parent instanceof IASTSwitchStatement) { |
| blockcase = 1; |
| } else if (parent instanceof IASTForStatement || parent instanceof IASTDoStatement |
| || parent instanceof IASTWhileStatement) { |
| if (block.getType() == MPIBlock.exit_join_type) { |
| blockcase = 1; |
| } else if (block.getType() == MPIBlock.expr_type) { |
| blockcase = 2; |
| } |
| } |
| } |
| if (blockcase == 1) { |
| newMV = Util.Union(newMV, block.getPhiVar()); |
| } else if (blockcase == 2) { |
| for (Iterator<IBlock> i = cond.iterator(); i.hasNext();) { |
| MPIBlock condblock = (MPIBlock) i.next(); |
| for (Iterator<String> ii = condblock.getUsedPhiVar().iterator(); ii.hasNext();) { |
| String v = ii.next(); |
| if (mv.contains(v)) { |
| newMV.add(v); |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * Intra-block slicing (Case #1) --- Given MV/SV used variable, |
| * determine whether defined variables are MV or SV. |
| */ |
| |
| IASTNode content = block.getContent(); |
| ExprMVAnalyzer emva = new ExprMVAnalyzer(content, mv, block); |
| emva.run(); |
| newMV = Util.Union(newMV, emva.getMVList()); |
| |
| /** |
| * Intra-block slicing (Case #3) -- any used only multi-valued |
| * variable is still multi-valued |
| */ |
| for (Iterator<String> i = mv.iterator(); i.hasNext();) { |
| String v = i.next(); |
| if (block.getUse().contains(v) && !block.getDef().contains(v)) { |
| if (!newMV.contains(v)) { |
| newMV.add(v); |
| } |
| } |
| } |
| |
| handlePointers(block, newMV); |
| handleBroadCast(block, newMV); |
| block.setMVvar(newMV); |
| |
| /** Inter-block slicing based on data dependences */ |
| for (Iterator<String> i = newMV.iterator(); i.hasNext();) { |
| String MVvar = i.next(); |
| List<IBlock> DUnext = DUSucc.get(MVvar); |
| if (DUnext != null) { |
| for (Iterator<IBlock> ii = DUnext.iterator(); ii.hasNext();) { |
| MPIBlock b = (MPIBlock) ii.next(); |
| if (b.sliced == true) { |
| continue; |
| } |
| if (!seeds.contains(b)) { |
| seeds.add(b); |
| // System.out.println("block " + b.getID() + |
| // " is added to seeds"); |
| } |
| if (!b.getMVvar().contains(MVvar)) { |
| b.getMVvar().add(MVvar); |
| } |
| } |
| } |
| } |
| |
| /** Inter-block slicing based on \Phi edges */ |
| for (Iterator<IBlock> i = block.getJoin().iterator(); i.hasNext();) { |
| MPIBlock join = (MPIBlock) i.next(); |
| if (!seeds.contains(join) && !join.sliced) { |
| seeds.add(join); |
| } |
| } |
| } |
| |
| List<String> MVlist = currentNode_.getMVSummary().get(var); |
| for (Iterator<String> i = currentNode_.getGlobalDef().iterator(); i.hasNext();) { |
| String v = i.next(); |
| if (((MPIBlock) cfg.getExit()).getMVvar().contains(v)) { |
| if (!MVlist.contains(v)) { |
| MVlist.add(v); |
| } |
| } |
| } |
| for (Iterator<String> i = currentNode_.getParamDef().iterator(); i.hasNext();) { |
| String v = i.next(); |
| if (((MPIBlock) cfg.getExit()).getMVvar().contains(v)) { |
| if (!MVlist.contains(v)) { |
| MVlist.add(v); |
| } |
| } |
| } |
| |
| if (returnMV()) { |
| if (!MVlist.contains(currentNode_.getFuncName())) { |
| MVlist.add(currentNode_.getFuncName()); |
| } |
| } |
| } |
| |
| } |
