Scheduling of conditional branches using SSA form for superscalar/VLIW processors

Global scheduling and optimization techniques are proposed to get more enough speedup for superscalar and VLIW(Very Long Instruction Word) processors. When we consider global scheduling and optimization, one of the most important issue is how to schedule conditional branches. Control dependences are caused by conditional branches and limit the scope of scheduling. Most of previous scheduling schemes are based on speculative or predicated execution techniques to overcome conditional branches. However, speculative execution requires computation for code motion and insertion of compensation code to preserve semantics. The complexity of scheduler is largely due to computation for code motion. In addition, performance is dependent on branch outcomes. Predicated execution makes it possible to schedule more simpler. But the difficulties in the design of the instruction set are a serious problem. This paper proposes scheduling method using SSA form. The scheduling algorithm can be more simpler by utilizing φ-functions aggressively because computations for code motion are not required. We don't need complex hardware support. Our scheme also makes the performance independent on the result of branch outcomes.