headers
David Brumley | 16 Nov 2006 19:12
Picon
Favicon

datalog operations allowed

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
Permalink | Reply | 3 comments |
headers
John Whaley | 27 Nov 2006 19:45
Picon

Re: datalog operations allowed

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:
(Continue reading)

Permalink | Reply | 2 comments |

Gmane