Accrue Pointer Analysis Exercise

Implement a pointer analysis

1. First download and install Accrue. (See here for further instructions.)

2. Create a package accrue.tutorial.pointer.

3. Create a class ProcedureStack that encapsulates a stack of ProcedureInstances. This class will represent our code contexts, so it should implement the interface accrue.analysis.pointer.CContext.

   You can hard-code the ProcedureStack to represent stacks of some fixed depth (e.g., 2). We suggest you implement a method ProcedureStack push(ProcedureInstance) which pushes a ProcedureInstance on to the top of the stack, and truncates the stack to the maximum depth. In the Polyglot style, this method should be pure (i.e., it does not modify the state of the receiver object, but returns a new ProcedureStack).

   Note: you need to implement methods int hashCode() and boolean equalsSemantic(CContext). You do not need to implement boolean equals(Object), as the Accrue pointer analyses use memoization for CContexts and HContexts, and rely on the equals(Object) method giving pointer equality.

4. Create a class AllocationName that encapsulates a pair of a ProcedureStack and an AllocSiteNode. This class will represent our abstract heap objects, so it should implement the interface accrue.analysis.pointer.HContext.

   Note: you again need to implement methods int hashCode() and boolean equalsSemantic(HContext), but do not override boolean equals(Object).

5. Create a class ContextSensitive in the package accrue.tutorial.pointer that extends accrue.analysis.pointer.analyses.HeapAbstractionFactory. Provide appropriate implementations of the methods initialContextImpl, mergeImpl and recordImpl.

   That is: initialContextImpl should return a ProcedureStack with an empty stack of procedures. Method mergeImpl should push the callee's ProcedureInstance (which can be gotten with the code callSite.callee()) onto the ProcedureStack of the caller. Finally, method recordImpl should return an AllocationName for the pair of the code context and the allocation site.

6. You can now try running your pointer analysis on Java programs, by using the following code:

   $ACCRUE/bin/accruec -classpath pathToYourTutorialClasses \
     -heapabstraction accrue.tutorial.pointer.ContextSensitive C.java
   

   You can find some example Java programs to run on in the examples directory of the Accrue tutorial code.

Create an AccrueExtensionInfo for CArray

1. Create a package accrue.tutorial.carray.

2. Create a class accrue.tutorial.carray.CArrayAccrueExtInfo which extends carray.ExtensionInfo and implements AccrueExtensionInfo. The interface AccrueExtensionInfo contains some method definitions useful for Accrue, such as methods to get the heap abstraction factory for the pointer analysis.

3. Define the method CArrayAccrueExtInfo.createNodeFactory to add Accrue extension objects to newly created AST nodes. The following code snippet describes how to do this.

   @Override
   protected NodeFactory createNodeFactory() {
       return new CArrayNodeFactory_c(CArrayLang_c.instance,
   				   new CArrayExtFactory_c(new AnalysisExtFactory_c()));
   }
   

4. Create class AccrueCArrayOptions and return a new instance of it from the method CArrayAccrueExtInfo.createOptions. Class AccrueCArrayOptions should extend CArrayOptions and implement AccrueOptions. The code for AccrueCArrayOptions will be very similar to the code found in the Accrue class AccrueJL5Options, as it uses an AccrueOptionsHelper object to help with handling the Accrue command line options.

5. Create class AccrueCArrayScheduler and return a new instance of it from the method CArrayAccrueExtInfo.createScheduler. Class AccrueCArrayScheduler should extend CArrayScheduler and implement AccrueScheduler. To implement AccrueScheduler, this class needs to define method helper() which returns a AccrueSchedulerHelper object. To enable us to easily add passes later, define class AccrueCArraySchedulerHelper which extends AccrueSchedulerHelper, and put the following code in the body of AccrueCArrayScheduler.

   final AccrueCArraySchedulerHelper helper;
   
   public AccrueCArrayScheduler(carray.ExtensionInfo extInfo) {
       super(extInfo);
       this.helper = new AccrueCArraySchedulerHelper(extInfo, this);
   }
   
   @Override
   public AccrueSchedulerHelper helper() {
       return this.helper;
   }
   

6. Insert the following boiler plate code into the class CArrayAccrueExtInfo.

   private PointsToEngine pointsToEngine = null;
   
   @Override
   public PointsToEngine pointsToEngine() {
       if (pointsToEngine == null) {
   	AccrueOptions opts = (AccrueOptions) this.getOptions();
   	pointsToEngine = opts.helper().createPointsToEngine();
       }
       return pointsToEngine;
   }
   
   @Override
   public HeapAbstractionFactory heapAbstractionFactory() {
       return this.pointsToEngine().heapAbstractionFactory();
   }
   
   @Override
   public StmtRegistrar createStmtRegistrar() {
       return new StmtRegistrar(this);
   }
   
   protected AnalysisSignatures analysisSignatures = null;
   
   @Override
   public AnalysisSignatures getAnalysisSignatures() {
       if (analysisSignatures == null) {
   	analysisSignatures = createAnalysisSignatures();
       }
       return analysisSignatures;
   
   }
   
   protected AnalysisSignatures createAnalysisSignatures() {
       return new AnalysisSignatures();
   }
   
   @Override
   public boolean isOutputExtensionInfo() {
       return false; // we will do the analysis before the CArray code is translated
   }
   
   @Override
   public void setIsOutputExtensionInfo(boolean isOutputExtensionInfo) {
   
   }
   

7. You can now try running your pointer analysis on CArray programs, by using the following code:

   extclass=accrue.tutorial.carray.CArrayAccrueExtInfo $ACCRUE/bin/accruec \
    -classpath pathToYourTutorialClasses -heapabstraction accrue.tutorial.pointer.ContextSensitive C.car
   

   You can find some example CArray programs to run on in the examples directory of the Accrue tutorial code.