Since we assign the instructions in top-down order, the relevant dependency for a given instruction is its predecessors. For each instruction, we track which SchedGroup its predecessors have been assigned to (if any). When deciding which SchedGroups to prioritize for an instruction, we look at the last (in top-down order) SchedGroup assigned for all its predecessors. We prioritize candidate SchedGroups that occur at or after (in top-down order) that SchedGroup. These SchedGroups will be the earliest possible SchedGroups that do not violate dependencies. Next, we look at the second-to-last SchedGroup assigned to an instructions predecessors. We prioritize candidate SchedGroups that occur at or after that SchedGroup. These SchedGroups will be earliest possible SchedGroups that violate one dependency. And so on.
This heuristic is much less computationally expensive than the cost heuristic. Additionally, we expect it to produce a good search order in the general case, but perhaps not as good as the cost heuristic. The search order will likely get better once we have a more intelligent processing order of pipeline instructions.
This patch also does a little bit to consolidate handling of heuristics.