InstructionCollector


1   /***
2    * InstructionCollector.java
3    *
4    * Description: Instruction buffer for the assembler
5    *
6    * Assembly consists of two passes, one to create the constant
7    * pool, and another to assemble the instructions to byte sequences.
8    * The InstructionBuffer holds instructions between these passes.
9    *
10   * The InstructionBuffer will be replaced by a FlowAnalyzer, which will
11   * perform basic-block analysis.  That's the main justification for
12   * keeping this class here, instead of adding a wrapper around
13   * Assembler the way peep-hole optimization is done.
14   *
15   * During the first pass (as instructions are collected), the buffer
16   * scans the instruction sequence for string arguments to PUSH
17   * instructions.  It computes an occurrence count for each string, and
18   * sorts the list of strings that occurred more than once by occurrence
19   * count.  The first 64K of these are placed in the constant pool.
20   * (The sort assures that PUSH can use one-byte indices for the most
21   * frequently-referenced strings.)
22   *
23   * During the second pass, each instruction is passed to the assembler,
24   * and the resulting bytecodes are appended to an accumulated bytecode
25   * sequence.
26   */
27  
28  /* J_LZ_COPYRIGHT_BEGIN *******************************************************
29  * Copyright 2001-2004 Laszlo Systems, Inc.  All Rights Reserved.              *
30  * Use is subject to license terms.                                            *
31  * J_LZ_COPYRIGHT_END *********************************************************/
32  
33  package org.openlaszlo.sc;
34  import java.io.*;
35  import java.nio.*;
36  import java.util.*;
37  import org.openlaszlo.sc.Instructions.*;
38  
39  public class InstructionCollector extends ArrayList {
40    public int nextLabel;
41    public ConstantCollector constantCollector;
42    public boolean constantsGenerated;
43  
44    public InstructionCollector(boolean disableConstantPool, boolean sortConstantPool) {
45      super();
46      this.nextLabel = 0;
47      if (! disableConstantPool) {
48        this.constantCollector = sortConstantPool ? new SortedConstantCollector() : new ConstantCollector();
49      } else {
50        this.constantCollector = null;
51      }
52      this.constantsGenerated = false;
53    }
54  
55    public void emit(Instruction instr) {
56      // Update the constant pool.
57      if (this.constantCollector != null && instr instanceof PUSHInstruction) {
58        PUSHInstruction push = (PUSHInstruction)instr;
59        for (Iterator i = push.args.iterator(); i.hasNext(); ) {
60          Object   next = i.next();
61          if (next instanceof String  ) {
62            this.constantCollector.add(next);
63          }
64        }
65      }
66      super.add(instr);
67    }
68  
69    public void push(Object   value) {
70      this.emit(Instructions.PUSH.__call__(value));
71    }
72  
73    public void generateConstants() {
74      // Only okay to call this once.
75      assert (! this.constantsGenerated);
76      ConstantCollector pool = this.constantCollector;
77      // TODO: [2003-07-15 ptw] (krank) turn off the constant pool
78      // for simplicity for now, but someday eliminate that
79      if (pool != null  && (! pool.isEmpty())) {
80        // TODO: [2003-03-06 ptw] Make CONSTANTS its own class?
81        super.add(0, Instructions.CONSTANTS.__call__(pool.getConstants()));
82        this.constantsGenerated = true;
83      }
84    }
85  
86    public void appendInstructions(Instruction[] instrs) {
87      // TODO [2003-03-06 ptw] Why not relabel all instructions? (I.e.,
88      // move this to emit)
89      Map labels = new HashMap();
90      for (int i = 0; i < instrs.length; i++) {
91        Instruction instr = instrs[i];
92        if (instr instanceof LABELInstruction) {
93          // Rename labels uniquely
94          Object   label = ((LABELInstruction)instr).name;
95          Object   newLabel;
96          if (labels.containsKey(label)) {
97            newLabel = labels.get(label);
98          } else {
99            newLabel = this.newLabel();
100           labels.put(label, newLabel);
101         }
102         instr = Instructions.LABEL.__call__(newLabel);
103       } else if (instr instanceof TargetInstruction) {
104         TargetInstruction target = (TargetInstruction)instr;
105         Object   label = target.getTarget();
106         Object   newLabel;
107         if (labels.containsKey(label)) {
108           newLabel = labels.get(label);
109         } else {
110           newLabel = this.newLabel();
111           labels.put(label, newLabel);
112         }
113         instr = target.replaceTarget(newLabel);
114       }
115       this.emit(instr);
116     }
117   }
118 
119   public List getInstructions(boolean generateConstants) {
120     if (! this.constantsGenerated && generateConstants) {
121       this.generateConstants();
122     }
123     return this;
124   }
125 
126   public String   newLabel() {
127     return "L" + this.nextLabel++;
128   }
129 
130   public static class ConstantCollector extends ArrayList {
131     public Object  [] getConstants() {
132       return this.toArray();
133     }
134   }
135 
136 
137   // Long way to go for a closure
138   public static class ConstantSorter implements Comparator {
139     public int compare(Object   o1, Object   o2) {
140       Map.Entry me1 = (Map.Entry)o1;
141       int n1 = ((Integer  )me1.getValue()).intValue();
142       Map.Entry me2 = (Map.Entry)o2;
143       int n2 = ((Integer  )me2.getValue()).intValue();
144       // Sort larger to the front (higher usage)
145       // Longer string wins in a tie
146       if (n1 == n2) {
147         int l1 = ((String  )me1.getKey()).length();
148         int l2 = ((String  )me2.getKey()).length();
149         return l2 - l1;
150       } else {
151         return n2 - n1;
152       }
153     }
154 
155     public boolean equals (Object   other) {
156       // Too specific?  Do we care?
157       return this == other;
158     }
159   }
160 
161   // There is probably some idiom for singletons that I don't know
162   private static ConstantSorter sorter = new ConstantSorter();
163 
164   // This is kind of like a sorted set, but delays the sorting until
165   // you ask for values from the set, and has a special limit on the
166   // number of values that can be in the set.
167   public static class SortedConstantCollector extends ConstantCollector {
168     public Map usageCount;
169     public boolean updated;
170 
171     SortedConstantCollector() {
172       super();
173       this.usageCount = new HashMap();
174       this.updated = false;
175     }
176 
177     public void add(int index, Object   value) {
178       this.updated = false;
179       if (this.usageCount.containsKey(value)) {
180         int n = ((Integer  )this.usageCount.get(value)).intValue();
181         this.usageCount.put(value, new Integer  (n + 1));
182       } else {
183         this.usageCount.put(value, new Integer  (1));
184       }
185     }
186 
187     public boolean add(Object   value) {
188       this.add(this.size(), value);
189       return true;
190     }
191 
192     public boolean addAll(int index, Collection c) {
193       for (Iterator i = c.iterator(); i.hasNext(); index++) {
194         this.add(index, i.next());
195       }
196       return true;
197     }
198 
199     public boolean addAll(Collection c) {
200       return this.addAll(this.size(), c);
201     }
202 
203     public void clear() {
204       this.updated = false;
205       this.usageCount.clear();
206       super.clear();
207     }
208 
209     public boolean contains(Object   value) {
210       // Should this return if value was ever added, or if value will
211       // be in the permitted subset?
212       return this.usageCount.containsKey(value);
213     }
214 
215     public int indexOf(Object   value) {
216       this.update();
217       return super.indexOf(value);
218     }
219 
220     public boolean isEmpty() {
221       return this.usageCount.size() == 0;
222     }
223 
224     public int lastIndexOf(Object   value) {
225       this.update();
226       return super.lastIndexOf(value);
227     }
228 
229     private Object   removeInternal(int index) {
230       this.updated = false;
231       Object   value = super.remove(index);
232       this.usageCount.remove(value);
233       return value;
234     }
235 
236     public Object   remove(int index) {
237       this.update();
238       return this.removeInternal(index);
239     }
240 
241     protected void removeRange(int fromIndex, int toIndex) {
242       this.update();
243       for (int i = fromIndex; i < toIndex; i++) {
244         this.removeInternal(i);
245       }
246     }
247 
248     public Object   set(int index, Object   value) {
249       this.update();
250       this.remove(index);
251       this.add(value);
252       return value;
253     }
254 
255     public Object  [] toArray() {
256       this.update();
257       return super.toArray();
258     }
259 
260     public Object  [] toArray(Object  [] array) {
261       this.update();
262       return super.toArray(array);
263     }
264 
265     public String   toString() {
266       this.update();
267       return super.toString();
268     }
269 
270     private void update() {
271       if (! this.updated) {
272         super.clear();
273         ArrayList sorted = new ArrayList();
274         for (Iterator i = this.usageCount.entrySet().iterator(); i.hasNext(); ) {
275           sorted.add(i.next());
276         }
277         Collections.sort(sorted, sorter);
278         // Total size of an action must be < 65535, opcode + length
279         // field is 3 bytes, also must account for encoding of strings
280         int room = 65535 - 3;
281         String   encoding = "UTF-8";
282         String   runtime = Instructions.getRuntime();
283         try {
284           for (Iterator i = sorted.iterator(); i.hasNext(); ) {
285             String   symbol = (String  )((Map.Entry)i.next()).getKey();
286             room -= (symbol.getBytes(encoding).length + 1);
287             if (room <= 0) break;
288             super.add(symbol);
289           }
290         } catch (UnsupportedEncodingException e) {
291           assert false : "this can't happen";
292         }
293         this.updated = true;
294       }
295     }
296 
297     public Object  [] getConstants() {
298       return this.toArray();
299     }
300   }
301 }
302
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags