/******************************************************************************/
/*		Available Expressions Analysis Using Prolog                   */
/*                    - Uday Khedker (uday@cse.iitb.ac.in)                    */
/*                      Tue Nov 23 02:35:20 IST 2004                          */
/******************************************************************************/

:- auto_table.

/***************** Basic Block representation *********************/

b_expr(e1,a,plus,b).			/* Expression `e1' conisists of `a+b' */
b_expr(e2,b,plus,c).
b_expr(e3,c,plus,d).
b_expr(e4,f,plus,g).
b_expr(e5,h,plus,i).
u_expr(e6,minus,a).

asgn(a1,c,e1).				/* Assignment `a1' is `c = a + b'     */
asgn(a2,h,e3).
asgn(a3,h,e6).
asgn(a4,e,e5).
asgn(a5,a,e4).

basicBlock(1,[a1,a2]).  
basicBlock(2,[a3,a4]).  
basicBlock(3,[a4]).  
basicBlock(4,[a5]).  

program([1,2,3,4]).

edge(1,2).
edge(1,3).
edge(2,4).
edge(3,4).
edge(4,3).

pred(N,P) :- setof(Node, edge(Node,N),P).
succ(N,P) :- setof(Node, edge(N,Node),P).

/**** Auxiliary Predicates for Local Properties in Available Expressions Analysis ****/

genExpr([A|R],Expr) :- asgn(A,W,Expr),
		       b_expr(Expr,U,_,V),
			W \= U, W\= V,
			transp(U,R),
			transp(V,R).
genExpr([A|R],Expr) :- genExpr(R,Expr).

transpExpr(L,Expr) :- b_expr(Expr,U,_,V),
			transp(U,L),
			transp(V,L).

transpExpr(L,Expr) :- u_expr(Expr,_,V),
			transp(V,L).


transp(U,[A|R]) :- not(asgn(A,U,_)),
		   transp(U,R).
transp(U,[]).

/**********************************************************************************/
computeAv :- program(L),
	     avForEachNode(L).

avForEachNode([A|R]) :- avIn(A,In),
			write('Avin['),write(A),write('] is '),write(In),nl,
		        avOut(A,Out),
			write('Avout['),write(A),write('] is '),write(Out),nl,
			avForEachNode(R).
avForEachNode([]).

avIn(1,[]).
avIn(N,E) :- setof(Expr,avinExpr(N,Expr,[]),E).
avOut(N,E) :- setof(Expr,avoutExpr(N,Expr,[]),E).

avinExpr(N,Expr,Visited) :- pred(N,P),
		    avProd(P,Expr,Visited).

avoutExpr(N,Expr,Visited) :-  basicBlock(N,L), 
	      		genExpr(L,Expr).

avoutExpr(N,Expr,Visited) :- avTranspExpr(N,Expr),
			     setof(Node, Node = N, Current),
		             union(Current,Visited,VisitedAfter),
			     avinExpr(N,Expr,VisitedAfter).


avGenExpr(N,Expr) :- basicBlock(N,StmntList),
		     genExpr(StmntList,Expr).
avTranspExpr(N,Expr) :- basicBlock(N,StmntList),
		     transpExpr(StmntList,Expr).

avProd([],Expr,Visited).
avProd([A|R],Expr,Visited) :- in(A,Visited),
		              avProd(R,Expr,Visited).
avProd([A|R],Expr,Visited) :- not(in(A,Visited)),
		      avoutExpr(A,Expr,Visited), 
		      avProd(R,Expr,Visited).