From e5cc479ae3801a2fc43b87eb2b64b4af965795c4 Mon Sep 17 00:00:00 2001 From: jzhou Date: Sun, 6 Mar 2011 00:24:45 +0000 Subject: [PATCH] Shrink the size of the final binary. If it is too large it will have problem executing on Tilera. We compress the virtual dispatch table: we use one row to represent the methods defined in interfaces that have the same prototype; and we do not generate colums for interfaces as there can not be instances of interfaces. Moreover, we do not generate methods that are never invoked. --- Robust/src/IR/ClassDescriptor.java | 19 ++- Robust/src/IR/Flat/BuildCode.java | 166 +++++++++++++++++++-- Robust/src/IR/Flat/BuildCodeMGC.java | 6 +- Robust/src/IR/Flat/BuildCodeMultiCore.java | 2 +- Robust/src/IR/State.java | 30 +++- Robust/src/IR/Tree/BuildIR.java | 10 ++ Robust/src/IR/Virtual.java | 116 +++++++------- 7 files changed, 277 insertions(+), 72 deletions(-) diff --git a/Robust/src/IR/ClassDescriptor.java b/Robust/src/IR/ClassDescriptor.java index 4e313bb7..ae11b75d 100644 --- a/Robust/src/IR/ClassDescriptor.java +++ b/Robust/src/IR/ClassDescriptor.java @@ -24,7 +24,7 @@ public class ClassDescriptor extends Descriptor { // for interfaces Vector superinterfaces; SymbolTable superIFdesc; - private boolean isInterface; + private int interfaceid; // for inner classes boolean isInnerClass=false; @@ -53,8 +53,12 @@ public class ClassDescriptor extends Descriptor { fields=new SymbolTable(); fieldvec=new Vector(); methods=new SymbolTable(); - this.isInterface = isInterface; - classid=UIDCount++; + if(isInterface) { + this.classid = -2; + this.interfaceid = -1; + } else { + classid=UIDCount++; + } this.packagename=packagename; superinterfaces = new Vector(); superIFdesc = new SymbolTable(); @@ -63,6 +67,9 @@ public class ClassDescriptor extends Descriptor { } public int getId() { + if(this.isInterface()) { + return this.interfaceid; + } return classid; } @@ -283,7 +290,11 @@ public class ClassDescriptor extends Descriptor { } public boolean isInterface() { - return this.isInterface; + return (this.classid == -2); + } + + public void setInterfaceId(int id) { + this.interfaceid = id; } public boolean isStatic() { diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 95645565..d12cc8ad 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -45,6 +45,7 @@ public class BuildCode { protected int maxtaskparams=0; protected int maxcount=0; ClassDescriptor[] cdarray; + ClassDescriptor[] ifarray; TypeDescriptor[] arraytable; SafetyAnalysis sa; CallGraph callgraph; @@ -66,6 +67,7 @@ public class BuildCode { fieldorder=new Hashtable(); flagorder=new Hashtable(); this.typeutil=typeutil; + checkMethods2Gen(); virtualcalls=new Virtual(state, null); printedfieldstbl = new Hashtable(); } @@ -248,6 +250,34 @@ public class BuildCode { postCodeGenCleanUp(); } + /* This method goes though the call graph and check which methods are really + * invoked and should be generated + */ + protected void checkMethods2Gen() { + MethodDescriptor md=typeutil.getMain(); + + if(md != null) { + // check the methods to be generated + state.setGenAllMethods(false); + } else { + // generate all methods + return; + } + this.state.addMethod2gen(md); + + Iterator it_classes = this.state.getClassSymbolTable().getDescriptorsIterator(); + while(it_classes.hasNext()) { + ClassDescriptor cd = (ClassDescriptor)it_classes.next(); + Iterator it_methods = cd.getMethodTable().getDescriptorsIterator(); + while(it_methods.hasNext()) { + md = (MethodDescriptor)it_methods.next(); + if(md.isStaticBlock() || md.getModifiers().isNative() || this.callgraph.getCallerSet(md).size() > 0 + || (cd.getSymbol().equals("Thread") && md.getSymbol().equals("staticStart"))) { + this.state.addMethod2gen(md); + } + } + } + } /* This method goes though the call graph and tag those methods that are @@ -500,6 +530,18 @@ public class BuildCode { while(methodit.hasNext()) { /* Classify parameters */ MethodDescriptor md=(MethodDescriptor)methodit.next(); + Set vec_md = this.state.getMethod2gen().getSet(md.getSymbol()); + boolean foundmatch = false; + for(Iterator matchit=vec_md.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + foundmatch=true; + break; + } + } + if(!foundmatch) { + continue; + } FlatMethod fm=state.getMethodFlat(md); if (!md.getModifiers().isNative()) { generateFlatMethod(fm, outmethod); @@ -548,7 +590,7 @@ public class BuildCode { (state.getArrayNumber((new TypeDescriptor(TypeDescriptor.BYTE)).makeArray(state).makeArray(state))+state.numClasses())); outstructs.println("#define NUMCLASSES "+state.numClasses()); - int totalClassSize = state.numClasses() + state.numArrays(); + int totalClassSize = state.numClasses() + state.numArrays() + state.numInterfaces(); outstructs.println("#define TOTALNUMCLASSANDARRAY "+ totalClassSize); if (state.TASK) { outstructs.println("#define STARTUPTYPE "+typeutil.getClass(TypeUtil.StartupClass).getId()); @@ -878,6 +920,9 @@ public class BuildCode { classit=state.getClassSymbolTable().getDescriptorsIterator(); while(classit.hasNext()) { ClassDescriptor cd=(ClassDescriptor)classit.next(); + if(cd.isInterface()) { + continue; + } fillinRow(cd, virtualtable, cd.getId()); } @@ -923,11 +968,20 @@ public class BuildCode { MethodDescriptor md=(MethodDescriptor)it.next(); if (md.isStatic()||md.getReturnType()==null) continue; - Vector numvec = virtualcalls.getMethodNumber(md); - for(int i = 0; i < numvec.size(); i++) { - int methodnum = numvec.elementAt(i).intValue(); - virtualtable[rownum][methodnum]=md; + Set vec_md = this.state.getMethod2gen().getSet(md.getSymbol()); + boolean foundmatch = false; + for(Iterator matchit=vec_md.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + foundmatch=true; + break; + } + } + if(!foundmatch) { + continue; } + int methodnum = virtualcalls.getMethodNumber(md); + virtualtable[rownum][methodnum]=md; } } @@ -941,11 +995,16 @@ public class BuildCode { Iterator it=state.getClassSymbolTable().getDescriptorsIterator(); cdarray=new ClassDescriptor[state.numClasses()]; + ifarray = new ClassDescriptor[state.numInterfaces()]; cdarray[0] = null; int interfaceid = 0; while(it.hasNext()) { ClassDescriptor cd=(ClassDescriptor)it.next(); - cdarray[cd.getId()] = cd; + if(cd.isInterface()) { + ifarray[cd.getId()] = cd; + } else { + cdarray[cd.getId()] = cd; + } } arraytable=new TypeDescriptor[state.numArrays()]; @@ -972,6 +1031,11 @@ public class BuildCode { TypeDescriptor arraytd=arraytable[i]; outclassdefs.println(arraytd.toPrettyString() +" "+(i+state.numClasses())); } + + for(int i=0; i0 ? cd.getSuperDesc() : null; + if(supercd != null && supercd.isInterface()) { + throw new Error("Super class can not be interfaces"); + } if (needcomma) outclassdefs.print(", "); if (supercd==null) @@ -1046,6 +1120,21 @@ public class BuildCode { outclassdefs.print(type); needcomma=true; } + + for(int i=0; itype*"+maxcount+"+"+virtualcalls.getMethodNumber(md).elementAt(0)+"])"); + output.print("))virtualtable["+generateTemp(fm,fc.getThis())+"->type*"+maxcount+"+"+virtualcalls.getMethodNumber(md)+"])"); } output.print("("); diff --git a/Robust/src/IR/Flat/BuildCodeMGC.java b/Robust/src/IR/Flat/BuildCodeMGC.java index f08ed4be..79ce5fcd 100644 --- a/Robust/src/IR/Flat/BuildCodeMGC.java +++ b/Robust/src/IR/Flat/BuildCodeMGC.java @@ -93,7 +93,6 @@ public class BuildCodeMGC extends BuildCode { // Output function prototypes and structures for parameters Iterator it=state.getClassSymbolTable().getDescriptorsIterator(); - int numclasses = this.state.numClasses(); while(it.hasNext()) { ClassDescriptor cn=(ClassDescriptor)it.next(); super.generateCallStructs(cn, outclassdefs, outstructs, outmethodheader, outglobaldefs, outglobaldefsprim); @@ -123,7 +122,7 @@ public class BuildCodeMGC extends BuildCode { /* Record maximum number of task parameters */ //outstructs.println("#define MAXTASKPARAMS "+maxtaskparams); /* Record maximum number of all types, i.e. length of classsize[] */ - outstructs.println("#define NUMTYPES "+(state.numClasses() + state.numArrays())); + outstructs.println("#define NUMTYPES "+(state.numClasses() + state.numArrays() + state.numInterfaces())); /* Record number of total cores */ outstructs.println("#define NUMCORES "+this.tcoreNum); /* Record number of active cores */ @@ -316,7 +315,6 @@ NextMethod: outmethod.println(" }"); } - } // else TODO normal java version - + } // else TODO normal java version } } diff --git a/Robust/src/IR/Flat/BuildCodeMultiCore.java b/Robust/src/IR/Flat/BuildCodeMultiCore.java index 7d67c3f0..7ce0e07d 100644 --- a/Robust/src/IR/Flat/BuildCodeMultiCore.java +++ b/Robust/src/IR/Flat/BuildCodeMultiCore.java @@ -305,7 +305,7 @@ public class BuildCodeMultiCore extends BuildCode { /* Record maximum number of task parameters */ outstructs.println("#define MAXTASKPARAMS "+maxtaskparams); /* Record maximum number of all types, i.e. length of classsize[] */ - outstructs.println("#define NUMTYPES "+(state.numClasses() + state.numArrays())); + outstructs.println("#define NUMTYPES "+(state.numClasses() + state.numArrays() + state.numInterfaces())); /* Record number of total cores */ outstructs.println("#define NUMCORES "+this.tcoreNum); /* Record number of active cores */ diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 30f89e46..54df5b66 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -16,6 +16,8 @@ public class State { this.sclasses=new SymbolTable(); this.treemethodmap=new Hashtable(); this.flatmethodmap=new Hashtable(); + this.genAllMethods = true; + this.methods2gen = new SymbolTable(); this.parsetrees=new HashSet(); this.arraytypes=new HashSet(); this.arraytonumber=new Hashtable(); @@ -180,9 +182,12 @@ public class State { public Set parsetrees; public Hashtable treemethodmap; public Hashtable flatmethodmap; + SymbolTable methods2gen; + boolean genAllMethods; private HashSet arraytypes; public Hashtable arraytonumber; private int numclasses=1; // start from 1 instead of 0 for multicore gc + private int numinterfaces = 0; private int numtasks=0; private int numstaticblocks=0; private int arraycount=0; @@ -239,16 +244,39 @@ public class State { if (classes.contains(tdn.getSymbol())) throw new Error("Class "+tdn.getSymbol()+" defined twice"); classes.add(tdn); - numclasses++; + if(tdn.isInterface()) { + numinterfaces++; + } else { + numclasses++; + } if((tdn.numstaticfields != 0) || (tdn.numstaticblocks != 0)) { sclasses.add(tdn); } } + public void setGenAllMethods(boolean flag) { + this.genAllMethods = flag; + } + + public void addMethod2gen(MethodDescriptor md) { + if(this.genAllMethods) { + throw new Error("The state.genAllMethods is TRUE, do not need to check methods to genenrate"); + } + this.methods2gen.add(md); + } + + public SymbolTable getMethod2gen() { + return this.methods2gen; + } + public int numClasses() { return numclasses; } + public int numInterfaces() { + return numinterfaces; + } + public int numStaticBlocks() { return numstaticblocks; } diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java index 8ec7fd66..742a9da9 100644 --- a/Robust/src/IR/Tree/BuildIR.java +++ b/Robust/src/IR/Tree/BuildIR.java @@ -19,6 +19,16 @@ public class BuildIR { public void buildtree(ParseNode pn, Set toanalyze) { parseFile(pn, toanalyze); + + // numering the interfaces + int if_num = 0; + Iterator it_classes = state.getClassSymbolTable().getValueSet().iterator(); + while(it_classes.hasNext()) { + ClassDescriptor cd = (ClassDescriptor)it_classes.next(); + if(cd.isInterface()) { + cd.setInterfaceId(if_num++); + } + } } Vector singleimports; diff --git a/Robust/src/IR/Virtual.java b/Robust/src/IR/Virtual.java index a46b6ad3..52c73104 100644 --- a/Robust/src/IR/Virtual.java +++ b/Robust/src/IR/Virtual.java @@ -1,5 +1,6 @@ package IR; import java.util.*; + import Analysis.Locality.LocalityBinding; import Analysis.Locality.LocalityAnalysis; @@ -7,14 +8,15 @@ import Analysis.Locality.LocalityAnalysis; public class Virtual { State state; LocalityAnalysis locality; - Hashtable> methodnumber; + Hashtable methodnumber; Hashtable classmethodcount; Hashtable localitynumber; // for interfaces int if_starts; + SymbolTable if_methods; - public Vector getMethodNumber(MethodDescriptor md) { + public Integer getMethodNumber(MethodDescriptor md) { return methodnumber.get(md); } @@ -30,11 +32,12 @@ public class Virtual { this.state=state; this.locality=locality; this.if_starts = 0; + this.if_methods = new SymbolTable(); classmethodcount=new Hashtable(); if (state.DSM||state.SINGLETM) localitynumber=new Hashtable(); else - methodnumber=new Hashtable>(); + methodnumber=new Hashtable(); doAnalysis(); } @@ -111,47 +114,51 @@ public class Virtual { if(!cd.isInterface()) { return 0; } - int start = 0; + int mnum = 0; if (classmethodcount.containsKey(cd)) return classmethodcount.get(cd).intValue(); // check the inherited interfaces Iterator it_sifs = cd.getSuperInterfaces(); while(it_sifs.hasNext()) { ClassDescriptor superif = (ClassDescriptor)it_sifs.next(); - start += numberMethodsIF(superif); + mnum += numberMethodsIF(superif); } for(Iterator it=cd.getMethods(); it.hasNext();) { MethodDescriptor md=(MethodDescriptor)it.next(); if (md.isStatic()||md.getReturnType()==null) continue; - boolean foundmatch=false; - // check if there is a matched method in inherited interfaces - it_sifs = cd.getSuperInterfaces(); - while(it_sifs.hasNext() && !foundmatch) { - ClassDescriptor superif = (ClassDescriptor)it_sifs.next(); - Set possiblematches_if=superif.getMethodTable().getSet(md.getSymbol()); - for(Iterator matchit=possiblematches_if.iterator(); matchit.hasNext();) { - MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); - if (md.matches(matchmd)) { - Vector num=methodnumber.get(matchmd); - if(!methodnumber.containsKey(md)) { - methodnumber.put(md, new Vector()); - } - Vector toadd = methodnumber.get(md); - toadd.addAll(num); - foundmatch=true; - } + Set vec_md = this.state.getMethod2gen().getSet(md.getSymbol()); + boolean foundmatch = false; + for(Iterator matchit=vec_md.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + foundmatch=true; + break; } } if(!foundmatch) { - Vector vec = new Vector(); - vec.add(new Integer(if_starts++)); - methodnumber.put(md, vec); - start++; + continue; + } + foundmatch=false; + // check if there is a matched method that has been assigned method num + Set possiblematches_if = if_methods.getSet(md.getSymbol()); + for(Iterator matchit=possiblematches_if.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + int num=methodnumber.get(matchmd); + methodnumber.put(md, new Integer(num)); + foundmatch=true; + break; + } + } + if(!foundmatch) { + methodnumber.put(md, new Integer(if_starts++)); + if_methods.add(md); + mnum++; } } - classmethodcount.put(cd, new Integer(start)); - return start; + classmethodcount.put(cd, new Integer(mnum)); + return mnum; } private int numberMethods(ClassDescriptor cd) { @@ -168,41 +175,44 @@ public class Virtual { MethodDescriptor md=(MethodDescriptor)it.next(); if (md.isStatic()||md.getReturnType()==null) continue; - boolean foundmatch=false; - if (superdesc!=null) { + Set vec_md = this.state.getMethod2gen().getSet(md.getSymbol()); + boolean foundmatch = false; + for(Iterator matchit=vec_md.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + foundmatch=true; + break; + } + } + if(!foundmatch) { + continue; + } + foundmatch=false; + // check if there is a matched method in methods defined in interfaces + Set possiblematches_if=if_methods.getSet(md.getSymbol()); + for(Iterator matchit=possiblematches_if.iterator(); matchit.hasNext();) { + MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); + if (md.matches(matchmd)) { + int num = methodnumber.get(matchmd); + methodnumber.put(md, new Integer(num)); + foundmatch=true; + break; + } + } + if (!foundmatch && superdesc!=null) { Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol()); for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) { MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); if (md.matches(matchmd)) { - Vector num = methodnumber.get(matchmd); - methodnumber.put(md, num); + int num = methodnumber.get(matchmd); + methodnumber.put(md, new Integer(num)); foundmatch=true; break; } } } - // check if there is a matched method in inherited interfaces - Iterator it_sifs = cd.getSuperInterfaces(); - while(it_sifs.hasNext()) { - ClassDescriptor superif = (ClassDescriptor)it_sifs.next(); - Set possiblematches_if=superif.getMethodTable().getSet(md.getSymbol()); - for(Iterator matchit=possiblematches_if.iterator(); matchit.hasNext();) { - MethodDescriptor matchmd=(MethodDescriptor)matchit.next(); - if (md.matches(matchmd)) { - Vector num = methodnumber.get(matchmd); - if(!methodnumber.containsKey(md)) { - methodnumber.put(md, new Vector()); - } - Vector toadd = methodnumber.get(md); - toadd.addAll(num); - foundmatch=true; - } - } - } if (!foundmatch) { - Vector vec = new Vector(); - vec.add(new Integer(start++)); - methodnumber.put(md, vec); + methodnumber.put(md, new Integer(start++)); mnum++; } } -- 2.34.1