From 53ca4456abf8f30b1e45ae73379be6d053f2b292 Mon Sep 17 00:00:00 2001 From: adash Date: Wed, 17 Oct 2007 03:03:57 +0000 Subject: [PATCH] Add prefetch analysis for FlatFieldNode. --- Robust/src/Analysis/Prefetch/:w | 193 ++++++++++++++++++ .../Analysis/Prefetch/PrefetchAnalysis.class | Bin 0 -> 5318 bytes .../Analysis/Prefetch/PrefetchAnalysis.java | 144 ++++++++++++- .../Prefetch/PrefetchAnalysis.java.old | 112 ++++++++++ .../src/Analysis/Prefetch/PrefetchPair.class | Bin 0 -> 805 bytes .../src/Analysis/Prefetch/PrefetchPair.java | 27 +++ 6 files changed, 473 insertions(+), 3 deletions(-) create mode 100644 Robust/src/Analysis/Prefetch/:w create mode 100644 Robust/src/Analysis/Prefetch/PrefetchAnalysis.class create mode 100644 Robust/src/Analysis/Prefetch/PrefetchAnalysis.java.old create mode 100644 Robust/src/Analysis/Prefetch/PrefetchPair.class create mode 100644 Robust/src/Analysis/Prefetch/PrefetchPair.java diff --git a/Robust/src/Analysis/Prefetch/:w b/Robust/src/Analysis/Prefetch/:w new file mode 100644 index 00000000..bdd1c501 --- /dev/null +++ b/Robust/src/Analysis/Prefetch/:w @@ -0,0 +1,193 @@ +package Analysis.Prefetch; + +import java.util.*; +import Analysis.CallGraph.CallGraph; +import Analysis.Prefetch.PrefetchPair; +import IR.SymbolTable; +import IR.State; +import IR.TypeUtil; +import IR.MethodDescriptor; +import IR.Flat.*; +import IR.ClassDescriptor; + +public class PrefetchAnalysis { + State state; + CallGraph callgraph; + TypeUtil typeutil; + + public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) { + this.typeutil=typeutil; + this.state=state; + this.callgraph=callgraph; + DoPrefetch(); + } + + private void DoPrefetch() { + Iterator classit=state.getClassSymbolTable().getDescriptorsIterator(); + while(classit.hasNext()) { + ClassDescriptor cn=(ClassDescriptor)classit.next(); + doMethodAnalysis(cn); + } + } + + private void doMethodAnalysis(ClassDescriptor cn) { + Iterator methodit=cn.getMethods(); + while(methodit.hasNext()) { + /* Classify parameters */ + MethodDescriptor md=(MethodDescriptor)methodit.next(); + FlatMethod fm=state.getMethodFlat(md); + doFlatNodeAnalysis(fm); + //tovisit = fm.getNodeSet(); + //visited = null; + //while (!tovisit.isEmpty()) { + // FlatNode fn = tovisit.iterator().next(); + // tovisit.remove(fn); + // doFlatNodeAnalysis(fn); + //} + } + } + + private void doFlatNodeAnalysis(FlatMethod fm) { + HashSet tovisit = new HashSet(); + //Set tovisit; + Hashtable prefetch_hash = new Hashtable(); + while(!tovisit.isEmpty()) { + FlatNode fn = (FlatNode)tovisit.iterator().next(); + tovisit.remove(fn); + System.out.println("DEBUG -> kind = " + fn.kind()); + FlatElementNode fen = (FlatElementNode)fn; + switch(fn.kind()) { + //Take care of all Flat nodes and generate prefetches and analysis for them + case FKind.FlatAtomicEnterNode: + break; + case FKind.FlatAtomicExitNode: + break; + case FKind.FlatGlobalConvNode: + break; + case FKind.FlatTagDeclaration: + break; + case FKind.FlatCall: + break; + case FKind.FlatFieldNode: + FlatFieldNode ffn = (FlatFieldNode) fn; + System.out.println("DEBUG -> is an object"); + System.out.println(ffn.toString()); + break; + case FKind.FlatElementNode: + //Set pp = new Set(); + if (fen.getDst().getType().isPtr()) { + System.out.println("DEBUG -> is a pointer"); + System.out.println(fen.toString()); + PrefetchPair pp = new PrefetchPair(fen.getDst(),(float)1.0); + prefetch_hash.put(fn, pp); + } + break; + case FKind.FlatSetElementNode: + break; + case FKind.FlatSetFieldNode: + break; + case FKind.FlatNew: + break; + case FKind.FlatOpNode: + break; + case FKind.FlatCastNode: + break; + case FKind.FlatLiteralNode: + break; + case FKind.FlatReturnNode: + break; + case FKind.FlatNop: + System.out.println("/* nop */"); + break; + case FKind.FlatCheckNode: + break; + case FKind.FlatFlagActionNode: + break; + } + } + } + + private void doAnalysis() { + Iterator classit=state.getClassSymbolTable().getDescriptorsIterator(); + while(classit.hasNext()) { + ClassDescriptor cn=(ClassDescriptor)classit.next(); + Iterator methodit=cn.getMethods(); + while(methodit.hasNext()) { + /* Classify parameters */ + MethodDescriptor md=(MethodDescriptor)methodit.next(); + FlatMethod fm=state.getMethodFlat(md); + System.out.println("DEBUG -> "); + printMethod(fm); + } + } + } + + private void printMethod(FlatMethod fm) { + System.out.println(fm.getMethod()+" {"); + HashSet tovisit=new HashSet(); + HashSet visited=new HashSet(); + int labelindex=0; + Hashtable nodetolabel=new Hashtable(); + tovisit.add(fm); + FlatNode current_node=null; + //Assign labels 1st + //Node needs a label if it is + while(!tovisit.isEmpty()) { + FlatNode fn=(FlatNode)tovisit.iterator().next(); + tovisit.remove(fn); + visited.add(fn); + System.out.println("DEBUG -> " + fn.kind()); + + for(int i=0;i0) { + //1) Edge >1 of node + nodetolabel.put(nn,new Integer(labelindex++)); + } + if (!visited.contains(nn)&&!tovisit.contains(nn)) { + tovisit.add(nn); + } else { + //2) Join point + nodetolabel.put(nn,new Integer(labelindex++)); + } + } + } + //Do the actual printing + tovisit=new HashSet(); + visited=new HashSet(); + tovisit.add(fm); + while(current_node!=null||!tovisit.isEmpty()) { + if (current_node==null) { + current_node=(FlatNode)tovisit.iterator().next(); + tovisit.remove(current_node); + } + visited.add(current_node); + if (nodetolabel.containsKey(current_node)) + System.out.println("L"+nodetolabel.get(current_node)+":"); + if (current_node.numNext()==0) { + System.out.println(" "+current_node.toString()); + current_node=null; + } else if(current_node.numNext()==1) { + System.out.println(" "+current_node.toString()); + FlatNode nextnode=current_node.getNext(0); + if (visited.contains(nextnode)) { + System.out.println("goto L"+nodetolabel.get(nextnode)); + current_node=null; + } else + current_node=nextnode; + } else if (current_node.numNext()==2) { + /* Branch */ + System.out.println(" "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1)))); + if (!visited.contains(current_node.getNext(1))) + tovisit.add(current_node.getNext(1)); + if (visited.contains(current_node.getNext(0))) { + System.out.println("goto L"+nodetolabel.get(current_node.getNext(0))); + current_node=null; + } else + current_node=current_node.getNext(0); + } else throw new Error(); + } + System.out.println("}"); + } + +} diff --git a/Robust/src/Analysis/Prefetch/PrefetchAnalysis.class b/Robust/src/Analysis/Prefetch/PrefetchAnalysis.class new file mode 100644 index 0000000000000000000000000000000000000000..e07068c6fbca249b098f4376191e18ce63388dc0 GIT binary patch literal 5318 zcma)A33yXg7XI(c^3wE`LLoq~Km>tOQtMhYEvQh+UKt8hz%6Z`C7329Nzn?3Ivvzu zM8m0a24sUeeCMQPVW)-(MaH|tu$>POrvRUuM?YP5oho)YF%7#Vxyyk)4&3j+19EDO0}ra$>%=T+=0hqTR`G~{ zEgJL3bOGnI$urCABlkY3x?(x69XNmJ;?>TqgH0ZWPG?b#HbuE!RHn^Jxh=x6La zKIo4|tMzDOB+wcQM=B+AQBzo&DJ|^Io;Kf{{O+Zx`%yL7lABIpk_Gso$r=5cL-V3Qu9 zjOq#FW>55#jrE)#2sL@ecr?6+_ceSV1-*w4HGG7RRUFXp3H~9_H+#$R;ZW1Kh(FXQ zQ#&oEk<>se5N6fnY51pH1u5lIGG(u>3FyHl8E8sPFAhXK{*Wi!uuyM|arI~TT*DXm zT*a3fzQWfkzR~clbjqMqB-1IL9>`pmq5V$7_tJ^`@q>nc;YSVsmPY*tKWX?G2kDh; zbtVM$7CmHSo zhhloOF4Yn?P1v!ItETbsu}VB1538~{91D9$D$ImxLL?Gqh{Q61A-`^JYKF1QEIr-u zAi;?y8mPwHYt~~%YSy*4G=zi6f-Nc;X`n!cMu_MkS7j&+5Z7ihHaa<`NBk^VPH=f9 zJyUdwDEcK;KqU;;>KDcgXqZPB2^lYaQbG(@nW|HSlbf2w5+#(TUnC9)j4~jkdo5KO z#&kytvn;z&P5CnaSWt{rN(Td+NumM;85;~9i@&LfNnB!DoUQCg8lwiH6Ixnh?R0t| z?H@JN) z;IW`}e+$*M`&(P}5H&2z*3hhXIwq4GIS{~wR$2N2#ZseR=W@it=0cW7%2`>6LOCXK z=ITY04Ok9_x_K_87eU`IR}SV$A(wBL$7L$`xE$BagCt0%6P_2t}vr%!wS^k}00; z?R3^#T4juRHfJJ{ockr^umY^nz(ur3i7}-8f89G4W+t(vhFL{#64ufMCeLTX8^5To zZmD$`GrFgi%zv}uW#*eBEAx#0aisi%BYCwugO_3}AD+W(A&+9C=izMhJbxkJ=U71l z>>M|uiLFjb9W2J$p{1P=rDZ#yl#bc~OR0AUtfgJB&FzGJ2UN~Fwvb)mJhp?NvhB@< zeUJwidho{B8~sS{k0HD-D)O{XZ=i4sU_|M5SQ5xf@VYo^7xD$x!o>m4fW0V~Uh3^c zkNBYjnN0>zQ=l067|3k~@i!Pl;lXg)tjK#oa)UGZW+SI}R04(5y-Cp?4h+#fYvsme z3H0(=OWoE^6vYp{mD$BKba3iV4bqL3w`OWeznQoXXQ+PfutU8pUqNXciG*x1O}|fV7JX>PvD5hQCOB7 zCQw}8VHZ@->$dH}K+4{VL0uS3sh*-E6Br`b4o%>w1coIr+<4nSeNLqHyeQC1z!iK} zk~WZ!htE(x!}*Nl6Q%34ak<$Nx4+xB9F&rU6hN)i~! z-fb@`O@Q_fkBdEVu`4bTaj`8fHpj&#$?f&2lAG=}xYY!XmYT9J_c;nr&Xc2K5;!)2 zbAP`rFTrK+nT`WdP_yVE1&zE zv>uz-ot$>FW^ieSoU2k}Lr#IEqKBoT&{gOzFxE|yeQM$HzMk%$+u=)~((Pb#7lyhG zN)`26xC2$DD7j>Gy|to89C;mu4Ayp6k98Q9V+rNE3)A{)=8}$lGS7%(g>=&xU%s?x zY|0ahq|;7GI*k*j(rJcBj!)C1cTB5H?+i2jkifWik_GudSj;Oi&zT84|ByN z%oB4kUo`Nep%rI~3vrIdPW(- zrOJA&RPMwo$acBX?v0MfWk zoFI5N%ljS%W&=TRBmXPd#Ngb^Fx-bJ*o+z2LMY#gIoL+kc(qPK))ho*C(HVJZj(fk zQ3*^)pr&Xd0mTH8Bw$TX0hp!2nnZq|O`>XXz3|y-%cOOv?j0ne2+Q z(TWxgk;I{Cw6atCy1n>()y)8@LY9ahna>9WGg+&n32 z*P*XBIVdm&#r5&S^LIE{Ubn>$&F^lEX@J}Q1e}Hm;&M6epJRvJ>n0XUJJ=Q1Qy=z( zp%EFc6`gM2ubdbsy*DH6JxQ9f4#Tr}eOdvwV)fN7H0UQY$B&Bw-{h-VY?M;vlf}^5Xw_$Ny-*x;M6Qh40SRi=m>L; z5$HkZm@mcBK~gtHW-Yu~J0#UgPUfn1a7EG}d;H*%F3jR-Hv2)YEtwL(q8;ldurL$L=Ri8t`E*pCC^U3?-wpDC62T&ckqN*%sb f7UL_W9bYR;@r}}fZ> prefetch_hash; public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) { this.typeutil=typeutil; this.state=state; this.callgraph=callgraph; - doAnalysis(); + prefetch_hash = new Hashtable(); + DoPrefetch(); + } + + private void DoPrefetch() { + Iterator classit=state.getClassSymbolTable().getDescriptorsIterator(); + while(classit.hasNext()) { + ClassDescriptor cn=(ClassDescriptor)classit.next(); + doMethodAnalysis(cn); + } + } + + private void doMethodAnalysis(ClassDescriptor cn) { + Iterator methodit=cn.getMethods(); + while(methodit.hasNext()) { + /* Classify parameters */ + MethodDescriptor md=(MethodDescriptor)methodit.next(); + FlatMethod fm=state.getMethodFlat(md); + doFlatNodeAnalysis(fm); + } + } + + private void doFlatNodeAnalysis(FlatMethod fm) { + Set tovisit = fm.getNodeSet(); //Flat nodes to process + tovisit.add(fm); + while(!tovisit.isEmpty()) { + HashSet parentnodes = new HashSet(); + HashSet s = new HashSet(); + FlatNode fn = (FlatNode)tovisit.iterator().next(); + //Create a set of parent nodes for any given node + for(int i = 0; i < fn.numPrev(); i++){ + if(fn.getPrev(i) != null) + parentnodes.add(fn.getPrev(i)); + } + tovisit.remove(fn); + //System.out.println("DEBUG -> kind = " + fn.kind()); + switch(fn.kind()) { + case FKind.FlatCondBranch: + //TODO: make this a method + FlatCondBranch fcb = (FlatCondBranch) fn; + System.out.print("DEBUG -> conditional\t"); + System.out.println(fcb.toString("")); + break; + case FKind.FlatAtomicEnterNode: + break; + case FKind.FlatAtomicExitNode: + break; + case FKind.FlatGlobalConvNode: + break; + case FKind.FlatTagDeclaration: + break; + case FKind.FlatCall: + break; + case FKind.FlatFieldNode: + //TODO: make this a method + // This implementation takes care of a case where int x = f.g + // => f needs to be prefetched and moved up in the parentnode + FlatFieldNode ffn = (FlatFieldNode) fn; + System.out.print("DEBUG -> is an object\t"); + System.out.println(ffn.toString()); + TempDescriptor currnode = ffn.getSrc(); + double prob = 1.0; + if(ffn.getDst().getType().isPtr()) { + PrefetchPair pp = new PrefetchPair(currnode,(float)prob); + if (prefetch_hash.containsKey(fn)) { + s = prefetch_hash.remove(fn); + } + s.add(pp); + prefetch_hash.put(fn, s); + } + /* Traverse parent nodes */ + for (int i = 0; i < parentnodes.size(); i++) { + FlatNode pnode = (FlatNode) parentnodes.iterator().next(); + if (prefetch_hash.containsKey(pnode)) { + //Get PrefetchPair and for each TempDescriptor in the prefetch pair + // compare it with the temp descriptor of its child + HashSet pp = prefetch_hash.remove(pnode); + boolean found = false; + for (int j = 0; j < pp.size(); j++) { + PrefetchPair tmp = (PrefetchPair) pp.iterator().next(); + //If match exists then find new probability + if (tmp.td.toString() == currnode.toString()) { + tmp.num = tmp.num * (float)prob; + prefetch_hash.put(pnode, pp); + found = true; + break; + } + } + + //If match does not exists then add the current prefetchpair to parentprefetchpair + if (!found) { + PrefetchPair moveup = new PrefetchPair(currnode, (float)prob); + pp.add(moveup); + prefetch_hash.put(pnode, pp); + } + } + } + break; + case FKind.FlatElementNode: + //TODO: make this a method + FlatElementNode fen = (FlatElementNode)fn; + if (fen.getDst().getType().isPtr()) { + System.out.print("DEBUG -> is a array\t"); + System.out.println(fen.toString()); + PrefetchPair pp = new PrefetchPair(fen.getSrc(),(float)1.0); + if (prefetch_hash.containsKey(fn)) { + s = prefetch_hash.get(fn); + s.add(pp); + prefetch_hash.put(fn, s); + } + //TODO: add the else part + } + break; + case FKind.FlatSetElementNode: + break; + case FKind.FlatSetFieldNode: + break; + case FKind.FlatNew: + break; + case FKind.FlatOpNode: + break; + case FKind.FlatCastNode: + break; + case FKind.FlatLiteralNode: + break; + case FKind.FlatReturnNode: + break; + case FKind.FlatNop: + //System.out.println("/* nop */"); + break; + case FKind.FlatCheckNode: + break; + case FKind.FlatFlagActionNode: + break; + } + } } private void doAnalysis() { - Iterator classit=state.getClassSymbolTable().getDescriptorsIterator( -); + Iterator classit=state.getClassSymbolTable().getDescriptorsIterator(); while(classit.hasNext()) { ClassDescriptor cn=(ClassDescriptor)classit.next(); Iterator methodit=cn.getMethods(); @@ -31,6 +167,7 @@ public class PrefetchAnalysis { /* Classify parameters */ MethodDescriptor md=(MethodDescriptor)methodit.next(); FlatMethod fm=state.getMethodFlat(md); + System.out.println("DEBUG -> "); printMethod(fm); } } @@ -50,6 +187,7 @@ public class PrefetchAnalysis { FlatNode fn=(FlatNode)tovisit.iterator().next(); tovisit.remove(fn); visited.add(fn); + System.out.println("DEBUG -> " + fn.kind()); for(int i=0;i0) { + //1) Edge >1 of node + nodetolabel.put(nn,new Integer(labelindex++)); + } + if (!visited.contains(nn)&&!tovisit.contains(nn)) { + tovisit.add(nn); + } else { + //2) Join point + nodetolabel.put(nn,new Integer(labelindex++)); + } + } + } + //Do the actual printing + tovisit=new HashSet(); + visited=new HashSet(); + tovisit.add(fm); + while(current_node!=null||!tovisit.isEmpty()) { + if (current_node==null) { + current_node=(FlatNode)tovisit.iterator().next(); + tovisit.remove(current_node); + } + visited.add(current_node); + if (nodetolabel.containsKey(current_node)) + System.out.println("L"+nodetolabel.get(current_node)+":"); + if (current_node.numNext()==0) { + System.out.println(" "+current_node.toString()); + current_node=null; + } else if(current_node.numNext()==1) { + System.out.println(" "+current_node.toString()); + FlatNode nextnode=current_node.getNext(0); + if (visited.contains(nextnode)) { + System.out.println("goto L"+nodetolabel.get(nextnode)); + current_node=null; + } else + current_node=nextnode; + } else if (current_node.numNext()==2) { + //Branch + System.out.println(" "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1)))); + if (!visited.contains(current_node.getNext(1))) + tovisit.add(current_node.getNext(1)); + if (visited.contains(current_node.getNext(0))) { + System.out.println("goto L"+nodetolabel.get(current_node.getNext(0))); + current_node=null; + } else + current_node=current_node.getNext(0); + } else throw new Error(); + } + System.out.println("}"); + } + +} diff --git a/Robust/src/Analysis/Prefetch/PrefetchPair.class b/Robust/src/Analysis/Prefetch/PrefetchPair.class new file mode 100644 index 0000000000000000000000000000000000000000..7005f65add46353175cd29f30b94059cece36bd9 GIT binary patch literal 805 zcmZ`%T~8BH5IuLhblYX2P^x@bzyj)a5jIBOAS8aIi3w36goMX!d#RUfx6SsJ#DArU zltdGMfIrH3Zd)Zl`mkqaXU@!-ncd%ie*6OP0=q6|u%3s9#|A16HeA?P&tcQpEtkP3 z#(SE>Gh=-RRR@89rJDjvhwndywK&q@iEMY@$zCH>UEN9dm_KK}G|Vd*H*e)KNxv;1 zY697Pl_-56knyXh0`}WZQwkIgRU$w1+jW_qMD>`FvOh_wX6l@l)Mf&K6~8)(DUj2h zW1Xs`#mUIKh%Tcrj*?b5igIfAxYJJ?vZjpa{81{;rEYvaid4F5*d9uF;9(X84@E2p zEZ*($rmy0rOu5~@hiyFfu#6Ss?J#uU;StILYp;_i{?b#u@Snne$4Cjx-L(B!zmN^h zOGVwTOnB2B|Nh|jcNx#Ym2UAz-S#H)QQ;S#;lGjL!##<>9Oj9_tW0au;~9t#`BtG7 zv{S(~#J3@Bk?6uAPLu2n=}Tk!OU6y>f}sc7SFnPuD`aj8i!3q9HnsCqo~5=hM;td; zr5)*ghxL_IegtB67%UNaVWJuB6}1et{1f)sHKvN$0i0lf+yMEaOMigryB(HUvC0|? GYkvWImY}f! literal 0 HcmV?d00001 diff --git a/Robust/src/Analysis/Prefetch/PrefetchPair.java b/Robust/src/Analysis/Prefetch/PrefetchPair.java new file mode 100644 index 00000000..1c23f82f --- /dev/null +++ b/Robust/src/Analysis/Prefetch/PrefetchPair.java @@ -0,0 +1,27 @@ +package Analysis.Prefetch; +import IR.Flat.*; +import java.util.*; +import IR.*; + +public class PrefetchPair { + TempDescriptor td; + FieldDescriptor fd; + public float num; + + public PrefetchPair() { + } + + public PrefetchPair(TempDescriptor td, float prob) { + this.td = td; + num = prob; + } + + public TempDescriptor getTemp() { + return td; + } + + public String toString() { + //if(getTemp()!=null) + return"<"+getTemp()+">"; + } +} -- 2.34.1