dev/core/src/com/google/gwt/dev/jjs/impl/codesplitter/LiveAtomsByRunAsyncSets.java - gwt - Git at Google

 /*
  * Copyright 2013 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
  * in compliance with the License. You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.gwt.dev.jjs.impl.codesplitter;

 import com.google.gwt.core.ext.TreeLogger;
 import com.google.gwt.dev.jjs.ast.JDeclaredType;
 import com.google.gwt.dev.jjs.ast.JField;
 import com.google.gwt.dev.jjs.ast.JMethod;
 import com.google.gwt.dev.jjs.ast.JNode;
 import com.google.gwt.dev.jjs.ast.JReferenceType;
 import com.google.gwt.dev.jjs.ast.JRunAsync;
 import com.google.gwt.dev.jjs.impl.ControlFlowAnalyzer;
 import com.google.gwt.thirdparty.guava.common.collect.LinkedHashMultiset;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;
 import com.google.gwt.thirdparty.guava.common.collect.Maps;
 import com.google.gwt.thirdparty.guava.common.collect.Multiset;

 import java.util.BitSet;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.PriorityQueue;

 /**
  * Maps an atom to a set of runAsyncs that can be live (NOT necessary exclusively) when that
  * runAsync is activated. The runAsyncs are represented by a bit set where S[i] is set if the atom
  * needs to be live when runAsync i is live.<br />
  *
  * In this class "payload size" is the size of the atoms that will be loaded (beyond the set of
  * atoms already loaded in the initial sequence) as part of a particular exclusive fragment.
  *
  * "Subset" refers to an arbitrary combination of runAsync ids.
  */
 class LiveAtomsByRunAsyncSets {

   LiveAtomsByRunAsyncSets(TreeLogger logger) {
     this.logger = logger;
   }

   private static class SubsetWithSize implements Comparable<SubsetWithSize> {
     private final int size;
     private final BitSet subset;

     public SubsetWithSize(BitSet subset, int size) {
       this.subset = subset;
       this.size = size;
     }

     @Override
     public int compareTo(SubsetWithSize o) {
       return Integer.valueOf(o.size).compareTo(Integer.valueOf(size));
     }
   }

   private static final int AVERAGE_METHOD_SIZE = 40;
   private static final int AVERAGE_NAME_SIZE = 2;
   private static final int FUNCTION_DEFINITION_CONSTANT_SIZE = "function".length() + "()".length();

   private static BitSet computeComplement(BitSet bitSet, int count) {
     BitSet notMergedSubset = (BitSet) bitSet.clone();
     notMergedSubset.flip(0, count);
     return notMergedSubset;
   }

   private static BitSet computeIntersection(BitSet thisSet, BitSet thatSet) {
     BitSet intersectionBitSet = (BitSet) thisSet.clone();
     intersectionBitSet.and(thatSet);
     return intersectionBitSet;
   }

   private static int getSizeEstimate(JDeclaredType type) {
     int defineClassSize = AVERAGE_NAME_SIZE + 50;
     int methodsSize = (3 + AVERAGE_NAME_SIZE) * type.getMethods().size();
     return defineClassSize + methodsSize;
   }

   private static int getSizeEstimate(JField field) {
     return AVERAGE_NAME_SIZE;
   }

   private static int getSizeEstimate(JMethod method) {
     int methodSize = FUNCTION_DEFINITION_CONSTANT_SIZE + (AVERAGE_NAME_SIZE + /* , */1
         + AVERAGE_METHOD_SIZE) * method.getParams().size();
     return methodSize;
   }

   private static int getSizeEstimate(Object obj) {
     if (obj instanceof JField) {
       return getSizeEstimate((JField) obj);
     } else if (obj instanceof JMethod) {
       return getSizeEstimate((JMethod) obj);
     } else if (obj instanceof String) {
       return getSizeEstimate((String) obj);
     } else if (obj instanceof JDeclaredType) {
       return getSizeEstimate((JDeclaredType) obj);
     }
     throw new UnsupportedOperationException(
         "estimateSize unsupported for type " + obj.getClass().getName());
   }

   private static int getSizeEstimate(String string) {
     return string.length();
   }

   private static boolean isSubset(BitSet smallerSet, BitSet biggerSet) {
     return computeIntersection(smallerSet, biggerSet).equals(smallerSet);
   }

   private final Map<JRunAsync, Integer> idForRunAsync = Maps.newHashMap();
   private Map<JField, BitSet> liveSubsetForField = Maps.newLinkedHashMap();
   private Map<JMethod, BitSet> liveSubsetForMethod = Maps.newLinkedHashMap();
   private Map<String, BitSet> liveSubsetForString = Maps.newLinkedHashMap();
   private Map<JDeclaredType, BitSet> liveSubsetForType = Maps.newLinkedHashMap();
   private int nextRunAsyncId = 0;
   private final Multiset<BitSet> payloadSizeBySubset = LinkedHashMultiset.create();
   private final Map<Integer, JRunAsync> runAsyncForId = Maps.newHashMap();
   private final TreeLogger logger;
   private Collection<Collection<JRunAsync>> groupedRunAsyncs;

   public int getRunAsyncCount() {
     return idForRunAsync.size();
   }

   /**
    * Returns a list of lists of runAsyncs where {@code pairCount} lists are the result of greedily
    * accumulating the pairs of runAsyncs that together result in the largest payload, while
    * referencing each runAsync only once.
    */
   public Collection<Collection<JRunAsync>> mergeSimilarPairs(int pairCount) {
     Collection<Collection<JRunAsync>> fragmentRunAsyncLists = Lists.newArrayList();
     BitSet mergedSubset = new BitSet();
     PriorityQueue<SubsetWithSize> subsetsDescending = computeSubsetsDescending();

     // Exclude the groupings prespecified by the user.
     // TODO(rluble): we could do better and treat a prespecified grouping as one runAsync for
     // merging purpose. For now prespecified groupings are excluded from merge by similarity.
     // will be treated better in v3.
     for (Collection<JRunAsync> runAsyncGroup : groupedRunAsyncs) {
       if (runAsyncGroup.size() <=  1) {
         continue;
       }
       // Premptively add them to the output.
       fragmentRunAsyncLists.add(runAsyncGroup);
       // And mark them as used.
       mergedSubset.or(asBitSet(runAsyncGroup));
     }

     // While there are still combinations to examine
     while (fragmentRunAsyncLists.size() < pairCount && !subsetsDescending.isEmpty()) {
       BitSet largestSubset = subsetsDescending.poll().subset;

       // If one of the runAsyncs in the current set of runAsyncs has already been used.
       if (largestSubset.intersects(mergedSubset)) {
         // Then throw this set out.
         continue;
       }

       logger.log(TreeLogger.Type.DEBUG, "Merging " + largestSubset);

       fragmentRunAsyncLists.add(asRunAsyncList(largestSubset));

       // Remember that the runAsyncs have already been used.
       mergedSubset.or(largestSubset);
     }

     // Get the ones that are not merged
     BitSet notMergedSubset = computeComplement(mergedSubset, getRunAsyncCount());

     fragmentRunAsyncLists.addAll(CodeSplitters.getListOfLists(asRunAsyncList(notMergedSubset)));
     return fragmentRunAsyncLists;
   }

   /**
    * Modifies a provided list of lists of runAsyncs (each of which represents a fragment) by
    * combining sets of runAsyncs whose output size is too small.
    */
   public Collection<Collection<JRunAsync>> mergeSmallFragments(
       Collection<Collection<JRunAsync>> fragmentRunAsyncLists, int minSize) {
     List<JRunAsync> smallFragmentRunAsyncs = Lists.newArrayList();

     Iterator<Collection<JRunAsync>> fragmentIterator = fragmentRunAsyncLists.iterator();
     while (fragmentIterator.hasNext()) {
       Collection<JRunAsync> fragmentRunAsyncs = fragmentIterator.next();
       if (isFragmentTooSmall(fragmentRunAsyncs, minSize)) {
         smallFragmentRunAsyncs.addAll(fragmentRunAsyncs);
         fragmentIterator.remove();
       }
     }

     if (!smallFragmentRunAsyncs.isEmpty() && !isFragmentTooSmall(smallFragmentRunAsyncs, minSize)) {
       // Keep the fragment combining all the small fragments.
       fragmentRunAsyncLists.add(smallFragmentRunAsyncs);
       logger.log(TreeLogger.Type.DEBUG, "Merging small fragments " + smallFragmentRunAsyncs +
           " together ");
     } else if (!smallFragmentRunAsyncs.isEmpty()) {
       // This fragment was still small so it is not added to fragmentRunAsyncLists and consequently
       // its contents will end up in the leftovers.
       logger.log(TreeLogger.Type.DEBUG, "Merging small fragments " + smallFragmentRunAsyncs +
           " into leftovers ");
     }

     return fragmentRunAsyncLists;
   }

   /**
    * Iteratively expand the initial sequence CFA with each runAsync, record the resulting live
    * atoms and finally compute the payload size for each subset.
    */
   public void recordLiveSubsetsAndEstimateTheirSizes(
       ControlFlowAnalyzer initialSequenceCfa, Collection<Collection<JRunAsync>> groupedRunAsyncs) {
     this.groupedRunAsyncs = groupedRunAsyncs;
     for (Collection<JRunAsync> runAsyncGroup : groupedRunAsyncs) {
       for (JRunAsync runAsync : runAsyncGroup) {
         ControlFlowAnalyzer withRunAsyncCfa = new ControlFlowAnalyzer(initialSequenceCfa);
         withRunAsyncCfa.traverseFromRunAsync(runAsync);
         recordLiveSubset(withRunAsyncCfa, runAsync);
       }
     }
     accumulatePayloadSizes();
   }

   private <T> void accumulatePayloadSizes(Map<T, BitSet> liveSubsetsByAtom) {
     for (Map.Entry<T, BitSet> entry : liveSubsetsByAtom.entrySet()) {
       BitSet liveSubset = entry.getValue();
       T atom = entry.getKey();

       // TODO(rluble): Underestimates the size of fragments resulting of merging more than 2
       // fragments. With the current strategy it can only happen for the set of very small fragments
       // and that is OK.
       if (liveSubset.cardinality() > 2) {
         continue;
       }

       payloadSizeBySubset.add(liveSubset, getSizeEstimate(atom));
     }
   }

   private void addRunAsync(JRunAsync runAsync) {
     int runAsyncId = nextRunAsyncId++;
     idForRunAsync.put(runAsync, runAsyncId);
     runAsyncForId.put(runAsyncId, runAsync);
   }

   private BitSet asBitSet(Collection<JRunAsync> runAsyncs) {
     BitSet result = new BitSet();
     for (JRunAsync runAsync : runAsyncs) {
       result.set(getIdForRunAsync(runAsync));
     }
     return result;
   }

   private List<JRunAsync> asRunAsyncList(BitSet subset) {
     int runAsyncId = -1;
     List<JRunAsync> runAsyncs = Lists.newArrayList();
     while ((runAsyncId = subset.nextSetBit(runAsyncId + 1)) != -1) {
       runAsyncs.add(runAsyncForId.get(runAsyncId));
     }
     return runAsyncs;
   }

   private PriorityQueue<SubsetWithSize> computeSubsetsDescending() {
     PriorityQueue<SubsetWithSize> subsetsDescending = new PriorityQueue<SubsetWithSize>();
     for (BitSet subset : payloadSizeBySubset.elementSet()) {
       if (subset.cardinality() != 2) {
         continue;
       }

       subsetsDescending.add(new SubsetWithSize(subset, payloadSizeBySubset.count(subset)));
     }
     return subsetsDescending;
   }

   /**
    * Accumulate payload sizes.
    */
   private void accumulatePayloadSizes() {
     accumulatePayloadSizes(liveSubsetForField);
     accumulatePayloadSizes(liveSubsetForMethod);
     accumulatePayloadSizes(liveSubsetForString);
     accumulatePayloadSizes(liveSubsetForType);
   }

   private int getIdForRunAsync(JRunAsync runAsync) {
     return idForRunAsync.get(runAsync);
   }

   private boolean isFragmentTooSmall(Collection<JRunAsync> fragmentRunAsyncs, int minSize) {
     BitSet fragmentSubset = asBitSet(fragmentRunAsyncs);

     int size = 0;
     // TODO(rluble): This might be quite inefficient as it compare to all possible (non trivially
     // empty) subsets (bounded by the number of atoms). But is only run at most #runAsyncs times to
     // determine whether to merge small fragments.
     for (BitSet subset : payloadSizeBySubset.elementSet()) {
       if (isSubset(subset, fragmentSubset)) {

         size += payloadSizeBySubset.count(subset);
         if (size >= minSize) {
           return false;
         }
       }
     }
     return true;
   }

   private ControlFlowAnalyzer recordLiveSubset(ControlFlowAnalyzer cfa, JRunAsync runAsync) {
     addRunAsync(runAsync);
     for (JNode node : cfa.getLiveFieldsAndMethods()) {
       if (node instanceof JField) {
         setLive(liveSubsetForField, (JField) node, runAsync);
       }
       if (node instanceof JMethod) {
         setLive(liveSubsetForMethod, (JMethod) node, runAsync);
       }
     }
     for (JField field : cfa.getFieldsWritten()) {
       setLive(liveSubsetForField, field, runAsync);
     }
     for (String string : cfa.getLiveStrings()) {
       setLive(liveSubsetForString, string, runAsync);
     }
     for (JReferenceType type : cfa.getInstantiatedTypes()) {
       if (type instanceof JDeclaredType) {
         setLive(liveSubsetForType, (JDeclaredType) type, runAsync);
       }
     }
     return cfa;
   }

   private <T> boolean setLive(Map<T, BitSet> liveSubsetsByAtom, T atom, JRunAsync runAsync) {
     int runAsyncId = idForRunAsync.get(runAsync);
     BitSet liveSubset = liveSubsetsByAtom.get(atom);
     if (liveSubset == null) {
       liveSubset = new BitSet();
       liveSubset.set(runAsyncId);
       liveSubsetsByAtom.put(atom, liveSubset);
       return true;
     } else {
       if (liveSubset.get(runAsyncId)) {
         return false;
       } else {
         liveSubset.set(runAsyncId);
         return true;
       }
     }
   }
 }
	/*
	* Copyright 2013 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
	* in compliance with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software distributed under the License
	* is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
	* or implied. See the License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.gwt.dev.jjs.impl.codesplitter;

	import com.google.gwt.core.ext.TreeLogger;
	import com.google.gwt.dev.jjs.ast.JDeclaredType;
	import com.google.gwt.dev.jjs.ast.JField;
	import com.google.gwt.dev.jjs.ast.JMethod;
	import com.google.gwt.dev.jjs.ast.JNode;
	import com.google.gwt.dev.jjs.ast.JReferenceType;
	import com.google.gwt.dev.jjs.ast.JRunAsync;
	import com.google.gwt.dev.jjs.impl.ControlFlowAnalyzer;
	import com.google.gwt.thirdparty.guava.common.collect.LinkedHashMultiset;
	import com.google.gwt.thirdparty.guava.common.collect.Lists;
	import com.google.gwt.thirdparty.guava.common.collect.Maps;
	import com.google.gwt.thirdparty.guava.common.collect.Multiset;

	import java.util.BitSet;
	import java.util.Collection;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.PriorityQueue;

	/**
	* Maps an atom to a set of runAsyncs that can be live (NOT necessary exclusively) when that
	* runAsync is activated. The runAsyncs are represented by a bit set where S[i] is set if the atom
	* needs to be live when runAsync i is live.<br />
	*
	* In this class "payload size" is the size of the atoms that will be loaded (beyond the set of
	* atoms already loaded in the initial sequence) as part of a particular exclusive fragment.
	*
	* "Subset" refers to an arbitrary combination of runAsync ids.
	*/
	class LiveAtomsByRunAsyncSets {

	LiveAtomsByRunAsyncSets(TreeLogger logger) {
	this.logger = logger;
	}

	private static class SubsetWithSize implements Comparable<SubsetWithSize> {
	private final int size;
	private final BitSet subset;

	public SubsetWithSize(BitSet subset, int size) {
	this.subset = subset;
	this.size = size;
	}

	@Override
	public int compareTo(SubsetWithSize o) {
	return Integer.valueOf(o.size).compareTo(Integer.valueOf(size));
	}
	}

	private static final int AVERAGE_METHOD_SIZE = 40;
	private static final int AVERAGE_NAME_SIZE = 2;
	private static final int FUNCTION_DEFINITION_CONSTANT_SIZE = "function".length() + "()".length();

	private static BitSet computeComplement(BitSet bitSet, int count) {
	BitSet notMergedSubset = (BitSet) bitSet.clone();
	notMergedSubset.flip(0, count);
	return notMergedSubset;
	}

	private static BitSet computeIntersection(BitSet thisSet, BitSet thatSet) {
	BitSet intersectionBitSet = (BitSet) thisSet.clone();
	intersectionBitSet.and(thatSet);
	return intersectionBitSet;
	}

	private static int getSizeEstimate(JDeclaredType type) {
	int defineClassSize = AVERAGE_NAME_SIZE + 50;
	int methodsSize = (3 + AVERAGE_NAME_SIZE) * type.getMethods().size();
	return defineClassSize + methodsSize;
	}

	private static int getSizeEstimate(JField field) {
	return AVERAGE_NAME_SIZE;
	}

	private static int getSizeEstimate(JMethod method) {
	int methodSize = FUNCTION_DEFINITION_CONSTANT_SIZE + (AVERAGE_NAME_SIZE + /* , */1
	+ AVERAGE_METHOD_SIZE) * method.getParams().size();
	return methodSize;
	}

	private static int getSizeEstimate(Object obj) {
	if (obj instanceof JField) {
	return getSizeEstimate((JField) obj);
	} else if (obj instanceof JMethod) {
	return getSizeEstimate((JMethod) obj);
	} else if (obj instanceof String) {
	return getSizeEstimate((String) obj);
	} else if (obj instanceof JDeclaredType) {
	return getSizeEstimate((JDeclaredType) obj);
	}
	throw new UnsupportedOperationException(
	"estimateSize unsupported for type " + obj.getClass().getName());
	}

	private static int getSizeEstimate(String string) {
	return string.length();
	}

	private static boolean isSubset(BitSet smallerSet, BitSet biggerSet) {
	return computeIntersection(smallerSet, biggerSet).equals(smallerSet);
	}

	private final Map<JRunAsync, Integer> idForRunAsync = Maps.newHashMap();
	private Map<JField, BitSet> liveSubsetForField = Maps.newLinkedHashMap();
	private Map<JMethod, BitSet> liveSubsetForMethod = Maps.newLinkedHashMap();
	private Map<String, BitSet> liveSubsetForString = Maps.newLinkedHashMap();
	private Map<JDeclaredType, BitSet> liveSubsetForType = Maps.newLinkedHashMap();
	private int nextRunAsyncId = 0;
	private final Multiset<BitSet> payloadSizeBySubset = LinkedHashMultiset.create();
	private final Map<Integer, JRunAsync> runAsyncForId = Maps.newHashMap();
	private final TreeLogger logger;
	private Collection<Collection<JRunAsync>> groupedRunAsyncs;

	public int getRunAsyncCount() {
	return idForRunAsync.size();
	}

	/**
	* Returns a list of lists of runAsyncs where {@code pairCount} lists are the result of greedily
	* accumulating the pairs of runAsyncs that together result in the largest payload, while
	* referencing each runAsync only once.
	*/
	public Collection<Collection<JRunAsync>> mergeSimilarPairs(int pairCount) {
	Collection<Collection<JRunAsync>> fragmentRunAsyncLists = Lists.newArrayList();
	BitSet mergedSubset = new BitSet();
	PriorityQueue<SubsetWithSize> subsetsDescending = computeSubsetsDescending();

	// Exclude the groupings prespecified by the user.
	// TODO(rluble): we could do better and treat a prespecified grouping as one runAsync for
	// merging purpose. For now prespecified groupings are excluded from merge by similarity.
	// will be treated better in v3.
	for (Collection<JRunAsync> runAsyncGroup : groupedRunAsyncs) {
	if (runAsyncGroup.size() <= 1) {
	continue;
	}
	// Premptively add them to the output.
	fragmentRunAsyncLists.add(runAsyncGroup);
	// And mark them as used.
	mergedSubset.or(asBitSet(runAsyncGroup));
	}

	// While there are still combinations to examine
	while (fragmentRunAsyncLists.size() < pairCount && !subsetsDescending.isEmpty()) {
	BitSet largestSubset = subsetsDescending.poll().subset;

	// If one of the runAsyncs in the current set of runAsyncs has already been used.
	if (largestSubset.intersects(mergedSubset)) {
	// Then throw this set out.
	continue;
	}

	logger.log(TreeLogger.Type.DEBUG, "Merging " + largestSubset);

	fragmentRunAsyncLists.add(asRunAsyncList(largestSubset));

	// Remember that the runAsyncs have already been used.
	mergedSubset.or(largestSubset);
	}

	// Get the ones that are not merged
	BitSet notMergedSubset = computeComplement(mergedSubset, getRunAsyncCount());

	fragmentRunAsyncLists.addAll(CodeSplitters.getListOfLists(asRunAsyncList(notMergedSubset)));
	return fragmentRunAsyncLists;
	}

	/**
	* Modifies a provided list of lists of runAsyncs (each of which represents a fragment) by
	* combining sets of runAsyncs whose output size is too small.
	*/
	public Collection<Collection<JRunAsync>> mergeSmallFragments(
	Collection<Collection<JRunAsync>> fragmentRunAsyncLists, int minSize) {
	List<JRunAsync> smallFragmentRunAsyncs = Lists.newArrayList();

	Iterator<Collection<JRunAsync>> fragmentIterator = fragmentRunAsyncLists.iterator();
	while (fragmentIterator.hasNext()) {
	Collection<JRunAsync> fragmentRunAsyncs = fragmentIterator.next();
	if (isFragmentTooSmall(fragmentRunAsyncs, minSize)) {
	smallFragmentRunAsyncs.addAll(fragmentRunAsyncs);
	fragmentIterator.remove();
	}
	}

	if (!smallFragmentRunAsyncs.isEmpty() && !isFragmentTooSmall(smallFragmentRunAsyncs, minSize)) {
	// Keep the fragment combining all the small fragments.
	fragmentRunAsyncLists.add(smallFragmentRunAsyncs);
	logger.log(TreeLogger.Type.DEBUG, "Merging small fragments " + smallFragmentRunAsyncs +
	" together ");
	} else if (!smallFragmentRunAsyncs.isEmpty()) {
	// This fragment was still small so it is not added to fragmentRunAsyncLists and consequently
	// its contents will end up in the leftovers.
	logger.log(TreeLogger.Type.DEBUG, "Merging small fragments " + smallFragmentRunAsyncs +
	" into leftovers ");
	}

	return fragmentRunAsyncLists;
	}

	/**
	* Iteratively expand the initial sequence CFA with each runAsync, record the resulting live
	* atoms and finally compute the payload size for each subset.
	*/
	public void recordLiveSubsetsAndEstimateTheirSizes(
	ControlFlowAnalyzer initialSequenceCfa, Collection<Collection<JRunAsync>> groupedRunAsyncs) {
	this.groupedRunAsyncs = groupedRunAsyncs;
	for (Collection<JRunAsync> runAsyncGroup : groupedRunAsyncs) {
	for (JRunAsync runAsync : runAsyncGroup) {
	ControlFlowAnalyzer withRunAsyncCfa = new ControlFlowAnalyzer(initialSequenceCfa);
	withRunAsyncCfa.traverseFromRunAsync(runAsync);
	recordLiveSubset(withRunAsyncCfa, runAsync);
	}
	}
	accumulatePayloadSizes();
	}

	private <T> void accumulatePayloadSizes(Map<T, BitSet> liveSubsetsByAtom) {
	for (Map.Entry<T, BitSet> entry : liveSubsetsByAtom.entrySet()) {
	BitSet liveSubset = entry.getValue();
	T atom = entry.getKey();

	// TODO(rluble): Underestimates the size of fragments resulting of merging more than 2
	// fragments. With the current strategy it can only happen for the set of very small fragments
	// and that is OK.
	if (liveSubset.cardinality() > 2) {
	continue;
	}

	payloadSizeBySubset.add(liveSubset, getSizeEstimate(atom));
	}
	}

	private void addRunAsync(JRunAsync runAsync) {
	int runAsyncId = nextRunAsyncId++;
	idForRunAsync.put(runAsync, runAsyncId);
	runAsyncForId.put(runAsyncId, runAsync);
	}

	private BitSet asBitSet(Collection<JRunAsync> runAsyncs) {
	BitSet result = new BitSet();
	for (JRunAsync runAsync : runAsyncs) {
	result.set(getIdForRunAsync(runAsync));
	}
	return result;
	}

	private List<JRunAsync> asRunAsyncList(BitSet subset) {
	int runAsyncId = -1;
	List<JRunAsync> runAsyncs = Lists.newArrayList();
	while ((runAsyncId = subset.nextSetBit(runAsyncId + 1)) != -1) {
	runAsyncs.add(runAsyncForId.get(runAsyncId));
	}
	return runAsyncs;
	}

	private PriorityQueue<SubsetWithSize> computeSubsetsDescending() {
	PriorityQueue<SubsetWithSize> subsetsDescending = new PriorityQueue<SubsetWithSize>();
	for (BitSet subset : payloadSizeBySubset.elementSet()) {
	if (subset.cardinality() != 2) {
	continue;
	}

	subsetsDescending.add(new SubsetWithSize(subset, payloadSizeBySubset.count(subset)));
	}
	return subsetsDescending;
	}

	/**
	* Accumulate payload sizes.
	*/
	private void accumulatePayloadSizes() {
	accumulatePayloadSizes(liveSubsetForField);
	accumulatePayloadSizes(liveSubsetForMethod);
	accumulatePayloadSizes(liveSubsetForString);
	accumulatePayloadSizes(liveSubsetForType);
	}

	private int getIdForRunAsync(JRunAsync runAsync) {
	return idForRunAsync.get(runAsync);
	}

	private boolean isFragmentTooSmall(Collection<JRunAsync> fragmentRunAsyncs, int minSize) {
	BitSet fragmentSubset = asBitSet(fragmentRunAsyncs);

	int size = 0;
	// TODO(rluble): This might be quite inefficient as it compare to all possible (non trivially
	// empty) subsets (bounded by the number of atoms). But is only run at most #runAsyncs times to
	// determine whether to merge small fragments.
	for (BitSet subset : payloadSizeBySubset.elementSet()) {
	if (isSubset(subset, fragmentSubset)) {

	size += payloadSizeBySubset.count(subset);
	if (size >= minSize) {
	return false;
	}
	}
	}
	return true;
	}

	private ControlFlowAnalyzer recordLiveSubset(ControlFlowAnalyzer cfa, JRunAsync runAsync) {
	addRunAsync(runAsync);
	for (JNode node : cfa.getLiveFieldsAndMethods()) {
	if (node instanceof JField) {
	setLive(liveSubsetForField, (JField) node, runAsync);
	}
	if (node instanceof JMethod) {
	setLive(liveSubsetForMethod, (JMethod) node, runAsync);
	}
	}
	for (JField field : cfa.getFieldsWritten()) {
	setLive(liveSubsetForField, field, runAsync);
	}
	for (String string : cfa.getLiveStrings()) {
	setLive(liveSubsetForString, string, runAsync);
	}
	for (JReferenceType type : cfa.getInstantiatedTypes()) {
	if (type instanceof JDeclaredType) {
	setLive(liveSubsetForType, (JDeclaredType) type, runAsync);
	}
	}
	return cfa;
	}

	private <T> boolean setLive(Map<T, BitSet> liveSubsetsByAtom, T atom, JRunAsync runAsync) {
	int runAsyncId = idForRunAsync.get(runAsync);
	BitSet liveSubset = liveSubsetsByAtom.get(atom);
	if (liveSubset == null) {
	liveSubset = new BitSet();
	liveSubset.set(runAsyncId);
	liveSubsetsByAtom.put(atom, liveSubset);
	return true;
	} else {
	if (liveSubset.get(runAsyncId)) {
	return false;
	} else {
	liveSubset.set(runAsyncId);
	return true;
	}
	}
	}
	}