Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 1997-2000 Raja Vallee-Rai
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
 
 /*
  * Modified by the Sable Research Group and others 1997-2000.
  * See the 'credits' file distributed with Soot for the complete list of
  * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
  */
 
 
 /*
     2000, March 20 - Updated code provided by Patrick Lam
                             <plam@sable.mcgill.ca>
                      from 1.beta.4.dev.60
                      to 1.beta.6.dev.34
                      Plus some bug fixes.
                      -- Janus <janus@place.org>
 
 
      KNOWN LIMITATION: the analysis doesn't handle traps since traps
                handler statements have predecessors, but they
                don't have the trap handler as successor.  This
                might be a limitation of the CompleteUnitGraph
                tho.
 */
 
 
 package soot.toolkits.scalar;
 
 import soot.*;
 import soot.util.*;
 import java.util.*;
 
 import soot.options.*;

Abstract class providing an engine for branched forward flow analysis. WARNING: This does not handle exceptional flow as branches!
 
 public abstract class ForwardBranchedFlowAnalysis<A> extends BranchedFlowAnalysis<Unit, A>
 {
     public ForwardBranchedFlowAnalysis(UnitGraph graph)
     {
         super(graph);
     }
 
     protected boolean isForward()
     {
         return true;
     }
 
     // Accumulate the previous afterFlow sets.
     private void accumulateAfterFlowSets(Unit s, A[] flowRepositoriesList<ObjectpreviousAfterFlows)
     {
         int repCount = 0;
         
         previousAfterFlows.clear();
         if (s.fallsThrough())
         {
             copy(.get(s).get(0), flowRepositories[repCount]);
             previousAfterFlows.add(flowRepositories[repCount++]);
         }
         
         if (s.branches())
         {
             List<A> l = (.get(s));
             Iterator<A> it = l.iterator();
 
             while (it.hasNext())
             {
                 A fs = (it.next());
                 copy(fsflowRepositories[repCount]);
                 previousAfterFlows.add(flowRepositories[repCount++]);
             }
         }
     } // end accumulateAfterFlowSets
 
 
     protected void doAnalysis()
     {
         final Map<UnitIntegernumbers = new HashMap<UnitInteger>();
         List orderedUnits = new PseudoTopologicalOrderer().newList(,false);
        {
            int i = 1;
            forIterator uIt = orderedUnits.iterator(); uIt.hasNext(); ) {
                final Unit u = (UnituIt.next();
                numbers.put(unew Integer(i));
                i++;
            }
        }
        TreeSet<UnitchangedUnits = new TreeSet<Unit>( new Comparator() {
            public int compare(Object o1Object o2) {
                Integer i1 = numbers.get(o1);
                Integer i2 = numbers.get(o2);
                return (i1.intValue() - i2.intValue());
            }
        } );
        Map<UnitArrayListunitToIncomingFlowSets = new HashMap<UnitArrayList>(.size() * 2 + 1, 0.7f);
        List heads = .getHeads();
        int numNodes = .size();
        int numComputations = 0;
        int maxBranchSize = 0;
        
        // initialize unitToIncomingFlowSets
        {
            Iterator it = .iterator();
            while (it.hasNext())
            {
                Unit s = (Unitit.next();
                unitToIncomingFlowSets.put(snew ArrayList());
            }
        }
        // Set initial values and nodes to visit.
        // WARNING: DO NOT HANDLE THE CASE OF THE TRAPS
        {
            Chain sl = ((UnitGraph)).getBody().getUnits();
            Iterator it = .iterator();
            while(it.hasNext())
            {
                Unit s = (Unitit.next();
                changedUnits.add(s);
                .put(snewInitialFlow());
                if (s.fallsThrough())
                {
                    ArrayList<A> fl = new ArrayList<A>();
                    fl.add((newInitialFlow()));
                    .put(sfl);
		    Unit succ=(Unitsl.getSuccOf(s);
		    // it's possible for someone to insert some (dead) 
		    // fall through code at the very end of a method body
		    if(succ!=null) {
			List<Objectl = (unitToIncomingFlowSets.get(sl.getSuccOf(s)));
			l.addAll(fl);
		    }
                }
                else
                    .put(snew ArrayList<A>());
                if (s.branches())
                {
                    ArrayList<A> l = new ArrayList<A>();
                    List<A> incList;
                    Iterator boxIt = s.getUnitBoxes().iterator();
                    while (boxIt.hasNext())
                    {
                        A f = (newInitialFlow());
                        l.add(f);
                        Unit ss = ((UnitBox) (boxIt.next())).getUnit();
                        incList = (unitToIncomingFlowSets.get(ss));
                                          
                        incList.add(f);
                    }
                    .put(sl);
                }
                else
                    .put(snew ArrayList<A>());
                if (s.getUnitBoxes().size() > maxBranchSize)
                    maxBranchSize = s.getUnitBoxes().size();
            }
        }
        // Feng Qian: March 07, 2002
        // init entry points
        {
            Iterator<Unitit = heads.iterator();
            while (it.hasNext()) {
                Unit s = it.next();
                // this is a forward flow analysis
                .put(sentryInitialFlow());
            }
        }
        if (treatTrapHandlersAsEntries())
        {
            Iterator trapIt = ((UnitGraph)).getBody().
                                   getTraps().iterator();
            while(trapIt.hasNext()) {
                Trap trap = (TraptrapIt.next();
                Unit handler = trap.getHandlerUnit();
                .put(handlerentryInitialFlow());
            }
        }
        // Perform fixed point flow analysis
        {
            List<ObjectpreviousAfterFlows = new ArrayList<Object>(); 
            List<ObjectafterFlows = new ArrayList<Object>();
            A[] flowRepositories = (A[]) new Object[maxBranchSize+1];
            for (int i = 0; i < maxBranchSize+1; i++)
                flowRepositories[i] = newInitialFlow();
            A[] previousFlowRepositories = (A[])new Object[maxBranchSize+1];
            for (int i = 0; i < maxBranchSize+1; i++)
                previousFlowRepositories[i] = newInitialFlow();
            while(!changedUnits.isEmpty())
            {
                A beforeFlow;
                Unit s = changedUnits.first();
                changedUnits.remove(s);
                boolean isHead = heads.contains(s);
                accumulateAfterFlowSets(spreviousFlowRepositoriespreviousAfterFlows);
                // Compute and store beforeFlow
                {
                    List<A> preds = unitToIncomingFlowSets.get(s);
                    beforeFlow = .get(s);
                    if(preds.size() == 1)
                        copy(preds.get(0), beforeFlow);
                    else if(preds.size() != 0)
                    {
                        Iterator<A> predIt = preds.iterator();
                        copy(predIt.next(), beforeFlow);
                        while(predIt.hasNext())
                        {
                            A otherBranchFlow = predIt.next();
                            A newBeforeFlow = newInitialFlow();
                            merge(sbeforeFlowotherBranchFlownewBeforeFlow);
                            copy(newBeforeFlowbeforeFlow);
                        }
                    }
                    if(isHead && preds.size() != 0)
                        mergeInto(sbeforeFlowentryInitialFlow());
                }
                // Compute afterFlow and store it.
                {
                    ArrayList<A> afterFallFlow = .get(s);
                    ArrayList<A> afterBranchFlow = .get(s);
                    if (Options.v().interactive_mode()){
                        A savedFlow = newInitialFlow();
                        copy(beforeFlowsavedFlow);
                        FlowInfo fi = new FlowInfo(savedFlowstrue);
                        if (InteractionHandler.v().getStopUnitList() != null && InteractionHandler.v().getStopUnitList().contains(s)){
                            InteractionHandler.v().handleStopAtNodeEvent(s);
                        }
                        InteractionHandler.v().handleBeforeAnalysisEvent(fi);
                    }
                    flowThrough(beforeFlows, (ListafterFallFlow, (ListafterBranchFlow);
                    if (Options.v().interactive_mode()){
                        ArrayList l = new ArrayList();
                        if (!((List)afterFallFlow).isEmpty()){
                            l.addAll((List)afterFallFlow);
                        }
                        if (!((List)afterBranchFlow).isEmpty()){
                            l.addAll((List)afterBranchFlow);
                        }
                        
                        /*if (s instanceof soot.jimple.IfStmt){
                            l.addAll((List)afterFallFlow);
                            l.addAll((List)afterBranchFlow);
                        }
                        else {
                            l.addAll((List)afterFallFlow);
                        }*/
                        FlowInfo fi = new FlowInfo(lsfalse);
                        InteractionHandler.v().handleAfterAnalysisEvent(fi);
                    }
                    numComputations++;
                }
                accumulateAfterFlowSets(sflowRepositoriesafterFlows);
                // Update queue appropriately
                if(!afterFlows.equals(previousAfterFlows))
                {
                    Iterator succIt = .getSuccsOf(s).iterator();
                    while(succIt.hasNext())
                    {
                        Unit succ = (UnitsuccIt.next();
                            
                        changedUnits.add(succ);
                    }
                }
            }
        }
        
        // G.v().out.println(graph.getBody().getMethod().getSignature() + " numNodes: " + numNodes + 
        //    " numComputations: " + numComputations + " avg: " + Main.truncatedOf((double) numComputations / numNodes, 2));
        
        Timers.v(). += numNodes;
        Timers.v(). += numComputations;
    } // end doAnalysis
// end class ForwardBranchedFlowAnalysis
New to GrepCode? Check out our FAQ X