+
+ private AllocSite createParameterAllocSite( ReachGraph rg,
+ TempDescriptor tempDesc,
+ boolean flagRegions
+ ) {
+
+ FlatNew flatNew;
+ if( flagRegions ) {
+ flatNew = new FlatNew( tempDesc.getType(), // type
+ tempDesc, // param temp
+ false, // global alloc?
+ "param"+tempDesc // disjoint site ID string
+ );
+ } else {
+ flatNew = new FlatNew( tempDesc.getType(), // type
+ tempDesc, // param temp
+ false, // global alloc?
+ null // disjoint site ID string
+ );
+ }
+
+ // create allocation site
+ AllocSite as = AllocSite.factory( allocationDepth,
+ flatNew,
+ flatNew.getDisjointId(),
+ false
+ );
+ for (int i = 0; i < allocationDepth; ++i) {
+ Integer id = generateUniqueHeapRegionNodeID();
+ as.setIthOldest(i, id);
+ mapHrnIdToAllocSite.put(id, as);
+ }
+ // the oldest node is a summary node
+ as.setSummary( generateUniqueHeapRegionNodeID() );
+
+ rg.age(as);
+
+ return as;
+
+ }
+
+private Set<FieldDescriptor> getFieldSetTobeAnalyzed(TypeDescriptor typeDesc){
+
+ Set<FieldDescriptor> fieldSet=new HashSet<FieldDescriptor>();
+ if(!typeDesc.isImmutable()){
+ ClassDescriptor classDesc = typeDesc.getClassDesc();
+ for (Iterator it = classDesc.getFields(); it.hasNext();) {
+ FieldDescriptor field = (FieldDescriptor) it.next();
+ TypeDescriptor fieldType = field.getType();
+ if (shouldAnalysisTrack( fieldType )) {
+ fieldSet.add(field);
+ }
+ }
+ }
+ return fieldSet;
+
+}
+
+ private HeapRegionNode createMultiDeimensionalArrayHRN(ReachGraph rg, AllocSite alloc, HeapRegionNode srcHRN, FieldDescriptor fd, Hashtable<HeapRegionNode, HeapRegionNode> map, Hashtable<TypeDescriptor, HeapRegionNode> mapToExistingNode, ReachSet alpha ){
+
+ int dimCount=fd.getType().getArrayCount();
+ HeapRegionNode prevNode=null;
+ HeapRegionNode arrayEntryNode=null;
+ for(int i=dimCount;i>0;i--){
+ TypeDescriptor typeDesc=fd.getType().dereference();//hack to get instance of type desc
+ typeDesc.setArrayCount(i);
+ TempDescriptor tempDesc=new TempDescriptor(typeDesc.getSymbol(),typeDesc);
+ HeapRegionNode hrnSummary ;
+ if(!mapToExistingNode.containsKey(typeDesc)){
+ AllocSite as;
+ if(i==dimCount){
+ as = alloc;
+ }else{
+ as = createParameterAllocSite(rg, tempDesc, false);
+ }
+ // make a new reference to allocated node
+ hrnSummary =
+ rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one
+ false, // single object?
+ true, // summary?
+ false, // out-of-context?
+ as.getType(), // type
+ as, // allocation site
+ alpha, // inherent reach
+ alpha, // current reach
+ ExistPredSet.factory(rg.predTrue), // predicates
+ tempDesc.toString() // description
+ );
+ rg.id2hrn.put(as.getSummary(),hrnSummary);
+
+ mapToExistingNode.put(typeDesc, hrnSummary);
+ }else{
+ hrnSummary=mapToExistingNode.get(typeDesc);
+ }
+
+ if(prevNode==null){
+ // make a new reference between new summary node and source
+ RefEdge edgeToSummary = new RefEdge(srcHRN, // source
+ hrnSummary, // dest
+ typeDesc, // type
+ fd.getSymbol(), // field name
+ alpha, // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+
+ rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
+ prevNode=hrnSummary;
+ arrayEntryNode=hrnSummary;
+ }else{
+ // make a new reference between summary nodes of array
+ RefEdge edgeToSummary = new RefEdge(prevNode, // source
+ hrnSummary, // dest
+ typeDesc, // type
+ arrayElementFieldName, // field name
+ alpha, // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+
+ rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
+ prevNode=hrnSummary;
+ }
+
+ }
+
+ // create a new obj node if obj has at least one non-primitive field
+ TypeDescriptor type=fd.getType();
+ if(getFieldSetTobeAnalyzed(type).size()>0){
+ TypeDescriptor typeDesc=type.dereference();
+ typeDesc.setArrayCount(0);
+ if(!mapToExistingNode.containsKey(typeDesc)){
+ TempDescriptor tempDesc=new TempDescriptor(type.getSymbol(),typeDesc);
+ AllocSite as = createParameterAllocSite(rg, tempDesc, false);
+ // make a new reference to allocated node
+ HeapRegionNode hrnSummary =
+ rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one
+ false, // single object?
+ true, // summary?
+ false, // out-of-context?
+ typeDesc, // type
+ as, // allocation site
+ alpha, // inherent reach
+ alpha, // current reach
+ ExistPredSet.factory(rg.predTrue), // predicates
+ tempDesc.toString() // description
+ );
+ rg.id2hrn.put(as.getSummary(),hrnSummary);
+ mapToExistingNode.put(typeDesc, hrnSummary);
+ RefEdge edgeToSummary = new RefEdge(prevNode, // source
+ hrnSummary, // dest
+ typeDesc, // type
+ arrayElementFieldName, // field name
+ alpha, // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+ rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
+ prevNode=hrnSummary;
+ }else{
+ HeapRegionNode hrnSummary=mapToExistingNode.get(typeDesc);
+ if(prevNode.getReferenceTo(hrnSummary, typeDesc, arrayElementFieldName)==null){
+ RefEdge edgeToSummary = new RefEdge(prevNode, // source
+ hrnSummary, // dest
+ typeDesc, // type
+ arrayElementFieldName, // field name
+ alpha, // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+ rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
+ }
+ prevNode=hrnSummary;
+ }
+ }
+
+ map.put(arrayEntryNode, prevNode);
+ return arrayEntryNode;
+}
+
+private ReachGraph createInitialTaskReachGraph(FlatMethod fm) {
+ ReachGraph rg = new ReachGraph();
+ TaskDescriptor taskDesc = fm.getTask();
+
+ for (int idx = 0; idx < taskDesc.numParameters(); idx++) {
+ Descriptor paramDesc = taskDesc.getParameter(idx);
+ TypeDescriptor paramTypeDesc = taskDesc.getParamType(idx);
+
+ // setup data structure
+ Set<HashMap<HeapRegionNode, FieldDescriptor>> workSet =
+ new HashSet<HashMap<HeapRegionNode, FieldDescriptor>>();
+ Hashtable<TypeDescriptor, HeapRegionNode> mapTypeToExistingSummaryNode =
+ new Hashtable<TypeDescriptor, HeapRegionNode>();
+ Hashtable<HeapRegionNode, HeapRegionNode> mapToFirstDimensionArrayNode =
+ new Hashtable<HeapRegionNode, HeapRegionNode>();
+ Set<String> doneSet = new HashSet<String>();
+
+ TempDescriptor tempDesc = fm.getParameter(idx);
+
+ AllocSite as = createParameterAllocSite(rg, tempDesc, true);
+ VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc);
+ Integer idNewest = as.getIthOldest(0);
+ HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest);
+
+ // make a new reference to allocated node
+ RefEdge edgeNew = new RefEdge(lnX, // source
+ hrnNewest, // dest
+ taskDesc.getParamType(idx), // type
+ null, // field name
+ hrnNewest.getAlpha(), // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+ rg.addRefEdge(lnX, hrnNewest, edgeNew);
+
+ // set-up a work set for class field
+ ClassDescriptor classDesc = paramTypeDesc.getClassDesc();
+ for (Iterator it = classDesc.getFields(); it.hasNext();) {
+ FieldDescriptor fd = (FieldDescriptor) it.next();
+ TypeDescriptor fieldType = fd.getType();
+ if (shouldAnalysisTrack( fieldType )) {
+ HashMap<HeapRegionNode, FieldDescriptor> newMap = new HashMap<HeapRegionNode, FieldDescriptor>();
+ newMap.put(hrnNewest, fd);
+ workSet.add(newMap);
+ }
+ }
+
+ int uniqueIdentifier = 0;
+ while (!workSet.isEmpty()) {
+ HashMap<HeapRegionNode, FieldDescriptor> map = workSet
+ .iterator().next();
+ workSet.remove(map);
+
+ Set<HeapRegionNode> key = map.keySet();
+ HeapRegionNode srcHRN = key.iterator().next();
+ FieldDescriptor fd = map.get(srcHRN);
+ TypeDescriptor type = fd.getType();
+ String doneSetIdentifier = srcHRN.getIDString() + "_" + fd;
+
+ if (!doneSet.contains(doneSetIdentifier)) {
+ doneSet.add(doneSetIdentifier);
+ if (!mapTypeToExistingSummaryNode.containsKey(type)) {
+ // create new summary Node
+ TempDescriptor td = new TempDescriptor("temp"
+ + uniqueIdentifier, type);
+
+ AllocSite allocSite;
+ if(type.equals(paramTypeDesc)){
+ //corresponding allocsite has already been created for a parameter variable.
+ allocSite=as;
+ }else{
+ allocSite = createParameterAllocSite(rg, td, false);
+ }
+ String strDesc = allocSite.toStringForDOT()
+ + "\\nsummary";
+ TypeDescriptor allocType=allocSite.getType();
+
+ HeapRegionNode hrnSummary;
+ if(allocType.isArray() && allocType.getArrayCount()>0){
+ hrnSummary=createMultiDeimensionalArrayHRN(rg,allocSite,srcHRN,fd,mapToFirstDimensionArrayNode,mapTypeToExistingSummaryNode,hrnNewest.getAlpha());
+ }else{
+ hrnSummary =
+ rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one
+ false, // single object?
+ true, // summary?
+ false, // out-of-context?
+ allocSite.getType(), // type
+ allocSite, // allocation site
+ hrnNewest.getAlpha(), // inherent reach
+ hrnNewest.getAlpha(), // current reach
+ ExistPredSet.factory(rg.predTrue), // predicates
+ strDesc // description
+ );
+ rg.id2hrn.put(allocSite.getSummary(),hrnSummary);
+
+ // make a new reference to summary node
+ RefEdge edgeToSummary = new RefEdge(srcHRN, // source
+ hrnSummary, // dest
+ type, // type
+ fd.getSymbol(), // field name
+ hrnNewest.getAlpha(), // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+
+ rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
+ }
+ uniqueIdentifier++;
+
+ mapTypeToExistingSummaryNode.put(type, hrnSummary);
+
+ // set-up a work set for fields of the class
+ Set<FieldDescriptor> fieldTobeAnalyzed=getFieldSetTobeAnalyzed(type);
+ for (Iterator iterator = fieldTobeAnalyzed.iterator(); iterator
+ .hasNext();) {
+ FieldDescriptor fieldDescriptor = (FieldDescriptor) iterator
+ .next();
+ HeapRegionNode newDstHRN;
+ if(mapToFirstDimensionArrayNode.containsKey(hrnSummary)){
+ //related heap region node is already exsited.
+ newDstHRN=mapToFirstDimensionArrayNode.get(hrnSummary);
+ }else{
+ newDstHRN=hrnSummary;
+ }
+ doneSetIdentifier = newDstHRN.getIDString() + "_" + fieldDescriptor;
+ if(!doneSet.contains(doneSetIdentifier)){
+ // add new work item
+ HashMap<HeapRegionNode, FieldDescriptor> newMap =
+ new HashMap<HeapRegionNode, FieldDescriptor>();
+ newMap.put(newDstHRN, fieldDescriptor);
+ workSet.add(newMap);
+ }
+ }
+
+ }else{
+ // if there exists corresponding summary node
+ HeapRegionNode hrnDst=mapTypeToExistingSummaryNode.get(type);
+
+ RefEdge edgeToSummary = new RefEdge(srcHRN, // source
+ hrnDst, // dest
+ fd.getType(), // type
+ fd.getSymbol(), // field name
+ srcHRN.getAlpha(), // beta
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
+ );
+ rg.addRefEdge(srcHRN, hrnDst, edgeToSummary);
+
+ }
+ }
+ }
+ }
+// debugSnapshot(rg, fm, true);
+ return rg;
+}
+
+// return all allocation sites in the method (there is one allocation
+// site per FlatNew node in a method)
+private HashSet<AllocSite> getAllocationSiteSet(Descriptor d) {
+ if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
+ buildAllocationSiteSet(d);
+ }
+
+ return mapDescriptorToAllocSiteSet.get(d);
+
+}
+
+private void buildAllocationSiteSet(Descriptor d) {
+ HashSet<AllocSite> s = new HashSet<AllocSite>();
+
+ FlatMethod fm;
+ if( d instanceof MethodDescriptor ) {
+ fm = state.getMethodFlat( (MethodDescriptor) d);
+ } else {
+ assert d instanceof TaskDescriptor;
+ fm = state.getMethodFlat( (TaskDescriptor) d);
+ }
+ pm.analyzeMethod(fm);
+
+ // visit every node in this FlatMethod's IR graph
+ // and make a set of the allocation sites from the
+ // FlatNew node's visited
+ HashSet<FlatNode> visited = new HashSet<FlatNode>();
+ HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
+ toVisit.add(fm);
+
+ while( !toVisit.isEmpty() ) {
+ FlatNode n = toVisit.iterator().next();
+
+ if( n instanceof FlatNew ) {
+ s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
+ }
+
+ toVisit.remove(n);
+ visited.add(n);
+
+ for( int i = 0; i < pm.numNext(n); ++i ) {
+ FlatNode child = pm.getNext(n, i);
+ if( !visited.contains(child) ) {
+ toVisit.add(child);
+ }
+ }
+ }
+
+ mapDescriptorToAllocSiteSet.put(d, s);
+ }
+
+ private HashSet<AllocSite> getFlaggedAllocationSites(Descriptor dIn) {
+
+ HashSet<AllocSite> out = new HashSet<AllocSite>();
+ HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
+ HashSet<Descriptor> visited = new HashSet<Descriptor>();
+
+ toVisit.add(dIn);
+
+ while (!toVisit.isEmpty()) {
+ Descriptor d = toVisit.iterator().next();
+ toVisit.remove(d);
+ visited.add(d);
+
+ HashSet<AllocSite> asSet = getAllocationSiteSet(d);
+ Iterator asItr = asSet.iterator();
+ while (asItr.hasNext()) {
+ AllocSite as = (AllocSite) asItr.next();
+ if (as.getDisjointAnalysisId() != null) {
+ out.add(as);
+ }
+ }
+
+ // enqueue callees of this method to be searched for
+ // allocation sites also
+ Set callees = callGraph.getCalleeSet(d);
+ if (callees != null) {
+ Iterator methItr = callees.iterator();
+ while (methItr.hasNext()) {
+ MethodDescriptor md = (MethodDescriptor) methItr.next();
+
+ if (!visited.contains(md)) {
+ toVisit.add(md);
+ }
+ }
+ }
+ }
+
+ return out;
+ }
+
+
+private HashSet<AllocSite>
+getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
+
+ HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
+ HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
+ HashSet<Descriptor> visited = new HashSet<Descriptor>();
+
+ toVisit.add(td);
+
+ // traverse this task and all methods reachable from this task
+ while( !toVisit.isEmpty() ) {
+ Descriptor d = toVisit.iterator().next();
+ toVisit.remove(d);
+ visited.add(d);
+
+ HashSet<AllocSite> asSet = getAllocationSiteSet(d);
+ Iterator asItr = asSet.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = (AllocSite) asItr.next();
+ TypeDescriptor typed = as.getType();
+ if( typed != null ) {
+ ClassDescriptor cd = typed.getClassDesc();
+ if( cd != null && cd.hasFlags() ) {
+ asSetTotal.add(as);
+ }
+ }
+ }
+
+ // enqueue callees of this method to be searched for
+ // allocation sites also
+ Set callees = callGraph.getCalleeSet(d);
+ if( callees != null ) {
+ Iterator methItr = callees.iterator();
+ while( methItr.hasNext() ) {
+ MethodDescriptor md = (MethodDescriptor) methItr.next();
+
+ if( !visited.contains(md) ) {
+ toVisit.add(md);
+ }
+ }
+ }
+ }
+
+ return asSetTotal;
+}
+
+ public Set<Descriptor> getDescriptorsToAnalyze() {
+ return descriptorsToAnalyze;
+ }
+
+ public EffectsAnalysis getEffectsAnalysis(){
+ return effectsAnalysis;
+ }
+
+ public ReachGraph getReachGraph(Descriptor d){
+ return mapDescriptorToCompleteReachGraph.get(d);
+ }
+
+
+ // get successive captures of the analysis state, use compiler
+ // flags to control
+ boolean takeDebugSnapshots = false;
+ String descSymbolDebug = null;
+ boolean stopAfterCapture = false;
+ int snapVisitCounter = 0;
+ int snapNodeCounter = 0;
+ int visitStartCapture = 0;
+ int numVisitsToCapture = 0;
+
+
+ void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) {
+ if( snapVisitCounter > visitStartCapture + numVisitsToCapture ) {
+ return;
+ }
+
+ if( in ) {
+
+ }
+
+ if( snapVisitCounter >= visitStartCapture ) {
+ System.out.println( " @@@ snapping visit="+snapVisitCounter+
+ ", node="+snapNodeCounter+
+ " @@@" );
+ String graphName;
+ if( in ) {
+ graphName = String.format( "snap%03d_%04din",
+ snapVisitCounter,
+ snapNodeCounter );
+ } else {
+ graphName = String.format( "snap%03d_%04dout",
+ snapVisitCounter,
+ snapNodeCounter );
+ }
+ if( fn != null ) {
+ graphName = graphName + fn;
+ }
+ rg.writeGraph( graphName,
+ true, // write labels (variables)
+ true, // selectively hide intermediate temp vars
+ true, // prune unreachable heap regions
+ false, // hide reachability
+ true, // hide subset reachability states
+ true, // hide predicates
+ false );// hide edge taints
+ }
+ }
+