% BASIC BLOCK INSTRUCTION SCHEDULING % % Intuitive readings for predicates: % % instruction(I) = I is an instruction % gap(I1,I2,G) = I2 must be executed at least G slots later than I1 % reach(I1,I2) = I1 is transitively connected to I2 through execution gaps % total(T) = T is the total number of instructions % indep(I,N) = N instructions (including I) do not depend on or from I % lower(I,S) = S >= 1 is the least slot to possibly execute instruction I % upper(I,S) = S >= 1 provides an upper bound for executing instruction I % range(I,L,U) = L and U are the least and upper slot to possibly execute I % range(I,S) = L <= S <= U is a slot at which I can possibly be executed % later(I1,I2,G,S) = When I1 is executed at S-G, executing I2 is delayed to S % block(I1,I2,S) = When I1 is executed at S-1, executing I2 may be delayed to S % opt(S) = Slot S is in-between the greatest least and upper slots % value(I,S) = Instruction I is executed at slot S % delay(I,S) = No slot preceding S is available to execute instruction I % penalty(S) = Execution is not finished at S beyond greatest least slot %%% DOMAIN RULES %%% lower(I1,1) :- instruction(I1). lower(I2,L+G) :- lower(I1,L), gap(I1,I2,G). reach(I1,I2) :- gap(I1,I2,G). reach(I1,I3) :- gap(I1,I2,G), reach(I2,I3). total(T) :- T = #count{ instruction(_) }. indep(I,T-D) :- instruction(I), total(T), D = #count{ reach(I,_), reach(_,I) }. upper(I1,D) :- indep(I1,D). upper(I2,U+G+D-1) :- upper(I1,U), gap(I1,I2,G), indep(I2,D). range(I,L,U) :- instruction(I), L = #max[ lower(I,M) = M ], U = #max[ upper(I,N) = N ]. range(I,L..U) :- range(I,L,U). later(I1,I2,G,L2+1..U1+G) :- gap(I1,I2,G), range(I1,L1,U1), range(I2,L2,U2). block(I1,I2,S+1) :- range(I1;I2,S), range(I2,S+1), not reach(I1,I2), not reach(I2,I1), I1 != I2. opt(L+1..U) :- L = #max[ range(I,M,N) = M ], U = #max[ range(I,M,N) = N ]. %%% CLAUSES DEFINING SOLUTIONS %%% value(I,S) | -delay(I,S) : range(I,S-1) | delay(I,S+1) : range(I,S+1) :- range(I,S). -value(I,S) | delay(I,S) :- range(I,S;S-1). -value(I,S) | -delay(I,S+1) :- range(I,S;S+1). delay(I2,S) | -delay(I1,S-G) :- later(I1,I2,G,S). delay(I2,S) | -value(I1,S-1) | -delay(I2,S-1) : range(I2,S-2) :- block(I1,I2,S). -delay(I2,S) | delay(I1,S-G) : later(I1,I2,G,S) | value(I1,S-1) : block(I1,I2,S) :- range(I2,S;S-1). -delay(I2,S) | delay(I2,S-1) :- range(I2,S;S-2). %%% OPTIMIZE SOLUTIONS %%% penalty(S) | -delay(I,S) :- range(I,S), opt(S). -penalty(S) | delay(I,S) : range(I,S) :- opt(S). #minimize{ penalty(S) }. %%% PROJECT SOLUTIONS %%% #hide. #show value/2. #show -value/2. #show delay/2. #show -delay/2. #show penalty/1. #show -penalty/1.