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 }