The present invention discloses a method and device for ordering memory operation
instructions in an optimizing compiler. for a processor that can potentially enter
a stall state if a memory queue is full. The method uses a dependency graph coupled
with one or more memory queues. The dependency graph is used to show the dependency
relationships between instructions in a program being compiled. After creating
the dependency graph, the ready nodes are identified. Dependency graph nodes that
correspond to memory operations may have the effect of adding an element to the
memory queue or removing one or more elements from the memory queue. The ideal
situation is to keep the memory queue as full as possible without exceeding the
maximum desirable number of elements, by scheduling memory operations to maximize
the parallelism of memory operations while avoiding stalls on the target processor.
