[llvm-dev] top-down vs. bottom-up list scheduling

[Andrew Trick via llvm-dev]

> On Nov 6, 2018, at 6:19 AM, Sjoerd Meijer via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Hello List!
> 
> I am looking at top-down vs. bottom-up list scheduling for simple(r) in-order
> cores. First, for some context, below is a fairly representative pseudo-code
> example of the sort of DSP-like codes I am looking at:
> 
>  uint64_t foo(int *pA, int *pB, unsigned N, unsigned C) {
>    uint64_t sum = 0;
>    while (N-- > 0) {
>      A1 = *pA++;
>      A2 = *pA++;
>      B1 = *pB++;
>      B2 = *pB++;
>      ...
>      sum += ((uint64_t) A1 * B1) >> C;
>      sum += ((uint64_t) A2 * B2) >> C;
>      ...
>    }
>    return sum;
>  }


Bottom-up scheduling would work for you in this case if the heuristics knew to minimize pressure at every point in the loop. Ideally, that could be detected from the shape of the DAG before list scheduling begins.

The closest thing we have to doing that in the current source is the “subtree” scheduling. See `computeDFSResult`.

…or maybe you find a simpler way to control the heurstics!

I’m not entirely sure why the top-down heuristics are working better for you in this case. What you’re proposing is similar in spirit to LLVM's bidirectional scheduling. The problem is that a list scheduler can dig itself into a hole in either direction so bidirectional doesn’t really save you unless you throw away the previous schedule and start over. LLVM’s normal no-backtracking approach is really designed to avoid compile-time issues.

-Andy