Patent ID: 7392516

Claim:
A method of performing dynamic by-pass instruction scheduling utilizing a data dependency graph (DDG), said DDG including at least one by-pass pair of nodes (A i p , A i s ) comprising a predecessor node A i p and a successor node A i s connected by a by-pass edge, said method comprising: computing a ranking of nodes in said DDG after setting all delays for by-pass pairs of nodes (A i p , A i s ) to 0; identifying all successor nodes A i s in said DDG; annotating each successor node A i s with a set of immediate predecessor nodes A i p to form a by-pass list BPL(A i s ) of by-pass pairs (A i p , A i s ); setting a delay DAi for all by-pass pairs (A i p , A i s ) in said by-pass list BPL( A i s ); removing from said by-pass list BPL(A i s ) any by-pass pair (A i p , A i s ) that is a predecessor to any other by-pass pair (A i p , A i s ); selecting from said by-pass list BPL(A i s ) a given predecessor node A i p being identified as the least important to schedule early, and marking said given predecessor node A i p as being bonded to its corresponding successor node A i s with a delay of 0 execution cycles; re-computing a ranking for each node in said DDG so that an earliest time for said given predecessor node A i p is calculated as an earliest time for said successor node A i s less 1 execution cycle; and scheduling nodes in said DDG so that, each time said given predecessor node A i p is scheduled, said corresponding successor node A i s is scheduled immediately thereafter; wherein said ranking of nodes in said DDG is computed and re-computed based on a critical path of said nodes, and said selecting a predecessor node A i p is based on identifying a given predecessor node A i p as having the shortest critical path.