/********************************************************************************\ * * * Inter-procedural reaching definitions analysis * * for C++SL2, a sublangage of C++ * * * * C++SL2 extends C++SL1 with function calls * * * * Note that global variables are not in C++SL2 * * * * This analysis specification ensures that the analysis operates on an SL2 * * program. Otherwise an error is reported by the generated analyzer. If it is * * assumed that the front end only passes SL2 programs to the analyzer then all * * those tests can be removed. * * * * For the exercises it can be assumed that only SL2 programs are passed to the * * analyzer. * * * * 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(exprstmt), _: case exprstmt of /* For a call of a void function a node is created in the ICFG with a use of the * auxiliary return variable - this permits removing the auxiliary variable */ VarRefExp(var) => kill_temporary_variable(val-aststring(var),@); /* otherwise it must be an SL1 assignment */ _ => sl1_assignment(exprstmt,label,@); endcase; /* declaration of a variable */ DeclareStmt(VariableSymbol(var),_), _: let info <= @; in let nonInitValSet = rdgen(val-aststring(var),-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 * we also consider the case of a temporary variable in an IfStmt which * is introduced in the CFG for handling short-circuit evaluation in boolean expresssions */ ScopeStatement(IfStmt(ExprStatement(cond))),_: kill_if_temporary_variable_exp(cond,@); /* 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,@); /* In the remaining transfer-section we specify transfer functions for inter-procedural analysis * of SL2 programs */ ReturnAssignment(VariableSymbol(var), VariableSymbol(retvar)), _: let x=val-aststring(var); in let y=val-aststring(retvar); in let info <= @; in lift(update_info(x,label,rdkill(y,info))); FunctionCall(funcname,actualParams),local_edge: bot; FunctionCall(funcname,actualParams),call_edge: @; FunctionEntry(funcname), _: @; FunctionExit(_, vars), _: let info <= @; in lift(kill_vars(info,vars)); FunctionReturn (funcname,actualParams),_: @; ArgumentAssignment(VarRefExp(var), exp), _: let x=val-aststring(var); in let info <= @; in lift(update_info(x,label,info)); /* The rhs auxiliary variable of the parameter assignment can be removed from the * analysis information because the auxiliary variable cannot be used or redefined */ ParamAssignment(VariableSymbol(var), VariableSymbol(param)), _: let x=val-aststring(var); in let y=val-aststring(param); in let info <= @; in lift(update_info(x,label,rdkill(y,info))); /* Join nodes simplify how analysis information is mapped back to the * original AST after an analysis. */ IfJoin(),_: @; WhileJoin(),_: @; /* should match external call here as well */ /* we report an error for any unmatched statement */ _, _: print("Label: ") print(label) print(":") error("Unknown statement. This is not an SL2 program."); SUPPORT /* required functions for combine, widening, equal */ comb(a,b) = a lub b; /*ret_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 info else print("Unknown expression at Node ") print(lab) print(": ") print(exp) error("This is not an SL2 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 /* one variable on each side of assignment */ AssignOp(VarRefExp(cvarname1),VarRefExp(cvarname2)) => let x = val-aststring(cvarname1); in let y = val-aststring(cvarname2); in if is_temp_var(y) then lift(update_info(x,lab,rdkill(y,info))) /* temporary variable */ else lift(update_info(x,lab,info)) /* program variable */ endif; /* arbitrary expression on rhs (but not a variable) */ AssignOp(VarRefExp(cvarname),rhsexp) => /* we convert the c-string to the pag string type 'str' and bind it with x */ let x = val-aststring(cvarname); 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 SL2 program.") endif; _ => print("unknown expression on lhs of assignment: Node") print(lab) lift(info); /*error("This is not an SL2 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 val-aststring(varname) for converting varname to str */ 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 the 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::str,snum,VarLabPairSet -> VarLabPairSet; update_info(x,lab,info) = union(rdkill(x,info),rdgen(x,lab)); /* kill-set for reaching definitions */ rdkill::str,VarLabPairSet -> VarLabPairSet; rdkill(var,varset) = {(var1,lab1) !! (var1,lab1) <-- varset, if !(var1=var) }; /* gen-set for reaching definitions */ rdgen::str,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, VariableSymbol(v)::vars) = kill_vars(rdkill(val-aststring(v),s), vars); is_temp_var :: str -> bool; is_temp_var(s) = substr(s, 0, 0) = "$"; kill_if_temporary_variable_exp :: Expression, VarLabPairSetLifted -> VarLabPairSetLifted; kill_if_temporary_variable_exp(exp,infoLifted) = let info <= infoLifted; in case exp of VarRefExp(var) => let x=val-aststring(var); in kill_temporary_variable(x,infoLifted); _ => infoLifted; endcase; kill_temporary_variable :: str, VarLabPairSetLifted -> VarLabPairSetLifted; kill_temporary_variable(var,infoLifted) = let info <= infoLifted; in if is_temp_var(var) then lift(rdkill(var,info)) else print("Variable used where only a generated auxiliary variable is expected.") error("This is not an SL2 program.") endif;