/********************************************************************************\ * * * Intra procedural reaching definitions analysis * * for C++SL1, a sublangage of C++ * * * * This analysis specification ensures that the analysis operates on an SL1 * * program. Otherwise an error is reported by the generated analyzer. If it is * * assumed that the front end only passes SL1 programs to the analyzer then all * * those tests can be removed. * * * * Author: Markus Schordan, 2006. * * * \********************************************************************************/ BLOCK label : snum# PROBLEM Reaching_Definitions direction: forward carrier: VarLabPairSetLifted init: bot init_start: lift({}) combine: comb retfunc: comb widening: wide equal: eq TRANSFER /* In C++ an expression statement contains an expression which can also be an assignment. In C++SL1 we only allow assignments of the form x=e, where x is a variable and e is an expression without an assignment (thus, a=b=c is not in SL1). */ ExprStatement(stmt), _: sl1_assignment(stmt,label,@); /* declaration of a variable */ DeclareStmt(VariableSymbol(var) as varSym,_), _: let info <= @; in let nonInitValSet = rdgen(varsym_varid(varSym),-1); in lift(union(info,nonInitValSet)); /* the list of declared variables that go out of scope */ UndeclareStmt(vars), _: let info <= @; in lift(kill_vars(info,vars)); /* this node is created for handling short-circuit evaluation of boolean expressions */ LogicalIf(cond), _: sl1_expression(cond,label,@); /* handle the condition of an if statement * note that assignements are not allowed in conditionals in C++SL1 */ ScopeStatement(IfStmt(ExprStatement(cond))),_: sl1_expression(cond,label,@); /* handle the condition of a while statement */ ScopeStatement(WhileStmt(ExprStatement(cond))),_: sl1_expression(cond,label,@); /* handle the return statement */ ReturnStmt(exp), _: sl1_expression(exp,label,@); /* we ignore this node in intra procedural analysis */ FunctionEntry(_), _: @; /* we ignore this node in intra procedural analysis */ FunctionExit(_, vars), _: @; /* Join nodes simplify how analysis information is mapped back to the * original AST after an analysis. */ IfJoin(),_: @; WhileJoin(),_: @; /* we report an error for any unmatched statement */ _, _: error("Unknown statement. This is not an SL1 program."); SUPPORT /* required functions for combine, widening, equal */ comb(a,b) = a lub b; wide(a,b) = b; eq(a,b) = (a = b); /* handling SL1 expressions in analysis - C++SL1 does not allow assignments in expressions. Therefore the transfer function is the identity function. We only check whether the expression is indeed a C++SL1 expression, otherwise an error is reported */ sl1_expression::Expression,snum,VarLabPairSetLifted -> VarLabPairSetLifted; sl1_expression(exp,lab,info) = if is_sl1_expression(exp) then case exp of VarRefExp(cvarname) as varRef => /* if boolean expression are used in conditional a single use of a temporary variable must be handled by the analysis. It is guaranteed that a temporary variable is used exactly once, therefore it can be removed from the analysis information because it is leaving its scope. */ let x = varref_varid(varRef); in if is_tmpvarid(x) then lift(rdkill(x,drop(info))) else info endif; _ => info; endcase else print("Unknown expression at Node ") print(lab) print(": ") print(exp) error("This is not an SL1 program.") endif ; /* handling SL1 assignments in analysis */ sl1_assignment::Expression,snum,VarLabPairSetLifted -> VarLabPairSetLifted; sl1_assignment(exp,lab,bot) = bot; sl1_assignment(exp,lab,top) = top; sl1_assignment(exp,lab,infoLifted) = let info <= infoLifted; in case exp of AssignOp(VarRefExp(cvarname) as varRef,rhsexp) => /* we map the varref to a varid and bind it with x */ let x = varref_varid(varRef); in /* we ensure that the rhs expression is an sl1 expression, otherwise an error is reported */ if is_sl1_expression(rhsexp) then lift(update_info(x,lab,info)) else print("Unknown expression on rhs of assignment: Node ") print(lab) print(": ") print(exp) error("This is not an SL1 program.") endif; _ => print("unknown expression on lhs of assignment: Node") print(lab) error("This is not an SL1 program."); endcase ; /* This function only tests whether an expression is an SL1 expression. It demonstrates how to access all parts of an SL1 expression. */ is_sl1_expression::Expression -> bool; is_sl1_expression(exp) = case exp of /* arithmetic SL1 operators */ AddOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); MultiplyOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); SubtractOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); DivideOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); ModOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); MinusOp(a) => is_sl1_expression(a); /* unary minus */ UnaryAddOp(a) => is_sl1_expression(a); /* unary plus */ /* relational SL1 operators */ EqualityOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); LessThanOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); GreaterThanOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); NotEqualOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); LessOrEqualOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); GreaterOrEqualOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); /* logical operators */ AndOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); OrOp(a,b) => is_sl1_expression(a) && is_sl1_expression(b); NotOp(a) => is_sl1_expression(a); /* int value; use val-int(value) for converting value to snum */ IntVal(value) => true; /* use of a variable; use VarRefExp as vr ... varref_varid(vr) for converting varref to VariableId */ VarRefExp(varname) => true; /* boolean value (represented as int 0,1); use val-int(value) for converting to snum */ BoolValExp(value) => true; /* initializer; this is a "wrapper" AST node around an initializer expression */ AssignInitializer(e) => is_sl1_expression(e); /* default case: no expression matches; not an SL1 program */ _ => false; /* other C/C++ operators are: CastExp(_, _), PlusAssignOp(_, _), MinusAssignOp(_, _), MultAssignOp(_, _), DivAssignOp(_, _) , ModAssignOp(_, _), MinusMinusOp(_), PlusPlusOp(_) */ endcase; /* update the analysis information with kill and gen functions */ update_info::VariableId,snum,VarLabPairSet -> VarLabPairSet; update_info(x,lab,info) = union(rdkill(x,info),rdgen(x,lab)); /* kill-set for reaching definitions */ rdkill::VariableId,VarLabPairSet -> VarLabPairSet; rdkill(var,varset) = {(var1,lab1) !! (var1,lab1) <-- varset, if !(var1=var) }; /* gen-set for reaching definitions */ rdgen::VariableId,snum -> VarLabPairSet; rdgen(var,lab) = {(var,lab)}; /* kill a set of variables (used for removing variables that go out of scope) */ kill_vars :: VarLabPairSet, *VariableSymbolNT -> VarLabPairSet; kill_vars(s, [!]) = s; kill_vars(s, v::vars) = /* v is a VariableSymbol */ kill_vars(rdkill(varsym_varid(v),s), vars); /* Predefined SATIrE Support Functions */ varsym_varid :: VariableSymbolNT -> VariableId; varref_varid :: Expression -> VariableId; is_tmpvarid :: VariableId -> bool;