/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * This file is part of SimpleC. * * See the file "SimpleC-LICENSE" for Copyright information and * * the terms and conditions for copying, distribution and * * modification of SimpleC. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ package org.sablecc.simplec; import org.sablecc.simplec.node.*; import org.sablecc.simplec.analysis.*; import java.util.*; import java.util.Map.Entry; class PointsToAnalysis extends DepthFirstAdapter { PointsTo pto; private boolean fct_def; private TIdentifier current_fct; PointsToAnalysis(PointsTo pto) { this.pto = pto; pto.ast.apply(this); } // x = y private void rule1(Variable x, Variable y) { Variable ref1 = ((Ref) x.ecr().type).ref.ecr(); Variable lam1 = ((Ref) x.ecr().type).lam.ecr(); Variable ref2 = ((Ref) y.ecr().type).ref.ecr(); Variable lam2 = ((Ref) y.ecr().type).lam.ecr(); if(ref1 != ref2) { ref1.cjoin(ref2); } if(lam1 != lam2) { lam1.cjoin(lam2); } } // x = &y private void rule2(Variable x, Variable y) { Variable ref1 = ((Ref) x.ecr().type).ref.ecr(); Variable ref2 = y.ecr(); if(ref1 != ref2) { ref1.join(ref2); } } // x = *y private void rule3(Variable x, Variable y) { Variable ref1 = ((Ref) x.ecr().type).ref.ecr(); Variable lam1 = ((Ref) x.ecr().type).lam.ecr(); Variable ref2 = ((Ref) y.ecr().type).ref.ecr(); if(ref2.type == Bottom.instance) { ref2.setType(new Ref()); } Variable ref3 = ((Ref) ref2.type).ref.ecr(); Variable lam3 = ((Ref) ref2.type).lam.ecr(); if(ref1 != ref3) { ref1.cjoin(ref3); } if(lam1 != lam3) { lam1.cjoin(lam3); } } // x = malloc() private void rule4(Variable x) { Variable ref = ((Ref) x.ecr().type).ref.ecr(); if(ref.type == Bottom.instance) { ref.setType(new Ref()); } } // *x = y private void rule5(Variable x, Variable y) { Variable ref1 = ((Ref) x.ecr().type).ref.ecr(); Variable ref2 = ((Ref) y.ecr().type).ref.ecr(); Variable lam2 = ((Ref) y.ecr().type).lam.ecr(); if(ref1.type == Bottom.instance) { ref1.setType(new Ref()); } Variable ref3 = ((Ref) ref1.type).ref.ecr(); Variable lam3 = ((Ref) ref1.type).lam.ecr(); if(ref2 != ref3) { ref3.cjoin(ref2); } if(lam2 != lam3) { lam3.cjoin(lam3); } } // x = p(y1,..yn) private void rule6(Variable x, Variable p, Variable[] y) { Variable lam = ((Ref) p.ecr().type).lam.ecr(); if(lam.type == Bottom.instance) { lam.setType(new Lam()); } for(int i = ((Lam) lam.type).args.size(); i < y.length; i++) { ((Lam) lam.type).args.add(new Variable(new Ref())); } Iterator it = ((Lam) lam.type).args.iterator(); for(int i = 0; i < y.length; i++) { Variable param = (Variable) it.next(); Variable ref1 = ((Ref) param.ecr().type).ref.ecr(); Variable lam1 = ((Ref) param.ecr().type).lam.ecr(); Variable ref2 = ((Ref) y[i].ecr().type).ref.ecr(); Variable lam2 = ((Ref) y[i].ecr().type).lam.ecr(); if(ref1 != ref2) { ref1.cjoin(ref2); } if(lam1 != lam2) { lam1.cjoin(lam2); } } Variable ref1 = ((Ref) ((Lam) lam.type).ret.ecr().type).ref.ecr(); Variable lam1 = ((Ref) ((Lam) lam.type).ret.ecr().type).lam.ecr(); Variable ref2 = ((Ref) x.ecr().type).ref.ecr(); Variable lam2 = ((Ref) x.ecr().type).lam.ecr(); if(ref1 != ref2) { ref2.cjoin(ref1); } if(lam1 != lam2) { lam2.cjoin(lam1); } } private Map automatic_declarations = new TreeMap(StringComparator.instance); private Variable variable(TIdentifier id) { try { return (Variable) pto.variables.get(pto.declarations.declarations.get(id)); } catch(RuntimeException e) { // Undeclared identifier! Variable var = (Variable) automatic_declarations.get(id.getText()); if(var == null) { Ref ref = new Ref(); ref.lam = new Variable(new Lam()); var = new Variable(ref); automatic_declarations.put(id.getText(), var); } return var; } } public void inAFunctionDefinition(AFunctionDefinition node) { fct_def = true; } public void outAFunctionDefinition(AFunctionDefinition node) { fct_def = false; } public void inAIdentifierDirectFunctionDeclarator(AIdentifierDirectFunctionDeclarator node) { if(fct_def) { current_fct = node.getIdentifier(); } } public void outAIdentifierValue(AIdentifierValue node) { setOut(node, variable(node.getIdentifier())); } public void outAConstantValue(AConstantValue node) { setOut(node, new Variable(new Ref())); } public void outAReturnValueStopStatement(AReturnValueStopStatement node) { // [1a] ret value; => fct.ret = value rule1( ((Lam) ((Ref) variable(current_fct).ecr().type).lam.ecr().type).ret, (Variable) getOut(node.getValue())); } public void outAReturnParStopStatement(AReturnValueStopStatement node) { // [1b] ret (value); => fct.ret = value rule1( ((Lam) ((Ref) variable(current_fct).ecr().type).lam.ecr().type).ret, (Variable) getOut(node.getValue())); } public void outACallExpressionBasicStatement(ACallExpressionBasicStatement node) { // [2] identifier(value,...); ACallExpression ce = (ACallExpression) node.getCallExpression(); String name = ce.getIdentifier().getText(); if(name.equals("malloc") || name.equals("calloc")) { return; } Variable p = variable(ce.getIdentifier()); LinkedList y = new LinkedList(); AArglist args = (AArglist) ce.getArglist(); if(args != null) { y.add(getOut(args.getValue())); for(Iterator i = args.getArglistTail().iterator(); i.hasNext();) { AArglistTail arg = (AArglistTail) i.next(); y.add(getOut(arg.getValue())); } } Object[] y1 = y.toArray(); Variable[] y2 = new Variable[y1.length]; System.arraycopy(y1, 0, y2, 0, y1.length); rule6(new Variable(new Ref()), p, y2); } PRhs rhs; Variable lhs; public void outAModifyExpressionBasicStatement(AModifyExpressionBasicStatement node) { // [3] lhs = rhs; // Dissect the 5 lhs cases (and get rhs) node.getModifyExpression().apply(new AnalysisAdapter() { public void caseADirectModifyExpression(ADirectModifyExpression node) { node.getVarname().apply(new AnalysisAdapter() { public void caseAArrayrefVarname(AArrayrefVarname node) { // (1) identifier[value]... = rhs //lhs = variable(((AArrayref) node.getArrayref()).getIdentifier()); lhs = new Variable(new Ref()); rule5(variable(((AArrayref) node.getArrayref()).getIdentifier()), lhs); } public void caseAComprefVarname(AComprefVarname node) { node.getCompref().apply(new AnalysisAdapter() { public void caseAIndirectCompref(AIndirectCompref node) { // (2) (*identifier).identifier... = rhs lhs = new Variable(new Ref()); rule5(variable(node.getIdentifier()), lhs); } public void caseADirectCompref(ADirectCompref node) { // (3) identifier.identifier... = rhs lhs = variable(node.getIdentifier()); } }); } public void caseAIdentifierVarname(AIdentifierVarname node) { // (4) identifier = rhs lhs = variable(node.getIdentifier()); } }); rhs = node.getRhs(); } public void caseAIndirectModifyExpression(AIndirectModifyExpression node) { // (5) (*identifier) = rhs lhs = new Variable(new Ref()); rule5(variable(node.getIdentifier()), lhs); rhs = node.getRhs(); } }); // Dissect the 19 rhs cases rhs.apply(new AnalysisAdapter() { public void caseABinaryRhs(ABinaryRhs node) { // (1) (value binop value) ABinaryExpression exp = (ABinaryExpression) node.getBinaryExpression(); rule1(lhs, (Variable) PointsToAnalysis.this.getOut(exp.getLValue())); rule1(lhs, (Variable) PointsToAnalysis.this.getOut(exp.getRValue())); } public void caseAUnaryRhs(AUnaryRhs node) { node.getUnaryExpression().apply(new AnalysisAdapter() { public void caseASimpleUnaryExpression(ASimpleUnaryExpression node) { node.getSimpleExpression().apply(new AnalysisAdapter() { public void caseAVarnameSimpleExpression(AVarnameSimpleExpression node) { node.getVarname().apply(new AnalysisAdapter() { public void caseAArrayrefVarname(AArrayrefVarname node) { // (2) identifier[value]... rule3(lhs, variable(((AArrayref) node.getArrayref()).getIdentifier())); } public void caseAComprefVarname(AComprefVarname node) { node.getCompref().apply(new AnalysisAdapter() { public void caseAIndirectCompref(AIndirectCompref node) { // (3) (*identifier).identifier... rule3(lhs, variable(node.getIdentifier())); } public void caseADirectCompref(ADirectCompref node) { // (4) identifier.identifier... rule1(lhs, variable(node.getIdentifier())); } }); } public void caseAIdentifierVarname(AIdentifierVarname node) { // (5) identifier rule1(lhs, variable(node.getIdentifier())); } }); } public void caseAConstantSimpleExpression(AConstantSimpleExpression node) { // (6) constant rule1(lhs, new Variable(new Ref())); } }); } public void caseAReferenceUnaryExpression(AReferenceUnaryExpression node) { // (7) (*identifier) rule3(lhs, variable(node.getIdentifier())); } public void caseAAddressUnaryExpression(AAddressUnaryExpression node) { node.getVarname().apply(new AnalysisAdapter() { public void caseAArrayrefVarname(AArrayrefVarname node) { // (8) (&identifier[value]...) rule1(lhs, variable(((AArrayref) node.getArrayref()).getIdentifier())); } public void caseAComprefVarname(AComprefVarname node) { node.getCompref().apply(new AnalysisAdapter() { public void caseAIndirectCompref(AIndirectCompref node) { // (9) (&(*identifier).identifier...) rule1(lhs, variable(node.getIdentifier())); } public void caseADirectCompref(ADirectCompref node) { // (10) (&identifier.identifier...) rule2(lhs, variable(node.getIdentifier())); } }); } public void caseAIdentifierVarname(AIdentifierVarname node) { // (11) (&identifier) rule2(lhs, variable(node.getIdentifier())); } }); } public void caseACallUnaryExpression(ACallUnaryExpression node) { // (12) identifier(value,...) ACallExpression ce = (ACallExpression) node.getCallExpression(); String name = ce.getIdentifier().getText(); if(name.equals("malloc") || name.equals("calloc")) { rule4(lhs); return; } Variable p = variable(ce.getIdentifier()); LinkedList y = new LinkedList(); AArglist args = (AArglist) ce.getArglist(); if(args != null) { y.add(PointsToAnalysis.this.getOut(args.getValue())); for(Iterator i = args.getArglistTail().iterator(); i.hasNext();) { AArglistTail arg = (AArglistTail) i.next(); y.add(PointsToAnalysis.this.getOut(arg.getValue())); } } Object[] y1 = y.toArray(); Variable[] y2 = new Variable[y1.length]; System.arraycopy(y1, 0, y2, 0, y1.length); rule6(lhs, p, y2); } public void caseAUnopUnaryExpression(AUnopUnaryExpression node) { // (13) unop value rule1(lhs, variable(node.getIdentifier())); } public void caseAParUnopUnaryExpression(AParUnopUnaryExpression node) { // (14) (unop value) rule1(lhs, variable(node.getIdentifier())); } public void caseACastUnaryExpression(ACastUnaryExpression node) { node.getVarname().apply(new AnalysisAdapter() { public void caseAArrayrefVarname(AArrayrefVarname node) { // (15) (typename) identifier[value]... rule3(lhs, variable(((AArrayref) node.getArrayref()).getIdentifier())); } public void caseAComprefVarname(AComprefVarname node) { node.getCompref().apply(new AnalysisAdapter() { public void caseAIndirectCompref(AIndirectCompref node) { // (16) (typename) (*identifier).identifier... rule3(lhs, variable(node.getIdentifier())); } public void caseADirectCompref(ADirectCompref node) { // (17) (typename) identifier.identifier... rule1(lhs, variable(node.getIdentifier())); } }); } public void caseAIdentifierVarname(AIdentifierVarname node) { // (18) (typename) identifier rule1(lhs, variable(node.getIdentifier())); } }); } public void caseACastConstUnaryExpression(ACastUnaryExpression node) { // (19) (typename) constant rule1(lhs, new Variable(new Ref())); } }); } }); } }