Writing analyses using Tamer

The analysis framework in Tamer uses a visitor pattern similar to the McSAF framework. Additionally, since the TameIR ( the tamer intermediate representation) reuses the expression nodes of the McSAF IR, the analysis framework for Tamer extends the McSAF one. This is done to avoid duplicating functionality. Tamer also has two analysis classes TIRAbstractSimpleStructuralForwardAnalysis and TIRAbstractSimpleStructuralBackwardAnalysis for forward and backward analyses respectively. Programmers can choose either classes depending on the analysis to be implemented. In this section we will be giving a tutorial on the writing the reaching definitions analysis, a forward analysis. Many of the steps will be similar to those in the McSAF analyses.

We start by extending the TIRAbstractSimpleStructuralForwardAnalysis class.

public class ReachingDefinitions extends
		TIRAbstractSimpleStructuralForwardAnalysis<Map<String, Set<TIRNode>>>

We then define class variables that we need. Note that the reaching definitions analysis requires the NameCollector analysis and the definitely assigned analysis. The tamer implementation is quite similar to the McSAF version. The two analysis can be found here and here

public static boolean DEBUG = false;
	private DefinedVariablesNameCollector fVariableNameCollector;
	private DefiniteAssignment fDefiniteAssignment;
	private Map<String, Set<TIRNode>> fStartMap;
	private LinkedList<TIRNode> fVisitedStmts;

For block statements such as the TIRIfStmt and TIRWhileStmt etc. the currentInSet is copied into the currentOutSet.

public void caseTIRIfStmt(TIRIfStmt node) {
		currentOutSet = copy(currentInSet);
		setInOutSet(node);
		fVisitedStmts.add(node);

		caseIfStmt(node);

		if (DEBUG)
			printMapForNode(node);
	}

	@Override
	public void caseTIRWhileStmt(TIRWhileStmt node) {
		currentOutSet = copy(currentInSet);
		setInOutSet(node);
		fVisitedStmts.add(node);

		caseWhileStmt(node);

		if (DEBUG)
			printMapForNode(node);
	}

In the case of TIRForStmt nodes, we add the current node as the definition site for all the nodes that are defined in the current node. This is done by calling the method populateOutSetWithDefinitionSitesForNode. The currentInSet and currentOutSet are added to the inFlowSets and outFlowSets respectively by calling the method setInOutSet.

	@Override
	public void caseTIRForStmt(TIRForStmt node) {
		currentOutSet = copy(currentInSet);
		Set<String> definedVariablesNames = fVariableNameCollector
				.getDefinedVariablesForNode(node);
		populateOutSetWithDefinitionSitesForNode(definedVariablesNames,
				currentOutSet, node);
		setInOutSet(node);
		fVisitedStmts.add(node);
		// We need to make the for assign statement visible to the statements
		// within the for loop
		currentInSet.put(definedVariablesNames.iterator().next(),
				Sets.<TIRNode> newHashSet(node));

		caseForStmt(node);

		if (DEBUG)
			printMapForNode(node);
	}

Similar to the TIRForStmt, in case of assignment statements we add the current node as the definition site for all the nodes for all the variables defined in this statement. We also have to consider arrays that may be implicitly defined. For example, in other languages, a(i) = ... will be considered a use of the array a. However, in MATLAB, a(i) will be considered a definition if a has not be defined before. We also have to considered this case. This is done using the If condition inside the for loop. If the node is of type TIRAbstractAssignFromVarStmt and whether the variable has already been defined before, the variable is not considered.

@Override
	public void caseTIRAbstractAssignStmt(TIRAbstractAssignStmt node) {
		currentOutSet = copy(currentInSet);
		Set<String> definedVariablesNames = fVariableNameCollector
				.getDefinedVariablesForNode(node);
		for (String variableName : definedVariablesNames) {
			// Arrays maybe implicitly defined
			if (node instanceof TIRAbstractAssignFromVarStmt
					&& fDefiniteAssignment.isDefinitelyAssignedAtInputOf(node,
							variableName)) {
				continue;
			}
			Set<TIRNode> newDefinitionSite = new HashSet<TIRNode>();
			newDefinitionSite.add(node);
			currentOutSet.put(variableName, newDefinitionSite);
		}
		setInOutSet(node);
		fVisitedStmts.add(node);

		if (DEBUG)
			printMapForNode(node);
	}

	@Override
	public void caseTIRAbstractAssignToListStmt(TIRAbstractAssignToListStmt node) {
		currentOutSet = copy(currentInSet);
		Set<String> definedVariablesNames = fVariableNameCollector
				.getDefinedVariablesForNode(node);
		populateOutSetWithDefinitionSitesForNode(definedVariablesNames,
				currentOutSet, node);
		setInOutSet(node);
		fVisitedStmts.add(node);

		if (DEBUG)
			printMapForNode(node);
	}

Next we implement the helper methods populateOutSetWithDefinitionSitesForNode and setInOutSet that we need. The methods associateInSet and associateOutSet are defined in the TIRAbstractSimpleStructuralForwardAnalysis class. These methods add the currentInSet and the currentOutSet to the inFlowSets and the outFlowSets.

	public void populateOutSetWithDefinitionSitesForNode(
			Set<String> definedVariablesNames,
			Map<String, Set<TIRNode>> outSet, TIRNode node) {
		for (String variableName : definedVariablesNames) {
			Set<TIRNode> newDefinitionSite = new HashSet<TIRNode>();
			newDefinitionSite.add(node);
			outSet.put(variableName, newDefinitionSite);
		}
	}

        private void setInOutSet(TIRNode node) {
		associateInSet((ASTNode<?>) node, getCurrentInSet());
		associateOutSet((ASTNode<?>) node, getCurrentOutSet());
	}

Finally we implement the merge and copy methods. These methods are defined as abstract methods in the TIRAbstractSimpleStructuralForwardAnalysis class and have to be overridden. The merge defines the operations to be performed during a merge point in the control flow graph. In this case we perform a union operation. Additionally, we also define the method newInitialFlow which defines the initial value of the data structure. In this case, we simply create a new HashSet.

       public Map<String, Set<TIRNode>> merge(Map<String, Set<TIRNode>> in1,
			Map<String, Set<TIRNode>> in2) {
		return MergeUtil.unionMerge(in1, in2,
				(a, b) -> new HashSet<>(Sets.union(a, b)));
	}

@Override
	public Map<String, Set<TIRNode>> copy(Map<String, Set<TIRNode>> in) {
		Map<String, Set<TIRNode>> out = new HashMap<>();
		if(in == null) {
			return in;
		}
		for (String s : in.keySet()) {
			out.put(s, new HashSet<>(in.get(s)));
		}
		return out;
	}
        @Override
	public Map<String, Set<TIRNode>> newInitialFlow() {
		return copy(fStartMap);
	}

The entire analysis can be found here.