1 19 20 package edu.umd.cs.findbugs.ba.vna; 21 22 import java.util.BitSet ; 23 import java.util.HashMap ; 24 import java.util.LinkedList ; 25 import java.util.Map ; 26 27 import edu.umd.cs.findbugs.SystemProperties; 28 29 35 public class MergeTree { 36 public static final boolean DEBUG = SystemProperties.getBoolean("vna.merge.debug"); 37 38 private ValueNumberFactory factory; 39 private Map <ValueNumber, BitSet > outputToInputMap; 40 41 46 public MergeTree(ValueNumberFactory factory) { 47 this.factory = factory; 48 this.outputToInputMap = new HashMap <ValueNumber, BitSet >(); 49 } 50 51 57 public void mapInputToOutput(ValueNumber input, ValueNumber output) { 58 BitSet inputSet = getInputSet(output); 59 inputSet.set(input.getNumber()); 60 if (DEBUG) { 61 System.out.println(input.getNumber()+ "->" + output.getNumber()); 62 System.out.println("Input set for " + output.getNumber() + " is now " + inputSet); 63 } 64 } 65 66 73 public BitSet getInputSet(ValueNumber output) { 74 BitSet outputSet = outputToInputMap.get(output); 75 if (outputSet == null) { 76 if (DEBUG) { 77 System.out.println("Create new input set for " + output.getNumber()); 78 } 79 outputSet = new BitSet (); 80 outputToInputMap.put(output, outputSet); 81 } 82 return outputSet; 83 } 84 85 92 public BitSet getTransitiveInputSet(ValueNumber output) { 93 BitSet visited = new BitSet (); 94 BitSet result = new BitSet (); 95 96 if (DEBUG) { 97 System.out.println("Output: " + output.getNumber()); 98 } 99 100 LinkedList <ValueNumber> workList = new LinkedList <ValueNumber>(); 101 workList.addLast(output); 102 while (!workList.isEmpty()) { 103 ValueNumber valueNumber = workList.removeFirst(); 104 if (DEBUG) { 105 System.out.println("Check: " + valueNumber.getNumber()); 106 } 107 visited.set(valueNumber.getNumber()); 108 BitSet inputSet = getInputSet(valueNumber); 109 if (DEBUG) { 110 System.out.println("\tInput set is " + inputSet); 111 } 112 result.or(inputSet); 113 for (int i = 0; i < factory.getNumValuesAllocated(); ++i) { 114 if (inputSet.get(i) && !visited.get(i)) { 115 if (DEBUG) { 116 System.out.println("\tExplore: " + i); 117 } 118 workList.addLast(factory.forNumber(i)); 119 } 120 } 121 } 122 if (DEBUG) { 123 System.out.println("Result: " + result); 124 } 125 126 return result; 127 } 128 } 129 | Popular Tags |