/******************************************************************************/
:- auto_table.
/***************** Basic Block representation *********************/

b_expr(e1,a,plus,b).			/* Binary 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).

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

genExpr([A|R],Expr) :- asgn(A,W,Expr),
		       transpExpr([A|R],Expr).
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,[]).

/**********************************************************************************/
computepAv :- program(L),
	     pAvForEachNode(L).

pAvForEachNode([A|R]) :- pavin(A,InSet),
			write('Pavin['),write(A),write('] is '),write(InSet),nl,
		        pavout(A,OutSet),
			write('Pavout['),write(A),write('] is '),write(OutSet),nl,
			pAvForEachNode(R).
pAvForEachNode([]).

pavin(N,InSet) :- setof(E, pAvIn(N,E), InSet).
pavin(N,[]) :- not(setof(E, pAvIn(N,E), InSet)).

pavout(N,OutSet) :- setof(E, pAvOut(N,E), OutSet).
pavout(N,[]) :- not(setof(E, pAvOut(N,E), OutSet)).

pAvIn(N,E) :- edge(M,N),
		pAvOut(M,E).

pAvOut(N,E) :- basicBlock(N,L), 
	      	genExpr(L,E).

pAvOut(N,E) :- basicBlock(N,StmntList),
	     transpExpr(StmntList,E),
	     pAvIn(N,E).