Extending List Scheduling to Consider Execution Frequency

Frequency-Based List Scheduling (FBLS) extends standard List Scheduling by considering execution frequencies within a schedule. This is useful for global instruction scheduling methods that schedule groups of basic blocks, called meta-blocks, as though they were a single block. Traditionallocal schedulers operate on the premise that each instruction is executed the same number of times as every other instruction in the "block", an unwarrented assumption for meta-blocks. This assumption can lead metablocks schedulers to produce inefficient code. FBLS provides ananswer to this problem by considering the differing execution frequencies within meta-blocks when scheduling operations. To evaluate our contention that FBLS is a useful extension to standard list scheduling, we implemented FBLS and compared it to standard list scheduling within the context of dominator-path scheduling [1], a meta-block global scheduling algorithm. Experimental results show overall run-time improvement of 10.9% f..