48 /**
49 * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
50 * block}.
51 */
52 private final int[] blocked;
53 private final Trace[] blockToTrace;
54
55 private UniDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
56 processed = new BitSet(blocks.length);
57 worklist = new PriorityQueue<>(UniDirectionalTraceBuilder::compare);
58 assert (worklist != null);
59
60 blocked = new int[blocks.length];
61 blockToTrace = new Trace[blocks.length];
62 for (AbstractBlockBase<?> block : blocks) {
63 blocked[block.getId()] = block.getPredecessorCount();
64 }
65 }
66
67 private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
68 return Double.compare(b.probability(), a.probability());
69 }
70
71 private boolean processed(AbstractBlockBase<?> b) {
72 return processed.get(b.getId());
73 }
74
75 @SuppressWarnings("try")
76 private TraceBuilderResult build(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
77 try (Indent indent = debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
78 ArrayList<Trace> traces = buildTraces(debug, startBlock);
79 return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
80 }
81 }
82
83 protected ArrayList<Trace> buildTraces(DebugContext debug, AbstractBlockBase<?> startBlock) {
84 ArrayList<Trace> traces = new ArrayList<>();
85 // add start block
86 worklist.add(startBlock);
87 // process worklist
88 while (!worklist.isEmpty()) {
93 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
94 blockToTrace[traceBlock.getId()] = trace;
95 }
96 trace.setId(traces.size());
97 traces.add(trace);
98 }
99 }
100 return traces;
101 }
102
103 /**
104 * Build a new trace starting at {@code block}.
105 */
106 @SuppressWarnings("try")
107 private List<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> traceStart) {
108 assert checkPredecessorsProcessed(traceStart);
109 ArrayList<AbstractBlockBase<?>> trace = new ArrayList<>();
110 int blockNumber = 0;
111 try (Indent i = debug.logAndIndent("StartTrace: %s", traceStart)) {
112 for (AbstractBlockBase<?> block = traceStart; block != null; block = selectNext(block)) {
113 debug.log("add %s (prob: %f)", block, block.probability());
114 processed.set(block.getId());
115 trace.add(block);
116 unblock(block);
117 block.setLinearScanNumber(blockNumber++);
118 }
119 }
120 return trace;
121 }
122
123 private boolean checkPredecessorsProcessed(AbstractBlockBase<?> block) {
124 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
125 assert processed(pred) : "Predecessor unscheduled: " + pred;
126 }
127 return true;
128 }
129
130 /**
131 * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
132 * the count reaches 0.
133 */
134 private void unblock(AbstractBlockBase<?> block) {
135 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
136 if (!processed(successor)) {
137 int blockCount = --blocked[successor.getId()];
138 assert blockCount >= 0;
139 if (blockCount == 0) {
140 worklist.add(successor);
141 }
142 }
143 }
144 }
145
146 /**
147 * @return The unprocessed predecessor with the highest probability, or {@code null}.
148 */
149 private AbstractBlockBase<?> selectNext(AbstractBlockBase<?> block) {
150 AbstractBlockBase<?> next = null;
151 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
152 if (!processed(successor) && (next == null || successor.probability() > next.probability())) {
153 next = successor;
154 }
155 }
156 return next;
157 }
158 }
|
48 /**
49 * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
50 * block}.
51 */
52 private final int[] blocked;
53 private final Trace[] blockToTrace;
54
55 private UniDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
56 processed = new BitSet(blocks.length);
57 worklist = new PriorityQueue<>(UniDirectionalTraceBuilder::compare);
58 assert (worklist != null);
59
60 blocked = new int[blocks.length];
61 blockToTrace = new Trace[blocks.length];
62 for (AbstractBlockBase<?> block : blocks) {
63 blocked[block.getId()] = block.getPredecessorCount();
64 }
65 }
66
67 private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
68 return Double.compare(b.getRelativeFrequency(), a.getRelativeFrequency());
69 }
70
71 private boolean processed(AbstractBlockBase<?> b) {
72 return processed.get(b.getId());
73 }
74
75 @SuppressWarnings("try")
76 private TraceBuilderResult build(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
77 try (Indent indent = debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
78 ArrayList<Trace> traces = buildTraces(debug, startBlock);
79 return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
80 }
81 }
82
83 protected ArrayList<Trace> buildTraces(DebugContext debug, AbstractBlockBase<?> startBlock) {
84 ArrayList<Trace> traces = new ArrayList<>();
85 // add start block
86 worklist.add(startBlock);
87 // process worklist
88 while (!worklist.isEmpty()) {
93 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
94 blockToTrace[traceBlock.getId()] = trace;
95 }
96 trace.setId(traces.size());
97 traces.add(trace);
98 }
99 }
100 return traces;
101 }
102
103 /**
104 * Build a new trace starting at {@code block}.
105 */
106 @SuppressWarnings("try")
107 private List<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> traceStart) {
108 assert checkPredecessorsProcessed(traceStart);
109 ArrayList<AbstractBlockBase<?>> trace = new ArrayList<>();
110 int blockNumber = 0;
111 try (Indent i = debug.logAndIndent("StartTrace: %s", traceStart)) {
112 for (AbstractBlockBase<?> block = traceStart; block != null; block = selectNext(block)) {
113 debug.log("add %s (freq: %f)", block, block.getRelativeFrequency());
114 processed.set(block.getId());
115 trace.add(block);
116 unblock(block);
117 block.setLinearScanNumber(blockNumber++);
118 }
119 }
120 return trace;
121 }
122
123 private boolean checkPredecessorsProcessed(AbstractBlockBase<?> block) {
124 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
125 assert processed(pred) : "Predecessor unscheduled: " + pred;
126 }
127 return true;
128 }
129
130 /**
131 * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
132 * the count reaches 0.
133 */
134 private void unblock(AbstractBlockBase<?> block) {
135 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
136 if (!processed(successor)) {
137 int blockCount = --blocked[successor.getId()];
138 assert blockCount >= 0;
139 if (blockCount == 0) {
140 worklist.add(successor);
141 }
142 }
143 }
144 }
145
146 /**
147 * @return The unprocessed predecessor with the highest probability, or {@code null}.
148 */
149 private AbstractBlockBase<?> selectNext(AbstractBlockBase<?> block) {
150 AbstractBlockBase<?> next = null;
151 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
152 if (!processed(successor) && (next == null || successor.getRelativeFrequency() > next.getRelativeFrequency())) {
153 next = successor;
154 }
155 }
156 return next;
157 }
158 }
|