Acyclic Scheduling and branches

Question

Hello,

(different thread for clarity)

I also have some questions left about acyclic scheduling and branches in programs.

For example if we have three BB that have no dependencies between each other besides the fact that at the end of B0 there is a bez to B2 (which has only one instruction). I would now have put the first instructions of each BB into one VLIW such that B2 gets executed although we do not yet know if the bez holds true or not. Since there is no other instruction in B2, I asked myself if we could omit the branch instruction in B0 since its target has already been executed fully anyway. Would that be the right thing to do?

Thanks in advance for any help!

Best regards
Marvin

Answer 1

The situation you are describing is a bit confusing. Since there is a branch instruction at the end of B0 that branches to B2, there seems to be a dependency between the instructions in B0 and B2. If the branch condition c does however not depend on B0, i.e., if the variables occurring in c are not written by B0, then the following can be done:

B0; if(c) B1 else B2  --> if(c) {B0;B1} else {B0;B2}

But acyclic scheduling usually prefers to do tail duplication which means the following:

{if(c) B1 else B2}; B3  -->  if(c) {B1;B3} else {B2;B3}

Tail duplication does not need any dependency checks (at least for structured programs).