8 Jan 2007 22:15
Re: datalog operations allowed
David Brumley <dbrumley <at> cs.cmu.edu>
2007-01-08 21:15:44 GMT
2007-01-08 21:15:44 GMT
Hi John,
I'm having troubles building bddbddb. Are there instructions anywhere?
If I just type 'make jikes' in bddbddb, I get:
*** Semantic Error: You need to modify your classpath, sourcepath,
bootclasspath, and/or extdirs setup. Jikes could not find package
"java.lang" in:
.
javabdd-2.0.jar
jwutil-1.0.jar
weka.jar
jdom.jar
.
make: *** [_jikes] Error 1
So I modify BUILD_CLASSPATH in the Makefile to include ${CLASSPATH}.
Then I get with 'make jikes':
jikes -target 1.3
-classpath .:/usr/java/jdk1.5.0_07/jre/lib/rt.jar:.:javabdd-2.
0.jar:jwutil-1.0.jar:weka.jar:jdom.jar <at> .source_list
Issued 1 semantic warning compiling
"net/sf/bddbddb/ir/BDDInterpreter.java":
69. InferenceRule ir = (InferenceRule) o;
....<many more warnings>.....
*** Semantic Error: The type of the left sub-expression,
"net.sf.bddbddb.ir.Oper
ation", cannot possibly be an instance of type
"net.sf.bddbddb.dataflow.PartialR
edundancy$Phi".
162. Phi p = (Phi) e2.op;
^---^
*** Semantic Error: An expression of type "net.sf.bddbddb.ir.Operation"
cannot b
e cast into type "net.sf.bddbddb.dataflow.Phi".
234. subExpression = new
Expression(phi, new
LinkedList(),depth);
^-----------------------
------------------^
*** Semantic Error: No applicable overload was found for a constructor
with sign
ature "Expression(net.sf.bddbddb.dataflow.PartialRedundancy.Phi,
java.util.Linke
dList, int)" in type "net.sf.bddbddb.dataflow.PartialRedundancy
$Expression". Per
haps you wanted the overloaded version
"Expression(net.sf.bddbddb.ir.Operation o
p, java.util.List subExpressions, int depth);" instead?
Any idea? I've attached a .txt of the make for easier parsing.
As for changes to bddbddb, I'd like to add:
bit shifting
multiplication
addition
if-then-else
as bdd operations. Limiting ourselves to a finite domain is fine, but
its going to be up to machine word sizes. So I think adding the
multiplication table won't be tractable.
Can we add the above operations as bdd operations in terms of the
circuit?
Thanks,
David
On Mon, 2006-11-27 at 10:45 -0800, John Whaley wrote:
> Hi David,
>
> For operations like addition and multiplication, you will need to
> build up a BDD that implements that function and load it in. For
> example, for multiplication you will need to make your own BDD that
> contains the multiplication table, i.e. it should have these tuples:
>
> mult(1,1,1).
> mult(1,2,2).
> mult(2,1,2).
> mult(2,2,4).
> mult(3,1,3).
> mult(3,2,6).
> ...
>
> As you guessed, BDDs aren't too good at representing multiplication,
> but if you limit the number (up to say, 256x256) it should be
> tractable. Addition is no problem.
>
> Adding native support for addition would be pretty easy as the pieces
> are mostly there. Just need to edit the parser to parse it correctly:
> see parseRuleTerm() in DatalogParser.java, and then use buildAdd() in
> BDDDomain.java or add() in BDDBitVector.java to actually build the
> addition relation.
>
> Let me know if you have any more questions.
>
> -John
>
>
> On 11/16/06, David Brumley <dbrumley <at> cs.cmu.edu> wrote:
> > Hi,
> > I'm looking at doing points-to analysis for x86 assembly, and was
> > interested in using bddbddb. x86 memory references are generally of the
> > form base+(index*scale)+ displacement. Thus, my analysis requires
> > addition and potentially multiplication and even less potentially,
> > though possible, modulus. (I understand multiplication is sometimes bad
> > for bdd's.)
> >
> >
> > Does bddbddb support addition and/or multiplication in rules, i.e., can
> > I write:
> >
> > fact(a,2).
> > fact(b,3).
> > foo(X,Y,Z) :- fact(X,I1), fact(Y,I2), Z is I1+ I2.
> >
> > and on query:
> > -? foo(a,b,Sum).
> >
> > Sum is 5
> >
> >
> > Thanks!
> > David
> >
> >
> >
> > -------------------------------------------------------------------------
> > Take Surveys. Earn Cash. Influence the Future of IT
> > Join SourceForge.net's Techsay panel and you'll get the chance to share your
> > opinions on IT & business topics through brief surveys - and earn cash
> > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> > _______________________________________________
> > bddbddb-devel mailing list
> > bddbddb-devel <at> lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bddbddb-devel
> >
>
Script started on Mon 08 Jan 2007 04:03:41 PM EST [dbrumley <at> rtfm bddbddb]$ jikes --version Jikes Compiler - Version 1.22 - 3 October 2004 Copyright (C) IBM Corporation 1997-2003, 2004. - Licensed Materials - Program Property of IBM - All Rights Reserved. Originally written by Philippe Charles and David Shields of IBM Research, Jikes is now maintained and refined by the Jikes Project at: <http://ibm.com/developerworks/opensource/jikes> Please consult this URL for more information and for reporting problems. [dbrumley <at> rtfm bddbddb]$ java -version java version "1.5.0_07" Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-b03) Java HotSpot(TM) Client VM (build 1.5.0_07-b03, mixed mode, sharing) [dbrumley <at> rtfm bddbddb]$ make jikes Building source list... jikes -target 1.3 -classpath .:/usr/java/jdk1.5.0_07/jre/lib/rt.jar:.:javabdd-2.0.jar:jwutil-1.0.jar:weka.jar:jdom.jar <at> .source_list Issued 1 semantic warning compiling "net/sf/bddbddb/ir/BDDInterpreter.java": 69. InferenceRule ir = (InferenceRule) o; ^^ *** Semantic Warning: Local "ir" shadows a field of the same name in "net.sf.bddbddb.ir.Interpreter". Issued 4 semantic warnings compiling "net/sf/bddbddb/Solver.java": 613. Collection rules = nav.prev(r); ^---^ *** Semantic Warning: Local "rules" shadows a field of the same name in "net.sf.bddbddb.Solver". 615. InferenceRule ir = (InferenceRule) i.next(); ^^ *** Semantic Warning: Local "ir" shadows a field of the same name in "net.sf.bddbddb.Solver". 1017. InferenceRule ir = (InferenceRule) rules.get(i); ^^ *** Semantic Warning: Local "ir" shadows a field of the same name in "net.sf.bddbddb.Solver". 1041. InferenceRule ir = (InferenceRule) i.next(); ^^ *** Semantic Warning: Local "ir" shadows a field of the same name in "net.sf.bddbddb.Solver". Issued 2 semantic warnings compiling "net/sf/bddbddb/BDDInferenceRule.java": 34. protected BDDSolver solver; ^----^ *** Semantic Warning: Field "solver" shadows a field of the same name in "net.sf.bddbddb.InferenceRule". 39. protected BDD[] oldRelationValues; ^---------------^ *** Semantic Warning: Field "oldRelationValues" shadows a field of the same name in "net.sf.bddbddb.InferenceRule". Issued 1 semantic warning compiling "net/sf/bddbddb/order/EpisodeCollection.java": 182. TrialInfo best = null; ^--^ *** Semantic Warning: Local "best" shadows a field of the same name in "net.sf.bddbddb.order.EpisodeCollection". Issued 1 semantic warning compiling "net/sf/bddbddb/FindBestDomainOrder.java": 569. Element constraintInfo = c.toXMLElement(solver); ^------------^ *** Semantic Warning: Local "constraintInfo" shadows a field of the same name in "net.sf.bddbddb.FindBestDomainOrder". Found 9 semantic errors and issued 3 warnings compiling "net/sf/bddbddb/dataflow/PartialRedundancy.java": 108. DataflowSolver solver = new DataflowSolver(); ^----^ *** Semantic Warning: Local "solver" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialRedundancy". 161. if(e2.op instanceof Phi && !visited.contains(e2.op)){ ^------------------^ *** Semantic Error: The type of the left sub-expression, "net.sf.bddbddb.ir.Operation", cannot possibly be an instance of type "net.sf.bddbddb.dataflow.PartialRedundancy$Phi". 162. Phi p = (Phi) e2.op; ^---^ *** Semantic Error: An expression of type "net.sf.bddbddb.ir.Operation" cannot be cast into type "net.sf.bddbddb.dataflow.Phi". 234. subExpression = new Expression(phi, new LinkedList(),depth); ^-----------------------------------------^ *** Semantic Error: No applicable overload was found for a constructor with signature "Expression(net.sf.bddbddb.dataflow.PartialRedundancy.Phi, java.util.LinkedList, int)" in type "net.sf.bddbddb.dataflow.PartialRedundancy$Expression". Perhaps you wanted the overloaded version "Expression(net.sf.bddbddb.ir.Operation op, java.util.List subExpressions, int depth);" instead? 257. public static class Phi extends Operation{ ^-------^ *** Semantic Error: Type "net.sf.bddbddb.dataflow.Operation" was not found. 319. return new Phi(dest,operations); ^----------------------^ *** Semantic Error: The type of this return expression, "net.sf.bddbddb.dataflow.PartialRedundancy$Phi", does not match the return type of the method, "net.sf.bddbddb.ir.Operation". 944. Set latest = ((LatestFact) PartialRedundancy.this.latest.getFact((Operation) o)).expressions; ^----^ *** Semantic Warning: Local "latest" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialRedundancy". 1215. Expression e; ^--------^ *** Semantic Error: The static type "net.sf.bddbddb.dataflow.PartialRedundancy$ExpressionWrapper" must use a qualified name to access the non-static member type "net.sf.bddbddb.dataflow.PartialRedundancy$Expression" of the enclosing type "net.sf.bddbddb.dataflow.PartialRedundancy". 1220. public ExpressionWrapper(Expression e) { ^--------^ *** Semantic Error: The static type "net.sf.bddbddb.dataflow.PartialRedundancy$ExpressionWrapper" must use a qualified name to access the non-static member type "net.sf.bddbddb.dataflow.PartialRedundancy$Expression" of the enclosing type "net.sf.bddbddb.dataflow.PartialRedundancy". 1345. int number = expressions.get(this); ^----^ *** Semantic Warning: Local "number" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialRedundancy$Expression". 1366. if(subE.op instanceof Phi){ ^--------------------^ *** Semantic Error: The type of the left sub-expression, "net.sf.bddbddb.ir.Operation", cannot possibly be an instance of type "net.sf.bddbddb.dataflow.PartialRedundancy$Phi". 1367. Phi phi = (Phi) subE.op; ^-----^ *** Semantic Error: An expression of type "net.sf.bddbddb.ir.Operation" cannot be cast into type "net.sf.bddbddb.dataflow.Phi". Found 2 semantic errors and issued 7 warnings compiling "net/sf/bddbddb/dataflow/PartialOrder.java": 191. public class PartialOrderTF extends TransferFunction implements OperationVisitor { ^--------------^ *** Semantic Error: Type "net.sf.bddbddb.dataflow.OperationVisitor" was not found. 204. op.visit(this); ^------------^ *** Semantic Error: No applicable overload for a method with signature "visit(net.sf.bddbddb.dataflow.PartialOrder.PartialOrderTF)" was found in type "net.sf.bddbddb.ir.Operation". Perhaps you wanted the overloaded version "java.lang.Object visit(net.sf.bddbddb.ir.OperationVisitor i);" instead? 668. ConstraintGraph graph = new ConstraintGraph(); ^---^ *** Semantic Warning: Local "graph" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 745. List constraints = new LinkedList(); ^---------^ *** Semantic Warning: Local "constraints" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 758. List constraints = new LinkedList(); ^---------^ *** Semantic Warning: Local "constraints" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 820. ConstraintGraph graph = (ConstraintGraph) info.get(0); ^---^ *** Semantic Warning: Local "graph" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 821. UnionFind uf = (UnionFind) info.get(1); ^^ *** Semantic Warning: Local "uf" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 827. List constraints = cycleToConstraints(cycle,repToAttributes); ^---------^ *** Semantic Warning: Local "constraints" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". 894. ConstraintGraph graph = new ConstraintGraph(constraints); ^---^ *** Semantic Warning: Local "graph" shadows a field of the same name in "net.sf.bddbddb.dataflow.PartialOrder$Constraints". Issued 1 semantic warning compiling "net/sf/bddbddb/NumberingRule.java": 43. boolean TRACE = false; ^---^ *** Semantic Warning: Field "TRACE" shadows a field of the same name in "net.sf.bddbddb.InferenceRule". Issued 1 semantic warning compiling "net/sf/bddbddb/CodeFragment.java": 217. Method method = c.getDeclaredMethod("go", new Class[] { type, BDD.class }); ^----^ *** Semantic Warning: Local "method" shadows a field of the same name in "net.sf.bddbddb.CodeFragment". Issued 1 semantic warning compiling "net/sf/bddbddb/Interactive.java": 84. MyReader in = new MyReader(new LineNumberReader(new FileReader(file))); ^^ *** Semantic Warning: Local "in" shadows a field of the same name in "net.sf.bddbddb.Interactive". Issued 1 semantic warning compiling "net/sf/bddbddb/TryDomainOrders.java": 114. int[] varorder = new int[nVars]; ^------^ *** Semantic Warning: Local "varorder" shadows a field of the same name in "net.sf.bddbddb.TryDomainOrders". make: *** [_jikes] Error 1 [dbrumley <at> rtfm bddbddb]$ exit Script done on Mon 08 Jan 2007 04:03:59 PM EST
------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys - and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________ bddbddb-devel mailing list bddbddb-devel <at> lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bddbddb-devel
RSS Feed