/* * * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * */ package adobe.abc; import java.io.*; // Note: java.util imports must be explicitly called out because // "import java.util.*" conflicts with adobe.abc.Algorithms.Deque import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; import java.util.Collection; import java.util.Comparator; import java.util.Date; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import java.util.Vector; import macromedia.asc.embedding.ConfigVar; import macromedia.asc.util.ObjectList; import static macromedia.asc.embedding.avmplus.ActionBlockConstants.*; import static adobe.abc.Algorithms.*; import static adobe.abc.OptimizerConstants.*; import static adobe.abc.TypeAnalysis.*; import static java.lang.Boolean.TRUE; import static java.lang.Boolean.FALSE; /* * TODO * * (done) merge phi nodes * (done) pretty print dags * (done) scope capture * (done) type tracking * (done) constness * (done) null tracking * (done) emitter * (done) convert lvn into dominator based dvn * (done) sort cpool entries by frequency of use * (done) eliminate unused cpool entries * (done) split dag nodes to tree nodes * (done) recalc local_count * (done) recalc max_stack * (done) recalc scope_depth * (done) allow nonempty stack between blocks - stk_sched2 * (done) give every slot a default value even if not from abc (vm-defined defaults) * (done) model exception edges, remove PURE * (done) flesh out branch simplifications in sccp * (done) respect try/catch regions * (done) don't assign local to OP_arg in catch. use arg & xarg * (done) if N handlers specify the same catch block, ensure phi's merge args correctly. * (done) strip unnecessary slot default values on export * (done) preserve metadata * (done) expand getlex to expose redundant findproperty * (done) add null-ness to sccp lattice, remove NOTNULL flag * (done) handle lt/gt correctly for strings * (done) hasnext2 codegen * (done) combine findpropstrict+getproperty into getlex when find's only use is get in same block. * (done) normalize inc/declocal/_i into inc/decrement/_i * * force stkout contents for xarg blocks rather than clearing stack at xarg definition. * don't allow xarg block to be combined with other blocks. * handle OP_equals for all const types * istype optimizations * model external data dependencies, remove EFFECT * treat pushwith & pushscope appropriately in findprop * expand implicit conversions to expose them to optimizations * fold implicit conversions to reduce code size * use locals for activation slots that dont escape (need array ssa?) * algebraic identities * combine sccp values & types into single lattice * add final-ness to Typeref * interprocedural analysis to determine effect of functions * check (prove?) correctness of SKIPTEST * insert kills & coerces to appease AVM verifier * add a no-catch edge to an EXIT block for any block with a PX expr. * if we have catch blocks, any PX should end its block. (FCFG notation is premature) * preds should include all edges, not just normal edges * script loading dependencies. remove EFFECT from findprop/finddef if script is already loaded. * convert chain of ifstricne into switch if ints are dense * write a verifier (easier than testing with actual avm) * merge scripts based on init dependencies. * in scheduler, propagate live & stk across exception edges * get smarter about removing phi(coerce) without losing verifiability * scope stack scheduling * turn add into increment/_i when possible * turn increment/decrement/_i into inc/declocal/_i if in/out assigned to same local in sched. * inline method if target is known and body is smaller than call (eg isNaN, trivial getters) * * TODO algorithms * * partial redundancy elimination * alias analysis * tail merging * loop inversion * remove redundant path expressions * * TODO file format changes * * remove/shorten version number * short branch offsets * optional init methods * every reference is a relative offset (eliminate lookup tables) * remove empty activation traits * optional trait names * OP_add_d * OP_concat */ /** * @author Edwin Smith */ public class GlobalOptimizer { // default configuration flags final boolean USE_CALLMETHOD = false; final boolean SHOW_CODE = true; final boolean SHOW_DOMINATORS=false; // Configuration flags settable by options boolean OUTPUT_DOT = false; boolean SHOW_DFG = false; boolean STRIP_DEBUG_INFO = true; boolean ALLOW_NATIVE_CTORS = false; boolean PRESERVE_METHOD_NAMES = false; boolean verbose_mode=false; boolean legacy_verifier=false; // TODO: Needs more work to get right -- // reading everything in-line means we're // never really sure if something's an // import or not b/c $GLOBALABC is processed // as a target in its own right during // the tamarin build. // Have to organize the files list ahead // of the read phase, would also help // integration with the ASC entry point. boolean reading_imports = true; /** * The number of input files being linked together. * @warn used to work around some linking bugs. */ int num_linked_files = 0; static TraceManager tm = new TraceManager(); public static void main(String[] args) throws IOException { GlobalOptimizer go = new GlobalOptimizer(); List a = new ArrayList(); List lengths = new ArrayList(); String filename = null; byte[] before = null; // Index of first export in the file list. int first_exported_file = 0; boolean obscure_natives = false; boolean no_c_gen = false; boolean quiet_mode = false; for (int i = 0; i < args.length; ++i) { if(args[i].equals("-obscure_natives")) { obscure_natives = true; continue; } if(args[i].equals("-no_c_gen")) { no_c_gen = true; continue; } if(args[i].equals("-d")) { go.STRIP_DEBUG_INFO=false; continue; } if(args[i].equals("-verbose")) { go.verbose_mode = true; quiet_mode = false; continue; } if ( args[i].equals("-quiet")) { quiet_mode = true; go.verbose_mode = false; continue; } if ( args[i].equals("-legacy_verifier")) { go.legacy_verifier = !go.legacy_verifier; addTraceAttr("legacy_verifier", go.legacy_verifier); go.verboseStatus("legacy_verifier set to " + go.legacy_verifier); continue; } if ( args[i].equals("-allow_native_ctors")) { go.ALLOW_NATIVE_CTORS = true; continue; } if ( args[i].equals("-trace") && i+1 < args.length ) { i++; tm.enable(new PrintWriter(new FileWriter(args[i]))); addTraceAttr("timestamp", new Date()); continue; } if ( args[i].equals("-dot") ) { go.OUTPUT_DOT = true; continue; } if ( args[i].equals("-dfg")) { go.SHOW_DFG = go.OUTPUT_DOT = true; continue; } if ( args[i].equals("-preserve_method_names")) { go.PRESERVE_METHOD_NAMES = true; continue; } if ( args[i].equals("-plugin") && i+1 < args.length) { i++; go.loadPlugin(args[i]); continue; } if ( args[i].startsWith("-") && args[i].contains(":")) { int delim_pos = args[i].indexOf(':'); String plugin_name = args[i].substring(1, delim_pos); String plugin_option = args[i].substring(delim_pos+1); PluginData plugin_data = go.analysis_phase_plugins.get(plugin_name); if ( null == plugin_data ) { // Iterate over the plugins and find a short // name that matches this monster. for ( PluginData search_plugin: go.analysis_phase_plugins.values() ) { if ( search_plugin.plugin.getClass().getSimpleName().equals(plugin_name)) { plugin_data = search_plugin; break; } } } if ( null != plugin_data ) { plugin_data.options.add(plugin_option); } else { throw new IllegalArgumentException("No plugin named " + plugin_name + " is loaded."); } continue; } if(args[i].equals("--")) { go.reading_imports = false; first_exported_file = a.size(); continue; } filename = args[i]; addTraceAttr("filename", filename); InputAbc ia = go.new InputAbc(); lengths.add(ia.readAbc(filename)); a.add(ia); if(obscure_natives) { ia.obscure_natives(); obscure_natives = false; } } if ( 0 == args.length || first_exported_file >= a.size() ) { System.err.println("usage: GlobalOptimizer [-obscure_natives] [-no_c_gen] [-verbose] [-quiet] [imports] -- [exports]"); return; } go.initializePlugins(); // merge exports together // TODO this is not right, it only works for builtin ABCs and only under TT... // we really need to construct a new script (that calls all the scripts in the initScripts list) // and append it to the end as the new initscript. List initScripts = new ArrayList(); InputAbc first = a.get(first_exported_file); int before_length = lengths.get(first_exported_file); initScripts.add(first.scripts.length - 1); // Combine other exported files. for(int i=first_exported_file+1; i < a.size(); i++) { first.combine(a.get(i)); initScripts.add(first.scripts.length - 1); before_length += lengths.get(i); go.num_linked_files++; } // Optimize the combined ABC file and emit. byte[] after = null; go.optimize(first); after = go.emit(first, filename, initScripts, no_c_gen); // Print summary statistics. if ( ! quiet_mode ) { System.out.println(); System.out.println("Before optimization: "+before_length); System.out.println("After optimization: "+after.length); int delta = before_length - after.length; long percent = Math.round(delta/(double)before_length*100); System.out.println("Difference: "+delta+ " "+percent+"%"); } } static byte[] load(String filename) throws IOException { InputStream in = new FileInputStream(filename); try { byte[] before = new byte[in.available()]; in.read(before); return before; } finally { in.close(); } } class PluginData { OptimizerPlugin plugin; Vector options; PluginData(OptimizerPlugin plugin) { this.plugin = plugin; this.options = new Vector(); } } private Map analysis_phase_plugins = new HashMap(); private void loadPlugin(String plugin_class_fqn) { try { Class clazz = Class.forName(plugin_class_fqn); OptimizerPlugin plugin = (OptimizerPlugin)clazz.newInstance(); analysis_phase_plugins.put(plugin_class_fqn, new PluginData(plugin)); } catch ( Throwable plugin_trouble) { System.err.println("Unable to initialize plugin " + plugin_class_fqn + " due to: " + plugin_trouble); } } private void initializePlugins() { for ( String plugin_name: analysis_phase_plugins.keySet()) { PluginData p = analysis_phase_plugins.get(plugin_name); p.plugin.initializePlugin(this, p.options); } } private void runPlugins() { } public class InputAbc { String strings[]; int ints[]; long uints[]; double doubles[]; Namespace namespaces[]; Nsset nssets[]; Name names[]; Method methods[]; Metadata metadata[]; Type classes[]; Type scripts[]; boolean containsObject = false; Set toResolve; List mergedAbcs = new ArrayList(); public String src_filename; InputAbc() { mergedAbcs.add(this); } Type lookup(int id) { if (0 == id) return ANY(); else return TypeCache.instance().lookup(names[id], OBJECT()); } int readAbc(String src_file) throws IOException { byte[] file_buffer = load(src_file); readAbc(file_buffer); return file_buffer.length; } void readAbc(byte[] abc) throws IOException { Reader p = new Reader(0, abc); if (p.readU16() != 16 || p.readU16() != 46) throw new RuntimeException("not an abc file"); ints = new int[p.readU30() + 1]; for (int i = 1, n = ints.length - 1; i < n; i++) ints[i] = p.readU30(); uints = new long[p.readU30() + 1]; for (int i = 1, n = uints.length - 1; i < n; i++) uints[i] = 0xffffffffL & p.readU30(); doubles = new double[p.readU30() + 1]; for (int i = 1, n = doubles.length - 1; i < n; i++) doubles[i] = p.readDouble(); strings = new String[p.readU30() + 1]; strings[0] = ""; for (int i = 1, n = strings.length - 1; i < n; i++) { int len = p.readU30(); strings[i] = new String(abc, p.pos, len, "UTF-8"); p.pos += len; } namespaces = new Namespace[p.readU30() + 1]; // TODO this should be AnyNamespace, not PUBLIC namespaces[0] = Name.PUBLIC; for (int i = 1, n = namespaces.length - 1; i < n; i++) namespaces[i] = new Namespace(p.readU8(), strings[p.readU30()]); nssets = new Nsset[p.readU30() + 1]; for (int i = 1, n = nssets.length-1; i < n; i++) { nssets[i] = new Nsset(new Namespace[p.readU30()]); for (int j = 0, m = nssets[i].length; j < m; j++) nssets[i].nsset[j] = namespaces[p.readU30()]; // ns_index } names = new Name[p.readU30() + 1]; for (int i = 1, n = names.length-1; i < n; i++) { names[i] = readName(p); } methods = new Method[p.readU30()]; int[] methodpos = new int[methods.length]; for (int i = 0, n = methods.length; i < n; i++) methods[i] = readMethod(p, methodpos, i); metadata = new Metadata[p.readU30()]; for (int i = 0, n = metadata.length; i < n; i++) metadata[i] = readMetadata(p); toResolve = new HashSet(); Type[] instances = new Type[p.readU30()]; for (int i = 0, n = instances.length; i < n; i++) instances[i] = readInstance(p); if ( containsObject ) TypeCache.instance().setupBuiltins(); // finish resolving methods using mp we saved earlier for (int i=0, n = methods.length; i < n; i++) resolveSignatureType(new Reader(methodpos[i], p.abc), i, methods[i]); classes = new Type[instances.length]; for (int i = 0, n = classes.length; i < n; i++) classes[i] = readClass(p, instances[i]); scripts = new Type[p.readU30()]; for (int i = 0, n = scripts.length; i < n; i++) scripts[i] = readScript(p, i); for (int i = 0, n = p.readU30(); i < n; i++) readBody(p); // lazy resolve slot type names for (Type t: toResolve) resolveType(t); toResolve = null; } void obscure_natives() { for(Type t: classes) { t.obscure_natives = true; if (t.itype != null) t.itype.obscure_natives = true; } for(Type t: scripts) { t.obscure_natives = true; if (t.itype != null) t.itype.obscure_natives = true; } } void combine(InputAbc abc) { int[] newInts = new int[ints.length + abc.ints.length]; System.arraycopy(ints, 0, newInts, 0, ints.length); System.arraycopy(abc.ints, 0, newInts, ints.length, abc.ints.length); ints = newInts; long[] newUints = new long[uints.length + abc.uints.length]; System.arraycopy(uints, 0, newUints, 0, uints.length); System.arraycopy(abc.uints, 0, newUints, uints.length, abc.uints.length); uints = newUints; double[] newDoubles = new double[doubles.length + abc.doubles.length]; System.arraycopy(doubles, 0, newDoubles, 0, doubles.length); System.arraycopy(abc.doubles, 0, newDoubles, doubles.length, abc.doubles.length); doubles = newDoubles; String[] newStrings = new String[strings.length + abc.strings.length]; System.arraycopy(strings, 0, newStrings, 0, strings.length); System.arraycopy(abc.strings, 0, newStrings, strings.length, abc.strings.length); strings = newStrings; Namespace[] newNamespaces = new Namespace[namespaces.length + abc.namespaces.length]; System.arraycopy(namespaces, 0, newNamespaces, 0, namespaces.length); System.arraycopy(abc.namespaces, 0, newNamespaces, namespaces.length, abc.namespaces.length); namespaces = newNamespaces; Nsset[] newNssets = new Nsset[nssets.length + abc.nssets.length]; System.arraycopy(nssets, 0, newNssets, 0, nssets.length); System.arraycopy(abc.nssets, 0, newNssets, nssets.length, abc.nssets.length); nssets = newNssets; Name[] newNames = new Name[names.length + abc.names.length]; System.arraycopy(names, 0, newNames, 0, names.length); System.arraycopy(abc.names, 0, newNames, names.length, abc.names.length); names = newNames; Method[] newMethods = new Method[methods.length + abc.methods.length]; System.arraycopy(methods, 0, newMethods, 0, methods.length); System.arraycopy(abc.methods, 0, newMethods, methods.length, abc.methods.length); methods = newMethods; // we change the .abc property for Methods but not Bindings, canEarlyBind* // deals with this by checking that Binding.abc is in the Method.abc.mergedAbcs set for(Method m: abc.methods) { m.abc = this; } Metadata[] newMetadata = new Metadata[metadata.length + abc.metadata.length]; System.arraycopy(metadata, 0, newMetadata, 0, metadata.length); System.arraycopy(abc.metadata, 0, newMetadata, metadata.length, abc.metadata.length); metadata = newMetadata; Type[] newClasses = new Type[classes.length + abc.classes.length]; System.arraycopy(classes, 0, newClasses, 0, classes.length); System.arraycopy(abc.classes, 0, newClasses, classes.length, abc.classes.length); classes = newClasses; Type[] newScripts = new Type[scripts.length + abc.scripts.length]; System.arraycopy(scripts, 0, newScripts, 0, scripts.length); System.arraycopy(abc.scripts, 0, newScripts, scripts.length, abc.scripts.length); scripts = newScripts; mergedAbcs.add(abc); } void resolveType(Type t) { if (t.size != 0) return; int size = 0; if (t.base != null) { resolveType(t.base); size = t.base.size; } int hole = -1; for (Binding b: t.defs.values()) { if (isSlot(b)) { if (!isClass(b)) resolveSlotType(b); // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // // the logic here is replicated in QVM and GlobalOptimizer.java and is assumed by the slot offsets // that it generates for native classes. If you change this here you must also change it there. // // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // NOTE NOTE NOTE NOTE NOTE // // @todo, this generates slots that are correct for 32-bit but not 64 bit builds // if (b.type.t == NUMBER()) { if (size%8 != 0) { hole = size; size += 4; } b.offset = size; size += 8; } else { if (hole != -1) { b.offset = hole; hole = -1; } else { b.offset = size; size += 4; } } } } if (size > 0) verboseStatus("sizeof "+t+" "+size); t.size = size; } Metadata readMetadata(Reader p) { Metadata md = new Metadata(); md.name = strings[p.readU30()]; Attr[] attrs = md.attrs = new Attr[p.readU30()]; for (int j = 0, n=attrs.length; j < n; j++) attrs[j] = new Attr(strings[p.readU30()]); for (int j = 0, n=attrs.length; j < n; j++) attrs[j].value = strings[p.readU30()]; return md; } void resolveSignatureType(Reader p, int i, Method m) { m.returns = lookup(p.readU30()).ref; // return type // Parameter types must be nullable // to satisfy the AVM verifier. for (int j = 1; j < m.getParams().length; j++) { int idx = p.readU30(); Type ptype = lookup(idx); assert(ptype != null); m.getParams()[j] = ptype.ref.nullable(); } p.readU30(); // debug name p.readU8(); // flags if (m.hasOptional()) { m.optional_count = p.readU30(); m.values = new Object[m.getParams().length]; int first_optional_param = m.getParams().length - m.optional_count; for (int j = first_optional_param; j < m.getParams().length; j++) { m.values[j] = readArgDefault(p); assert(m.values[j] != null); } } } void readBody(Reader p) { Method m = methods[p.readU30()]; addTraceAttr("method", m); m.max_stack = p.readU30(); m.local_count = p.readU30(); m.max_scope = -(p.readU30()-p.readU30()); m.code_len = p.readU30(); Reader pcode = new Reader(p); p.pos += m.code_len; readCode(m, pcode, p); Type act = new Type(); m.activation = act.ref.nonnull(); act.base = ANY(); if (m.getName() != null) act.name = (m.getName().append(" activation")); readTraits(p, act); } Method readMethod(Reader p, int[] methodpos, int i) { Method m = new Method(i, this); int param_count = p.readU30(); m.params = new Typeref[param_count+1]; m.getParams()[0] = ANY().ref; methodpos[i] = p.pos; p.readU30(); // return type for (int j = 1; j <= param_count; j++) p.readU30(); // param type // debugName is specified as a bare index into the string pool. m.debugName = strings[p.readU30()]; m.name = new Name(m.debugName); m.flags = p.readU8(); if (m.hasOptional()) { // Skip past optional parameters; they're re-read // and recorded in resolveSignatureType(). int optional_count = p.readU30(); assert(optional_count > 0); for (int j = 0; j < optional_count; j++) { readArgDefault(p); } } if (m.hasParamNames()) { m.paramNames = new Name[param_count+1]; for (int j = 1; j <= param_count; j++) m.paramNames[j] = new Name(strings[p.readU30()]); } return m; } Name readName(Reader p) { int kind = p.readU8(); switch (kind) { default: throw new RuntimeException("Unknown name kind: "+kind); case CONSTANT_TypeName: { int index = p.readU30(); // Index to the Multiname type, i.e. Vector int count = p.readU30(); // number of type parameter names assert(count == 1); // all we support for now int typeparm = p.readU30(); // Multinames for the type parameters, i.e. String for a Vector. Name mn = this.names[index]; Name type_param = this.names[typeparm]; return new Name(kind, mn.name, mn.nsset, type_param.name); } case CONSTANT_Qname: case CONSTANT_QnameA: return new Name(kind, namespaces[p.readU30()], strings[p.readU30()]); case CONSTANT_Multiname: case CONSTANT_MultinameA: return new Name(kind, strings[p.readU30()], nssets[p.readU30()]); case CONSTANT_RTQname: case CONSTANT_RTQnameA: return new Name(kind, uniqueNs(), strings[p.readU30()]); case CONSTANT_MultinameL: case CONSTANT_MultinameLA: return new Name(kind, unique(), nssets[p.readU30()]); case CONSTANT_RTQnameL: case CONSTANT_RTQnameLA: return new Name(kind); } } void readTraits(Reader p, Type t) { toResolve.add(t); t.defs = new Symtab(); // Start counting slots either from // the base type's last-used slot // or from zero if there's no base. int slot_id = (t.base != null)? t.base.slotCount: 0; // Slots used by this type. int count = p.readU30(); for (int i = 0; i < count; i++) { Name name = names[p.readU30()]; Binding b = new Binding(p.readU8(), name, this); Binding old = t.defs.get(name); while (old != null && old.peer != null) old = old.peer; if (old != null) old.peer = b; t.defs.put(name, b); int slot = p.readU30(); // slot_id | disp_id b.id = p.readU30(); // typename | class_id | method_id switch (b.kind()) { case TRAIT_Var: case TRAIT_Const: case TRAIT_Class: if (isClass(b)) { // TODO this is a bit tenuous b.type = classes[b.id].ref.nonnull(); b.value = NULL(); } else { b.value = readSlotDefault(p); b.type = ANY().ref; if (b.value instanceof Namespace) TypeCache.instance().namespaceNames.put((Namespace)b.value, name); } // TODO add vm's logic to accept or ignore compiler-assigned slot_id if (slot == 0) slot = ++slot_id; else if (slot > slot_id) slot_id = slot; b.slot = slot; break; case TRAIT_Method: case TRAIT_Getter: case TRAIT_Setter: b.slot = 0; Method m = b.method = methods[b.id]; m.cx = t; m.getParams()[0] = t.ref.nonnull(); m.kind = isMethod(b) ? "function" : isGetter(b) ? "get" : "set"; m.name = name; // ignore compiler-assigned disp_id's // if (!slot) slot = ++disp_id; // else if (slot > disp_id) disp_id = slot; break; default: System.err.println("illegal trait kind " + b.kind() + " at offset " + p.pos); assert (false); } if (b.hasMetadata()) { b.md = new Metadata[p.readU30()]; for (int j=0, m=b.md.length; j < m; j++) b.md[j] = metadata[p.readU30()]; } } t.slotCount = slot_id; } Object readSlotDefault(Reader p) { int i = p.readU30(); if (i != 0) { int kind = p.readU8(); return defaultValue(kind,i); } return null; } Object readArgDefault(Reader p) { int i = p.readU30(); int kind = p.readU8(); Object v = defaultValue(kind, i); return v; } Object defaultValue(int kind, int i) { switch (kind) { case CONSTANT_False: return FALSE; case CONSTANT_True: return TRUE; case CONSTANT_Null: return NULL(); case CONSTANT_Void: return UNDEFINED; case CONSTANT_Utf8: return strings[i]; case CONSTANT_Integer: return ints[i]; case CONSTANT_UInteger: return uints[i]; case CONSTANT_Double: return doubles[i]; case CONSTANT_Namespace: case CONSTANT_PackageNamespace: case CONSTANT_ProtectedNamespace: case CONSTANT_PackageInternalNs: case CONSTANT_ExplicitNamespace: case CONSTANT_StaticProtectedNs: case CONSTANT_PrivateNamespace: return namespaces[i]; } assert(false); return null; } void resolveSlotType(Binding b) { b.type = lookup(b.id).ref; if (b.value == null) b.value = b.type.t.defaultValue; } Type readScript(Reader p, int i) { Type s = new Type(); assert(OBJECT() != null); s.base = OBJECT(); s.name = new Name("global"+i); Method init = s.init = methods[p.readU30()]; // init_id init.cx = s; Typeref sref = s.ref.nonnull(); init.getParams()[0] = sref; init.name = s.getName(); init.kind = "init"; readTraits(p, s); for (Binding b : s.defs.values()) TypeCache.instance().globals.put(b.getName(), sref); s.setFinal(); return s; } Type readClass(Reader p, Type it) { Type c = new Type(); assert(CLASS() != null); c.base = CLASS(); c.itype = it; c.name = it.getName().append("$"); Method init = c.init = methods[p.readU30()]; // init_id init.cx = c; init.getParams()[0] = c.ref.nonnull(); init.name = c.getName(); init.kind = "init"; readTraits(p, c); c.setFinal(); return c; } Type readInstance(Reader p) { Type t = new Type(); // Qualified name of the type. t.name = names[p.readU30()]; // Base name of the type is in the ABC; // resolve it, and note that the base type // has been used as a base, so it won't be // emitted as *. t.base = lookup(p.readU30()); TypeCache.instance().baseTypes.add(t.base); t.flags = p.readU8(); if (t.hasProtectedNs()) t.protectedNs = namespaces[p.readU30()]; t.interfaces = new Type[p.readU30()]; for (int j = 0, n = t.interfaces.length; j < n; j++) { t.interfaces[j] = lookup(p.readU30()); } t.init = methods[p.readU30()]; // init_id if(t.init.isNative() && !ALLOW_NATIVE_CTORS) throw new RuntimeException("Constructors can't be native: "+t); t.init.cx = t; t.init.getParams()[0] = t.ref.nonnull(); t.init.kind = "init"; t.init.name = t.getName(); readTraits(p, t); TypeCache.instance().namedTypes.put(t.getName(), t); if (t.getName().equals(new Name(Name.PKG_PUBLIC,"Object"))) { containsObject = true; } return t; } void readCode(Method m, Reader p, Reader ptry) { addTraceAttr("Method", m); addTraceAttr("code_start", p.pos); int local_count = m.local_count; int end_pos = p.pos + m.code_len; // initial state of frame Expr[] frame = new Expr[local_count + m.max_scope + m.max_stack]; Map blocks = new TreeMap(); Map states = new TreeMap(); int scopep = local_count; int sp = local_count+m.max_scope; traceEntry("InitialFrame"); addTraceAttr("length", frame.length); addTraceAttr("sp", sp); addTraceAttr("scopep", scopep); m.entry = new Edge(m,null,0); Block b = createBlock(m, m.entry, states, frame, sp, scopep); Expr e; { int i; for (i=0; i < m.getParams().length; i++) { // argument i b.add(e = frame[i] = new Expr(m, OP_arg, i)); if (i==0) e.ref = new Name("this"); else if (m.paramNames != null) e.ref = m.paramNames[i]; else e.ref = new Name("arg"+i); } if (m.needsArguments() || m.needsRest()) { b.add(e = frame[i] = new Expr(m, OP_arg, i)); e.ref = new Name(m.needsArguments() ? "arguments" : "rest"); i++; } for (; i < local_count; i++) { // remaining locals are undefined, but we use OP_arg // to suppress any codegen. sccp_eval knows what to do. b.add(e = frame[i] = new Expr(m, OP_arg, i)); e.ref = new Name("local"+i); } } BitSet trylabels = new BitSet(); BitSet catchlabels = new BitSet(); // Remember start position of the code reader to compute // relative offsets vs. absolute positions. int code_start = p.pos; int try_start = ptry.pos; // FIXME: use m.handlers-based processing, remove this Handler[] handlers = m.handlers = new Handler[ptry.readU30()]; if ( handlers.length > 0 ) { // TODO arg 0 only needs to be fixed if // this is an instance method. m.fixedLocals.put(frame[0], -1); for (int j = 0, n=handlers.length; j < n; j++) { Handler h = handlers[j] = new Handler(); int from = ptry.readU30(); int to = ptry.readU30(); int target = ptry.readU30(); h.type = lookup(ptry.readU30()).ref.nonnull(); int name_idx = ptry.readU30(); Name name = h.name = names[name_idx]; // The name may be null if the catch variable // did not have a name. // NOTE: Also see the emitCode write logic. if ( name != null ) { Type a = new Type(name,ANY()); h.activation = a.ref.nonnull(); Binding bind = new Binding(TRAIT_Var, name, this); bind.type = h.type; a.defs.put(name, bind); } else { h.activation = ANY().ref.nonnull(); } trylabels.set(from); trylabels.set(to); catchlabels.set(target); } } boolean reachable = true; boolean in_catch_block = false; while (p.pos < end_pos) { int pos = p.pos; int op = p.readU8(); if ( OP_label == op || blocks.containsKey(pos) || trylabels.get(pos-code_start) || catchlabels.get(pos-code_start) ) { if ( catchlabels.get(pos-code_start) ) { in_catch_block = true; } else { in_catch_block = false; } Edge edge = null; if (reachable) { assert(!in_catch_block); Edge succ[] = b.succ(); if (0 == succ.length) { b.add(e = new Expr(m,OP_jump)); e.succ = new Edge[] { edge = new Edge(m,b,0,blocks.get(pos)) }; } else { edge = succ[0]; } traceEntry("Successor"); addTraceAttr("Edge", edge); } // For non-catch blocks, the block's saved stack frame // needs to be updated with the current stack frame -- // this may create that saved stack frame as a // side effect. For a catch block, the stack frame // set up by the catch handler is already present // and is known to be the correct starting state // of the block. if (! in_catch_block) { merge(m,edge, blocks, states, pos, frame, sp, scopep); } b = blocks.get(pos); assert(b != null); FrameState state = states.get(b); assert(state != null); System.arraycopy(state.frame, 0, frame, 0, frame.length); sp = state.sp; scopep = state.scopep; reachable = true; } // now we know what block we're in and pos is where it starts. // Do we need to set up exception handlers? if (handlers.length > 0 && b.xsucc == noedges) { // start of new block, add handlers. addTraceAttr("offset", pos - code_start); List xsucc = new ArrayList(); ptry.pos = try_start; int n=ptry.readU30(); addTraceAttr("NumHandlers", n); for (int j=0; j < n; j++) { int from = code_start + ptry.readU30(); int to = code_start + ptry.readU30(); int target = code_start + ptry.readU30(); traceEntry("Handler"); addTraceAttr("from", from - code_start); addTraceAttr("to", to - code_start); addTraceAttr("target", target - code_start); if (pos >= from && pos < to) { addTraceAttr("activeHandler"); Edge edge = new Edge(m, b, j, handlers[j]); xmerge(m, edge, blocks, states, target, frame, sp, scopep); xsucc.add(edge); } ptry.readU30(); // type ptry.readU30(); // name } b.xsucc = xsucc.toArray(new Edge[xsucc.size()]); } addTraceAttr("offset", pos-code_start); addTraceAttr("op", op); addTraceAttr("opName", opNames[op]); switch (op) { case OP_label: // already handled above break; case OP_throw: case OP_returnvalue: b.add(e = new Expr(m,op, frame, sp--, 1)); e.succ = noedges; reachable = false; merge(m,null, blocks, states, p.pos, frame, sp, scopep); break; case OP_dxnslate: b.add(new Expr(m,op,frame, sp--, 1)); break; case OP_pushwith: case OP_pushscope: { // includes a null pointer check and moves value to scope stack, so this isn't just a copy b.add(frame[scopep++] = e = new Expr(m, op, frame, sp--, 1)); // The activation record saved for catch blocks' use // is live across regions of code that the optimizer // and verifier don't agree on, so it gets fixed into // a local and "conflicts" with everything. if ( in_catch_block && OP_phi == e.args[0].op ) { Expr activ = e.args[0]; while ( OP_phi == activ.op && activ.args != null && activ.args.length > 0) { activ = activ.args[0]; } if ( OP_newactivation == activ.op) { m.fixedLocals.put(activ, -1); } } break; } case OP_popscope: b.add(e = new Expr(m, op)); e.scopes = new Expr[] { frame[--scopep] }; frame[scopep] = null; break; case OP_nextname: case OP_hasnext: case OP_nextvalue: b.add(e = new Expr(m,op, frame, sp, 2)); sp -= 2; frame[sp++] = e; break; case OP_pushnull: b.add(frame[sp++] = new Expr(m,op,NULL())); break; case OP_pushundefined: b.add(frame[sp++] = new Expr(m,op,UNDEFINED)); break; case OP_pushtrue: b.add(frame[sp++] = new Expr(m,op,TRUE)); break; case OP_pushfalse: b.add(frame[sp++] = new Expr(m,op,FALSE)); break; case OP_pushnan: b.add(frame[sp++] = new Expr(m,op,Double.NaN)); break; case OP_newactivation: b.add(frame[sp++] = new Expr(m,op)); break; case OP_getglobalscope: b.add(e = frame[sp++] = new Expr(m, op)); e.scopes = capture(frame, scopep, scopep-local_count); traceEntry("scopep", scopep); break; case OP_getscopeobject: b.add(e = frame[sp++] = new Expr(m, op)); e.scopes = capture(frame, local_count+p.readU8()+1, 1); break; case OP_pop: sp--; break; case OP_dup: frame[sp] = frame[sp-1]; sp++; break; case OP_swap: { e = frame[sp-1]; frame[sp-1] = frame[sp-2]; frame[sp-2] = e; break; } case OP_returnvoid: b.add(e = new Expr(m,op)); e.succ = noedges; reachable = false; merge(m,null, blocks, states, p.pos, frame, sp, scopep); break; case OP_convert_s: case OP_esc_xelem: case OP_esc_xattr: case OP_convert_i: case OP_convert_u: case OP_convert_d: case OP_coerce_s: case OP_negate: case OP_increment: case OP_decrement: case OP_not: case OP_bitnot: case OP_increment_i: case OP_decrement_i: case OP_negate_i: case OP_coerce_o: case OP_convert_o: case OP_typeof: case OP_convert_b: case OP_coerce_a: // unary w/ possible side effect b.add(frame[sp-1] = new Expr(m,op, frame, sp, 1)); break; case OP_checkfilter: // possible exception b.add(new Expr(m,op, frame, sp, 1)); break; case OP_astypelate: case OP_add: case OP_subtract: case OP_multiply: case OP_divide: case OP_modulo: case OP_lshift: case OP_rshift: case OP_urshift: case OP_bitand: case OP_bitor: case OP_bitxor: case OP_equals: case OP_lessthan: case OP_lessequals: case OP_greaterthan: case OP_greaterequals: case OP_instanceof: case OP_in: case OP_add_i: case OP_subtract_i: case OP_multiply_i: case OP_istypelate: case OP_strictequals: b.add(frame[sp-2] = new Expr(m,op, frame, sp, 2)); sp--; break; case OP_getlocal0: case OP_getlocal1: case OP_getlocal2: case OP_getlocal3: frame[sp++] = frame[op-OP_getlocal0]; break; case OP_setlocal0: case OP_setlocal1: case OP_setlocal2: case OP_setlocal3: frame[op-OP_setlocal0] = frame[--sp]; break; case OP_kill: b.add(frame[p.readU30()] = new Expr(m,OP_pushundefined,UNDEFINED)); break; case OP_pushshort: b.add(frame[sp++] = new Expr(m,op, new Integer((short)p.readU30()))); break; case OP_pushstring: b.add(frame[sp++] = new Expr(m,op, strings[p.readU30()])); break; case OP_pushint: b.add(frame[sp++] = new Expr(m,op, new Integer(ints[p.readU30()]))); break; case OP_pushuint: b.add(frame[sp++] = new Expr(m,op, new Long(uints[p.readU30()]))); break; case OP_pushdouble: b.add(frame[sp++] = new Expr(m,op, new Double(doubles[p.readU30()]))); break; case OP_pushnamespace: b.add(frame[sp++] = new Expr(m,op, namespaces[p.readU30()])); break; case OP_getlocal: frame[sp++] = frame[p.readU30()]; break; case OP_setlocal: frame[p.readU30()] = frame[--sp]; break; case OP_coerce: case OP_astype: case OP_istype: { b.add(e = frame[sp-1] = new Expr(m, op, names[p.readU30()], frame, sp, 1)); break; } case OP_dxns: b.add(new Expr(m,op, strings[p.readU30()])); break; case OP_inclocal_i: case OP_declocal_i: case OP_inclocal: case OP_declocal: { // turn these into increment/decrement, forget which local was used. int i = p.readU30(); op = op == OP_inclocal_i ? OP_increment_i : op == OP_inclocal ? OP_increment : op == OP_declocal_i ? OP_decrement_i : OP_decrement; b.add(e = frame[i] = new Expr(m, op, i, frame, i+1, 1)); break; } case OP_newfunction: { e = new Expr(m,op); e.m = methods[p.readU30()]; e.scopes = capture(frame, scopep, scopep-local_count); traceEntry("scopep", scopep); b.add(frame[sp++] = e); break; } case OP_newclass: { e = new Expr(m, op, frame, sp, 1); e.scopes = capture(frame, scopep, scopep-local_count); traceEntry("scopep", scopep); e.c = classes[p.readU30()]; b.add(frame[sp-1] = e); break; } case OP_newobject: { int argc = 2*p.readU30(); e = new Expr(m,op, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_newarray: { int argc = p.readU30(); e = new Expr(m,op, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_newcatch: { e = new Expr(m, op, p.readU30()); b.add(frame[sp++] = e); break; } case OP_getsuper: { Name ref = names[p.readU30()]; int argc = 1 + refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_setsuper: { Name ref = names[p.readU30()]; int argc = 2 + refArgc[ref.kind]; b.add(e = new Expr(m,op, ref, frame, sp, argc)); sp -= argc; break; } case OP_call: { int argc = 2+p.readU30(); e = new Expr(m, op, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_construct: { int argc = 1+p.readU30(); e = new Expr(m,op, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_getdescendants: case OP_deldescendants: case OP_deleteproperty: case OP_getproperty: { Name ref = names[p.readU30()]; int argc = 1 + refArgc[ref.kind]; e = new Expr(m, op, ref, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_getlex: { Name ref = names[p.readU30()]; assert(refArgc[ref.kind] == 0); e = new Expr(m, OP_findpropstrict, ref, frame, sp, 0); e.scopes = capture(frame, scopep, scopep-local_count); b.add(e); e = new Expr(m, OP_getproperty, ref, new Expr[] { e }, 1, 1); b.add(frame[sp++] = e); break; } case OP_findpropstrict: case OP_findproperty: { Name ref = names[p.readU30()]; int argc = refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); e.scopes = capture(frame, scopep, scopep-local_count); sp -= argc; b.add(frame[sp++] = e); break; } case OP_finddef: { Name ref = names[p.readU30()]; int argc = refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_setproperty: case OP_initproperty: { Name ref = names[p.readU30()]; int argc = 2 + refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); sp -= argc; b.add(e); break; } case OP_getslot: { e = new Expr(m,op, p.readU30(), frame, sp, 1); b.add(e); frame[sp-1] = e; break; } case OP_setslot: { e = new Expr(m,op, p.readU30(), frame, sp, 2); b.add(e); sp -= 2; break; } case OP_jump: { int offset = p.readS24(); if (reachable) { b.add(e = new Expr(m,op)); e.succ = new Edge[] { new Edge(m,b, 0, blocks.get(p.pos+offset)) }; merge(m, null, blocks, states, p.pos, frame, sp, scopep); merge(m,e.succ[0], blocks, states, p.pos+offset, frame, sp, scopep); reachable = false; } break; } case OP_iftrue: case OP_iffalse: { b.add(e = new Expr(m, op, frame, sp--, 1)); int offset = p.readS24(); e.succ = new Edge[] { new Edge(m,b,0,blocks.get(p.pos)), new Edge(m,b,1,blocks.get(p.pos+offset)) }; merge(m,null, blocks, states, p.pos, frame, sp, scopep); merge(m,e.succ[1], blocks, states, p.pos+offset, frame, sp, scopep); break; } case OP_ifnlt: case OP_ifnle: case OP_ifngt: case OP_ifnge: case OP_ifne: case OP_ifstrictne: { b.add(e = new Expr(m, ifoper(op), frame, sp, 2)); traceEntry("ConditionalBranch"); addTraceAttr(e); b.add(e = new Expr(m, OP_iffalse, new Expr[] { e }, 1, 1)); int offset = p.readS24(); sp-=2; e.succ = new Edge[] { new Edge(m,b,0,blocks.get(p.pos)), new Edge(m,b,1,blocks.get(p.pos+offset)) }; merge(m,null, blocks, states, p.pos, frame, sp, scopep); merge(m,e.succ[1], blocks, states, p.pos+offset, frame, sp, scopep); break; } case OP_ifeq: case OP_iflt: case OP_ifle: case OP_ifgt: case OP_ifge: case OP_ifstricteq: { b.add(e = new Expr(m, ifoper(op), frame, sp, 2)); traceEntry("ConditionalBranch"); addTraceAttr(e); b.add(e = new Expr(m, OP_iftrue, new Expr[] { e }, 1, 1)); int offset = p.readS24(); sp-=2; e.succ = new Edge[] { new Edge(m,b,0,blocks.get(p.pos)), new Edge(m,b,1,blocks.get(p.pos+offset)) }; merge(m,null, blocks, states, p.pos, frame, sp, scopep); merge(m,e.succ[1], blocks, states, p.pos+offset, frame, sp, scopep); break; } case OP_lookupswitch: { b.add(e = new Expr(m,op, frame,sp--,1)); // Default target int target = pos+p.readS24(); // "There are case_count+1 case offsets." int case_count = 1+p.readU30(); e.succ = new Edge[case_count+1]; // Default case goes last. e.succ[case_count] = new Edge(m,b, case_count, blocks.get(target)); merge(m,e.succ[case_count], blocks, states, target, frame, sp, scopep); for (int i=0; i < case_count; i++) { target = pos+p.readS24(); e.succ[i] = new Edge(m,b, i, blocks.get(target)); merge(m,e.succ[i], blocks, states, target, frame, sp, scopep); } // no fall-through for switch reachable = false; break; } case OP_pushbyte: { e = frame[sp++] = new Expr(m,op, new Integer((byte)p.readU8())); b.add(e); break; } case OP_hasnext2: { int oloc = p.readU30(); int iloc = p.readU30(); Expr index = frame[iloc]; Expr obj = frame[oloc]; addTraceAttr("index", index); addTraceAttr("obj", obj); b.add(e = frame[sp] = new Expr(m,op)); e.locals = new Expr[] { obj, index }; b.add(e = frame[oloc] = new Expr(m, OP_hasnext2_o)); e.locals = new Expr[] { obj }; b.add(e = frame[iloc] = new Expr(m, OP_hasnext2_i)); e.locals = new Expr[] { index }; sp++; b.must_isolate_block = true; break; } case OP_callmethod: { int id = p.readU30(); int argc = 1+p.readU30(); e = new Expr(m,op, id, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_callstatic: { int id = p.readU30(); int argc = 1+p.readU30(); e = new Expr(m,op, frame, sp, argc); e.m = methods[id]; sp -= argc; b.add(frame[sp++] = e); break; } case OP_applytype: { int argc = 1+p.readU30(); e = new Expr(m,op, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_constructsuper: { int argc = 1+p.readU30(); e = new Expr(m,op, frame, sp, argc); sp -= argc; b.add(e); break; } case OP_callsuper: case OP_callproperty: case OP_constructprop: case OP_callproplex: { Name ref = names[p.readU30()]; int argc = 1 + p.readU30() + refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); sp -= argc; b.add(frame[sp++] = e); break; } case OP_callsupervoid: case OP_callpropvoid: { Name ref = names[p.readU30()]; int argc = 1 + p.readU30() + refArgc[ref.kind]; e = new Expr(m,op, ref, frame, sp, argc); sp -= argc; b.add(e); break; } case OP_debugfile: { int ii = p.readU30(); if (!STRIP_DEBUG_INFO) b.add(e = new Expr(m,op, strings[ii])); addTraceAttr("file", strings[ii]); break; } case OP_debugline: case OP_bkptline: { int ii = p.readU30(); if (!STRIP_DEBUG_INFO) b.add(e = new Expr(m,op, ii)); addTraceAttr("line", ii); break; } case OP_debug: { int i1 = p.readU8(); int i2 = p.readU30(); int i3 = p.readU8(); int i4 = p.readU30(); if (!STRIP_DEBUG_INFO) { e = new Expr(m,op); e.imm = new int[] { i1, i2, i3, i4 }; b.add(e); } break; } case OP_bkpt: if (!STRIP_DEBUG_INFO) { // no args but position matters b.add(new Expr(m,op)); } break; case OP_timestamp: // no args but position matters b.add(new Expr(m,op)); break; case OP_nop: break; default: System.err.println("Unknown ABC bytecode "+op); assert (false); } } dce(m); } public int nameIndex(Name n) { int idx = 0; for (Name x: names) { if ( x != null && ( x == n || x.equals(n) ) ) return idx; idx++; } return -1; } } static int rtcounter; static String unique() { return unique("[]"); } static String unique(String prefix) { return prefix+(rtcounter++); } static Namespace uniqueNs() { return new Namespace(unique("ns")); } Type OBJECT() { return TypeCache.instance().OBJECT;} Type FUNCTION() { return TypeCache.instance().FUNCTION;} Type CLASS() { return TypeCache.instance().CLASS;} Type ARRAY() { return TypeCache.instance().ARRAY;} Type INT() { return TypeCache.instance().INT;} Type UINT() { return TypeCache.instance().UINT;} Type NUMBER() { return TypeCache.instance().NUMBER;} Type BOOLEAN() { return TypeCache.instance().BOOLEAN;} Type STRING() { return TypeCache.instance().STRING;} Type NAMESPACE() { return TypeCache.instance().NAMESPACE;} Type XML() { return TypeCache.instance().XML;} Type XMLLIST() { return TypeCache.instance().XMLLIST;} Type QNAME() { return TypeCache.instance().QNAME;} Type NULL() { return TypeCache.instance().NULL;} Type VOID() { return TypeCache.instance().VOID;} Type ANY() { return TypeCache.instance().ANY();} static class Metadata implements Comparable { String name; Attr[] attrs; public int compareTo(Object o) { Metadata md = (Metadata)o; if (this == md) return 0; int d = md.name.compareTo(name); if (d != 0) return d; if ((d = attrs.length - md.attrs.length) != 0) return d; for (int i=0, n=attrs.length; i < n; i++) if ((d = attrs[i].compareTo(md.attrs[i])) != 0) return d; return 0; } } static class Attr implements Comparable { String name; String value; Attr(String name) { this.name = name; } public int compareTo(Object o) { Attr a = (Attr)o; if (this == a) return 0; int d = name.compareTo(a.name); if (d != 0) return d; if ((d = value.compareTo(a.value)) != 0) return d; return 0; } } /** * Methods ready for optimization. * Populated by readyMethod(), called from readyType() * and by initial processing of the OP_newfunction Expr. */ List ready = new ArrayList(); /** * Track already-processed methods so they never go on the ready list twice. * @warn Methods are tracked by hashCode() b/c Method defines a compare function * that can compare different Methods as equal (if they're in different types). * If Method.hashCode() is modified, then Method will need a unique ID to * make this set work. */ Set already_processed = new HashSet(); void readyType(Type t) { readyMethod(t.init); for (Binding b1: t.defs.values()) if (b1.method != null) readyMethod(b1.method); } void readyMethod(Method m) { traceEntry("readyMethod"); addTraceAttr(m); if (m.entry != null && ! already_processed.contains(m) ) { addTraceAttr("process", true); ready.add(m); already_processed.add(m); } } void optimize(InputAbc a) { for ( PluginData plugin: this.analysis_phase_plugins.values()) { CallGraph cg = new CallGraph(a); plugin.plugin.runPlugin(a.src_filename, cg); } for (Type t: a.scripts) readyType(t); while (!ready.isEmpty()) optimize(getMethod(ready)); } /** * organize the pools so the most commonly referenced elements * have the lowest indexes. * * TODO - remove dup namespaces from nssets & remove dup nssets * * @author edwsmith */ class Abc { Pool intPool = new Pool(1); Pool uintPool = new Pool(1); Pool doublePool = new Pool(1); Pool stringPool = new Pool(1); Pool nsPool = new Pool(1); Pool nssetPool = new Pool(1); Pool namePool = new Pool(1); Pool methodPool1 = new Pool(0); Pool methodPool2 = new Pool(0); Pool metaPool = new Pool(0); int bodyCount; boolean haveNatives; List scripts = new ArrayList(); List classes = new ArrayList(); int typeRef(Typeref tref) { return typeRef(tref.t); } int typeRef(Type t) { if (t == ANY()) return 0; else if(t.emitAsAny()) { verboseStatus("Emitting: " + t + " as any"); return 0; } else return namePool.id(t.getName()); } Pool poolFor(Method m) { // put abc methods first, native methods second. return m.isNative() ? methodPool2 : methodPool1; } int methodId(Method m) { return poolFor(m).id(m); } void addScript(Type s) { // global object type addMethod(s.init); addTraits(s.defs); scripts.add(s); } void addClass(Type c) { // instance type Type t = c.itype; addName(t.getName()); if (t.base != NULL()) addTypeRef(t.base); if (t.hasProtectedNs()) addNamespace(t.protectedNs); for (Type i: t.interfaces) addInterfaceRef(i); addMethod(t.init); addTraits(t.defs); // class type addMethod(c.init); addTraits(c.defs); classes.add(c); } int classId(Type c) { return classes.indexOf(c); } int scriptId(Type c) { return scripts.indexOf(c); } void addTraits(Symtab defs) { for (Binding b: defs.values()) { addName(b.getName()); switch (b.kind()) { case TRAIT_Class: addClass(b.type.t); break; case TRAIT_Var: case TRAIT_Const: addTypeRef(b.type); if (b.value != null) { addConst(b.value); } break; case TRAIT_Method: case TRAIT_Getter: case TRAIT_Setter: addMethod(b.method); break; } /*if (b.hasMetadata()) for (Metadata md : b.md) addMetadata(md);*/ } } void addMetadata(Metadata md) { if (metaPool.add(md) == 1) { stringPool.add(md.name); for (Attr a: md.attrs) { stringPool.add(a.name); stringPool.add(a.value); } } } void addConst(Object value) { if (value instanceof Integer) intPool.add(intValue(value)); else if (value instanceof Long) uintPool.add(uintValue(value)); else if (value instanceof Double) doublePool.add(doubleValue(value)); else if (value instanceof String) stringPool.add((String)value); else if (value instanceof Namespace) addNamespace((Namespace) value); } int constId(int kind, Object value) { switch (kind) { case CONSTANT_Integer: return intPool.id(intValue(value)); case CONSTANT_UInteger: return uintPool.id(uintValue(value)); case CONSTANT_Utf8: return stringPool.id((String)value); case CONSTANT_Double: return doublePool.id(doubleValue(value)); case CONSTANT_Namespace: return nsPool.id((Namespace)value); case CONSTANT_True: return CONSTANT_True; case CONSTANT_False: return CONSTANT_False; case CONSTANT_Null: return CONSTANT_Null; } return 0; } int constKind(Object value) { if (value instanceof Integer) return CONSTANT_Integer; if (value instanceof Long) return CONSTANT_UInteger; if (value instanceof Double) return CONSTANT_Double; if (value instanceof String) return CONSTANT_Utf8; if (value instanceof Namespace) return ((Namespace)value).kind; if (value == TRUE) return CONSTANT_True; if (value == FALSE) return CONSTANT_False; if (value == UNDEFINED) return CONSTANT_Void; if (value == NULL()) return CONSTANT_Null; return 0; } void addNamespace(Namespace ns) { if (nsPool.add(ns) == 1) { if (!ns.isPrivateOrInternal()) stringPool.add(ns.uri); } } void addNsset(Nsset nsset) { if (nssetPool.add(nsset) == 1) for (Namespace ns: nsset) addNamespace(ns); } void addName(Name n) { if (namePool.add(n) == 1) switch (n.kind) { case CONSTANT_Multiname: case CONSTANT_MultinameA: addNsset(n.nsset); stringPool.add(n.name); break; case CONSTANT_Qname: case CONSTANT_QnameA: addNamespace(n.nsset(0)); stringPool.add(n.name); break; case CONSTANT_RTQname: case CONSTANT_RTQnameA: stringPool.add(n.name); break; case CONSTANT_MultinameL: case CONSTANT_MultinameLA: addNsset(n.nsset); break; } } void addTypeRef(Typeref tref) { addTypeRef(tref.t); } void addTypeRef(Type t) { if (t != ANY() && !t.emitAsAny()) addName(t.getName()); } void addInterfaceRef(Type t) { addName(t.getName()); } void addMethod(Method m) { if (poolFor(m).add(m) > 1) return; if (m.entry != null) bodyCount++; addTypeRef(m.returns.t); for (int i=1, n=m.getParams().length; i < n; i++) addTypeRef(m.getParams()[i]); if (m.hasOptional()) for (Object v: m.values) if (v != null) addConst(v); if (!STRIP_DEBUG_INFO) { if (m.hasParamNames()) for (int i=1; i < m.paramNames.length; i++) addName(m.paramNames[i]); } if ( PRESERVE_METHOD_NAMES ) { addConst(m.debugName); } for (Handler t: m.handlers) { if ( t.name != null ) addName(t.name); addTypeRef(t.type); } // native and interface methods don't have a body haveNatives |= m.isNative(); if (m.entry == null) return; for (Block b: dfs(m.entry.to)) { for (Expr e: b) { switch (e.op) { case OP_debugfile: if (!STRIP_DEBUG_INFO) addConst(e.value); break; case OP_pushint: case OP_pushuint: case OP_pushstring: case OP_pushnamespace: case OP_pushdouble: case OP_dxns: addConst(e.value); break; case OP_istype: case OP_astype: case OP_findproperty: case OP_findpropstrict: case OP_callproperty: case OP_callproplex: case OP_callsuper: case OP_callsupervoid: case OP_constructprop: case OP_getproperty: case OP_setproperty: case OP_deleteproperty: case OP_getdescendants: case OP_coerce: case OP_getlex: case OP_finddef: case OP_callpropvoid: case OP_initproperty: addName(e.ref); break; case OP_newfunction: case OP_callstatic: addMethod(e.m); break; } } } addTraits(m.activation.t.defs); } void sort() { verboseStatus("NAMES RANK " + namePool.refs); intPool.sort(); uintPool.sort(); doublePool.sort(); stringPool.sort(); nsPool.sort(); nssetPool.sort(); namePool.sort(); metaPool.sort(); methodPool1.sort(); methodPool2.countFrom = methodPool1.size(); methodPool2.sort(); verboseStatus("NAMES " + namePool.values); // topological sort of the classes, base classes come first if ( legacy_verifier ) { if ( num_linked_files > 1 ) { classes = new Algorithms.TopologicalSort().toplogicalSort( classes, new Algorithms.TopologicalSort.DependencyChecker() { public boolean depends(Type dep, Type parent) { return (dep.itype.isDerivedFrom(parent.itype)); } } ); } } else { // HACK ALERT: This sort is incorrect, but the topological // sort causes tamarin-tracing builds to fail in shell.abc. TreeSet cs = new TreeSet(new Comparator() { public int compare(Type a, Type b) { if (a == b) return 0; // no, this is subtly wrong: we might be comparing two classes that have no parent-child relationship // (eg SyntaxError and EvalError). this logic will push UP subclasses and push DOWN no-rel-classes and superclasses. // it's more reliable to push DOWN superclasses and UP subclasses and no-rel-classes. (we can't just return 0 // for no-rel because TreeSet will assume they are identical and eliminate one...) // else if (istype(a.itype, b.itype)) return 1; // else return -1; else if (b.itype.extendsOrIsBase(a.itype)) return -1; else return 1; } }); cs.addAll(classes); classes.clear(); classes.addAll(cs); } } public int interfaceRef(Type t) { return namePool.id(t.getName()); } } int argc(Expr e) { switch (e.op) { case OP_callproperty: case OP_callproplex: case OP_callpropvoid: case OP_callsuper: case OP_callsupervoid: case OP_constructprop: return e.args.length - refArgc[e.ref.kind] - 1; case OP_applytype: case OP_callstatic: case OP_callmethod: case OP_constructsuper: case OP_construct: return e.args.length-1; case OP_call: return e.args.length-2; case OP_newarray: return e.args.length; case OP_newobject: assert(e.args.length % 2 == 0); return e.args.length/2; default: assert(false); } return 0; } static class IndentingPrintWriter extends PrintWriter { int indent; IndentingPrintWriter(Writer w) { super(w); } public void println() { super.println(); for (int i=0; i < indent; i++) print(" "); } } byte[] emit(InputAbc a, String filename, List initScripts, boolean no_c_gen) throws IOException { // schedule everything that is reachable. this will assign new id's to // stuff, then we can write it all out in the right order. Abc abc = new Abc(); for (Type s: a.scripts) abc.addScript(s); abc.sort(); String scriptname = filename.substring(0,filename.lastIndexOf('.')); byte[] data = emitAbc(abc); OutputStream out = new FileOutputStream(scriptname+".abc2"); try { out.write(data); } finally { out.close(); } if (abc.haveNatives && !no_c_gen) { PrintWriter out_h = new PrintWriter(new FileWriter(scriptname+".h2")); IndentingPrintWriter out_c = new IndentingPrintWriter(new FileWriter(scriptname+".cpp2")); try { emitSource(abc, scriptname, data, initScripts, out_h, out_c); } finally { out_c.close(); out_h.close(); } } return data; } void emitSource(Abc abc, String name, byte[] data, List initScripts, PrintWriter out_h, IndentingPrintWriter out_c) { // header file - definitions & native method decls out_h.println("/* machine generated file -- do not edit */"); out_h.println("namespace avmplus {"); out_h.println("AVMPLUS_NATIVEMAP_DECLARE("+name+", "+ abc.methodPool1.size()+")"); out_c.println("/* machine generated file -- do not edit */"); out_c.println("namespace avmplus {"); // output vm creation init method out_h.println("extern AvmInstance "+name+"_init(GC* gc, const AvmConfiguration& c, const uint8_t* abc_data=NULL, size_t length=0);"); // data buf decl only visible to init method out_c.println("extern const uint8_t "+name+"_abc_data["+data.length+"];"); out_c.println("AvmInstance "+name+"_init(GC* gc, const AvmConfiguration& c, const uint8_t* abc_data/*=NULL*/, size_t length/*=0*/)"); out_c.printf("{\n\tif (abc_data==NULL) { abc_data = %s_abc_data; length = %s; }\n", name, data.length); out_c.printf("\tAvmInstance _vm = AvmInit(gc, c, abc_data, length, %s_natives, %s_offset);\n", name, name); for(int i: initScripts) { out_c.printf("\tAvmInitScript(_vm, %d);\n", i); } out_c.printf("\treturn _vm;\n}\n"); StringWriter b = new StringWriter(); PrintWriter out_t = new PrintWriter(b); Map impls = new TreeMap(); for (Type s: abc.scripts) emitSourceTraits("", abc, s, out_h, impls, out_t, out_c); out_c.print("AVMPLUS_NATIVEMAP_BEGIN("+name+")"); out_c.indent++; out_c.println(); for (int id: impls.keySet()) { String s = impls.get(id); if (s.charAt(0) == 'f') out_c.println("AVMPLUS_NATIVEMAP_FORTHMETHOD("+s.substring(1)+")"); else out_c.println("AVMPLUS_NATIVEMAP_CMETHOD("+s.substring(1)+")"); } out_c.indent--; out_c.println("AVMPLUS_NATIVEMAP_END()"); out_c.println(); // put thunks in cpp file out_t.flush(); out_c.println(b); out_c.println(); // cpp file - abc data, thunks out_c.print("const uint8_t "+name+"_abc_data["+data.length+"] = {"); out_c.indent++; out_c.println(); for (int i=0, n=data.length; i < n; i++) { int x = data[i] & 255; if (x < 10) out_c.print(" "); else if (x < 100) out_c.print(' '); out_c.print(x); if (i+1 < n) out_c.print(", "); if (i%16 == 15) out_c.println(); } out_c.indent--; out_c.println("};"); out_c.println("} /* namespace avmplus */"); out_h.println("} /* namespace avmplus */"); } void emitSourceTraits(String prefix, Abc abc, Type s, PrintWriter out_h, Map impls, PrintWriter out_t, PrintWriter out_c) { out_h.println(); assert(!s.init.isNative()); for (Binding b: s.defs.values()) { Namespace ns = b.getName().nsset(0); String id = prefix + propLabel(b, ns); boolean isNative = false; String ctype = null; if (b.md.length > 0) for (Metadata md : b.md) if (md.name.equals("native")) { isNative = true; for (Attr a: md.attrs) if (a.name.equals("type")) ctype = a.value; } if (b.method != null) { if(b.method.isNative()) emitSourceMethod(prefix, abc, b, ns, out_h, impls, out_t, s.obscure_natives); else if(isNative && !s.obscure_natives) { int scriptId = abc.scriptId(s); if(scriptId == -1) throw new RuntimeException("Only scripts can have native callins"); emitCallinMethod(b, ns, abc.scriptId(s), out_h, out_c); } } else if (isClass(b)) emitSourceClass(abc, out_h, out_c, impls, out_t, b, ns, s.obscure_natives); else if (isSlot(b) && isNative) emitSourceSlot(prefix, abc, b, ns, id, ctype, out_h, out_t, s.obscure_natives); } } void emitSourceSlot(String prefix, Abc abc, Binding b, Namespace ns, String id, String ctype, PrintWriter out_h, PrintWriter out_t, boolean obscure_natives) { if (obscure_natives) return; if (b.type.t.isAtom()) { if (ctype != null) { // native GCObject's must be stored as atoms, field type must be *. if (b.type.t != ANY() || !ns.isPrivateOrInternal()) throw new RuntimeException("native field "+id+" must be private or internal and type *"); out_h.println("AVMPLUS_NATIVE_SLOT_DECL_GC("+ctype+","+b.offset+","+id+")"); } else { out_h.println("AVMPLUS_NATIVE_SLOT_DECL_ATOM("+b.offset+","+id+")"); } } else if (b.type.t.emitAsAny()) { ctype = ctype(b.type); out_h.println("AVMPLUS_NATIVE_SLOT_DECL_GC("+ctype+","+b.offset+","+id+")"); } else if (b.type.t.numeric) { ctype = ctype(b.type); out_h.println("AVMPLUS_NATIVE_SLOT_DECL_PRIM("+ctype+","+b.offset+","+id+")"); } else { ctype = ctype(b.type); out_h.println("AVMPLUS_NATIVE_SLOT_DECL_RC("+ctype+","+b.offset+","+id+")"); } } void emitSourceClass(Abc abc, PrintWriter out_h, PrintWriter out_c, Mapimpls, PrintWriter out_t, Binding b, Namespace ns, boolean obscure_natives) { String label = (ns.isPublic()||ns.isInternal()) ? b.getName().name : ns.isProtected() ? "protected_"+b.getName().name : TypeCache.instance().namespaceNames.containsKey(ns) ? TypeCache.instance().namespaceNames.get(ns)+"_"+b.getName().name : (ns.uri.replace(' ', '_').replace('.','_').replace('$','_')+'_'+b.getName().name); Type c = b.type.t; if (!obscure_natives) { out_h.println("const int abcclass_"+ label + " = " + abc.classId(c) + ";"); } emitSourceTraits(label+"_", abc, c, out_h, impls, out_t, out_c); emitSourceTraits(label+"_", abc, c.itype, out_h, impls, out_t, out_c); } String ctype(Typeref tref) { Type t = tref.t; if (t == VOID()) return "void"; if (t.isAtom()) return "AvmBox"; if (t == INT()) return "int32_t"; if (t == BOOLEAN()) return "bool"; // no, this would be bad. if (t == UINT()) return "uint32_t"; if (t == STRING()) return "AvmString"; if (t == NAMESPACE()) return "AvmNamespace"; if (t == NUMBER()) return "double"; if (t.base == null) return tref.nonnull().toString() + "*"; else return "AvmObject /*"+tref.toString()+"*/"; } void emitSourceMethod(String prefix, Abc abc, Binding b, Namespace ns, PrintWriter out_h, Map impls, PrintWriter out_t, boolean obscure_natives) { Method m = b.method; String impl = prefix + propLabel(b, ns); if (isGetter(b)) impl += "_get"; else if (isSetter(b)) impl += "_set"; String forthword = null; if (b.md.length > 0) { for (Metadata md : b.md) { if (md.name.equals("forth")) { for (Attr a: md.attrs) { if (a.name.equals("word")) { forthword = a.value; break; } } if (forthword == null) throw new RuntimeException("the forth metadata must specify the word attribute"); break; } } } if (forthword != null) { // note that forth methods are allowed to have optional parameters, but // the default values will be ignored! it is up to the forth implementation // to check and fill them in properly (that is, the optional args are allowed // only to satisfy signature requirements). out_h.printf("AVMPLUS_FORTH_METHOD_DECL(%s, %s)\n", forthword, impl); impls.put(abc.methodId(m), "f" + forthword); } else { if (m.hasOptional()) { throw new RuntimeException("native methods may not have optional parameters: "+impl); } if (m.needsRest()) { throw new RuntimeException("native methods may not have rest args: "+impl); } // create a C++ declaration for the native thunk. createThunkArgs(out_h, impl, m, obscure_natives); if(m.returns.t != VOID() && m.returns.t.base == null && !m.returns.t.isAtom()) out_h.printf("AVMPLUS_NATIVE_METHOD_DECL_GCOBJ(%s, %s)\n", ctype(m.returns), impl); else out_h.printf("AVMPLUS_NATIVE_METHOD_DECL(%s, %s)\n", ctype(m.returns), impl); impls.put(abc.methodId(m), "n" + impl); } } String propLabel(Binding b, Namespace ns) { return (ns.isPublic()||ns.isInternal()) ? b.getName().name : ns.isPrivate() ? "private_"+b.getName().name : ns.isProtected() ? "protected_"+b.getName().name : TypeCache.instance().namespaceNames.get(ns)+"_"+b.getName().name; } /** * create C++ code for a struct for the argtypes for this method * * @param out_t * @param id * @param m */ void createThunkArgs(PrintWriter out_h, String id, Method m, boolean obscure_natives) { if (!m.hasParamNames() && m.getParams().length > 1) { throw new RuntimeException("native method " + id + " must be generated with debug info (have no fear, it will be stripped)"); } out_h.println(); if (obscure_natives) { out_h.println("struct " + id + "_args;"); return; } out_h.println("struct " + id + "_args"); out_h.println("{"); // args int i=0; for (int n=m.getParams().length; i < n; i++) { String argname = (i == 0) ? ((m.getParams()[i].toString().indexOf("$") >= 0) ? "classself" : "self") : m.paramNames[i].name; if (m.getParams()[i].t==NUMBER()) { out_h.printf(" public: double %s;\n", argname); } else if (m.getParams()[i].t==BOOLEAN()) { out_h.printf(" public: int32_t %s_b; private: int32_t %s_pad; public: inline bool %s() const { return %s_b != 0; }\n", argname, argname, argname, argname); } else if (m.getParams()[i].t==OBJECT() || m.getParams()[i].t==ANY()) { out_h.printf(" public: AvmBoxArg %s;\n", argname); } else { out_h.printf(" public: %s %s; private: int32_t %s_pad; \n", ctype(m.getParams()[i]), argname, argname); } } out_h.printf(" public: AvmStatusOut status_out;\n"); out_h.println("};"); } void emitCallinMethod(Binding b, Namespace ns, int class_id, PrintWriter out_h, PrintWriter out_c) { Method m = b.method; String impl = ns.uri.replace('.', '_') + "_" + b.getName().name; writeCallin(m, class_id, impl, out_h, out_c); } String boxSetter(Type t) { if(t == INT()) return "Int"; else if(t == UINT()) return "Uint"; else if(t == BOOLEAN()) return "Bool"; else if(t == STRING()) return "String"; else if(t == NAMESPACE()) return "Namespace"; else if(t == NUMBER()) return "Double"; else if(t.base == null) // same test use to emit ANY for native slots, valid? return "GCObject"; return "Object"; } void writeCallin(Method m, int script_id, String impl, PrintWriter out_h, PrintWriter out_c) { StringWriter bodySW = new StringWriter(); StringWriter declSW = new StringWriter(); PrintWriter decl = new PrintWriter(declSW); PrintWriter body = new PrintWriter(bodySW); decl.printf("%s %s(AvmInstance vm", ctype(m.returns), impl); body.print("\n{\n"); if(m.getParams().length > 1) body.printf("\tAvmBox _args[%d];\n", m.getParams().length - 1); // args int i=1; for (int n=m.getParams().length; i < n; i++) { Typeref t = m.getParams()[i]; decl.printf(", %s %s", ctype(t), m.paramNames[i]); body.printf("\t_args[%d] = AvmBox%s(%s);\n", i-1, boxSetter(t.t), m.paramNames[i]); } decl.print(")"); body.print("\t"); if(m.returns.t != VOID()) body.print("const AvmBox _returnBox = "); body.printf("\tAvmInvokeCallin(vm, %d, %d, %d, %s);\n", script_id, m.emit_id, m.getParams().length - 1, m.getParams().length > 1 ? "(AvmBox*)&_args" : "NULL"); if(m.returns.t != VOID()) body.printf("\treturn AvmUnBox%s(_returnBox);\n", boxSetter(m.returns.t)); else body.print(";\n"); body.print("}\n"); out_h.printf("%s;\n", declSW.getBuffer()); out_c.print(declSW.getBuffer()); out_c.print(bodySW.getBuffer()); } byte[] emitAbc(Abc abc) throws IOException { AbcWriter w = new AbcWriter(); w.writeU16(16); w.writeU16(46); int pos = w.size(); w.writeU30(abc.intPool.size()); for (int x: abc.intPool.values) w.writeU30(x); verboseStatus("ints count "+abc.intPool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.uintPool.size()); for (long x: abc.uintPool.values) w.writeU30((int)x); verboseStatus("uints count "+abc.uintPool.size()+ " size " + (w.size()-pos)); pos = w.size(); verboseStatus("doubles "+abc.doublePool.size()); w.writeU30(abc.doublePool.size()); for (double x: abc.doublePool.values) w.write64(Double.doubleToLongBits(x)); verboseStatus("double count "+abc.doublePool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.stringPool.size()); for (String s: abc.stringPool.values) { w.writeU30(s.length()); w.write(s.getBytes("UTF-8")); } verboseStatus("strings count "+abc.stringPool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.nsPool.size()); for (Namespace ns: abc.nsPool.values) emitNamespace(abc, w, ns); verboseStatus("ns count "+abc.nsPool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.nssetPool.size()); for (Nsset nsset: abc.nssetPool.values) { w.writeU30(nsset.length); for (Namespace ns: nsset) w.writeU30(abc.nsPool.id(ns)); } verboseStatus("nsset count "+abc.nssetPool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.namePool.size()); for (Name n: abc.namePool.values) { w.write(n.kind); switch (n.kind) { case CONSTANT_TypeName: /* * TODO: this code is correct in isolation, * but until the rest of the type plumbing * supports parameterized types, the resulting * bytecode fails. So fail fast instead. w.writeU30(abc.stringPool.id(n.name)); // TODO: replace with the parameter count // when we begin supporting it. w.writeU30(1); w.writeU30(abc.stringPool.id(n.type_param)); break; */ throw new IllegalArgumentException("CONSTANT_TypeName is only allowed in an import file."); case CONSTANT_Qname: case CONSTANT_QnameA: w.writeU30(abc.nsPool.id(n.nsset(0))); w.writeU30(abc.stringPool.id(n.name)); break; case CONSTANT_Multiname: case CONSTANT_MultinameA: w.writeU30(abc.stringPool.id(n.name)); w.writeU30(abc.nssetPool.id(n.nsset)); break; case CONSTANT_RTQname: case CONSTANT_RTQnameA: w.writeU30(abc.stringPool.id(n.name)); break; case CONSTANT_MultinameL: case CONSTANT_MultinameLA: w.writeU30(abc.nssetPool.id(n.nsset)); break; case CONSTANT_RTQnameL: case CONSTANT_RTQnameLA: break; default: assert (false); } } verboseStatus("name count "+abc.namePool.size()+ " size " + (w.size()-pos)); pos = w.size(); w.writeU30(abc.methodPool2.size()); int method_id=0; for (Method m: abc.methodPool1.values) emitMethod(abc, w, method_id++, m); for (Method m: abc.methodPool2.values) emitMethod(abc, w, method_id++, m); w.writeU30(abc.metaPool.size()); for (Metadata md: abc.metaPool.values) { w.writeU30(abc.stringPool.id(md.name)); w.writeU30(md.attrs.length); for (Attr a: md.attrs) w.writeU30(abc.stringPool.id(a.name)); for (Attr a: md.attrs) w.writeU30(abc.stringPool.id(a.value)); } w.writeU30(abc.classes.size()); for (Type c: abc.classes) { Type t = c.itype; w.writeU30(abc.namePool.id(t.getName())); w.writeU30(abc.typeRef(t.base)); w.write(t.flags); if (t.hasProtectedNs()) w.writeU30(abc.nsPool.id(t.protectedNs)); w.writeU30(t.interfaces.length); for (Type i: t.interfaces) w.writeU30(abc.interfaceRef(i)); w.writeU30(abc.methodId(t.init)); emitTraits(w, abc, t); } for (Type c: abc.classes) { w.writeU30(abc.methodId(c.init)); emitTraits(w, abc, c); } w.writeU30(abc.scripts.size()); for (Type s: abc.scripts) { w.writeU30(abc.methodId(s.init)); emitTraits(w, abc, s); } w.writeU30(abc.bodyCount); emitBodies(abc, w, abc.methodPool1); emitBodies(abc, w, abc.methodPool2); return w.toByteArray(); } void emitNamespace(Abc emitNamespace, AbcWriter w, Namespace ns) { if (ns.isPrivateOrInternal()) { // internal -> private == sealed packages! w.write(CONSTANT_PrivateNamespace); w.writeU30(0); } else { w.write(ns.kind); w.writeU30(emitNamespace.stringPool.id(ns.uri)); } } void emitBodies(Abc abc, AbcWriter w, Pool pool) throws IOException { for (Method m: pool.values) { if (m.entry == null) continue; w.writeU30(m.emit_id); w.writeU30(m.max_stack); w.writeU30(m.local_count); if (m.cx != null && m.cx.scopes != null) { w.writeU30(m.cx.scopes.length); // init_scope_depth w.writeU30(m.cx.scopes.length+m.max_scope); // max_scope_depth } else { w.writeU30(0); // init_scope_depth w.writeU30(m.max_scope); // max_scope_depth } emitCode(w, abc, m); emitTraits(w, abc, m.activation.t); } } void emitMethod(Abc abc, AbcWriter w, int method_id, Method m) { m.emit_id = method_id; verboseStatus("METHOD " + method_id + " was " + m.id); w.writeU30(m.getParams().length-1); w.writeU30(abc.typeRef(m.returns)); for (int i=1, n=m.getParams().length; i < n; i++) w.writeU30(abc.typeRef(m.getParams()[i])); if (PRESERVE_METHOD_NAMES) w.writeU30(abc.stringPool.id(m.debugName)); else w.writeU30(0); int flags = m.flags; if (STRIP_DEBUG_INFO) flags &= ~METHOD_HasParamNames; w.write(flags); if (m.hasOptional()) { w.writeU30(m.optional_count); for (int j = m.getParams().length - m.optional_count; j < m.getParams().length; j++) { int kind = abc.constKind(m.values[j]); w.writeU30(abc.constId(kind, m.values[j])); // index w.write(kind); } } if ((flags & METHOD_HasParamNames) != 0) { for (int i=1; i < m.paramNames.length; i++) w.writeU30(abc.stringPool.id(m.paramNames[i].name)); } } void emitBlock(AbcWriter out, Block b, Abc abc) { addTraceAttr("Block", b); // emit all but the last instruction of each block. for (Expr e: b) { // Don't emit control-flow insns here; // they're handled by intrablock // processing. if (e.succ != null) break; traceEntry("Expr", "Expr", e); addTraceAttr("op", opNames[e.op]); addTraceAttr("pos", out.size()); out.write(e.op); switch (e.op) { case OP_hasnext2: out.writeU30(e.imm[0]); out.writeU30(e.imm[1]); break; case OP_findproperty: case OP_findpropstrict: case OP_getlex: case OP_getsuper: case OP_setsuper: case OP_getproperty: case OP_setproperty: case OP_deleteproperty: case OP_getdescendants: case OP_initproperty: case OP_istype: case OP_coerce: case OP_astype: case OP_finddef: out.writeU30(abc.namePool.id(e.ref)); break; case OP_callproperty: case OP_callproplex: case OP_callpropvoid: case OP_callsuper: case OP_callsupervoid: case OP_constructprop: out.writeU30(abc.namePool.id(e.ref)); out.writeU30(argc(e)); break; case OP_constructsuper: case OP_call: case OP_construct: case OP_newarray: case OP_newobject: out.writeU30(argc(e)); break; case OP_getlocal: case OP_setlocal: if (e.imm[0] < 4) { out.rewind(1); out.write((e.op == OP_getlocal ? OP_getlocal0 : OP_setlocal0)+e.imm[0]); break; } // else fall through case OP_getslot: case OP_setslot: case OP_kill: case OP_inclocal: case OP_declocal: case OP_inclocal_i: case OP_declocal_i: case OP_newcatch: //case OP_getglobalslot: //case OP_setglobalslot: out.writeU30(e.imm[0]); break; case OP_newclass: out.writeU30(abc.classId(e.c)); break; case OP_newfunction: out.writeU30(abc.methodId(e.m)); break; case OP_applytype: out.writeU30(argc(e)); break; case OP_callstatic: //case OP_callmethod: out.writeU30(abc.methodId(e.m)); out.writeU30(argc(e)); break; case OP_pushshort: out.writeU30(intValue(e.value)); break; case OP_pushbyte: out.write(intValue(e.value)); break; case OP_getscopeobject: out.write(e.imm[0]); break; case OP_pushstring: case OP_dxns: out.writeU30(abc.stringPool.id((String)e.value)); break; case OP_debugfile: if (STRIP_DEBUG_INFO) throw new RuntimeException("impossible"); out.writeU30(abc.stringPool.id((String)e.value)); break; case OP_pushnamespace: out.writeU30(abc.nsPool.id((Namespace)e.value)); break; case OP_pushint: out.writeU30(abc.intPool.id(intValue(e.value))); break; case OP_pushuint: out.writeU30(abc.uintPool.id(uintValue(e.value))); break; case OP_pushdouble: out.writeU30(abc.doublePool.id(doubleValue(e.value))); break; case OP_debugline: case OP_bkptline: if (STRIP_DEBUG_INFO) throw new RuntimeException("impossible"); out.writeU30(e.imm[0]); break; case OP_debug: if (STRIP_DEBUG_INFO) throw new RuntimeException("impossible"); out.write(e.imm[0]); out.writeU30(e.imm[1]); out.write(e.imm[2]); out.writeU30(e.imm[3]); break; } } } void emitCode(AbcWriter out, Abc abc, Method m) throws IOException { addTraceAttr("Method", m); Map padding = new HashMap(); Deque code = schedule(m.entry.to); Map writers = new HashMap(); // Find back edges to see where we need labels // Note: can't use isBackedge() here b/c schedule // may not lay out blocks in the same order. BitSet labels = new BitSet(); BitSet done = new BitSet(); for (Block b: code) { done.set(b.id); for (Edge e: b.succ()) if ( done.get(e.to.id) ) { labels.set(e.to.id); } } // emit the code and leave room for the branch offsets, // and compute the final position of each block. Map pos = new HashMap(); Map blockends = new HashMap(); int code_len = 0; Deque work = new ArrayDeque(code); while (!work.isEmpty()) { Block b = work.removeFirst(); addTraceAttr("Block", b); addTraceAttr("pos", code_len); pos.put(b,code_len); AbcWriter w = new AbcWriter(); writers.put(b, w); if (labels.get(b.id)) { addTraceAttr("hasLabel"); w.write(OP_label); } emitBlock(w, b, abc); code_len += w.size(); Expr last = b.last(); if (last.succ.length == 0) { // returnvoid, returnvalue, or throw w.write(last.op); code_len++; traceEntry("TransferOut", "op", opNames[last.op]); } else if (isJump(last)) { traceEntry("Jump", "target", last.succ[0].to); if (work.isEmpty() || last.succ[0].to != work.peekFirst()) { // target is not fall through block so we'll emit a jump. code_len += 4; padding.put(b, 4); addTraceAttr("fallThrough", false); } else addTraceAttr("fallThrough", true); } else if (isBranch(last)) { if (work.isEmpty() || last.succ[0].to != work.peekFirst()) { code_len += 8; padding.put(b, 8); } else { code_len += 4; padding.put(b, 4); } } else { assert(last.op == OP_lookupswitch); // Switch table contains a U30 case count and S24 offsets. int switch_size = 1 + out.sizeOfU30(last.succ.length) + 3*last.succ.length; code_len += switch_size; padding.put(b, switch_size); } blockends.put(b,code_len); } out.writeU30(code_len); int code_start = out.size(); traceEntry("WriteCode", "Start", code_start); for (Block b: code) { addTraceAttr("Block", b); addTraceAttr("postorder", b.postorder); addTraceAttr("startPos", out.size()); addTraceAttr("offset", out.size() - code_start); writers.get(b).writeTo(out); if (padding.containsKey(b)) { Expr last = b.last(); addTraceAttr(last); addTraceAttr("op", opNames[last.op]); addTraceAttr("padding", padding.get(b)); if (isBranch(last)) { addTraceAttr("isBranch"); emitBranch(out, last.op, last.succ[1].to, code_start, pos); padding.put(b, padding.get(b)-4); } if (padding.get(b) == 4) { traceEntry("ImpliedJump"); addTraceAttr("EdgeId", last.succ[0].id); emitBranch(out, OP_jump, last.succ[0].to, code_start, pos); } if ( last.op == OP_lookupswitch ) { emitLookupswitch(out, last, code_start, pos); } } } // Input code occasionally contains // an empty (or non-effecting, and // thus effectively empty) try block. // Elide these. int valid_handlers_count = 0; for (Handler h: m.handlers) { if ( h.entry != null ) valid_handlers_count++; } out.writeU30(valid_handlers_count); for (Handler h: m.handlers) { if ( null == h.entry ) continue; int from = code_len; int to = 0; for (Block b: code) { for (Edge x: b.xsucc) { if (x.to == h.entry) { if (pos.get(b) < from) from = pos.get(b); if (blockends.get(b) > to) to = blockends.get(b); } } } out.writeU30(from); out.writeU30(to); int off = pos.get(h.entry); verboseStatus("handler "+h.entry+ " ["+from+","+to+")->"+off); out.writeU30(off); out.writeU30(abc.typeRef(h.type)); // See corresponding logic // in readCode() where the // handler's read in. if ( h.name != null ) out.writeU30(abc.namePool.id(h.name)); else out.writeU30(0); } } void emitBranch(AbcWriter out, int op, Block target, int code_start, Mappos) { traceEntry("emitBranch"); addTraceAttr("op", opNames[op]); addTraceAttr("target", target); out.write(op); int to = code_start + pos.get(target); int from = out.size()+3; addTraceAttr("to", to); addTraceAttr("from", from); addTraceAttr("offset", to-from); out.writeS24(to-from); } void emitLookupswitch(AbcWriter out, Expr insn_switch, int code_start, Map pos) { // "The base location is the address of the lookupswitch instruction itself." - AVM2 int base_loc = out.size(); addTraceAttr("baseLoc", base_loc); out.write(OP_lookupswitch); int case_size = insn_switch.succ.length - 2; addTraceAttr("case_size", case_size); int default_target = code_start + pos.get(insn_switch.succ[case_size + 1].to) - base_loc; traceEntry("default", "target", default_target); addTraceAttr("Block", insn_switch.succ[case_size + 1].to); out.writeS24(default_target); out.writeU30(case_size); for ( int i = 0; i <= case_size; i++ ) { int case_target = code_start + pos.get(insn_switch.succ[i].to) - base_loc; traceEntry("case", "target", case_target); addTraceAttr("Block", insn_switch.succ[i].to); out.writeS24(case_target); } } void emitTraits(AbcWriter out, Abc abc, Type t) { Symtab defs = t.defs; out.writeU30(defs.size()); for (Binding b: defs.values()) { out.writeU30(abc.namePool.id(b.getName())); out.write(b.flags_kind & ~(TRAIT_FLAG_metadata<<4)); switch (b.kind()) { case TRAIT_Var: case TRAIT_Const: if ( t.base == null || 0 == t.base.slotCount ) out.writeU30(b.slot); else out.write(0); out.writeU30(abc.typeRef(b.type)); if (!b.defaultValueChanged()) { // vm fills in default value based on type out.writeU30(0); } else { // non-default default value int kind = abc.constKind(b.value); int id = abc.constId(kind, b.value); out.writeU30(id); if (id != 0) out.write(kind); } break; case TRAIT_Class: out.writeU30(b.slot); out.writeU30(abc.classId(b.type.t)); break; case TRAIT_Method: case TRAIT_Getter: case TRAIT_Setter: out.writeU30(b.slot); out.writeU30(abc.methodId(b.method)); break; default: assert(false); } } } void optimize(Method m) { verboseStatus("OPTIMIZE "+m.id + " "+ m.getName()); if(m.entry == null) return; addTraceAttr("Method", m); printMethod(m, "BEFORE OPT"); if (OUTPUT_DOT) dot("-before",m); sccp(m); dvn(m); if (cfgopt(m)) { printMethod(m, "AFTER CFGOPT"); sccp(m); dvn(m); } // find operations to fold together. fold(m); printMethod(m, "AFTER FOLD"); insert_casts(m); remove_phi(m); if (OUTPUT_DOT) dot("-after",m); if ( legacy_verifier ) { appeaseLegacyVerifier(m); if (OUTPUT_DOT) dot("-appeased",m); } computeFrameCounts(m); if ( verbose_mode ) { printabc(schedule(m.entry.to)); } } public static byte[] optimize( byte[] raw_abc, String filename, ObjectList optimizer_configs, ObjectList import_filespecs ) throws java.io.IOException { GlobalOptimizer go = new GlobalOptimizer(); go.legacy_verifier = true; boolean quiet_mode = false; for ( ConfigVar config_var: optimizer_configs ) { if (config_var.name.equalsIgnoreCase("-IMPORT")) { go.new InputAbc().readAbc(load(config_var.value)); } else if ( config_var.name.equalsIgnoreCase("-LEGACY_VERIFIER")) { go.legacy_verifier = !go.legacy_verifier; } else if ( config_var.name.equalsIgnoreCase("-PRESERVE_METHOD_NAMES")) { go.PRESERVE_METHOD_NAMES = true; } else if ( config_var.name.equalsIgnoreCase("-QUIET")) { quiet_mode = true; } else if ( config_var.name.equalsIgnoreCase("-ALLOW_NATIVE_CTORS")) { go.ALLOW_NATIVE_CTORS = true; } if ( config_var.name.equalsIgnoreCase("-plugin") ) { go.loadPlugin(config_var.value); continue; } if ( config_var.name.startsWith("-") && config_var.name.contains(":")) { int delim_pos = config_var.name.indexOf(':'); String plugin_name = config_var.name.substring(1, delim_pos); String plugin_option = config_var.name.substring(delim_pos+1); PluginData plugin_data = go.analysis_phase_plugins.get(plugin_name); if ( null == plugin_data ) { // Iterate over the plugins and find a short // name that matches this monster. for ( PluginData search_plugin: go.analysis_phase_plugins.values() ) { if ( search_plugin.plugin.getClass().getSimpleName().equals(plugin_name)) { plugin_data = search_plugin; break; } } } if ( null != plugin_data ) { plugin_data.options.add(plugin_option); } else { throw new IllegalArgumentException("No plugin named " + plugin_name + " is loaded."); } continue; } else { throw new IllegalArgumentException("Unknown -o2:configuration_value " + config_var.name); } } // TODO: ASC and GO data structures need to interoperate. // For now, just redo the imports. for ( String import_filespec: import_filespecs) { go.new InputAbc().readAbc(import_filespec); } InputAbc input_abc = go.new InputAbc(); input_abc.src_filename = filename; input_abc.readAbc(raw_abc); go.initializePlugins(); go.optimize(input_abc); Abc abc = go.new Abc(); for (Type s: input_abc.scripts) { abc.addScript(s); } abc.sort(); byte[] optimized_abc = go.emitAbc(abc); if ( !quiet_mode ) { System.out.println("Original ABC size: " + raw_abc.length); System.out.println("Optimized ABC size: " + optimized_abc.length); } return optimized_abc; } void fold(Method m) { Deque code = dfs(m.entry.to); EdgeMap uses = findUses(code); for (Block b: code) { for (Expr e: b) { switch (e.op) { case OP_iftrue: case OP_iffalse: { Expr a0 = e.args[0]; if (containsOnly(uses.get(a0),e)) { if (false) ; else if (a0.op == OP_not) subsume_arg(e, (e.op == OP_iftrue ? OP_iffalse : OP_iftrue), uses); else if (a0.op == OP_convert_b) subsume_arg(e, e.op, uses); else if (a0.op == OP_greaterequals) subsume_arg(e, (e.op == OP_iftrue ? OP_ifge : OP_ifnge), uses); else if (a0.op == OP_greaterthan) subsume_arg(e, (e.op == OP_iftrue ? OP_ifgt : OP_ifngt), uses); else if (a0.op == OP_lessthan) subsume_arg(e, (e.op == OP_iftrue ? OP_iflt : OP_ifnlt), uses); else if (a0.op == OP_lessequals) subsume_arg(e, (e.op == OP_iftrue ? OP_ifle : OP_ifnle), uses); // too aggressive, breaks (at least) zlib //else if (a0.op == OP_equals) // subsume_arg(e, (e.op == OP_iftrue ? OP_ifeq : OP_ifne), uses); else if (a0.op == OP_strictequals) subsume_arg(e, (e.op == OP_iftrue ? OP_ifstricteq : OP_ifstrictne), uses); } break; } case OP_getproperty: { Expr a0 = e.args[0]; if (containsOnly(uses.get(a0),e) && a0.op == OP_findpropstrict && a0.args.length == 0 && e.args.length == 1) { e.op = OP_getlex; e.args = noexprs; e.scopes = a0.scopes; a0.setPure(); e.flags |= a0.flags&PX | a0.flags&EFFECT; } } break; } } } dce(m); } int findPhiArg(Expr phi, Edge e) { for (int i=0, n=phi.pred.length; i < n; i++) if (phi.pred[i].equals(e)) return i; assert(false); return -1; } /** * determine if the two blocks have the same exception scope. * @param b1 * @param b2 * @return */ boolean sameExScope(Block b1, Block b2) { if (b1 == b2) return true; Edge[] xs1 = b1.xsucc; Edge[] xs2 = b2.xsucc; if (xs1.length != xs2.length) return false; for (int i=0, n=xs1.length; i < n; i++) { Edge e1 = xs1[i]; Edge e2 = xs2[i]; if (e1.to != e2.to || e1.handler != e2.handler) return false; } return true; } /** * control flow optimizations. * * turn B1->B2 into B1B2 as long as B1's only successor is B2 and B2's only predecessor is B1. * * any branch to a jump can branch to the jump's target * * jump to a return can be replaced by the return * * ISSUE phi's represent copies on an edge. Need to validate that removing * edges doesn't remove a required phi-copy. Any critical edges that have * been split by previous operations may be removed by this pass. * * Should we only do this pass on non-ssa form? */ boolean cfgopt(Method m) { Deque code = dfs(m.entry.to); SetMap pred = allpreds(code); boolean changedout=false; boolean changed; do { changed = false; blocks: for (Block b: code) { Expr last = b.last(); Block taken; if (isJump(last) && sameExScope(b, taken=last.succ[0].to)) { Edge s = last.succ[0]; if (containsOnly(pred.get(taken), s) && !taken.must_isolate_block) { // phi nodes can only occur in nodes with more than one predecessor assert(taken.first().op != OP_phi); verboseStatus("STRAIGHTEN "+s); b.remove(last); b.addAll(taken); for (Edge edge: taken.succ()) edge.from = b; changed = true; printabc(b, new PrintWriter(System.out)); break blocks; } Expr first = taken.first(); if (first.op == OP_returnvalue || first.op == OP_returnvoid) { verboseStatus("PRUNE "+b+"->"+s); last.op = first.op; last.args = first.op == OP_returnvoid ? noexprs : new Expr[] { first.args[0] }; last.succ = noedges; changed = true; break blocks; } Expr r; if (first.op == OP_phi && taken.size()==2 && (r=taken.last()).op == OP_returnvalue && r.args[0] == first) { // successor block is returnvalue(phi) verboseStatus("PRUNE "+b+"->"+s); int i = findPhiArg(first, last.succ[0]); last.op = r.op; last.args = new Expr[] { first.args[i] }; last.succ = noedges; first.removePhiInput(i); changed = true; break blocks; } } if (isBranch(last)) { Edge out = last.succ[1]; Expr cond = last.args[0]; taken = out.to; Expr phi, br; if (last.args.length == 1 && taken.size()==2 && (phi=taken.first()).op==OP_phi && ((br=taken.last()).op == OP_iftrue || br.op == OP_iffalse)) { int i = findPhiArg(phi,out); if (phi.args[i]==cond) { // cond is in phi contributed by this edge. so we have a redundant test. // we want to retarget the branch: and adjust any phi nodes that are affected. Edge before = br.op == last.op ? br.succ[1] : br.succ[0]; verboseStatus("SKIPTEST old "+out+" new "+before); phi.removePhiInput(i); copyTargetPhi(phi, cond, before, out); changed = true; break blocks; } } if (pred.get(last.succ[0].to).size() > 1 && pred.get(taken).size() == 1) { // fall through has multiple preds, taken has only one. reverse the sense // of the test and reverse the edges. Note that this doesn't change the // flow so we don't need to recompute preds, etc. invert(last); changed = true; break blocks; } } for (Edge edge : last.succ) { if (skip(edge)) { changed = true; break blocks; } } } if (changed) { dce(m); code = dfs(m.entry.to); pred = allpreds(code); changedout = true; } } while (changed); return changedout; } boolean skip(Edge edge) { Block to = edge.to; Expr j = to.last(); if (to.size()==1 && isJump(j)) { // any edge targeting a jump can target the jump's target. verboseStatus("SKIP " + j.succ[0]); copyTarget(j.succ[0], edge); return true; } return false; } /** * reverse the sense of a conditional test and swap the outgoing edges. * @param br */ void invert(Expr br) { verboseStatus("INVERT "+br); switch (br.op) { case OP_iftrue: br.op = OP_iffalse; break; case OP_iffalse: br.op = OP_iftrue; break; case OP_ifnlt: br.op = OP_iflt; break; case OP_ifnle: br.op = OP_ifle; break; case OP_ifngt: br.op = OP_ifgt; break; case OP_ifnge: br.op = OP_ifge; break; case OP_ifeq: br.op = OP_ifne; break; case OP_ifne: br.op = OP_ifeq; break; case OP_iflt: br.op = OP_ifnlt; break; case OP_ifle: br.op = OP_ifnle; break; case OP_ifgt: br.op = OP_ifngt; break; case OP_ifge: br.op = OP_ifnge; break; case OP_ifstricteq: br.op = OP_ifstrictne; break; case OP_ifstrictne:br.op = OP_ifstricteq; break; } Edge e0 = br.succ[0]; Edge e1 = br.succ[1]; e0.label = 1; e1.label = 0; br.succ[0] = e1; br.succ[1] = e0; } int ifoper(int op) { switch (op) { default: assert(false); return 0; case OP_iflt: case OP_ifnlt: return OP_lessthan; case OP_ifle: case OP_ifnle: return OP_lessequals; case OP_ifgt: case OP_ifngt: return OP_greaterthan; case OP_ifge: case OP_ifnge: return OP_greaterequals; case OP_ifne: case OP_ifeq: return OP_equals; case OP_ifstricteq: case OP_ifstrictne: return OP_strictequals; } } /** * for each phi in the target block, add a new phi arg for the new edge, * contributing the same variable that the old edge contributed. * @param succ * @param oldpred * @param newpred */ void copyTarget(Edge before, Edge after) { after.to = before.to; for (Expr e: before.to) if (e.op == OP_phi) e.append(e.args[findPhiArg(e,before)], after); } void copyTargetPhi(Expr phi, Expr a, Edge before, Edge after) { after.to = before.to; for (Expr e: before.to) { if (e.op == OP_phi) { Expr phiArg = e.args[findPhiArg(e,before)]; e.append(phiArg==phi ? a : phiArg, after); } else break; } } boolean containsOnly(Collection c, Object elem) { return c.size() == 1 && c.contains(elem); } boolean equiv(Name a, Name b) { return a.match(b) == 0; } boolean equiv(Expr[] a, Expr[] b) { if (a == null || b == null) return false; if (a.length != b.length) return false; for (int i=0; i < a.length; i++) if (!equiv(a[i],b[i])) return false; return true; } boolean equiv(Expr a, Expr b) { if (a == b) return true; if (a != null && b != null && a.op == b.op) { switch (a.op) { case OP_pushtrue: case OP_pushfalse: case OP_pushnan: case OP_pushnull: case OP_pushundefined: case OP_getlocal0: case OP_getlocal1: case OP_getlocal2: case OP_getlocal3: return true; case OP_pushbyte: case OP_pushshort: case OP_pushint: case OP_pushuint: case OP_pushdouble: case OP_pushnamespace: case OP_pushstring: return a.value.equals(b.value); case OP_getlocal: case OP_arg: return a.imm[0] == b.imm[0]; case OP_getglobalscope: return a.scopes.length == 0 && b.scopes.length == 0 || a.scopes.length > 0 && b.scopes.length > 0 && equiv(a.scopes[0], b.scopes[0]); /*case OP_getslot: // TODO unsafe, don't know about intervening stores return a.imm[0] == b.imm[0] && equiv(a.args[0],b.args[0]); case OP_getproperty: // TODO unsafe -- ignores intervening stores & side effects return equiv(a.ref, b.ref) && equiv(a.args,b.args);*/ case OP_finddef: return 0 == a.ref.match(b.ref); } } return false; } void makeCopy(Expr e, Expr a) { // make e be a copy of a assert(e != a); e.op = OP_dup; e.locals = new Expr[] { a }; e.scopes = e.args = noexprs; e.setPure(); } void makeNop(Expr e) { e.op = OP_nop; e.args = e.locals = e.scopes = noexprs; e.setPure(); } Expr dvn_find(Expr e, Block b, Mapidom) { do { for (Expr a: b) { if (a == e) break; if (equiv(a,e)) return a; } b = idom.get(b); } while (b != null); return null; } /** * dominator based value numbering. This is just LVN plus a search up the * dominator tree. When a matching expression is found turn the * instruction into a copy of the found expression. * @param code */ void dvn(Method m) { Deque code = dfs(m.entry.to); Map idom = idoms(code, preds(code)); boolean changed; do { changed = false; for (Block b: code) { for (Expr e: b) { Expr a = dvn_find(e, b, idom); if (a != null) { makeCopy(e,a); changed = true; } } } if (changed) dce(m); } while (changed); } boolean constify(Expr e, Object v) { if (v != null && v != BOTTOM && e.value == null && !hasSideEffect(e)) { // expr is const if (v instanceof Integer) { int i = intValue(v); e.op = (i == (byte)i) ? OP_pushbyte : (i == (short)i) ? OP_pushshort : OP_pushint; } else if (v instanceof Long) { e.op = OP_pushuint; } else if (v instanceof Number) { double d = doubleValue(v); e.op = Double.isNaN(d) ? OP_pushnan : OP_pushdouble; } else if (v instanceof Boolean) { e.op = v == TRUE ? OP_pushtrue : OP_pushfalse; } else if (v instanceof Namespace) { e.op = OP_pushnamespace; } else if (v == UNDEFINED) { e.op = OP_pushundefined; } else if (v == NULL()) { assert(!e.onScope()); e.op = OP_pushnull; } else { assert(v instanceof String); e.op = OP_pushstring; } e.pred = noedges; e.args = e.scopes = e.locals = noexprs; e.value = v; return true; } return false; } boolean jumpify(Expr e, Set reached) { Edge taken = null; for (Edge s: e.succ) { if (reached.contains(s)) { if (taken == null) taken = s; else if (s != taken) { taken = null; break; } } } if (taken != null) { e.op = OP_jump; e.args = noexprs; e.succ = new Edge[] { taken }; return true; } return false; } boolean makeConvert(Expr e, Type t, int op, Map types) { e.op = op; e.args = new Expr[] { e.args[1] }; e.flags = flagTable[op]; if (type(types,e.args[0]).isPrimitive()) e.setPure(); return true; } boolean convertify(Expr e, Binding b0, Maptypes) { if (b0.type != null && e.args.length == 2) { if (b0.type.t.itype == NUMBER()) return makeConvert(e,NUMBER(),OP_convert_d,types); if (b0.type.t.itype == INT()) return makeConvert(e,INT(),OP_convert_i,types); if (b0.type.t.itype == UINT()) return makeConvert(e,UINT(),OP_convert_u,types); if (b0.type.t.itype == STRING()) return makeConvert(e,STRING(),OP_convert_s,types); if (b0.type.t.itype == BOOLEAN()) return makeConvert(e,BOOLEAN(),OP_convert_b,types); } return false; } Expr unwrapScope(Expr e, int i) { // Phi pseudo-Exprs may appear in the scope stack // if the block immediately follows a try/catch, // or if the block is the fall-through alternative // of a conditional jump. In either of these cases, // the compiler set up all phi inputs to refer back // to the same underlying object, so just traverse // back along the first dataflow edge. while ( e.scopes[i].op == OP_phi ) { assert(e.scopes[i].args != null && e.scopes[i].args[0] != null); e.scopes[i] = e.scopes[i].args[0]; } assert(e.scopes[i].onScope()); return e.scopes[i].args[0]; } static Type[] copyOf(Type[] in, int newlen) { Type[] out = new Type[newlen]; if (newlen > in.length) newlen = in.length; System.arraycopy(in, 0, out, 0, newlen); return out; } static Typeref[] copyOf(Typeref[] in, int newlen) { Typeref[] out = new Typeref[newlen]; if (newlen > in.length) newlen = in.length; System.arraycopy(in, 0, out, 0, newlen); return out; } static Expr[] copyOf(Expr[] in, int newlen) { Expr[] out = new Expr[newlen]; if (newlen > in.length) newlen = in.length; System.arraycopy(in, 0, out, 0, newlen); return out; } static Edge[] copyOf(Edge[] in, int newlen) { Edge[] out = new Edge[newlen]; if (newlen > in.length) newlen = in.length; System.arraycopy(in, 0, out, 0, newlen); return out; } /** * sparse conditional constant propagation * @param code */ void sccp(Method m) { addTraceAttr("Method", m); // first build the SSA Edges. Deque code = dfs(m.entry.to); EdgeMap uses = findUses(code); Map values = new TreeMap(); Map types = new TreeMap(); Set reached = new TreeSet(); sccp_analyze(m, uses, values, types, reached); verboseStatus("REACHED " + reached); verboseStatus("TYPES " + types); sccp_cfgopt(values, types, reached); // now the CFG is cleaned up dce(m); // now do type/value based peephole work on each expr in DFS order code = dfs(m.entry.to); uses = findUses(code); // modify the code based on analysis: // * capture scope types for OP_newclass & OP_newfunction // * turn expressions into constants TreeSet work = new TreeSet(); for (Block b: code) for (Expr e: b) work.add(e); while (!work.isEmpty()) { Expr e = getExpr(work); sccp_modify(m, uses, values, types, e, work); } dce(m); //verboseStatus("after sccp"); //print(dfs(m.entry.to)); } void sccp_cfgopt(Map values, Map types, Set reached) { Set blocks = new TreeSet(); for (Edge e: reached) blocks.add(e.to); for (Block b: blocks) { // clean up phis for (Expr e: b) { if (e.op == OP_phi) { for (int j=e.pred.length-1; j >= 0; j--) { Edge p = e.pred[j]; if (!reached.contains(p)) e.removePhiInput(j); } } else if (e.succ != null) { if (e.succ.length > 1 && !jumpify(e, reached) && e.op == OP_lookupswitch) { Expr phi; if (b.size()==2 && (phi=b.first()).op == OP_phi && e.args[0]==phi) { // block is switch(phi) // TODO what about a switch with only some branches not taken? for (int i=phi.args.length-1; i >= 0; i--) { Object v = values.get(phi.args[i]); if (v instanceof Number) { int j = intValue(v); Edge in = phi.pred[i]; Edge out = e.succ[j]; copyTarget(out, in); phi.removePhiInput(i); } } } } } else if (e.isOper() && e.onStack()) { boolean pure = true; for (Expr a: e.args) if (!type(types,a).isPrimitive()) pure = false; for (Expr a: e.locals) if (!type(types,a).isPrimitive()) pure = false; if (pure) e.setPure(); constify(e, values.get(e)); } } } } boolean subsume_arg(Expr e, int op, EdgeMapuses) { e.op = op; Expr a = e.args[0]; e.flags |= a.flags & (PX|EFFECT); a.setPure(); // so it becomes dead and is removed. uses.get(a).remove(e); e.args = copyOf(a.args, a.args.length); for (Expr x: e.args) uses.get(x).add(e); return true; } boolean canEarlyBindMethod(Method m, Binding b) { return m.abc.mergedAbcs.contains(b.abc); } boolean canEarlyBindSlot(Method m, Binding b) { return b.slot != 0 && m.abc.mergedAbcs.contains(b.abc); } static final Name AS3_TOSTRING = new Name(Name.AS3, "toString"); void sccp_modify(Method m, EdgeMap uses, Map values, Map types, Expr e, TreeSet work) { sccp_rename(uses, e, e.args); sccp_rename(uses, e, e.locals); boolean changed; do { changed = false; switch (e.op) { case OP_newclass: { // capture scope chain Type c = e.c; c.scopes = copyOf(m.cx.scopes, m.cx.scopes.length+e.scopes.length); int i = m.cx.scopes.length; for (Expr s: e.scopes) c.scopes[i++] = types.get(s); readyType(c); Type t = c.itype; t.scopes = copyOf(c.scopes, c.scopes.length+1); t.scopes[c.scopes.length] = c.ref.nonnull(); readyType(t); break; } case OP_newfunction: { Method f = e.m; // TODO makeIntoPrototypeFunction() Type t = new Type(m.getName(), FUNCTION()); t.scopes = copyOf(m.cx.scopes, m.cx.scopes.length+e.scopes.length); int i = m.cx.scopes.length; for (Expr s: e.scopes) t.scopes[i++] = types.get(s); f.cx = t; readyMethod(f); break; } case OP_returnvalue: if (type(types,e.args[0]) == VOID()) { e.op = OP_returnvoid; e.args = noexprs; } else { Type t0 = type(types,e.args[0]); if (t0.extendsOrIsBase(m.returns.t)) { Expr a0 = e.args[0]; if (m.returns.t == INT() && a0.op == OP_convert_i) { uses.get(a0).remove(e); a0 = e.args[0] = a0.args[0]; uses.get(a0).add(e); } } } break; case OP_getglobalscope: { if (m.cx.scopes.length == 0) { // global is inner scope 0, so copy that makeCopy(e, unwrapScope(e, 0)); changed = true; } break; } case OP_getscopeobject: { makeCopy(e, unwrapScope(e, 0)); changed = true; break; } case OP_istypelate: { Type t1 = type(types,e.args[1]); if (t1.itype != null && TypeCache.instance().containsNamedType(t1.itype)) { e.op = OP_istype; e.ref = t1.itype.getName(); e.args = new Expr[] { e.args[0] }; e.clearPx(); changed = true; } break; } case OP_istype: { if (TypeCache.instance().containsNamedType(e.ref)) e.clearPx(); break; } case OP_pushscope: case OP_pushwith: { if (!types.get(e.args[0]).nullable) e.clearPx(); break; } case OP_coerce: { Expr a0 = e.args[0]; Typeref t = types.get(e); Typeref t0 = types.get(a0); if (t == t0) { // upcast makeCopy(e, a0); changed = true; } else { Object v0 = values.get(a0); if (v0 == NULL() && t0.nullable && t0.t != VOID()) { makeCopy(e, a0); changed = true; } else { if (TypeCache.instance().namedTypes.get(e.ref) == OBJECT()) { e.op = OP_coerce_o; e.clearEffect(); e.ref = null; e.imm = null; changed = true; } } } break; } // turn findprop into either getglobalscope, getscopeobject, or finddef to expose redundancies case OP_findpropstrict: case OP_findproperty: { int i = findInner(e.ref, e.scopes, types); if (i >= 0) { makeCopy(e, unwrapScope(e,i)); for (Expr s: e.scopes) uses.get(s).remove(e); changed = true; } else if ((i = findOuter(e.ref, m.cx.scopes)) >= 0) { if (i == 0) // getglobalscope { e.op = OP_getglobalscope; e.scopes = noexprs; e.setPure(); for (Expr s: e.scopes) uses.get(s).remove(e); changed = true; } else { // can't change the opcode e.setPure(); // TODO - early bind e.ref } } else if (TypeCache.instance().globals.contains(e.ref)) { e.op = OP_finddef; e.flags = flagTable[e.op]; e.scopes = noexprs; e.ref = TypeCache.instance().globals.getName(e.ref); for (Expr s: e.scopes) uses.get(s).remove(e); changed = true; } /* * TODO: This transformation is too simplistic. * else if (e.op == OP_findproperty) { // will return global if nothing found. if (m.cx.scopes.length == 0) { makeCopy(e, unwrapScope(e,0)); for (Expr s: e.scopes) uses.get(s).remove(e); changed = true; } else { e.op = OP_getglobalscope; for (Expr s: e.scopes) uses.get(s).remove(e); e.scopes = noexprs; e.setPure(); changed = true; } } */ break; } // getsuper should look in base of enclosing type. // if either bind to a final getter, use callstatic. case OP_getproperty: case OP_getsuper: { Typeref t0 = types.get(e.args[0]); Binding bind = t0.findGet(e.ref); if (isSlot(bind)) { e.clearEffect(); if (!t0.nullable) e.clearPx(); e.ref = bind.getName(); if (canEarlyBindSlot(m, bind)) { if (!isConst(bind) || !constify(e, values.get(e))) { e.op = OP_getslot; e.imm = new int[] { bind.slot }; changed = true; } } } else if (bind != null) { // narrow the binding e.ref = bind.getName(); } break; } case OP_initproperty: { Type t0 = type(types,e.args[0]); Object v1 = values.get(e.args[1]); Binding bind = t0.find(e.ref); if (bind != null) { // narrow the binding e.ref = bind.getName(); // isSlot() is to aggressive, breaks (at least) zlib if (isConst(bind) && bind.value != null && bind.value.equals(v1)) { // initializing a slot to it's known default value? // TODO ensure no intervening writes to non-const values makeNop(e); for (Expr a: e.args) uses.get(a).remove(e); } else if (isSlot(bind) && canEarlyBindSlot(m, bind)) { e.op = OP_setslot; e.imm = new int[] { bind.slot }; changed = true; } } break; } case OP_setproperty: case OP_setsuper: { Type t0 = type(types,e.args[0]); Binding bind = t0.find(e.ref); if (isSlot(bind)) { e.ref = bind.getName(); if (canEarlyBindSlot(m, bind)) { e.op = OP_setslot; e.imm = new int[] { bind.slot }; changed = true; } } else if (bind != null) { // narrow the binding e.ref = bind.getName(); } break; } case OP_callproperty: case OP_callproplex: case OP_callsuper: case OP_constructprop: case OP_callpropvoid: { // TODO turn callproplex into callproperty if binding is method Type t0 = type(types,e.args[0]); Binding b0 = t0.findGet(e.ref); if (b0 != null) { // narrow the binding e.ref = b0.getName(); if (e.op == OP_callproperty && isMethod(b0)) { if (t0.isPrimitive() && e.args.length==1 && e.ref.equals(AS3_TOSTRING) && type(types,e) == STRING()) { // TODO this may open up further reductions. how to iterate? // or, need to add similar logic in sccp_eval e.op = OP_convert_s; e.setPure(); changed=true; } else if (canEarlyBindMethod(m,b0) && (t0.isFinal() || b0.isFinal())) { e.op = OP_callstatic; e.m = b0.method; changed=true; } else if (USE_CALLMETHOD && canEarlyBindMethod(m,b0)) { e.op = OP_callmethod; e.imm = new int[] { b0.slot }; changed = true; } } else if (e.op == OP_callproperty && isClass(b0)) { changed |= convertify(e, b0, types); } } if (uses.get(e).isEmpty()) { if (e.op == OP_callsuper) e.op = OP_callsupervoid; if (e.op == OP_callproperty) e.op = OP_callpropvoid; } break; } case OP_convert_u: if (e.args[0].op == OP_convert_i) e.args[0] = e.args[0].args[0]; // fall through case OP_coerce_s: case OP_convert_s: case OP_convert_d: case OP_coerce_o: case OP_convert_b: case OP_convert_i: case OP_coerce_a: { Expr a0 = e.args[0]; Type t = type(types,e); Type t0 = type(types,e.args[0]); if (t == t0) { makeCopy(e,e.args[0]); changed=true; } else if (e.op == OP_convert_i) { if (a0.op == OP_negate) { // convert_i(negate(x)) => negate_i(x) e.op = OP_negate_i; e.args = new Expr[] { a0.args[0] }; changed=true; } else if (a0.op == OP_decrement) { e.op = OP_decrement_i; e.args = new Expr[] { a0.args[0] }; changed = true; } } break; } case OP_subtract: { Object v1 = values.get(e.args[1]); if (doubleValue(v1) == 1) { e.args = new Expr[] { e.args[0] }; e.op = OP_decrement; changed = true; } else if (doubleValue(v1) == -1) { e.args = new Expr[] { e.args[0] }; e.op = OP_increment; changed = true; } break; } case OP_add: { Type t = type(types,e); Object v0 = values.get(e.args[0]); Object v1 = values.get(e.args[1]); if (t.numeric) { if (doubleValue(v0)==1) { e.args = new Expr[] { e.args[1] }; e.op = OP_increment; changed = true; } else if (doubleValue(v1)==1) { e.args = new Expr[] { e.args[0] }; e.op = OP_increment; changed = true; } else if (doubleValue(v0) == -1) { e.args = new Expr[] { e.args[1] }; e.op = OP_decrement; changed = true; } else if (doubleValue(v1) == -1) { e.args = new Expr[] { e.args[0] }; e.op = OP_decrement; changed = true; } } else if (t == STRING()) { if ("".equals(v0)) { e.args = new Expr[] { e.args[1] }; e.op = OP_convert_s; changed = true; } else if ("".equals(v1)) { e.args = new Expr[] { e.args[0] }; e.op = OP_convert_s; changed = true; } } } } if (changed) work.addAll(uses.get(e)); } while (changed); } void sccp_rename(EdgeMap uses, Expr e, Expr[]args) { addTraceAttr(e); for (int i=args.length-1; i >= 0; i--) { Expr a = args[i]; if (a.op == OP_dup) { uses.get(a).remove(e); a = args[i] = a.locals[0]; traceEntry("renamedLocal"); addTraceAttr(a); uses.get(a).add(e); } } } Map verify_types(Method m, Deque code, Map idom) { EdgeMap uses = findUses(code); Map types = new TreeMap(); Set work = new TreeSet(); for (Block b: code) work.addAll(b.exprs); do { Expr e = getExpr(work); if (e.onStack() || e.inLocal() || e.onScope() || e.op==OP_phi) { Typeref tref = verify_eval(m, e, types, idom); if (!tref.equals(types.get(e))) { types.put(e, tref); work.addAll(uses.get(e)); } } } while (!work.isEmpty()); return types; } void sccp_analyze(Method m, EdgeMap uses, Map values, Map types, Set reached) { addTraceAttr("Method", m); Set flowWork = new TreeSet(); Set ssaWork = new TreeSet(); Set ready = new TreeSet(); flowWork.add(m.entry); do { while (!flowWork.isEmpty()) { Edge edge = getEdge(flowWork); if (!reached.contains(edge)) { reached.add(edge); Block b = edge.to; ready.addAll(b.exprs); ssaWork.addAll(b.exprs); for (Edge x: b.xsucc) flowWork.add(x); } } while (!ssaWork.isEmpty()) { Expr e = getExpr(ssaWork); if (ready.contains(e)) { addTraceAttr("Expr", e); sccp_eval(m, e, values, types, flowWork, ssaWork, uses); } } } while (!flowWork.isEmpty()); } void insert_casts(Method m) { Deque code = dfs(m.entry.to); SetMap pred = preds(code); Map idom = idoms(code, pred); m.verifier_types = verify_types(m, code, idom); // TODO this fixes things by inserting upcasts only. We could use // the types we know from sccp_analyze and insert casts that tell // the verifier what we know that it can't figure out on its own. // this can be done expression by expression rather than looking // at phi nodes & splitting critical edges. // it would also be a good sanity check. If the verifier deduces a // more specific type than we have, then we have a bug in either the // verifier or the optimizer. for (Block b: code) { for (Expr e: b) { if (e.op == OP_phi) { Typeref etype = m.verifier_types.get(e); // merged type, possibly mdb of arg types for (int i=e.args.length-1; i >= 0; i--) { Expr a = e.args[i]; Edge p = e.pred[i]; if ( a.onScope() ) continue; Typeref atype = m.verifier_types.get(a); if (isLoop(p, idom) ? !etype.equals(atype) : etype.t.isAtom() != atype.t.isAtom()) { // skip String->String? if((etype.t == atype.t) && etype.nullable) continue; verboseStatus("MISSING CAST " + a + " " + atype+"->"+etype+" on " + p); if (isCritical(p,pred)) { split(p, m, pred); p = e.pred[i]; } // TODO best to insert this right after a? Expr upcast = upcast(a, m, etype.t); append(p, upcast); e.args[i] = upcast; } } } } } verboseStatus("VERIFY TYPES "+m.verifier_types); } Expr upcast(Expr a, Method m, Type t) { if (t == ANY()) { return new Expr(m, OP_coerce_a, a); } else if (t == OBJECT()) { return new Expr(m, OP_coerce_o, a); } return new Expr(m, OP_coerce, t.getName(), a); } /** * visit a single expression. compute it's type and constant value. If * either change, add any dependents to the appropriate work list. * * @param m * @param e * @param values * @param types * @param flowWork * @param ssaWork * @param uses */ void sccp_eval(Method m, Expr e, Map values, Map types, SetflowWork, SetssaWork, EdgeMap uses) { Object v = null; Typeref tref = null; if (e.op == OP_phi) { for (Expr a: e.args) { // compute the phi() meet operation. ignore any inputs we // haven't evaluated yet. If all inputs have the same value, // phi() has that value. Otherwise return BOTTOM. Object av = values.get(a); if (av == null) continue; // ignore TOP inputs if (v == null) v = av; else if (!av.equals(v)) v = BOTTOM; // same idea for types, but if they aren't all the same // then compute the most derived base class (mdb) of the types. Typeref aref = types.get(a); if (tref == null) tref = aref; else if (!tref.equals(aref)) tref = mdb(tref,aref); } } else { // if any arg is TOP result is TOP (unchanged) for (Expr a : e.args) if (!values.containsKey(a)) return; for (Expr a : e.scopes) if (!values.containsKey(a)) return; for (Expr a : e.locals) if (!values.containsKey(a)) return; v = BOTTOM; tref = ANY().ref; switch (e.op) { default: System.err.println("unhandled op:" + e.op + ":"+ opNames[e.op]); assert(false); case OP_hasnext2_o: case OP_nextname: case OP_nextvalue: case OP_call: case OP_callsuper: case OP_getsuper: case OP_getdescendants: break; case OP_convert_o: { tref = types.get(e.args[0]).nonnull(); v = values.get(e.args[0]); break; } case OP_esc_xattr: case OP_esc_xelem: tref = STRING().ref.nonnull(); break; case OP_newcatch: tref = m.handlers[e.imm[0]].activation; break; case OP_newobject: tref = OBJECT().ref.nonnull(); break; case OP_newarray: tref = ARRAY().ref.nonnull(); break; case OP_newactivation: tref = m.activation; break; case OP_getglobalscope: if (m.cx.scopes.length > 0) { tref = m.cx.scopes[0]; } else { // same as getscopeobject<0> v = values.get(e.scopes[0].args[0]); tref = types.get(e.scopes[0].args[0]); } break; case OP_getscopeobject: v = values.get(e.scopes[0].args[0]); tref = types.get(e.scopes[0].args[0]); if ( tref == null ) { // FIXME: Should be more thorough. tref = ANY().ref; } break; case OP_newclass: tref = e.c.ref.nonnull(); break; case OP_newfunction: tref = FUNCTION().ref.nonnull(); break; case OP_finddef: if (TypeCache.instance().globals.contains(e.ref)) tref = TypeCache.instance().globals.get(e.ref); break; case OP_findpropstrict: case OP_findproperty: { int i = findInner(e.ref, e.scopes, types); if (i >= 0) { v = values.get(e.scopes[i]); tref = types.get(e.scopes[i]); } else if ((i = findOuter(e.ref, m.cx.scopes)) >= 0) { tref = m.cx.scopes[i]; } else if (TypeCache.instance().globals.contains(e.ref)) { tref = TypeCache.instance().globals.get(e.ref); } else { // not found. use global. if (m.cx.scopes.length > 0) { tref = m.cx.scopes[0]; } else { v = values.get(e.scopes[0]); tref = types.get(e.scopes[0]); } } break; } case OP_getlex: { // findproperty + getproperty int i = findInner(e.ref, e.scopes, types); Typeref stref = i >= 0 ? types.get(e.scopes[i]) : (i=findOuter(e.ref, m.cx.scopes)) >= 0 ? m.cx.scopes[i] : TypeCache.instance().globals.contains(e.ref) ? TypeCache.instance().globals.get(e.ref) : m.cx.scopes.length > 0 ? m.cx.scopes[0] : types.get(e.scopes[0]); Binding b = stref.t.findGet(e.ref); // code below is a copy of OP_getproperty if (isSlot(b)) { // TODO we only compute const value here if primitive type. // it would be more correct if we knew whether the initializer // changed the const value. (consts can be computed in init). tref = b.type; if (isConst(b) && b.defaultValueChanged()) v = b.value; } else if (isMethod(b)) { // TODO if base type is or might be XML, return ANY // TODO use MethodClosure, more specific than Function tref = FUNCTION().ref.nonnull(); } else if (isGetter(b)) { tref = b.method.returns; } break; } case OP_construct: { tref = OBJECT().ref.nonnull(); break; } case OP_constructprop: { Type ot = type(types,e.args[0]); // type of base object Binding b = ot.findGet(e.ref); if (b != null && b.type != null && b.type.t.itype != null) { tref = b.type.t.itype.ref.nonnull(); break; } break; } case OP_callproperty: case OP_callproplex: { Type ot = type(types, e.args[0]); Binding b = ot.findGet(e.ref); if (isMethod(b)) { tref = b.method.returns; } else if (isSlot(b) && b.type != null) { // each of these has same logic as convert_i, convert_s, etc if (b.type.t.itype == INT()) { tref = INT().ref; if ( e.args.length > 1) v = eval_convert_i(values.get(e.args[1])); } else if (b.type.t.itype == UINT()) { tref = UINT().ref; if ( e.args.length > 1) v = eval_convert_u(values.get(e.args[1])); } else if (b.type.t.itype == STRING()) { tref = STRING().ref.nonnull(); if ( e.args.length > 1) v = eval_convert_s(values.get(e.args[1])); } else if (b.type.t.itype == BOOLEAN()) { tref = BOOLEAN().ref; if ( e.args.length > 1) v = eval_convert_b(values.get(e.args[1])); } else if (b.type.t.itype == NUMBER()) { tref = NUMBER().ref; if ( e.args.length > 1) v = eval_convert_d(values.get(e.args[1])); } } break; } case OP_applytype: tref = types.get(e.args[0]).nonnull(); break; case OP_callstatic: tref = e.m.returns; break; case OP_arg: if (e.imm[0] < m.getParams().length) tref = m.getParams()[e.imm[0]]; else if (m.needsArguments()||m.needsRest() && e.imm[0] == m.getParams().length) tref = ARRAY().ref.nonnull(); else tref = VOID().ref; break; case OP_xarg: tref = m.handlers[e.imm[0]].type; break; case OP_getslot: { Type t0 = type(types, e.args[0]); Binding b = t0.findSlot(e.imm[0]); if (b != null) tref = b.type; break; } case OP_getproperty: { Type t0 = type(types, e.args[0]); Binding b = t0.findGet(e.ref); if (isSlot(b)) { // TODO we only compute const value here if primitive type. // it would be more correct if we knew whether the initializer // changed the const value. (consts can be computed in init). tref = b.type; if (isConst(b) && b.defaultValueChanged()) v = b.value; } else if (isMethod(b)) { // TODO if base type is or might be XML, return ANY // TODO use MethodClosure, more specific than Function tref = FUNCTION().ref.nonnull(); } else if (isGetter(b)) { tref = b.method.returns; } break; } case OP_pushundefined: v = e.value; tref = VOID().ref; break; case OP_pushnull: v = e.value; tref = NULL().ref; break; case OP_pushtrue: case OP_pushfalse: v = e.value; tref = BOOLEAN().ref; break; case OP_pushbyte: case OP_pushshort: case OP_pushint: v = e.value; tref = INT().ref; break; case OP_pushuint: v = e.value; tref = UINT().ref; break; case OP_pushstring: v = e.value; tref = STRING().ref.nonnull(); break; case OP_pushnan: case OP_pushdouble: v = e.value; tref = NUMBER().ref; break; case OP_pushnamespace: v = e.value; tref = NAMESPACE().ref.nonnull(); break; case OP_jump: flowWork.add(e.succ[0]); return; case OP_lookupswitch: { Object v1 = values.get(e.args[0]); if (v1 == BOTTOM) for (Edge s: e.succ) flowWork.add(s); else { // input is const int i = intValue(v1); if (i < 0 || i >= e.succ.length-1) i = e.succ.length-1; flowWork.add(e.succ[i]); } return; } case OP_iffalse: case OP_iftrue: { Object v1 = values.get(e.args[0]); if (v1 == BOTTOM) { flowWork.add(e.succ[0]); flowWork.add(e.succ[1]); } else if (e.op == OP_iffalse) flowWork.add(e.succ[booleanValue(v1) ? 0 : 1]); else if (e.op == OP_iftrue) flowWork.add(e.succ[booleanValue(v1) ? 1 : 0]); return; } case OP_pushscope: case OP_pushwith: // treat this as a copy. v = values.get(e.args[0]); tref = types.get(e.args[0]).nonnull(); break; case OP_convert_b: tref = BOOLEAN().ref; v = eval_convert_b(values.get(e.args[0])); break; case OP_not: { tref = BOOLEAN().ref; Object v0 = values.get(e.args[0]); if (v0 != BOTTOM) v = booleanValue(v0) ? FALSE : TRUE; break; } case OP_deleteproperty: // TODO result is const false for any declared property case OP_deldescendants: case OP_hasnext: case OP_hasnext2: case OP_equals: case OP_strictequals: case OP_in: case OP_istype: case OP_istypelate: case OP_instanceof: tref = BOOLEAN().ref; break; case OP_lessthan: case OP_lessequals: case OP_greaterthan: case OP_greaterequals: { tref = BOOLEAN().ref; Object v0 = values.get(e.args[0]); Object v1 = values.get(e.args[1]); if (v0.equals(NAN) || v0 == UNDEFINED || v1.equals(NAN) || v1 == UNDEFINED) v = FALSE; else if (v0 != BOTTOM && v1 != BOTTOM) v = e.op == OP_lessthan ? lessthan(v0,v1) : e.op == OP_lessequals ? !lessthan(v1,v0) : e.op == OP_greaterthan ? lessthan(v1,v0) : !lessthan(v0,v1); break; } case OP_convert_s: tref = STRING().ref.nonnull(); v = eval_convert_s(values.get(e.args[0])); break; case OP_coerce_s: { tref = eval_coerce_s(types.get(e.args[0])); v = eval_coerce_s(values.get(e.args[0])); break; } case OP_coerce_o: { Typeref t0 = types.get(e.args[0]); tref = eval_coerce_o(t0); v = eval_coerce_o(values.get(e.args[0]), t0.t); break; } case OP_coerce_a: { // This cast has meaning if it's casting from void. // Otherwise, it's an upcast and can be removed; // casts will be re-inserted as appropriate. if ( ! (types.get(e.args[0]).equals(VOID().ref) ) ) { v = values.get(e.args[0]); tref = types.get(e.args[0]); } else { tref = ANY().ref; } break; } case OP_coerce: { Typeref t0 = types.get(e.args[0]); Object v0 = values.get(e.args[0]); Type t = TypeCache.instance().namedTypes.get(e.ref); assert ( t != null ); if (t == STRING()) { tref = eval_coerce_s(t0); v = eval_coerce_s(v0); } else if (t == OBJECT()) { tref = eval_coerce_o(t0); v = eval_coerce_o(v0,t0.t); } else if (t == INT()) { tref = t.ref; v = eval_convert_i(v0); } else if (t == UINT()) { tref = t.ref; v = eval_convert_u(v0); } else if (t == NUMBER()) { tref = t.ref; v = eval_convert_d(v0); } else if (t == BOOLEAN()) { tref = t.ref; v = eval_convert_b(v0); } else { // pointer style cast if (t0.t.extendsOrIsBase(t)) { // ignore upcasts tref = t0; v = v0; } else if (t0.t == NULL() || t0.t == VOID()) { tref = NULL().ref; } else { tref = t.ref; } } break; } case OP_astype: // TODO constant folding tref = TypeCache.instance().namedTypes.get(e.ref).ref; break; case OP_astypelate: { Typeref t1 = types.get(e.args[1]); if (t1.t.itype != null) { if (t1.t.itype.atom || t1.t.itype.numeric) tref = OBJECT().ref; else tref = t1.t.itype.ref; } else { tref = ANY().ref; } break; } case OP_typeof: { Type t0 = type(types,e.args[0]); if (t0 == INT() || t0 == UINT() || t0 == NUMBER()) v = "number"; else if (t0 == STRING()) v = "string"; else if (t0.extendsOrIsBase(XML()) || t0.extendsOrIsBase(XMLLIST())) v = "xml"; else if (t0 == VOID()) v = "undefined"; else if (t0 == BOOLEAN()) v = "boolean"; else if (t0.extendsOrIsBase(FUNCTION())) v = "function"; else if (t0 != OBJECT() && t0.extendsOrIsBase(OBJECT())) v = "object"; tref = STRING().ref.nonnull(); break; } case OP_add: { Expr a0 = e.args[0]; Expr a1 = e.args[1]; Typeref t0 = types.get(a0); Typeref t1 = types.get(a1); Object v0 = values.get(a0); Object v1 = values.get(a1); if (t0.t == STRING() && !t0.nullable || t1.t == STRING() && !t1.nullable) { tref = STRING().ref.nonnull(); if (v0 != BOTTOM && v1 != BOTTOM) v = stringValue(v0) + stringValue(v1); } else if (t0.t.numeric && t1.t.numeric) { tref = NUMBER().ref; if (v0 instanceof Number && v1 instanceof Number) v = doubleValue(v0) + doubleValue(v1); } else { // TODO make all primitives extend a type so we can use that type here. tref = OBJECT().ref.nonnull(); // will be a String or a Number } break; } case OP_divide: { tref = NUMBER().ref; Object v0 = values.get(e.args[0]); Object v1 = values.get(e.args[1]); if (v0 instanceof Number && v1 instanceof Number) v = doubleValue(v0) / doubleValue(v1); break; } case OP_subtract: case OP_multiply: case OP_modulo: case OP_negate: case OP_increment: case OP_decrement: tref = NUMBER().ref; break; case OP_convert_d: tref = NUMBER().ref; v = eval_convert_d(values.get(e.args[0])); break; case OP_convert_i: tref = INT().ref; v = eval_convert_i(values.get(e.args[0])); break; case OP_convert_u: tref = UINT().ref; v = eval_convert_u(values.get(e.args[0])); break; case OP_bitor: { tref = INT().ref; Object v0 = values.get(e.args[0]); Object v1 = values.get(e.args[1]); if (v0 instanceof Number && v1 instanceof Number) v = intValue(v0) | intValue(v1); break; } case OP_bitand: { tref = INT().ref; Object v0 = values.get(e.args[0]); Object v1 = values.get(e.args[1]); if (v0 instanceof Number && v1 instanceof Number) { v = intValue(v0) & intValue(v1); } break; } case OP_bitnot: case OP_add_i: case OP_subtract_i: case OP_multiply_i: case OP_negate_i: case OP_bitxor: case OP_lshift: case OP_rshift: case OP_hasnext2_i: case OP_increment_i: case OP_decrement_i: // TODO constant folding tref = INT().ref; break; case OP_urshift: // TODO constant folding tref = UINT().ref; break; // these ops do not produce any value case OP_setslot: case OP_setproperty: case OP_setsuper: //case OP_setglobalslot: // deprecated case OP_initproperty: case OP_callpropvoid: case OP_constructsuper: case OP_callsupervoid: case OP_returnvoid: case OP_returnvalue: case OP_throw: case OP_popscope: case OP_debug: case OP_debugline: case OP_debugfile: case OP_bkpt: case OP_bkptline: case OP_checkfilter: return; } } assert(tref != null && tref.t != null); // singleton types have a specific value. if (tref.t == VOID()) v = UNDEFINED; else if (tref.t == NULL()) v = NULL(); if (v != null && !v.equals(values.get(e))) { values.put(e, v); ssaWork.addAll(uses.get(e)); } if (!tref.equals(types.get(e))) { types.put(e, tref); ssaWork.addAll(uses.get(e)); } } Typeref verify_eval(Method m, Expr e, Map types, Map idom) { Typeref tref = null; if (e.op == OP_phi) { boolean loop = false; for (int i=e.args.length-1; i >= 0; i--) { Expr a = e.args[i]; loop |= isLoop(e.pred[i],idom); // compute the phi() meet operation. ignore any inputs we // haven't evaluated yet. If all inputs have the same value, // phi() has that value. Otherwise return BOTTOM. // same idea for types, but if they aren't all the same // then compute the most derived base class (mdb) of the types. Typeref aref = types.get(a); if (aref == null) continue; // ignore unprocessed inputs if (tref == null) tref = aref; else if (!tref.equals(aref)) tref = mdb(tref,aref); } if ( null == tref ) { tref = ANY().ref; } // make nullable types nullable at top of loop so verifier // won't ever need to iterate. if (loop) tref = tref.t.ref; } else { tref = ANY().ref; // if any arg is TOP result is TOP (unchanged) for (Expr a : e.args) if (!types.containsKey(a)) return tref; for (Expr a : e.scopes) if (!types.containsKey(a)) return tref; for (Expr a : e.locals) if (!types.containsKey(a)) return tref; switch (e.op) { default: assert(false); case OP_hasnext2_o: case OP_nextname: case OP_nextvalue: case OP_call: case OP_getsuper: case OP_getdescendants: tref = ANY().ref; break; case OP_convert_o: // bug in verifier -- doesn't set state nonnull here. tref = types.get(e.args[0]); //tref = types.get(e.args[0]).nonnull(); break; case OP_esc_xattr: case OP_esc_xelem: tref = STRING().ref.nonnull(); break; case OP_newcatch: tref = m.handlers[e.imm[0]].activation; break; case OP_newobject: tref = OBJECT().ref.nonnull(); break; case OP_newarray: tref = ARRAY().ref.nonnull(); break; case OP_newactivation: tref = m.activation; break; case OP_getglobalscope: if (m.cx.scopes.length > 0) { tref = m.cx.scopes[0]; } else { // same as getscopeobject<0> tref = types.get(e.scopes[0].args[0]); } break; case OP_getscopeobject: tref = types.get(e.scopes[0].args[0]); break; case OP_newclass: tref = e.c.ref.nonnull(); break; case OP_newfunction: tref = FUNCTION().ref.nonnull(); break; case OP_finddef: if (TypeCache.instance().globals.contains(e.ref)) tref = TypeCache.instance().globals.get(e.ref); break; case OP_findpropstrict: case OP_findproperty: { int i = findInner(e.ref, e.scopes, types); if (i >= 0) { tref = types.get(e.scopes[i]); } else if ((i = findOuter(e.ref, m.cx.scopes)) >= 0) { tref = m.cx.scopes[i]; } else if (TypeCache.instance().globals.contains(e.ref)) { tref = TypeCache.instance().globals.get(e.ref); } else { // not found. use global. if (m.cx.scopes.length > 0) { tref = m.cx.scopes[0]; } else { tref = types.get(e.scopes[0]); } } break; } case OP_getlex: { // findproperty + getproperty int i = findInner(e.ref, e.scopes, types); Typeref stref = i >= 0 ? types.get(e.scopes[i]) : (i=findOuter(e.ref, m.cx.scopes)) >= 0 ? m.cx.scopes[i] : TypeCache.instance().globals.contains(e.ref) ? TypeCache.instance().globals.get(e.ref) : m.cx.scopes.length > 0 ? m.cx.scopes[0] : types.get(e.scopes[0]); Binding b = stref.t.findGet(e.ref); tref = verify_eval_getproperty(tref, b); break; } case OP_construct: { Type base_type = type(types,e.args[0]); if ( base_type.itype != null ) tref = base_type.itype.ref.nonnull(); else tref = base_type.ref.nonnull(); break; } case OP_constructprop: { Type ot = type(types,e.args[0]); // type of base object Binding b = ot.findGet(e.ref); if (b != null && b.type != null && b.type.t.itype != null) { tref = b.type.t.itype.ref.nonnull(); break; } break; } case OP_callproperty: case OP_callproplex: { Type ot = type(types, e.args[0]); Binding b = ot.findGet(e.ref); if (isMethod(b)) { tref = b.method.returns; } else if (isSlot(b) && b.type != null && b.type.t.itype != null) { // calling a class as a function, return type is cast to instance type // issue what about special cases? RegExp? Date? tref = b.type.t.itype.ref; } break; } case OP_callsuper: { Type ot = m.cx.base; Binding b = ot.findGet(e.ref); if (isMethod(b)) { tref = b.method.returns; } break; } case OP_applytype: tref = types.get(e.args[0]).nonnull(); break; case OP_callstatic: tref = e.m.returns; break; case OP_arg: if (e.imm[0] < m.getParams().length) tref = m.getParams()[e.imm[0]]; else if (m.needsArguments()||m.needsRest() && e.imm[0] == m.getParams().length) tref = ARRAY().ref.nonnull(); else tref = VOID().ref; break; case OP_xarg: tref = m.handlers[e.imm[0]].type; break; case OP_getslot: { Type t0 = type(types, e.args[0]); Binding b = t0.findSlot(e.imm[0]); if (b != null) tref = b.type; break; } case OP_getproperty: { Type t0 = type(types, e.args[0]); Binding b = t0.findGet(e.ref); tref = verify_eval_getproperty(tref, b); break; } case OP_kill: tref = ANY().ref; break; case OP_pushundefined: tref = VOID().ref; break; case OP_pushnull: tref = NULL().ref; break; case OP_pushnamespace: tref = NAMESPACE().ref.nonnull(); break; case OP_pushscope: case OP_pushwith: // treat this as a copy. tref = types.get(e.args[0]).nonnull(); break; case OP_pushtrue: case OP_pushfalse: case OP_convert_b: case OP_not: case OP_deleteproperty: case OP_deldescendants: case OP_hasnext: case OP_hasnext2: case OP_equals: case OP_strictequals: case OP_in: case OP_istype: case OP_istypelate: case OP_instanceof: case OP_lessthan: case OP_lessequals: case OP_greaterthan: case OP_greaterequals: tref = BOOLEAN().ref; break; case OP_convert_s: case OP_pushstring: tref = STRING().ref.nonnull(); break; case OP_coerce_s: { Typeref t0 = types.get(e.args[0]); tref = new Typeref(STRING(), t0.nullable); break; } case OP_coerce_o: { Typeref t0 = types.get(e.args[0]); tref = new Typeref(OBJECT(), t0.nullable); break; } case OP_coerce_a: { Typeref t0 = types.get(e.args[0]); tref = new Typeref(ANY(), t0.nullable); break; } case OP_coerce: tref = TypeCache.instance().namedTypes.get(e.ref).ref; break; case OP_astype: { Typeref t0 = types.get(e.args[0]); Type t = TypeCache.instance().namedTypes.get(e.ref); if (!t0.t.extendsOrIsBase(t) || t0.t.isAtom() != t.isAtom()) { // TODO figure out what verifier is really doing here. tref = t.ref; } else { tref = t0; } break; } case OP_astypelate: { Typeref t1 = types.get(e.args[1]); if (t1.t.itype != null) { if (t1.t.itype.atom || t1.t.itype.numeric) tref = OBJECT().ref; else tref = t1.t.itype.ref; } else { tref = ANY().ref; } break; } case OP_typeof: tref = STRING().ref.nonnull(); break; case OP_add: { Expr a0 = e.args[0]; Expr a1 = e.args[1]; Typeref t0 = types.get(a0); Typeref t1 = types.get(a1); if (t0.t == STRING() && !t0.nullable || t1.t == STRING() && !t1.nullable) { tref = STRING().ref.nonnull(); } else if (t0.t.numeric && t1.t.numeric) { tref = NUMBER().ref; } else { // TODO make all primitives extend a type so we can use that type here. tref = OBJECT().ref.nonnull(); // will be a String or a Number } break; } case OP_divide: case OP_subtract: case OP_multiply: case OP_modulo: case OP_negate: case OP_increment: case OP_decrement: case OP_convert_d: case OP_pushnan: case OP_pushdouble: tref = NUMBER().ref; break; case OP_convert_i: case OP_bitor: case OP_bitand: case OP_add_i: case OP_subtract_i: case OP_multiply_i: case OP_negate_i: case OP_bitxor: case OP_lshift: case OP_rshift: case OP_hasnext2_i: case OP_increment_i: case OP_decrement_i: case OP_pushbyte: case OP_pushshort: case OP_pushint: case OP_bitnot: tref = INT().ref; break; case OP_pushuint: case OP_convert_u: case OP_urshift: tref = UINT().ref; break; } } assert(tref != null && tref.t != null); return tref; } private Typeref verify_eval_getproperty(Typeref tref, Binding b) { if (isSlot(b)) { tref = b.type; } else if (isMethod(b)) { //tref = FUNCTION().ref.nonnull(); // TODO use MethodClosure // avmplus uses ANY here. see Verifier::readBinding(). tref = ANY().ref; } else if (isGetter(b)) { tref = b.method.returns; } return tref; } boolean isCritical(Edge e, SetMappred) { return e.from.succ().length > 1 && pred.get(e.to).size() > 1; } /** * * @param e - the edge to split. * @post e points at the new block. * @param m - the containing Method. * @param pred - predecessors. Not entirely relevant... * @return the Edge from the new block to e's original "to." */ Edge split(Edge e, Method m, SetMappred) { assert(e.handler == null); // can't split exception edges Expr j = new Expr(m, OP_jump); Block d = new Block(m); Block to = e.to; Edge e2 = new Edge(m,d,0,to); j.succ = new Edge[] { e2 }; d.add(j); verboseStatus("SPLIT "+e + " ... " + d + ", " + e2); e.to = d; pred.get(d).add(e); pred.get(to).remove(e); pred.get(to).add(e2); replacePred(to,e,e2); return e2; } void replacePred(Block b, Edge before, Edge after) { for (Expr e: b) { if (e.op == OP_phi) { for (int i=0, n=e.pred.length; i < n; i++) if (e.pred[i] == before) e.pred[i] = after; } } } Expr append(Edge edge, Expr e) { edge.from.appendExpr(e); return e; } Expr prepend(Edge edge, Expr e) { Deque exprs = edge.from.exprs; exprs.addFirst(e); return e; } Expr setlocal(Method m, int i, Expr a) { return new Expr(m, OP_setlocal, i, new Expr[] { a }, 1, 1); } Expr getlocal(Method m, int i) { return new Expr(m, OP_getlocal, i); } Expr dup(Method m, Expr e) { Expr dup = new Expr(m, OP_dup); dup.locals = new Expr[] { e }; return dup; } /** * the last phase before emitting code. * - stack scheduling * - scope scheduling * - assign local variables * - replace phi's with copies if necessary * - recompute frame size * @param code */ void remove_phi(Method m) { Deque code = dfs(m.entry.to); SetMap pred = preds(code); Map locals = new TreeMap(); Map> exprs = new TreeMap>(); ConflictGraph conflicts = new ConflictGraph(); printMethod(m, "BEFORE SCHED"); addTraceAttr(m); restused: if (m.needsArguments() || m.needsRest()) { // if we have a rest param or arguments and we don't use it, // clear those flags and set the ignore-extra-args flag. int rest = m.getParams().length; for (Expr e: m.entry.to) if (e.op == OP_arg && e.imm[0] == rest) break restused; m.flags &= ~(METHOD_Arguments|METHOD_Needrest); m.flags |= METHOD_IgnoreRest; verboseStatus("IGNORE_REST for "+m.getName()); } int max_local = m.getParams().length-1; sched_greedy(m, code, locals, pred, exprs, conflicts); alloc_locals(code, locals, conflicts, m.fixedLocals); // insert phi copies on edges where needed Set splits = new TreeSet(); for (Block b: code) { // identify the edges that need copies, split them, add copies. // only split an edge once during this whole pass. for (Expr e: b) { if (e.op != OP_phi) break; if (!locals.containsKey(e.id)) continue; addTraceAttr(e); int lhs = locals.get(e.id); for (int i=e.args.length-1; i>=0; i--) { traceEntry("PhiInput"); addTraceAttr("i", i); addTraceAttr(e.args[i]); int rhs = locals.get(e.args[i].id); if (lhs != rhs) { Edge p = e.pred[i]; if (!splits.contains(p)) { split(p,m,pred); splits.add(p = e.pred[i]); } traceEntry("copyPhiInput"); addTraceAttr("lhs", lhs); addTraceAttr("rhs", rhs); Expr get = getlocal(m, rhs); prepend(p, get); append(p, setlocal(m,lhs,get)); } } } // now swap in the scheduled code and renumber the get/setlocals we have in there. b.exprs = exprs.get(b); for ( Expr e: b.exprs) { // assign locals & update local_count int loc = max_local; if (e.op == OP_getlocal || e.op == OP_setlocal) { loc = e.imm[0] = locals.get(e.imm[0]); } else if (e.op == OP_hasnext2) { int loc0 = locals.get(e.locals[0].id); int loc1 = locals.get(e.locals[1].id); e.imm = new int[] { loc0, loc1 }; loc = loc0 > loc1 ? loc0 : loc1; } if (loc > max_local) max_local = loc; } } m.local_count = max_local+1; // some of the edges we split didn't need to be. cfgopt(m); printMethod(m, "AFTER SCHED"); } /** * Compute a Method's max_stack and max_scope settings. * @param m - the Method of interest. * @post m.max_stack and m_max_scope set. * @note Factored out of remove_phi so that the verifier * appeasment logic can safely issue getlocal insns. */ void computeFrameCounts(Method m) { Deque code = dfs(m.entry.to); int max_stack = 0; int max_scope = 0; Mapstkin = new TreeMap(); Mapscpin = new TreeMap(); stkin.put(m.entry.to, 0); scpin.put(m.entry.to, 0); for ( Block b: code ) { int stkdepth = stkin.get(b); int scpdepth = scpin.get(b); for (Expr e: b) { assert(!e.isSynthetic()); // compute max_stack assert(stkdepth >= e.args.length); stkdepth -= e.args.length; if (e.onStack()) { stkdepth++; } if (stkdepth > max_stack) max_stack = stkdepth; // compute max_scope assert(scpdepth >= e.scopes.length); if (e.op == OP_popscope) scpdepth--; else if (e.onScope()) scpdepth++; if (scpdepth > max_scope) max_scope = scpdepth; } for (Edge s: b.succ()) update_depth(s.to, stkdepth, stkin, scpdepth, scpin); for (Edge s: b.xsucc) update_depth(s.to, 1, stkin, 0, scpin); } m.max_stack = max_stack; m.max_scope = max_scope; } /** * Work around legacy verifier restrictions: * Kill predecessor blocks' locals if they're live out * on more than one path and not live in to a block. * @param m - the Method under analysis. */ void appeaseLegacyVerifier(Method m) { addTraceAttr(m); Deque code = schedule(m.entry.to); SetMap pred = preds(code); Set single_path_to_exit = new HashSet(); Map reg_state_by_block = getLocalVarState(m); TypeConstraintMap constraints = new TypeConstraintMap(); // Create type constraints: // Find edges where locals' types // conflict with the expected type, which // may be the consensus type for the local // in the block or may be specific to the // block. Apply coercions as necessary. for ( Block b: code) { verboseStatus("Building constraints for " + b); LocalVarState block_state = reg_state_by_block.get(b); assert (block_state != null); BitSet active = block_state.getActiveVariables(); // Kill active variables that aren't in a successor // block's live-in set. for ( Edge s:b.succ()) { if ( singlePathToExit(s, pred, single_path_to_exit)) { // No possibliity of conflict. continue; } Block successor = s.to; LocalVarState to_state = reg_state_by_block.get(successor); assert ( to_state != null); TypeConstraints tc = constraints.getConstraints(s); BitSet to_livein = to_state.getLivein(); for ( Integer r : foreach(active) ) { if ( !( to_livein.get(r) || m.fixedLocals.values().contains(r) ) ) { // If the target block redefines this variable, // and all incoming types agree, then the kill // is redundant. if ( to_state.def.get(r) || to_state.killed_vars.get(r) ) { Typeref first_incoming_type = to_state.getInitialType(r); for ( Edge p: pred.get(successor) ) { boolean needs_kill; // TODO: It should be possible to extend this // "zone of protection" to more than one // predecessor block, but the verifier rejects it. needs_kill = pred.get(successor).size() > 1; /* Typeref pred_incoming_type = reg_state_by_block.get(p.from).getFinalType(r); if ( successor.is_backwards_branch_target ) needs_kill = !first_incoming_type.equals(pred_incoming_type); else needs_kill = !first_incoming_type.t.isMachineCompatible(pred_incoming_type.t); // TODO: Need better analysis of when ANY means ANY and when it means "low." needs_kill |= pred_incoming_type.t.equals(ANY); */ if ( needs_kill ) { // TODO: These can be largely eliminated // when the verifier gets smarter. tc.addKill(r); break; } } } else { tc.addKill(r); } } } } // Analyze the types of live-in variables; form an // objective input type, then coerce as necessary // to get to that type. BitSet livein = block_state.getLivein(); for ( Integer r : foreach(livein) ) { Typeref consensus_type = block_state.getInitialType(r); assert(consensus_type != null); for ( Edge p: pred.get(b)) { LocalVarState from_state = reg_state_by_block.get(p.from); assert( from_state != null); consensus_type = typeMeet(consensus_type, from_state.getFinalType(r)); } for ( Edge p: pred.get(b)) { LocalVarState from_state = reg_state_by_block.get(p.from); assert( from_state != null); TypeConstraints tc = constraints.getConstraints(p); if ( block_state.hard_coercions[r] != null ) { tc.addCoercion(r, block_state.hard_coercions[r]); } else if ( needsCoercion(m, consensus_type, from_state.getFinalType(r), b.is_backwards_branch_target )) { tc.addCoercion(r, consensus_type); } } } } // Find kills and coercions that can be done in the // in the source block instead of the target blocks. // TODO: Reach back through exblocks? for ( Block b: code ) { LocalVarState block_state = reg_state_by_block.get(b); assert (block_state != null); BitSet active = block_state.getActiveVariables(); TypeConstraints source_block_constraints = null; for ( Integer r: foreach(active)) { TypeConstraints first_constraint = null; boolean all_constraints_agree = true; for ( Edge s:b.succ() ) { TypeConstraints tc = constraints.getConstraints(s); if ( null == first_constraint ) { first_constraint = tc; } // If the active register isn't in the constraint set, // then this will be false, and thus it's necessary to // ask the first constraint if it agrees with itself. all_constraints_agree = first_constraint.agreesWith(tc, r); if ( !all_constraints_agree ) break; } if ( all_constraints_agree ) { if ( null == source_block_constraints ) source_block_constraints = new TypeConstraints(null); for ( Edge s: b.succ()) { source_block_constraints.takeConstraintFrom(constraints.get(s), r); } } } if ( source_block_constraints != null ) fixConstraints(m, b, source_block_constraints, block_state); } // Fix any remaining constraints by // splitting the affected edge and applying // constraints to the new block. // TODO: These blocks should be amenable to pooling. for ( Block b: code ) { for ( Edge p:b.succ() ) { // Split the liveout block, and apply // the constraints to the split block. TypeConstraints tc = constraints.getConstraints(p); if ( tc != null && tc.killregs.size() > 0 || tc.coercions.size() > 0 ) { split(p, m, pred); p.to.must_isolate_block = true; fixConstraints(m, p.to, tc, null); } } } } boolean singlePathToExit(Edge s, SetMap pred, Set known_single_paths) { Block b = s.to; if ( pred.get(b).size() > 1 ) return false; else if ( known_single_paths.contains(s) ) return true; boolean single_path = false; // not a control value, compiler appeasement if ( b.succ() == noedges ) single_path = true; else { for ( Edge s_prime: b.succ() ) { single_path = singlePathToExit(s_prime, pred, known_single_paths); if ( !single_path ) break; } } if ( single_path ) { known_single_paths.add(s); } return single_path; } boolean needsCoercion(Method m, Typeref to_ty, Typeref from_ty, boolean backwards_branch) { if ( to_ty.equals(from_ty) || ignoreTypeConflict(m, to_ty, from_ty) ) return false; if ( isNumericType(from_ty) && isNumericType(to_ty)) return false; boolean needs_coercion; Typeref merged_type = typeMerge(to_ty, from_ty); if ( null == merged_type ) { // No sensible meet of these types, // coercion necessary. needs_coercion = true; } else if ( backwards_branch ) { // FIXME: The type modeling in LocalVarState // needs to account for cross-block nullable changes. needs_coercion = true; //needs_coercion = ! from_ty.equals(to_ty); } else { needs_coercion = !to_ty.t.isMachineCompatible(merged_type.t); } return needs_coercion; } private boolean isNumericType(Typeref ty) { return ty.t.numeric; } /** * Ignore type conflicts that are probably due to other bugs. * @param m * @param liveinType - the suspect type. * @param from_ty * @return true if the type appears to be bogus. * @warn this routine is bogus. */ boolean ignoreTypeConflict(Method m, Typeref to_ty, Typeref from_ty) { boolean result = to_ty.t.getName().name.startsWith("global") && from_ty.t.getName().name.startsWith("global"); result |= from_ty.t.equals(m.activation.t) && to_ty.t.equals(m.activation.t); return result; } /** * Fix type constraints for a block. * @param m - the Method that contains the Block. * @param b - the Block to be fixed. * @param bc - the Block's constraints. * @param block_state */ void fixConstraints(Method m, Block b, TypeConstraints bc, LocalVarState block_state) { verboseStatus("fixConstraints " + b ); // A fair number of expressions can be coerced // when they're defined. Map coerce_in_place = new HashMap(); if ( block_state != null ) { Set coerced_locals = new HashSet(bc.coercions.keySet()); for ( Integer r: coerced_locals ) { if ( ! block_state.read_after_def.get(r)) { Expr generator = block_state.generating_exprs.get(r); if ( generator != null ) { coerce_in_place.put(generator, coerceExpr(m, bc.coercions.get(r).t, generator)); bc.coercions.remove(r); } } } if ( !coerce_in_place.isEmpty() ) { Deque replaced_exprs = new ArrayDeque(); while ( !b.exprs.isEmpty()) { Expr ex = b.exprs.removeFirst(); if ( coerce_in_place.containsKey(ex)) { replaced_exprs.add(coerce_in_place.get(ex)); coerce_in_place.remove(ex); } replaced_exprs.add(ex); } assert(coerce_in_place.isEmpty()); b.exprs = replaced_exprs; } } Expr last = b.succ().length > 0? b.exprs.removeLast(): null; for ( Integer regnum: bc.coercions.keySet() ) { Typeref ty = bc.coercions.get(regnum); if ( ty.equals(VOID().ref) ) { Expr void_expr = new Expr(m, OP_pushundefined); b.exprs.add(void_expr); b.exprs.add(setlocal(m, regnum, void_expr)); } if ( ty.equals(NULL().ref) ) { Expr void_expr = new Expr(m, OP_pushnull); b.exprs.add(void_expr); b.exprs.add(setlocal(m, regnum, void_expr)); } else { Expr getlocal = getlocal(m, regnum); b.exprs.add(getlocal); Expr coerce_expr = coerceExpr(m, ty.t, getlocal); b.exprs.add(coerce_expr); b.exprs.add(setlocal(m, regnum, coerce_expr)); } verboseStatus("\tlocal " + regnum); } for ( Integer k: bc.killregs ) { b.exprs.add(new Expr(m, OP_kill, k.intValue())); verboseStatus("kill " + k); } if ( last != null ) b.exprs.add(last); } Expr coerceExpr(Method m, Type t, Expr a) { Expr result = null; assert(t != null); if ( ANY().equals(t)) result = new Expr(m, OP_coerce_a, a); else if (VOID().equals(t) ) result = new Expr(m, OP_pushundefined); else if ( NULL().equals(t) ) result = new Expr(m, OP_pushnull); else if ( INT().equals(t)) result = new Expr(m, OP_convert_i, a); else if ( OBJECT().equals(t)) result = new Expr(m, OP_coerce_o, a); else if ( STRING().equals(t)) result = new Expr(m, OP_coerce_s, a); else { result = new Expr(m, OP_coerce, t.getName(), a); } verboseStatus("coerceExpr " + formatExpr(result)); return result; } void alloc_locals(Deque code, Map locals, ConflictGraph conflicts, Map fixed_locals) { for (Block b: code) { for (Expr e: b) { if (locals.containsKey(e.id)) { alloc1(e,conflicts,locals); if ( fixed_locals.containsKey(e) && locals.get(e.id) != -1) fixed_locals.put(e, locals.get(e.id)); } } } for (Block b: code) { for (Expr e: b) { if (locals.containsKey(e.id)) { alloc2(e,conflicts,locals); if ( fixed_locals.containsKey(e) && locals.get(e.id) != -1) fixed_locals.put(e, locals.get(e.id)); } } } verboseStatus("CONFLICTS " + conflicts); verboseStatus("LOCALS "+locals); } void update_depth(Block b, int stkdepth, Map stkin, int scpdepth, Map scpin) { if (stkin.containsKey(b)) assert(stkin.get(b) == stkdepth); else stkin.put(b,stkdepth); if (scpin.containsKey(b)) {}// assert(scpin.get(b) == scpdepth); else scpin.put(b,scpdepth); } void allocate(int id, int loc, Maplocals, ConflictGraph conflicts) { traceEntry("allocate"); addTraceAttr("id", id); addTraceAttr("loc", loc); assert(locals.get(id) == -1 && loc != -1); locals.put(id, loc); // sanity check for (int j: conflicts.get(id)) assert(locals.get(j) != loc); } void alloc1(Expr e, ConflictGraph conflicts, Map locals) { if (locals.get(e.id) != -1) return; BitSet used = new BitSet(); for (int i: conflicts.get(e.id)) if (locals.get(i) != -1) used.set(locals.get(i)); int loc = -1; // If the expression's locked to a specific local (e.g., it's an arg), it must use that local. if (e.locals.length == 1 && e.inLocal() && locals.containsKey(e.locals[0].id) && (loc=locals.get(e.locals[0].id)) != -1) { assert(!used.get(loc)); allocate(e.id, loc, locals, conflicts); } if (e.op != OP_phi) return; // If any phi input is already allocated, and the local's available, use that slot. for (Expr a: e.args) { if (locals.containsKey(a.id) && (loc=locals.get(a.id)) != -1 && !used.get(loc)) { allocate(e.id, loc, locals, conflicts); break; } } if (loc == -1) { // No previous allocation found; allocate lowest-numbered free local. loc = 0; while (used.get(loc)) loc++; allocate(e.id, loc, locals, conflicts); } // try to assign all inputs to the same local to avoid copies nextarg: for (Expr a: e.args) { if (locals.get(a.id) == -1) { for (int j: conflicts.get(a.id)) if (locals.get(j) == loc) continue nextarg; allocate(a.id, loc, locals, conflicts); } } } void alloc2(Expr e, ConflictGraph conflicts, Map locals) { if (locals.get(e.id) != -1) return; BitSet used = new BitSet(); for (int i: conflicts.get(e.id)) if (locals.get(i) != -1) used.set(locals.get(i)); // Ensure that nothing leaked out of alloc1. assert ( ! (e.locals.length == 1 && e.inLocal() && locals.containsKey(e.locals[0].id) && (locals.get(e.locals[0].id)) != -1) ); int loc; // If an arg has a register allocated, try to re-use it. if (e.args.length != 0 && locals.containsKey(e.args[0].id) && (loc=locals.get(e.args[0].id)) != -1 && !used.get(loc)) { addTraceAttr("MayUseLoc", loc); allocate(e.id, loc, locals, conflicts); return; } // otherwise assign the lowest numbered free local loc = 0; while (used.get(loc)) loc++; allocate(e.id, loc, locals, conflicts); } Map getLocalVarState(Method m) { Map result = new TreeMap(); Map frames_by_block = new TreeMap(); Deque code = schedule(m.entry.to); // Verifier's initial frame state: // Parameters have known types, // locals are type ANY. Typeref[] frame_state = new Typeref[m.local_count]; System.arraycopy(m.getParams(), 0, frame_state, 0, m.getParams().length); for (int i = m.getParams().length; i < frame_state.length; i++) frame_state[i] = ANY().ref; verboseStatus("FRAME_STATE"); for ( Block b: code ) { if ( frames_by_block.containsKey(b)) frame_state = frames_by_block.get(b); frame_state = buildLocalState(m, b, frame_state, result, frames_by_block); } // Compute liveout sets. computeLiveout(code, result); return result; } Typeref[] buildLocalState(Method m, Block b, Typeref[] frame_state, Map local_map, Map states_by_block) { LocalVarState block_state = local_map.get(b); if ( null == block_state ) { block_state = new LocalVarState(m, b, frame_state); local_map.put(b, block_state); switch (b.exprs.peekLast().op) { default: { break; } case OP_lookupswitch: { for ( Edge p: b.succ()) checkTarget(b, p.to, block_state.fs_out, states_by_block); break; } case OP_jump: { checkTarget(b, b.succ()[0].to, block_state.fs_out, states_by_block); break; } case OP_ifnlt: case OP_ifnle: case OP_ifngt: case OP_ifnge: case OP_ifne: case OP_ifstrictne: case OP_iftrue: case OP_iffalse: case OP_ifeq: case OP_iflt: case OP_ifle: case OP_ifgt: case OP_ifge: case OP_ifstricteq: { checkTarget(b, b.succ()[1].to, block_state.fs_out, states_by_block); // Leading edge is always the fall-through. break; } } } return local_map.get(b).fs_out; } void checkTarget(Block branching_block, Block target_block, Typeref[] current_frame_state, Map frames_by_block) { if ( !frames_by_block.containsKey(target_block)) { verboseStatus (" .. checkTarget(" + branching_block + "->" + target_block + ") copying frame state"); Typeref[] target_frame = new Typeref[current_frame_state.length]; System.arraycopy(current_frame_state, 0, target_frame, 0, current_frame_state.length); frames_by_block.put(target_block, target_frame); } else { Typeref[] previous_state = frames_by_block.get(target_block); verboseStatus(" .. checkTarget(" + branching_block + "->" + target_block + ") merging frame state"); for ( int i = 0; i < previous_state.length; i++) { Typeref merged_type = typeMeet(previous_state[i], current_frame_state[i]); if ( target_block.is_backwards_branch_target) previous_state[i] = merged_type.nullable(); else previous_state[i] = merged_type; } } dumpFrameState(current_frame_state); } void dumpFrameState(Typeref[] fs_out) { if ( verbose_mode ) { StringBuffer frame_state_buffer = new StringBuffer(); frame_state_buffer.append("\tLocals: "); for ( int i = 0; i < fs_out.length; i++) { frame_state_buffer.append(fs_out[i].toString()); frame_state_buffer.append(" "); } verboseStatus(frame_state_buffer); } } /** * Compute variable live-out sets for a control-flow graph. * Follows Cooper & Torczon's [section 9.2.2] Round-robin, iterative solver * @param code - The CFG. Not required to be in any particular order. * @param live_map - the result map of blocks to sets of live-out variables. * @pre live_map must already have per-block data * for upwardly exposed vars, defines, and kills. */ void computeLiveout(Deque code, Map live_map) { boolean changed = true; while ( changed ) { changed = false; for ( Block b: code) { LocalVarState current_state = live_map.get(b); BitSet next_liveout = new BitSet(); for ( Edge p: b.succ() ) { next_liveout.or(live_map.get(p.to).getLivein()); } for ( Edge x:b.xsucc) { next_liveout.or(live_map.get(x.to).getLivein()); } changed |= current_state.mergeLiveout(next_liveout); } } } static class ConflictGraph { Map> conflicts = new TreeMap>(); void add(Expr e1, Expr e2) { get(e1.id).add(e2.id); get(e2.id).add(e1.id); } boolean contains(Expr a, Expr b) { return conflicts.containsKey(a.id) && conflicts.get(a.id).contains(b.id); } public String toString() { return String.valueOf(conflicts); } Set get(int i) { Set s = conflicts.get(i); if (s == null) conflicts.put(i, s = new TreeSet()); return s; } } boolean hasStackEffect(Expr e) { if (e == null || e.op == OP_arg) return true; return e.onStack() || e.args.length > 0; } Typeref typeMerge(Typeref t1, Typeref t2) { Typeref result = null; Type merged_type = typeMeet(t1.t, t2.t); if (!merged_type.equals(ANY()) || (t1.t.equals(ANY()) && t2.t.equals(ANY()))) result = new Typeref ( merged_type, t1.nullable || t2.nullable); return result; } Typeref typeMeet(Typeref t1, Typeref t2) { Typeref result = null; Type merged_type = typeMeet(t1.t, t2.t); result = new Typeref ( merged_type, t1.nullable | t2.nullable); return result; } /** * Type-meet as per the AVM verifier. * @param t1 a type. May be null. * @param t2 a type. May be null. * @return the type meet of these types. * @return null if no common type exists. */ Type typeMeet(Type t1, Type t2) { if ( t1.equals(t2) ) return t1; else if ( isNumericType(t1.ref) && isNumericType(t2.ref)) return NUMBER(); else if ( VOID().equals(t1) || NULL().equals(t1)) return t2; else if ( VOID().equals(t2) || NULL().equals(t2) ) return t1; // Return the common base type or ANY. Type common_base = mdb(t1.ref, t2.ref).t; return common_base; } /** * Schedule the expressions in the method to maximize use of the operand * stack, by processing the flow graph and expressions backwards. If we can't * issue an instruction to fill a stack slot then we issue a getlocal instead, * mark the expression live. * * When an expression is marked live, add a conflict edge with each other live * expression at that point. [Chotin paper?] * * Phi expressions are handled specially - we make each argument live * at the end of the corresponding predecessor block. Since the stack is empty * at the end of each BB, all phi nodes are allocated to a variable. However, * later, we attempt to allocate locals so phi nodes don't require copies. * * @param code * @param locals * @param pred * @return */ ConflictGraph sched_greedy(Method m, Deque code, Map locals, SetMappred, Map> exprs, ConflictGraph cg) { addTraceAttr(m); SetMap liveout = new SetMap(); Map> stkout = new TreeMap>(); Map> scpout = new TreeMap>(); HashMap> listings = new HashMap>(); // low postorder numbers are first, PriorityQueue work = new PriorityQueue(code.size(),new Comparator() { public int compare(Block b1,Block b2) { return b1.postorder-b2.postorder; } }); work.addAll(code); while (!work.isEmpty()) { Block b = work.remove(); while (work.peek() == b) work.remove(); // remove dups Set live = new TreeSet(); Deque in = new ArrayDeque(b.exprs); Deque stk = new ArrayDeque(); Deque scp = new ArrayDeque(); Deque verbose = new LinkedDeque(); Deque out = new LinkedDeque(); Set out_of_order = new TreeSet(); addTraceAttr(b); live.addAll(liveout.get(b)); live.addAll(b.getLiveOut()); live.addAll(m.fixedLocals.keySet()); for (Expr l: live) locals.put(l.id, l.op == OP_arg ? l.imm[0] : -1); exprs.put(b,out); listings.put(b,verbose); Setphis = new TreeSet(); while (!in.isEmpty() || !stk.isEmpty()) { while (!stk.isEmpty() && hasStackEffect(in.peekLast())) { showstate(live, stk, scp, verbose); Expr e = remove_dup(stk, m, out, verbose); addTraceAttr(e); addTraceAttr("formattedExpr", formatExpr(e)); if (e.inLocal() || e.op == OP_phi || e != in.peekLast() || stk.contains(e)) { /* if ( e != in.peekLast() && ! e.hasEffect() ) { verboseStatus(".. out-of-order, but issue " + e); issue_expr(e, m, out, verbose, stk, scp, live, locals); out_of_order.add(e); } else */ { addTraceAttr(e); if ( e.inLocal() ) addTraceAttr("inLocal"); else if ( e.op == OP_phi ) addTraceAttr("OP_phi"); else if ( e != in.peekLast() ) addTraceAttr("stackMismatch", e.toString() + " != last Expr: " + formatExpr(in.peekLast()) ); else if ( stk.contains(e) ) addTraceAttr("stackOverload", "stk.contains(" + e.toString() + ")"); issue_load(e, m, out, verbose, live, locals); } } else if (live.contains(e)) { // stack top ready to be issued but it's live. issue store. // push e back twice: once for store, once to consume. then // go around loop once more to handle the dup + issue. traceEntry("DefineLiveExpr", e); define(e,live,cg); issue_store(e, m, out, verbose, stk); traceEntry("PushBack", e); stk.add(e); } else if (e.op == OP_xarg) { assert(stk.isEmpty()); while (!stk.isEmpty()) loadTOS(m, stk, scp, out, verbose, live, locals); verbose.addFirst(in.removeLast()); } else { // e is ready to issue traceEntry("IssueExpr", e); issue_expr(in.removeLast(), m, out, verbose, stk, scp, live, locals); } continue; } if (!in.isEmpty()) { showstate(live, stk, scp, verbose); Expr e = in.removeLast(); addTraceAttr(e); addTraceAttr("formattedExpr", formatExpr(e)); if ( out_of_order.contains(e) ) { traceEntry("IssuedOutOfOrder", e ); continue; } else if (e.op == OP_phi) { issue_phi(e, verbose, phis, live, cg); } else if (e.op == OP_arg) { verbose.addFirst(e); if (live.contains(e)) define(e,live,cg); } else { if (live.contains(e)) { traceEntry("LiveExpr"); addTraceAttr(e); define(e,live,cg); // ISSUE: Why not just issue a dup before the store? if (e.onStack()) { traceEntry("StoreLiveExprFromStack ", e); issue_store(e, m, out, verbose, stk); traceEntry("PushBackOnStack", e); in.add(e); } else if (e.inLocal()) { traceEntry("IssueExprFromLocal", e); issue_expr(e, m, out, verbose, stk, scp, live, locals); } else if (e.onScope()) { traceEntry("IssueScopeExpr", e); issue_expr(e, m, out, verbose, stk, scp, live, locals); } else { assert(false); } } else if (e.op == OP_xarg) { issue_pop(m,out,verbose,e); verbose.addFirst(e); } else { addTraceAttr(e); if (e.onStack()) { traceEntry("StackPop", e); issue_pop(m,out,verbose,e); } issue_expr(e, m, out, verbose, stk, scp, live, locals); } } } } fwd_state(m, locals, pred, liveout, stkout, scpout, work, b, live, stk, scp, verbose, out, phis); } verboseStatus("STK_LIVEOUT " + liveout); verboseStatus("CONFLICTS " + cg); for (Block b: code) { verboseStatus(""); verboseStatus(b); for (Object o: listings.get(b)) if (o instanceof Expr) print((Expr)o); else verboseStatus(o); } return cg; } static void traceEntry(String traceTag) { tm.traceEntry(traceTag); } static void traceEntry(String traceTag, String attrValue) { tm.traceEntry(traceTag, attrValue); } static void traceEntry(String traceTag, String attrName, String attrValue) { tm.traceEntry(traceTag, attrName, attrValue); } static void traceEntry(String traceTag, String attrName, Object attrValue) { tm.traceEntry(traceTag); addTraceAttr(attrName, attrValue); } static void traceEntry(String traceTag, int attrValue) { tm.traceEntry(traceTag, attrValue); } static void traceEntry(String traceTag, Expr expr) { traceEntry(traceTag); addTraceAttr(expr); } static void addTraceAttr(String attrName) { tm.addAttr(attrName, "true"); } static void addTraceAttr(Object o) { if ( null == o ) return; else if ( o instanceof Block ) addTraceAttr("Block", o); else if ( o instanceof Edge) addTraceAttr("Edge", o); else if ( o instanceof Expr) addTraceAttr("Expr", o); else if ( o instanceof Method ) addTraceAttr("Method", o); else addTraceAttr(o.getClass().getSimpleName(), o); } static void addTraceAttr(String attrName, Object attr) { tm.addAttr(attrName, attr); if ( attr != null && ( attrName.equalsIgnoreCase("Expr") || attrName.equalsIgnoreCase("Method") || attrName.equalsIgnoreCase("Block"))) { tm.addAttr("HashCode", Integer.toHexString(attr.hashCode())); } } static void addTraceAttr(String attrName, int attr) { tm.addAttr(attrName, attr); } static void addTraceAttr(String attrName, String attr) { tm.addAttr(attrName, attr); } void showstate(Set live, Deque stk, Deque scp, Deque verbose) { verbose.addFirst(" live "+live + " stk " + stk); if (!scp.isEmpty()) verbose.addFirst(" scp "+scp); } Expr remove_dup(Dequestk, Method m, Dequeout, Dequeverbose) { Expr e = stk.removeLast(); while (e == stk.peekLast()) issue_dup(stk.removeLast(), m, out, verbose); return e; } void try_dup(Dequestk, Method m, Dequeout, Dequeverbose) { if (stk.size()>2) { Expr e = stk.removeLast(); while (e == stk.peekLast()) issue_dup(stk.removeLast(), m, out, verbose); stk.add(e); } } void issue_phi(Expr e, Dequeverbose, Setphis, Setlive, ConflictGraph cg) { addTraceAttr(e); addTraceAttr("live", live.contains(e)); verbose.addFirst(e); phis.add(e); if (live.contains(e)) for (Expr l: live) if (l != e) { traceEntry("conflict"); addTraceAttr(e); addTraceAttr("conflictsWith", l); cg.add(l,e); } } ConflictGraph sched_lazy(Method m, Deque code, Map locals, SetMappred, Map> exprs, ConflictGraph cg) { SetMap liveout = new SetMap(); Map> stkout = new TreeMap>(); Map> scpout = new TreeMap>(); HashMap> listings = new HashMap>(); // low postorder numbers are first, PriorityQueue work = new PriorityQueue(code.size(),new Comparator() { public int compare(Block b1,Block b2) { return b1.postorder-b2.postorder; } }); work.addAll(code); while (!work.isEmpty()) { Block b = work.remove(); while (work.peek() == b) work.remove(); // remove dups Set live = new TreeSet(); Deque in = new ArrayDeque(b.exprs); Deque stk = new ArrayDeque(); Deque scp = new ArrayDeque(); Deque verbose = new LinkedDeque(); Deque out = new LinkedDeque(); // if any succ has defined an expected stack, use it. // if more than one have then they all have to match. if (stkout.containsKey(b)) stk.addAll(stkout.get(b)); // merge the live vars from each succ live.addAll(liveout.get(b)); for (Expr l: live) locals.put(l.id, l.op == OP_arg ? l.imm[0] : -1); exprs.put(b,out); listings.put(b,verbose); Setphis = new TreeSet(); while (!in.isEmpty()) { showstate(live, stk, scp, verbose); Expr e = in.removeLast(); if (e.op == OP_phi) { issue_phi(e, verbose, phis, live, cg); continue; } assert(phis.isEmpty()); boolean onstack = false; while (stk.contains(e)) { onstack = true; Expr f = remove_dup(stk, m, out, verbose); if (f != e || stk.contains(e)) issue_load(f,m,out,verbose,live,locals); } if (e.op == OP_arg) { if (onstack) issue_load(e,m,out,verbose,live,locals); verbose.addFirst(e); if (live.contains(e)) define(e,live,cg); } else { if (live.contains(e)) { if (e.op == OP_xarg) while (!stk.isEmpty()) loadTOS(m,stk,scp,out,verbose,live,locals); define(e, live, cg); if (onstack) stk.add(e); issue_store(e, m, out, verbose, stk); in.add(e); } else if (e.op == OP_xarg) { if (!stk.isEmpty()) { while (!stk.isEmpty()) loadTOS(m,stk,scp,out,verbose,live,locals); in.add(e); // put xarg back if (onstack) stk.add(e); // make xarg the only thing on the stack. } else { if (!onstack) issue_pop(m,out,verbose,e); verbose.addFirst(e); //print but don't issue it. } } else { if (!onstack && e.onStack()) issue_pop(m,out,verbose,e); issue_expr(e, m, out, verbose, stk, scp, live, locals); } } } fwd_state(m, locals, pred, liveout, stkout, scpout, work, b, live, stk, scp, verbose, out, phis); } verboseStatus("SCHED LIVEOUT " + liveout); verboseStatus("SCHED STKOUT " + stkout); verboseStatus("SCHED CONFLICTS " + cg); for (Block b: code) { verboseStatus(""); verboseStatus(b); for (Object o: listings.get(b)) if (o instanceof Expr) print((Expr)o); else verboseStatus(o); } return cg; } /** * issue a load for whatever is on the stack top */ void loadTOS(Method m, Dequestk, Dequescp, Dequeout, Dequeverbose, Setlive, Maplocals) { // stk doesn't match, make all successors expect nothing. showstate(live, stk, scp, verbose); Expr e = stk.removeLast(); if (e == stk.peekLast()) issue_dup(e, m, out, verbose); else issue_load(e, m, out, verbose, live, locals); } /** * forward the stack & live variable state from the top of the current * block (b) to the end of each predecessor block, translating phi nodes * at the same time. * * @param m * @param locals * @param pred * @param liveout * @param stkout * @param work * @param b * @param live * @param stk * @param verbose * @param out * @param phis */ void fwd_state(Method m, Map locals, SetMap pred, SetMap liveout, Map> stkout, Map> scpout, PriorityQueue work, Block b, Set live, Deque stk, Deque scp, Deque verbose, Deque out, Set phis) { // first prune stack to something safe to forward. TreeMap>stkout2 = new TreeMap>(stkout); for (Edge p: pred.get(b)) { Block f = p.from; Deque stk2 = clone_stk(phis,stk,p); if (!stkout2.containsKey(f)) { stkout2.put(f,stk2); } else { int prefix = stacks_equal(stk2,stkout2.get(f)); assert(stk.size() >= prefix); while (stk.size() > prefix) loadTOS(m,stk,scp,out,verbose,live,locals); } } showstate(live, stk, scp, verbose); for (Edge p: pred.get(b)) { Block f = p.from; // forward live exprs Set live2 = clone_live(phis,live,p); if (liveout.get(f).addAll(live2)) work.add(f); // forward stack exprs Deque stk2 = clone_stk(phis,stk,p); if (!stkout.containsKey(f)) { stkout.put(f, stk2); } else { int prefix = stacks_equal(stk2,stkout.get(f)); assert(stk2.size() == prefix && stkout.get(f).size() >= prefix); if (stkout.get(f).size() > prefix) { stkout.put(f, stk2); work.add(f); for (Edge s: f.succ()) if (s.to != b) work.add(s.to); } } } } /** * clone the live vars set for a particular predecessor edge, * replacing phi's with the expr corresponding to that edge. * * @param phis * @param live * @param p * @return */ Set clone_live(Setphis, Setlive, Edge p) { if (phis.isEmpty() || live.isEmpty()) return live; Set copy = new TreeSet(); for (Expr e: live) copy.add(phis.contains(e) ? e.args[findPhiArg(e, p)] : e); return copy; } /** * clone the stack layout for a predecessor edge, replacing phi's * with the argument coming from that edge. * * @param phis * @param stk * @param p * @return */ Deque clone_stk(Setphis, Dequestk, Edge p) { if (phis.isEmpty() || stk.isEmpty()) return stk; Deque copy = new ArrayDeque(); for (Expr e: stk) copy.add(phis.contains(e) ? e.args[findPhiArg(e, p)] : e); return copy; } int stacks_equal(Dequestk1, Dequestk2) { int i=0; Iterator i1 = stk1.iterator(); Iterator i2 = stk2.iterator(); while (i1.hasNext() && i2.hasNext()) { if (i1.next() != i2.next()) return i; i++; } return i; } void define(Expr e, Set live, ConflictGraph cg) { addTraceAttr(e); live.remove(e); for (Expr l: live) { cg.add(e,l); traceEntry("conflict"); addTraceAttr(e); addTraceAttr("conflictsWith", l); } } void issue_expr(Expr e, Method m, Dequeout, Deque verbose, Dequestk, Dequescp, Setlive, Map locals) { addTraceAttr(e); if (!e.isSynthetic()) out.addFirst(e); verbose.addFirst(e); for (Expr a: e.args) { traceEntry("PushArg", "Expr", a); stk.add(a); } for (Expr a: e.locals) { traceEntry("UseLocal", "Expr", a); use(a, live, locals); } try_dup(stk, m, out, verbose); } void issue_store(Expr e, Method m, Dequeout, Deque verbose, Dequestk) { Expr set = setlocal(m, e.id, e); addTraceAttr("setlocalExpr", formatExpr(set)); out.addFirst(set); verbose.addFirst(set); traceEntry("Push", formatExpr(e)); stk.add(e); } void issue_dup(Expr e, Method m, Dequeout, Deque verbose) { Expr dup = dup(m,e); out.addFirst(dup); traceEntry("issue_dup", dup); verbose.addFirst(dup); } void issue_pop(Method m, Dequeout, Deque verbose, Expr a) { Expr pop = new Expr(m, OP_pop, a); out.addFirst(pop); verbose.addFirst(pop); } void issue_load(Expr e, Method m, Dequeout, Dequeverbose, Setlive, Maplocals) { use(e, live, locals); Expr get = getlocal(m,e.id); out.addFirst(get); traceEntry("issue_load", get); verbose.addFirst(get); } void use(Expr e, Set live, Map locals) { traceEntry("use"); addTraceAttr(e); live.add(e); locals.put(e.id, e.op == OP_arg ? e.imm[0] : -1); addTraceAttr("locals_entry", locals.get(e.id)); } void rename(Expr e, Expr[] args, Map map, EdgeMap ssaSucc) { addTraceAttr(e); for (int i=0, n=args.length; i = op(@j) * * additionally, references to a dup are replaced by references to the * dup's argument. Dup is a copy instruction inserted by some previous * optimization. * * @i = dup(@j), op(@i) => op(@j) * * We take advantage of SSA's sparseness by propagating changes along * def->use edges and iterating until our worklist is empty. * * This pass also removes any phi arguments that are dead, i.e. if the * edge contributing the argument is from an unreachable block. This * may turn the phi into a copy which is subsequently removed. */ void cp(Deque code) { EdgeMap uses = findUses(code); Map map = new HashMap(); Set work = new TreeSet(); for (Block b: code) { if ( ! b.must_isolate_block) { for (Expr e: b) if (e.op == OP_phi || e.op == OP_dup) work.add(e); } } while (!work.isEmpty()) { Expr e = getExpr(work); rename(e, e.args, map, uses); rename(e, e.scopes, map, uses); rename(e, e.locals, map, uses); if (e.op == OP_dup) { map.put(e, e.locals[0]); work.addAll(uses.get(e)); } else if (e.op == OP_phi) { assert(e.args.length == e.pred.length); for (int j=e.pred.length-1; j >= 0; j--) if (!code.contains(e.pred[j].from)) e.removePhiInput(j); Expr a = null; for (int j=e.pred.length-1; j >= 0; j--) { if (e.args[j] != e && e.args[j] != a) if (a == null) a = e.args[j]; else { a = null; break; } } if (a != null && map.get(e) != a) { map.put(e, a); work.addAll(uses.get(e)); e.clearEffect(); } } } // Marshall live-out exprs by block. for ( Block b: code) { for ( Expr e: b.exprs) { if ( e.is_live_out ) { b.addLiveOut(e); } } } } boolean hasSideEffect(Expr e) { return e.isPx() || e.hasEffect(); } void schedule_loop(Block b, EdgeMap loops, Deque scheduled) { Set loop = loops.get(b); for (Block lb: dfs(b)) { if (!scheduled.contains(lb) && loop.contains(lb)) { scheduled.add(lb); if (loops.containsKey(lb)) schedule_loop(lb, loops, scheduled); } } } /** * layout blocks. Normal forward flow is laid out in reverse postorder. * Loops are handled specially to keep blocks in the loop body close to * each other. loop exit blocks are postponed until after the loop. * @param entry * @return */ Deque schedule(Block entry) { Dequecode = dfs(entry); Dequescheduled = new ArrayDeque(); SetMap pred = preds(code); Map idom = idoms(code,pred); EdgeMap loops = findLoops(code,idom,pred); if (!loops.isEmpty()) verboseStatus("LOOPS "+loops); for (Block b: code) { // TODO: Post-test loops fail the AVM verifier // under certain conditions (not well understood). if (!scheduled.contains(b)) scheduled.add(b); if (loops.containsKey(b)) schedule_loop(b, loops, scheduled); } // Rearrange conditional branches so that fall-through edges // occur in the optimizer's natural flow, and flag any // backwards branch targets. Deque branch_analysis = new ArrayDeque(); branch_analysis.addAll(scheduled); Set already_seen = new HashSet(); while (branch_analysis.size()>1) { Block b = branch_analysis.removeFirst(); Expr last = b.last(); Block next = branch_analysis.peekFirst(); if (isBranch(last) && last.succ[0].to != next && last.succ[1].to == next) invert(last); // Check for backwards branches. already_seen.add(b); b.is_backwards_branch_target = false; for ( Edge s: b.succ()) { s.to.is_backwards_branch_target |= s.is_backwards_branch = already_seen.contains(s.to); } } if ( verbose_mode ) for (Block b: code) if ( b.is_backwards_branch_target ) verboseStatus(".. backwards branch target:" + b); return scheduled; } boolean isJump(Expr e) { return e.op == OP_jump; } boolean isBranch(Expr e) { return e.succ != null && e.succ.length == 2 && e.op != OP_lookupswitch; } /** * returns true if P->S is a loop back edge. This is the * case if S is visited first in reverse postorder and S * dominates P. * * @param p * @param s * @param idom * @return */ boolean isLoop(Edge e, Mapidom) { return e.isBackedge() && dominates(e.to, e.from, idom); } EdgeMap findLoops(Deque code) { SetMap pred = preds(code); return findLoops(code, idoms(code, pred), pred); } /** * loop code layout * the loop is defined by the back edge from T->H. H (header) is the source * of the back edge. We want H at the bottom of the loop and T at the top. * Lay the blocks out in DFS order starting with T and skipping any blocks * that aren't part of the loop. * * prefer to have fall-through blocks that are part of the loop. */ EdgeMap findLoops(Deque code, Mapidom, SetMappred) { EdgeMap loops = new EdgeMap(); for (Block b: code) for (Edge s: b.succ()) if (isLoop(s, idom)) { verboseStatus("backedge "+s); Block h = s.to; // find the set of blocks that are in the loop body. Set loop = loops.get(h); Set work = new TreeSet(); for (Edge p: pred.get(h)) { if (isLoop(p,idom) && !loop.contains(p.from) && p.from != h) { loop.add(p.from); work.add(p.from); } } while (!work.isEmpty()) { Block x = getBlock(work); for (Edge p: pred.get(x)) { if (p.from != h && !loop.contains(p.from)) { loop.add(p.from); work.add(p.from); } } } } return loops; } void dce_mark(BitSet used, Expr e) { if (used.get(e.id)) return; used.set(e.id); for (Expr a: e.args) dce_mark(used, a); for (Expr a: e.scopes) dce_mark(used, a); for (Expr a: e.locals) dce_mark(used, a); } /** * Dead Code Elimination. First perform copy propagation and then * remove any expressions not used by the essential expressions * that have side effects. * @param m */ void dce(Method m) { Deque code = dfs(m.entry.to); cp(code); BitSet marked = new BitSet(); for (Block b: code) for (Expr e: b) if (hasSideEffect(e)) dce_mark(marked,e); for (Block b: code) for (Iterator i = b.iterator(); i.hasNext();) if (!marked.get(i.next().id)) { i.remove(); } } class TypeConstraintMap extends HashMap { /** @see Serializable */ private static final long serialVersionUID = 1903880092224622848L; TypeConstraintMap() { super(); } /** * Retrieve or create an Edge's constraints. * @param key - the Edge of interest. * @return the Edge's constraints. */ TypeConstraints getConstraints(Edge key) { TypeConstraints result = get(key); if ( null == result ) { result = new TypeConstraints(key); put(key, result); } return result; } } String format(char op, Object[] a, char cp) { if (a == null) return ""; StringBuilder s = new StringBuilder(); s.append(op); for (Object o: a) s.append(o).append(' '); if (a.length > 0) s.setCharAt(s.length()-1,cp); else s.append(cp); return s.toString(); } static boolean isSlot(Binding b) { return (b != null)? b.isSlot(): false; } static boolean isConst(Binding b) { return (b != null)? b.isConst(): false; } static boolean isClass(Binding b) { return (b != null)? b.isClass(): false; } static boolean isMethod(Binding b) { return (b != null)? b.isMethod() :false; } static boolean isGetter(Binding b) { return (b != null)? b.isGetter(): false; } static boolean isSetter(Binding b) { return (b != null)? b.isSetter(): false; } /** * how many stack elements need to be popped to complete * the given multiname reference. */ static int[] refArgc = { 0,//byte CONSTANT_Void = 0x00; // not actually interned 0,//byte CONSTANT_Utf8 = 0x01; 0, //0x02 0,//byte CONSTANT_Integer = 0x03; 0,//byte CONSTANT_UInteger = 0x04; 0,//byte CONSTANT_PrivateNamespace = 0x05; 0,//byte CONSTANT_Double = 0x06; 0,//byte CONSTANT_Qname = 0x07; // ns::name, const ns, const name 0,//byte CONSTANT_Namespace = 0x08; 0,//byte CONSTANT_Multiname = 0x09; //[ns...]::name, const [ns...], const name 0,//byte CONSTANT_False = 0x0A; 0,//byte CONSTANT_True = 0x0B; 0,//byte CONSTANT_Null = 0x0C; 0,//byte CONSTANT_QnameA = 0x0D; // @ns::name, const ns, const name 0,//byte CONSTANT_MultinameA = 0x0E;// @[ns...]::name, const [ns...], const name 1,//byte CONSTANT_RTQname = 0x0F; // ns::name, var ns, const name 1,//byte CONSTANT_RTQnameA = 0x10; // @ns::name, var ns, const name 2,//byte CONSTANT_RTQnameL = 0x11; // ns::[name], var ns, var name 2,//byte CONSTANT_RTQnameLA = 0x12; // @ns::[name], var ns, var name 0,//0x13 0,//0x14 0,//byte CONSTANT_Namespace_Set = 0x15; // a set of namespaces - used by multiname 0,//byte CONSTANT_PackageNamespace = 0x16; // a namespace that was derived from a package 0,//byte CONSTANT_PackageInternalNs = 0x17; // a namespace that had no uri 0,//byte CONSTANT_ProtectedNamespace = 0x18; 0,//byte CONSTANT_ExplicitNamespace = 0x19; 0,//byte CONSTANT_StaticProtectedNs = 0x1A; 1,//byte CONSTANT_MultinameL = 0x1B; 1,//byte CONSTANT_MultinameLA = 0x1C; }; static class FrameState { Expr[] frame; int sp; int scopep; public FrameState(Expr[] frame, int sp, int scopep) { super(); this.frame = new Expr[frame.length]; this.sp = sp; this.scopep = scopep; } } static boolean isLive(int i, Method m, int scopep) { return i < scopep || i >= m.local_count + m.max_scope; } Block createBlock(Method m, Edge edge, Mapstates, Expr[] frame, int sp, int scopep) { Block b = new Block(m); addTraceAttr("Block", b); FrameState state = new FrameState(frame,sp,scopep); if (edge != null) { edge.to = b; traceEntry("Edge"); addTraceAttr("to", b); } for (int i=0; i < sp; i++) { if (isLive(i,m,scopep) && frame[i] != null) { Expr e = new Expr(m,OP_phi); if (edge != null) { e.args = new Expr[] { frame[i] }; e.pred = new Edge[] { edge }; } b.add(state.frame[i] = e); } } traceFrame("NewBlockFrame", m, frame, scopep, sp); states.put(b, state); return b; } /** * merge state with block at position pos. If the target block * doesn't exist, create it first. * * @param m * @param edge * @param blocks * @param states * @param pos * @param frame * @param sp * @param scopep */ void merge(Method m, Edge edge, Map blocks, Map states, int pos, Expr[] frame, int sp, int scopep) { addTraceAttr("Edge", edge); if (!blocks.containsKey(pos)) { Block b = createBlock(m,edge,states,frame,sp,scopep); blocks.put(pos, b); } else if (edge != null) { edge.to = blocks.get(pos); mergeFrameStates(m, edge, states, frame, sp, scopep); } } /** * merge current state with existing block (edge.to) * @param m * @param edge * @param states * @param frame * @param sp * @param scopep */ void mergeFrameStates(Method m, Edge edge, Mapstates, Expr[] frame, int sp, int scopep) { FrameState target = states.get(edge.to); /* // FIXME: There are a restricted set of circumstances // where it's permissible to have a stack mismatch -- // asc doesn't completely restore scope stacks at a join // from a catch block to a return, for example. // Need a bottom value or sth similar to represent this. assert(target.sp == sp); assert(target.scopep == scopep); */ for (int i=0; i < sp; i++) { if (isLive(i,m,scopep) && frame[i] != target.frame[i]) { if ( target.frame[i] == null ) { // FIXME: See above comment; // only valid value here is // an invalid value. } else { assert(frame[i] != null && target.frame[i].op == OP_phi); target.frame[i].append(frame[i], edge); } } } } void xmerge(Method m, Edge edge, Map blocks, Map states, int pos, Expr[] frame, int sp, int scopep) { scopep = m.local_count; sp = scopep + m.max_scope; Handler h = edge.handler; if (h.entry == null) { // first time, create handler block that jumps to catch block addTraceAttr("firstTime"); Block hb = h.entry = createBlock(m, edge, states, frame, sp, scopep); Expr xarg, jump; hb.add(xarg = new Expr(m,OP_xarg, edge.label)); hb.add(jump = new Expr(m,OP_jump)); jump.succ = new Edge[] { new Edge(m, hb, 0, blocks.get(pos)) }; Expr save = frame[sp]; frame[sp] = xarg; traceEntry("HandlerBlock"); addTraceAttr("Block", hb); addTraceAttr("Edge", edge); traceFrame("Frame", m, frame, scopep, sp); // and merge the handler block with the real exception target. merge(m, jump.succ[0], blocks, states, pos, frame, sp+1, scopep); frame[sp] = save; } else { // each time, merge current state with handler block state. addTraceAttr("notFirstTime"); edge.to = h.entry; mergeFrameStates(m, edge, states, frame, sp, scopep); } } void traceFrame(String desc, Method m, Expr[] frame, int scopep, int sp) { int i = 0; for ( i = 0; i < m.local_count; i++ ) { traceEntry("Local"); addTraceAttr("number", i); addTraceAttr("value", frame[i]); } addTraceAttr("scopep", scopep); for (; i < scopep; i++ ) { traceEntry("Scope"); addTraceAttr("index", i); addTraceAttr("value", frame[i]); } addTraceAttr("sp", sp); for ( i = m.local_count + m.max_scope; i < sp; i++ ) { traceEntry("Operand"); addTraceAttr("index", i); addTraceAttr("value", frame[i]); } } static Expr[] capture(Expr[] frame, int top, int len) { Expr[] args = new Expr[len]; System.arraycopy(frame, top-len, args, 0, len); addTraceAttr("stackPtr", top); addTraceAttr("len", len); for ( int i = 0; i < len; i++) { traceEntry("PopStack"); addTraceAttr(args[i]); } return args; } void print(Expr e) { if ( !verbose_mode ) return; PrintWriter pw = new PrintWriter(System.out); printssa(e, pw); pw.flush(); } void printabc(Expr e, PrintWriter out) { if ( verbose_mode ) out.println(formatExprAsAbc(e)); } String formatExprAsAbc(Expr e) { StringBuilder s = new StringBuilder(); s.append(" " + opNames[e.op]); if (e.imm != null) { s.append('<'); for (int i: e.imm) s.append(i).append(','); s.setCharAt(s.length()-1,'>'); } if (e.succ != null) s.append(format('[',e.succ,']')); if (e.value != null) { s.append(" "); s.append(formatObject(e.value)); } if (e.ref != null) { s.append(" "); s.append(e.ref); } return s.toString(); } void printssa(Expr e, PrintWriter out) { out.println(formatExpr(e)); } String formatExpr(Expr e) { if ( null == e ) { return "null"; } StringBuffer outBuffer = new StringBuffer(); outBuffer.append(e.toString()); if (e.onStack() || e.inLocal() || e.onScope()) outBuffer.append(" ="); else outBuffer.append(" "); if (e.value == null) outBuffer.append(" "+opNames[e.op]); if (e.imm != null) { outBuffer.append('<'); for (int i: e.imm) outBuffer.append(i).append(','); outBuffer.setCharAt(outBuffer.length()-1,'>'); } if (e.args.length > 0) outBuffer.append(format('(',e.args,')')); if (e.locals.length > 0) outBuffer.append(format('(',e.locals,')')); if (e.scopes.length > 0) outBuffer.append(format('{',e.scopes,'}')); if (e.pred.length>0) outBuffer.append(format('[',e.pred,']')); if (e.succ != null) outBuffer.append(format('[',e.succ,']')); if (e.value != null) outBuffer.append(formatObject(e.value)); if (e.ref != null) outBuffer.append(" "+e.ref);//.format()); // full name return outBuffer.toString(); } void print(Object value, PrintWriter out) { out.print(formatObject(value)); } String formatObject(Object value) { if (value instanceof String) return(" \"" + ((String)value).replace("\n","\\n").replace("\r","\\r") + "\""); else return(" "+ value); } void printMethod(Method m, String banner) { if ( ! verbose_mode ) return; PrintWriter pw = new PrintWriter(System.out); pw.println(); pw.println(); pw.println(banner); pw.println("\t"+m.getName()+" local_count="+m.local_count+" max_stack="+m.max_stack+" max_scope="+m.max_scope); Deque blocks = dfs(m.entry.to); pw.println(blocks); for (Block b: blocks) print(b,pw); pw.println(); pw.flush(); } void printabc(Deque blocks) { if ( ! verbose_mode ) return; verboseStatus(blocks); PrintWriter pw = new PrintWriter(System.out); for (Block b: blocks) printabc(b,pw); pw.flush(); } void print(Block b, PrintWriter pw) { pw.println(); printssa(b, pw); } void printabc(Block b, PrintWriter out) { out.println(); out.println(b); if (b.xsucc.length > 0) out.println(Arrays.toString(b.xsucc)); for (Expr s: b) printabc(s,out); } void printssa(Block b, PrintWriter out) { out.println(b); if (b.xsucc.length > 0) out.println(Arrays.toString(b.xsucc)); for (Expr s: b) printssa(s,out); } void dot(String suffix, Method m) { // don't bother with single-block methods. if (m.entry.to.succ().length == 0) return; // save a dot file for the method try { PrintWriter out = new PrintWriter(new FileWriter(m.getName()+suffix+".dot")); try { Deque code = dfs(m.entry.to); out.println("digraph {"); out.println("compound=true;"); out.println("label=\""+m.getName()+suffix+"\";"); out.println("labelloc=top;"); out.println("fontsize=10;"); if (SHOW_DFG) { out.println("ranksep=.1; nodesep=.1;"); out.println("node [shape=plaintext,width=.05,height=.05,fontsize=12];"); } else { out.println("ranksep=.25; nodesep=.25;"); out.println("node [shape=box,width=.1,height=.1,fontsize=12];"); } out.println("edge [arrowsize=.5,fontsize=8,labelfontsize=8];"); for (Block b: code) if (SHOW_DFG) dot_dfg(b,out); else dot(b,out); if ( SHOW_DOMINATORS ) { Map doms = idoms(code,allpreds(code)); out.println("node [shape=box];"); out.println("subgraph cluster1 { label=\"Dominators\"; color=white; "); for (Block b: dfs(m.entry.to)) { out.println("D"+b+" [label="+b+"];"); if (doms.containsKey(b)) out.println("D"+doms.get(b)+" -> D"+b); } out.println("}"); } out.println("}"); } finally { out.close(); } } catch (IOException e) { throw new RuntimeException(e); } } static class LabelWriter extends PrintWriter { StringWriter w; LabelWriter(StringWriter w) { super(w); this.w = w; } public void println() { print("\\l"); flush(); } public void print(String s) { super.print(s.replace("\"","''").replace("\u0278","φ")); } public String toString() { return w.toString(); } } void dot(Block b, PrintWriter out) { LabelWriter w = new LabelWriter(new StringWriter()); // create the label if (SHOW_CODE) printssa(b,w); else w.print(b); String attr = "label=\""+w+"\""; out.println(b+" ["+attr+"];"); // CFG edges for (Edge e: b.succ()) dot(e, out); for (Edge e: b.xsucc) dot(e, out); } void dot_dfg(Block b, PrintWriter out) { LabelWriter w = new LabelWriter(new StringWriter()); // create the label w.print(b); String attr = "label=\""+w+"\"; labeljust=l"; // dfg edges out.println("subgraph cluster"+b+" { "+attr+";"); Expr n = null; Iterator i = b.iterator(); if (i.hasNext()) n = i.next(); while (n != null) { Expr e = n; w = new LabelWriter(new StringWriter()); printssa(e,w); out.print("E"+e.id+" [label=\""+w+"\"];"); if (i.hasNext()) { n = i.next(); out.print("E"+e.id+" -> E"+n.id+" [style=invisible,arrowhead=none,weight=4];"); } else { n = null; } } out.println("}"); for (Expr e: b) { for (Expr a: e.args) out.print("E"+a.id+" -> E"+e.id+" [color=green];"); for (Expr a: e.locals) out.print("E"+a.id+" -> E"+e.id+" [color=green];"); for (Expr a: e.scopes) out.print("E"+a.id+" -> E"+e.id+" [color=grey,style=dashed];"); if (e.isPx()) { for (Edge x: b.xsucc) { //out.print("E"+e.id+" -> E"+x.to.first().id+ // " [weight=2,style=dashed,ltail=cluster"+x.from+",lhead=cluster"+x.to+"];"); out.print("E"+e.id+" -> E"+x.to.first().id+ " [weight=2,style=dashed,color=red];"); } } } for (Edge s: b.succ()) { Expr e = b.last(); int weight = s==b.last().succ[0] ? 4 : 2; //out.print("E"+e.id+" -> E"+s.to.first().id+ // " [weight="+weight+",ltail=cluster"+s.from+",lhead=cluster"+s.to+"];"); out.print("E"+e.id+" -> E"+s.to.first().id+ " [weight="+weight+"];"); } } void dot(Edge e, PrintWriter out) { ArrayList attrs = new ArrayList(); if (e.isThrowEdge()) { attrs.add("style=dashed"); } else { // TODO smarter edge classification if (e.isBackedge()) attrs.add("tailport=w,headport=w"); if (e.label == 0) attrs.add("weight=2"); else attrs.add("taillabel=\""+e.label+"\""); } out.println(e.from + " -> " + e.to + " "+attrs+";"); } void verboseStatus(String msg) { if ( verbose_mode ) System.out.println(msg); } void verboseStatus(Object o) { if ( verbose_mode ) System.out.println(o.toString()); } class LocalVarState { /** * Simulated verifier frame state; * only locals are simulated. */ Typeref[] fs_out; /** * Expected types of input registers. */ Typeref[] fs_in; Typeref[] hard_coercions; /** * Live-Out variables are variables that are * used (without being redefined) in a successor * block. Note: the relationship is transitive. */ private BitSet liveout = new BitSet(); /** * Variables killed in this block via explicit OP_kill insn. */ private BitSet killed_vars = new BitSet(); /** * Variables defined in this block. * @warn denormalized from defining_exprs */ private BitSet def = new BitSet(); /** * Upwardly-exposed variables, read in this block * before any definition. This means that their * value comes from predecessor blocks. */ private BitSet ue_vars = new BitSet(); /** * Variables read in block after their definition. This means * the variable can't be cast at its definition site, although * it could if the read's type agreed with the successors'. */ private BitSet read_after_def = new BitSet(); /** * Generating expresssions for variable definitions; these are * candidates for coercion before the variable's set, saving a * considerable amount of hassle down the CFG. */ private Map generating_exprs = new HashMap(); /** * Set on backwards branch targets, catch * targets, etc -- the verifier will use * more conservative type assumptions. */ private boolean conservative_verifier_rules; private Method m; private Block b; /** * Construct a LocalVariableState; compute its * def, kill, and upwardly-exposed sets; and * compute its frame state. * @param m - the Method under analysis. * @param b - the Block to which this analysis applies. * @param initial_frame_state - the previously computed frame state. * @param is_scheduled_backedge */ LocalVarState(Method m, Block b, Typeref[] initial_frame_state) { this.conservative_verifier_rules = b.is_backwards_branch_target; this.fs_in = new Typeref[initial_frame_state.length]; if ( ! this.conservative_verifier_rules ) { System.arraycopy(initial_frame_state, 0, this.fs_in, 0, initial_frame_state.length); } else { for ( int i = 0; i < m.local_count; i ++ ) { this.fs_in[i] = initial_frame_state[i].nullable(); } for ( int i = m.local_count + m.max_scope; i < this.fs_in.length; i++) { this.fs_in[i] = initial_frame_state[i].nullable(); } } this.fs_out = new Typeref[initial_frame_state.length]; System.arraycopy(this.fs_in, 0, this.fs_out, 0, this.fs_in.length); this.hard_coercions = new Typeref[initial_frame_state.length]; this.m = m; this.b = b; // Keep a shadow of the frame state so that it's only dumped when it changes. Typeref[] saved_fs = null; if ( verbose_mode ) { verboseStatus(b); StringBuffer verbose_succ = new StringBuffer(); verbose_succ.append("\tsucc: "); for ( Edge p: b.succ()) { verbose_succ.append(p); verbose_succ.append(" "); } verboseStatus(verbose_succ); dumpFrameState(fs_out); saved_fs = new Typeref[initial_frame_state.length]; System.arraycopy(fs_out, 0, saved_fs, 0, fs_out.length); } for ( Expr e: b.exprs) { if ( verbose_mode ) verboseStatus(formatExprAsAbc(e)); switch(e.op) { case OP_getlocal0: case OP_getlocal1: case OP_getlocal2: case OP_getlocal3: { uses( e.op - OP_getlocal0); break; } case OP_getlocal: { uses(e.imm[0]); break; } case OP_setlocal0: case OP_setlocal1: case OP_setlocal2: case OP_setlocal3: { defines( e.op - OP_setlocal0, e ); break; } case OP_setlocal: { defines(e.imm[0], e); break; } case OP_hasnext2: { uses(e.imm[0]); uses(e.imm[1]); expectsType(e.imm[0], ANY().ref); expectsType(e.imm[1], INT().ref); hard_coercions[e.imm[0]] = ANY().ref; defines(e.imm[0], e); break; } case OP_kill: { setKilled(e.imm[0]); break; } case OP_inclocal: case OP_inclocal_i: case OP_declocal: case OP_declocal_i: { uses(e.imm[0]); break; } case OP_getslot: case OP_setslot: { Expr stem = e.args[0]; if ( stem.inLocal() ) { expectsType(stem.imm[0], m.verifier_types.get(stem)); } break; } case OP_nextvalue: case OP_nextname: { // TODO: Anything to do here? break; } default: assert(!e.inLocal()); } if ( verbose_mode ) { for ( int i = 0; i < fs_out.length; i++ ) { if ( saved_fs[i] != fs_out[i] ) { dumpFrameState(fs_out); System.arraycopy(fs_out, 0, saved_fs, 0, fs_out.length); break; } } } } } private void expectsType(int i, Typeref expected_type) { // If the variable's defined in this block, // then it doesn't need coercion. if ( !( def.get(i) || this.fs_in[i].t.equals(expected_type.t) ) ) { // TODO: track these coerced locals with a new bit set // and cross check to ensure they're all livein. verboseStatus("\texpectsType " + i + " " + expected_type); this.fs_in[i] = this.fs_out[i] = expected_type; } } /** * @param reg - the local of interest. * @return the live-in type the verifier will expect * to see on entry to the block. */ public Typeref getInitialType(int reg) { return fs_in[reg]; } /** * @param reg - the local of interest. * @return the type the local has at the end of this block. */ public Typeref getFinalType(int reg) { return fs_out[reg]; } public BitSet getKilled() { return (BitSet)this.killed_vars.clone(); } private boolean mergeLiveout(BitSet next_liveout) { next_liveout.or(this.liveout); boolean result = !this.liveout.equals(next_liveout); if ( result ) { this.liveout = next_liveout; } return result; } /** * Registers contributed by predecessor blocks. * @return (liveout - def) + UE */ BitSet getLivein() { BitSet result = (BitSet)this.liveout.clone(); result.andNot(this.def); result.or(this.ue_vars); return result; } /** * Locals still active at the end of a block. * @note changes as variables are killed. * @return (UE + def) - killed */ BitSet getActiveVariables() { BitSet result = getLivein(); result.or(this.def); if ( b.equals(m.entry.to)) { // Note parameters as active. for ( int i = 0; i < m.getParams().length; i++) result.set(i); } result.andNot(this.killed_vars); return result; } BitSet getLiveout() { return (BitSet)liveout.clone(); } BitSet getDefined() { return (BitSet)this.def.clone(); } private void uses(int varnum) { if ( !def.get(varnum) ) { if ( !isAPriori(varnum) ) ue_vars.set(varnum); } else { read_after_def.set(varnum); } } /** * Is this local a routine parameter? * If so, it is a priori present and * shouldn't be considered upwardly exposed. * @param varnum - the local of interest. * @return true if the local's a parameter. */ private boolean isAPriori(int varnum) { return (this.b.equals(this.m.entry.to) && varnum < this.m.getParams().length); } private void defines(int varnum, Expr generating_expr) { fs_out[varnum] = definingType(generating_expr); def.set(varnum); generating_exprs.put(varnum, generating_expr); killed_vars.clear(varnum); read_after_def.clear(varnum); } private Typeref definingType(Expr e) { Typeref result = null; if ( OP_hasnext2 == e.op ) { result = ANY().ref; } else if ( OP_setlocal == e.op ) { Expr value = e.args[0]; if ( OP_getlocal == value.op ) { result = fs_out[value.imm[0]]; } else { result = verify_eval(this.m, value, m.verifier_types, null); } } else { assert(false); } assert ( result != null ); return result; } public void setKilled(int varnum) { assert(!killed_vars.get(varnum)); killed_vars.set(varnum); generating_exprs.remove(varnum); } } static class TypeConstraints implements Comparable { Set killregs = new TreeSet(); Map coercions = new HashMap(); /** * Path to the destination block. */ Edge path; /** * The original destination block. * May be different than path.to if * the path is split during fixup. * @see compareTo */ Block dest_block; TypeConstraints(Edge path) { this.path = path; if ( path != null) this.dest_block = path.to; } void takeConstraintFrom(TypeConstraints tc, Integer r) { if ( killregs.contains(r) ) { assert(tc.killregs.contains(r)); tc.killregs.remove(r); } else if ( coercions.containsKey(r) ) { assert(tc.coercions.containsKey(r) && tc.coercions.get(r).t.isMachineCompatible(this.coercions.get(r).t)); tc.coercions.remove(r); } else if ( tc.killregs.contains(r) ) { this.killregs.add(r); tc.killregs.remove(r); } else if ( tc.coercions.containsKey(r) ) { this.coercions.put(r, tc.coercions.get(r)); tc.coercions.remove(r); } else throw new IllegalStateException("neither constraint set contains local " + r); } boolean agreesWith(TypeConstraints tc, Integer r) { if ( this.killregs.contains(r)) return tc.killregs.contains(r); else if ( this.coercions.containsKey(r)) return tc.coercions.containsKey(r) && this.coercions.get(r).t.isMachineCompatible((tc.coercions.get(r).t)); // Local not found in this constraint set; // by definition, the sets are in conflict // with respect to this local. return false; } void addKill(int reg) { assert(!coercions.containsKey(reg)); this.killregs.add(reg); } void addCoercion(int reg, Typeref ty) { assert(!coercions.containsKey(reg) && !killregs.contains(reg)); coercions.put(reg, ty); } public boolean equals(Object o) { return 0 == compareTo(o); } public int compareTo(Object arg0) { if ( ! ( arg0 instanceof TypeConstraints ) ) return -1; TypeConstraints other = (TypeConstraints) arg0; if ( dest_block.id != other.dest_block.id ) return (dest_block.id > other.dest_block.id)? 1:-1; if ( killregs.size() > other.killregs.size()) return 1; else if ( other.killregs.size() > this.killregs.size()) return -1; if ( coercions.size() > other.coercions.size() ) return 1; else if ( other.coercions.size() > this.coercions.size()) return -1; for ( Integer x: this.killregs ) if ( ! other.killregs.contains(x)) return 1; for ( Integer y: other.killregs ) if ( ! this.killregs.contains(y)) return -1; for ( Integer r: this.coercions.keySet() ) { Typeref this_ctype = coercions.get(r); Typeref other_ctype = other.coercions.get(r); if ( null == other_ctype ) return 1; if ( !this_ctype.equals(other_ctype) ) return ( this_ctype.hashCode() > other_ctype.hashCode() )? 1: -1; } for ( Integer o_r: other.coercions.keySet()) if ( !this.coercions.containsKey(o_r)) return -1; return 0; } } class Reader { int pos; byte[] abc; Reader(int pos, byte[] abc) { this.pos = pos; this.abc = abc; } Reader(Reader r) { this(r.pos, r.abc); } int readU8() { return 255 & abc[pos++]; } int readU16() { return readU8() | readU8() << 8; } int readS24() { return readU16() | ((byte) readU8()) << 16; } int readU30() { int result = readU8(); if (0==(result & 0x00000080)) return result; result = result & 0x0000007f | readU8()<<7; if (0==(result & 0x00004000)) return result; result = result & 0x00003fff | readU8()<<14; if (0==(result & 0x00200000)) return result; result = result & 0x001fffff | readU8()<<21; if (0==(result & 0x10000000)) return result; return result & 0x0fffffff | readU8()<<28; } double readDouble() { return Double.longBitsToDouble(readU16() | ((long)readU16())<<16 | ((long)readU16())<<32 | ((long)readU16())<<48); } } class AbcWriter extends ByteArrayOutputStream { void rewind(int n) { super.count -= n; } void writeU16(int i) { write(i); write(i>>8); } void writeS24(int i) { writeU16(i); write(i>>16); } void write64(long i) { writeS24((int)i); writeS24((int)(i>>24)); writeU16((int)(i>>48)); } void writeU30(int v) { if (v < 128 && v >= 0) { write(v); } else if (v < 16384 && v >= 0) { write(v & 0x7F | 0x80); write(v >> 7); } else if (v < 2097152 && v >= 0) { write(v & 0x7F | 0x80); write(v >> 7 | 0x80); write(v >> 14); } else if (v < 268435456 && v >= 0) { write(v & 0x7F | 0x80); write(v >> 7 | 0x80); write(v >> 14 | 0x80); write(v >> 21); } else { write(v & 0x7F | 0x80); write(v >> 7 | 0x80); write(v >> 14 | 0x80); write(v >> 21 | 0x80); write(v >> 28); } } int sizeOfU30(int v) { if (v < 128 && v >= 0) { return 1; } else if (v < 16384 && v >= 0) { return 2; } else if (v < 2097152 && v >= 0) { return 3; } else if (v < 268435456 && v >= 0) { return 4; } else { return 5; } } } }