001    /* Copyright (c) 2011, Jesper Öqvist <jesper.oqvist@cs.lth.se>
002     * All rights reserved.
003     *
004     * Redistribution and use in source and binary forms, with or without
005     * modification, are permitted provided that the following conditions are met:
006     *
007     * 1. Redistributions of source code must retain the above copyright notice,
008     * this list of conditions and the following disclaimer.
009     *
010     * 2. Redistributions in binary form must reproduce the above copyright notice,
011     * this list of conditions and the following disclaimer in the documentation
012     * and/or other materials provided with the distribution.
013     *
014     * 3. Neither the name of the copyright holder nor the names of its
015     * contributors may be used to endorse or promote products derived from this
016     * software without specific prior written permission.
017     *
018     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019     * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021     * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
022     * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023     * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024     * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025     * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026     * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027     * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
028     * POSSIBILITY OF SUCH DAMAGE.
029     */
030    
031    /**
032     * <p>This aspect adds the Project Coin/JSR 334 Strings in Switch language
033     * change to the ExtendJ backend.
034     *
035     * <p>The following features were modified:
036     * <ul>
037     * <li>code generation for switch statement</li>
038     * </ul>
039     */
040    aspect StringsInSwitch {
041    
042      syn boolean SwitchStmt.isSwitchWithString() = getExpr().type().isString();
043    
044      // inherit equation for typeString
045      inh TypeDecl SwitchStmt.typeString();
046    
047      /**
048       * We two extra locals for switch for switch with string!
049       */
050      eq SwitchStmt.getChild().localNum() =
051          localNum() + typeInt().variableSize() + typeString().variableSize();
052    
053      /**
054       * Local index for the first switch variable.
055       */
056      syn int SwitchStmt.localNumA() = localNum();
057    
058      /**
059       * Local index for the second switch variable.
060       */
061      syn int SwitchStmt.localNumB() = localNum() + typeInt().variableSize();
062    
063      /**
064       * Group multiple case labels as one.
065       */
066      class CaseGroup {
067        int lbl;
068        int hashCode;
069        java.util.List<CaseLbl> lbls = new LinkedList<CaseLbl>();
070    
071        public CaseGroup(SwitchStmt ss, int hash) {
072          lbl = ss.hostType().constantPool().newLabel();
073          hashCode = hash;
074        }
075    
076        public void addCase(CaseLbl lbl) {
077          lbls.add(lbl);
078        }
079      }
080    
081      /**
082       * Handles code generation for individual case labels.
083       */
084      class CaseLbl {
085        int lbl;
086        int serial;
087        String value;
088        java.util.List<Stmt> stmts = new ArrayList<Stmt>();
089    
090        CaseLbl(int lbl) {
091          this.lbl = lbl;
092        }
093    
094        CaseLbl(ConstCase cc, CodeGeneration gen) {
095          lbl = cc.label();
096          value = cc.getValue().constant().stringValue();
097        }
098    
099        void addStmt(Stmt stmt) {
100          stmts.add(stmt);
101        }
102    
103        /**
104         * Code generation for case label.
105         */
106        void createBCode(CodeGeneration gen) {
107          for (Stmt stmt : stmts) {
108            stmt.createBCode(gen);
109          }
110        }
111      }
112    
113      /**
114       * Utility method to compute offsets between labels.
115       */
116      syn int SwitchStmt.labelOffset(CodeGeneration gen, int lbl1, int lbl2) =
117          gen.addressOf(lbl1) - gen.addressOf(lbl2);
118    
119      /**
120       * Two switch statements are generated.
121       * The first switch will switch on the hash code of the switch expression.
122       * The first switch statement computes a value for a variable that selects
123       * a case in the second switch statement.
124       *
125       */
126      refine AutoBoxingCodegen
127        public void SwitchStmt.createBCode(CodeGeneration gen) {
128        if (getExpr().type().isString()) {
129          // add line number for start of statement
130          super.createBCode(gen);
131    
132          // Enumerate case labels with same hash value
133          TreeMap< Integer, CaseGroup > groups = new TreeMap< Integer, CaseGroup >();
134          java.util.List<CaseLbl> labels = new LinkedList<CaseLbl>();
135    
136          CaseLbl defaultLbl = null;
137          CaseLbl caseLbl = null;
138          int serial = 1;
139          for (Stmt stmt : getBlock().getStmts()) {
140            if (stmt instanceof ConstCase) {
141              ConstCase cc = (ConstCase) stmt;
142              caseLbl = new CaseLbl(cc, gen);
143              caseLbl.serial = serial++;
144              labels.add(caseLbl);
145              int key = caseLbl.value.hashCode();
146              if (groups.containsKey(key)) {
147                groups.get(key).addCase(caseLbl);
148              } else {
149                CaseGroup group = new CaseGroup(this, key);
150                group.addCase(caseLbl);
151                groups.put(key, group);
152              }
153            } else if (stmt instanceof DefaultCase) {
154              defaultLbl = new CaseLbl(hostType().constantPool().newLabel());
155              caseLbl = defaultLbl;
156            } else if (caseLbl != null) {
157              caseLbl.addStmt(stmt);
158            }
159          }
160    
161          int index_a = localNumA();
162          genFirstSwitch(gen, groups, index_a);
163          genSecondSwitch(gen, labels, index_a, defaultLbl);
164    
165        } else {
166          refined(gen);
167        }
168      }
169    
170      private void SwitchStmt.genFirstSwitch(
171          CodeGeneration gen,
172          TreeMap<Integer, CaseGroup> groups,
173          int index_a) {
174        int switch_label = gen.constantPool().newLabel();
175        int end_label1 = gen.constantPool().newLabel();
176        int index_b = localNumB();
177    
178        // Initialize switch variable for second switch
179        IntegerLiteral.push(gen, 0);
180        typeInt().emitStoreLocal(gen, index_a);
181    
182        // Store the value of the switch expr so that it is only evaluated once!
183        getExpr().createBCode(gen);
184    
185        // Push the hash code for the switch instruction
186        if (getExpr().isConstant()) {
187          typeString().emitStoreLocal(gen, index_b);
188    
189          int hashCode = getExpr().constant().stringValue().hashCode();
190          IntegerLiteral.push(gen, hashCode);
191        } else {
192          typeString().emitDup(gen);
193          typeString().emitStoreLocal(gen, index_b);
194          hashCodeMethod().emitInvokeMethod(gen,
195              lookupType("java.lang", "Object"));
196        }
197    
198        // Emit switch instruction
199        int low = groups.isEmpty() ? 0 : groups.firstKey();
200        int high = groups.isEmpty() ? 0 : groups.lastKey();
201    
202        int tableSwitchSize = 4 * (3 + (high - low + 1));
203        int lookupSwitchSize = 4 * (2 + 2 * groups.size());
204        int pad;
205        int switchSize;
206        int switchPos;
207        boolean tableSwitch = tableSwitchSize < lookupSwitchSize;
208    
209        gen.addLabel(switch_label);
210    
211        // Select the switch type which produces the smallest switch instr.
212        if (tableSwitch) {
213          // TABLESWITCH
214          gen.emit(Bytecode.TABLESWITCH);
215          switchSize = tableSwitchSize;
216        } else {
217          // LOOKUPSWITCH
218          gen.emit(Bytecode.LOOKUPSWITCH);
219          switchSize = lookupSwitchSize;
220        }
221    
222        pad = emitPad(gen);
223        switchPos = gen.pos();
224    
225        // leave room for the address table
226        gen.skip(switchSize);
227    
228        // Code generation for switch body
229        for (CaseGroup group : groups.values()) {
230          gen.addLabel(group.lbl);
231    
232          // Possible hash miss. Check for equality.
233          Iterator<CaseLbl> iter = group.lbls.iterator();
234          while (iter.hasNext()) {
235            CaseLbl lbl = iter.next();
236            int thenLbl;
237            if (iter.hasNext()) {
238              thenLbl = gen.constantPool().newLabel();
239            } else
240              // last conditional branches to end label
241              thenLbl = end_label1;
242    
243            typeString().emitLoadLocal(gen, index_b);
244            StringLiteral.push(gen, lbl.value);
245            equalsMethod().emitInvokeMethod(gen,
246                lookupType("java.lang", "Object"));
247            gen.emitCompare(Bytecode.IFEQ, thenLbl);
248            IntegerLiteral.push(gen, lbl.serial);
249            typeInt().emitStoreLocal(gen, index_a);
250            gen.emitGoto(end_label1);
251    
252            if (iter.hasNext()) {
253              gen.addLabel(thenLbl);
254            }
255          }
256        }
257    
258        // write jump address table
259        int endpos = gen.pos();
260        gen.setPos(switchPos);
261        if (tableSwitch) {
262          int defaultOffset = 1 + pad + switchSize;
263          gen.add4(defaultOffset);
264          gen.add4(low);
265          gen.add4(high);
266          for (int i = low; i <= high; i++) {
267            if (groups.containsKey(i)) {
268              CaseGroup group = groups.get(i);
269              int offset = labelOffset(gen, group.lbl, switch_label);
270              gen.add4(offset);
271            } else {
272              gen.add4(defaultOffset);
273            }
274          }
275        } else {
276          int defaultOffset = 1 + pad + switchSize;
277          gen.add4(defaultOffset);
278          gen.add4(groups.size());
279          for (CaseGroup group : groups.values()) {
280            gen.add4(group.hashCode);
281            int offset = labelOffset(gen, group.lbl, switch_label);
282            gen.add4(offset);
283          }
284        }
285        gen.setPos(endpos);
286    
287        gen.addLabel(end_label1);
288      }
289    
290      private void SwitchStmt.genSecondSwitch(
291          CodeGeneration gen,
292          java.util.List<CaseLbl> labels,
293          int index_a,
294          CaseLbl defaultLbl) {
295        int switch_label = gen.constantPool().newLabel();
296        int default_label = gen.constantPool().newLabel();
297    
298        // push the switch variable
299        typeInt().emitLoadLocal(gen, index_a);
300    
301        // Emit switch instruction
302        gen.addLabel(switch_label);
303        gen.emit(Bytecode.TABLESWITCH);
304        int high = labels.size();
305        int low = 0;
306        int pad;
307        int switchSize = 4 * (3 + (high - low + 1));
308        int switchPos;
309    
310        pad = emitPad(gen);
311        switchPos = gen.pos();
312        gen.skip(switchSize);
313    
314        // Code generation for case labels
315    
316        for (CaseLbl lbl : labels) {
317          gen.addLabel(lbl.lbl);
318          lbl.createBCode(gen);
319        }
320    
321        gen.addLabel(default_label);
322        if (defaultLbl != null) {
323          defaultLbl.createBCode(gen);
324        }
325    
326        int endpos = gen.pos();
327        gen.setPos(switchPos);
328        int defaultOffset = 1 + pad + switchSize;
329        gen.add4(defaultOffset);
330        gen.add4(low);
331        gen.add4(high);
332        int offset = labelOffset(gen, default_label, switch_label);
333        gen.add4(offset);
334        for (CaseLbl lbl : labels) {
335          offset = labelOffset(gen, lbl.lbl, switch_label);
336          gen.add4(offset);
337        }
338        gen.setPos(endpos);
339    
340        gen.addLabel(end_label());
341      }
342    
343      /**
344       * Generate invocation of method
345       * {@code java.lang.Object.hashCode()}.
346       */
347      private MethodDecl SwitchStmt.hashCodeMethod() {
348        TypeDecl objectType = lookupType("java.lang", "Object");
349        if (objectType.isUnknown()) {
350          throw new Error("Could not find java.lang.Object");
351        }
352        for (MethodDecl method :
353            (Collection<MethodDecl>) objectType.memberMethods("hashCode")) {
354          if (method.getNumParameter() == 0) {
355            return method;
356          }
357        }
358        throw new Error("Could not find java.lang.Object.hashCode()");
359      }
360    
361      /**
362       * Generate invocation of method
363       * {@code java.lang.Object.equals(java.lang.Object)}.
364       */
365      private MethodDecl SwitchStmt.equalsMethod() {
366        TypeDecl objectType = lookupType("java.lang", "Object");
367        if (objectType.isUnknown()) {
368          throw new Error("Could not find java.lang.Object");
369        }
370        for (MethodDecl method :
371            (Collection<MethodDecl>) objectType.memberMethods("equals")) {
372          if (method.getNumParameter() == 1 &&
373              method.getParameter(0).getTypeAccess().type() == objectType)
374            return method;
375        }
376        throw new Error("Could not find java.lang.Object.equals()");
377      }
378    }