| << Prev | - Up - |
Continuation.
The second normalization step described in Section 6.2.2 is the elimination of redundant dominance edges. The implementation we present here doesn't use the transitive reduction algorithm we mentioned earlier, but simply goes through each dominance edge in the graph and checks whether the lower end can still be reached from the upper end if the dominance edge is removed. This algorithm is slower than transitive reduction, but much simpler.
elimRedundancy(usr(Ns,LCs,DCs,BCs),Irredundant) :-
mySelect(dom(X,Y),DCs,DCsRest),
reachable(Y,X,usr(Ns,LCs,DCsRest,BCs)),!,
elimRedundancy(usr(Ns,LCs,DCsRest,BCs),Irredundant).
elimRedundancy(Usr,Usr).
First, a dominance edge dom(X,Y) is removed from DCs. Second, it is checked whether the node Y is still reachable from the node X (the predicate reachable/3 can be found in cllsLib.pl). If so, the removed dominance edge was redundant. In this case, the redundancy elimination continues with a constraint containing all remaining dominance edges (DCsRest). Note that in this case, the cut prevents any further backtracking.
But what happens if a dominance edge that is necessary for establishing some reachability in the graph is deleted? Well, in this case reachable/3 fails and backtracking selects (and removes) another dominance edge instead, checking the reachability again afterwards. Eventually all redundant edges will have been removed, at which point all calls to reachable/3 will fail, and the second clause is used to return the irredundant graph.
?- Question!
Look at the declaration of reachable/3 in cllsLib.pl and explain in your own words, how reachability is checked there.
| << Prev | - Up - |