[MachinePipeliner] Fix incorrect handlings of unpipelineable insts (#126057)

There was a case where `normalizeNonPipelinedInstructions` didn't
schedule unpipelineable instructions correctly, which could generate
illegal code. This patch fixes this issue by rejecting the schedule if
we fail to insert the unpipelineable instructions at stage 0.

Here is a part of the debug output for `sms-unpipeline-insts3.mir`
before applying this patch.

```
SU(0):   %27:gpr32 = PHI %21:gpr32all, %bb.3, %28:gpr32all, %bb.4
  Successors:
    SU(14): Data Latency=0 Reg=%27
    SU(15): Anti Latency=1

...

SU(14):   %41:gpr32 = ADDWrr %27:gpr32, %12:gpr32common
  Predecessors:
    SU(0): Data Latency=0 Reg=%27
    SU(16): Ord  Latency=0 Artificial
  Successors:
    SU(15): Data Latency=1 Reg=%41
SU(15):   %28:gpr32all = COPY %41:gpr32
  Predecessors:
    SU(14): Data Latency=1 Reg=%41
    SU(0): Anti Latency=1
SU(16):   %30:ppr = WHILELO_PWW_S %27:gpr32, %15:gpr32, implicit-def $nzcv
  Predecessors:
    SU(0): Data Latency=0 Reg=%27
  Successors:
    SU(14): Ord  Latency=0 Artificial

...

Do not pipeline SU(16)
Do not pipeline SU(1)
Do not pipeline SU(0)
Do not pipeline SU(15)
Do not pipeline SU(14)
SU(0) is not pipelined; moving from cycle 19 to 0 Instr: ...
SU(1) is not pipelined; moving from cycle 10 to 0 Instr: ...
SU(15) is not pipelined; moving from cycle 28 to 19 Instr: ...
SU(16) is not pipelined; moving from cycle 19 to 0 Instr: ...
Schedule Found? 1 (II=10)

...

cycle 9 (1) (14) %41:gpr32 = ADDWrr %27:gpr32, %12:gpr32common

cycle 9 (1) (15) %28:gpr32all = COPY %41:gpr32
```

The SUs are traversed in the order of the original basic block, so in
this case a new cycle of each instruction is determined in the order of
`SU(0)`, `SU(1)`, `SU(14)`, `SU(15)`, `SU(16)`. Since there is an
artificial dependence from `SU(16)` to `SU(14)`, which is contradict to
the original SU order, the new cycle of `SU(14)` must be greater than or
equal to the cycle of `SU(16)` at that time. This results in the failure
of scheduling `SU(14)` at stage 0. For now, we reject the schedule for
such cases.
2 files changed
tree: 6da7175568cfc99ce47c98944f19463c3d1ce545
  1. .ci/
  2. .github/
  3. bolt/
  4. clang/
  5. clang-tools-extra/
  6. cmake/
  7. compiler-rt/
  8. cross-project-tests/
  9. flang/
  10. flang-rt/
  11. libc/
  12. libclc/
  13. libcxx/
  14. libcxxabi/
  15. libunwind/
  16. lld/
  17. lldb/
  18. llvm/
  19. llvm-libgcc/
  20. mlir/
  21. offload/
  22. openmp/
  23. polly/
  24. pstl/
  25. runtimes/
  26. third-party/
  27. utils/
  28. .clang-format
  29. .clang-tidy
  30. .git-blame-ignore-revs
  31. .gitattributes
  32. .gitignore
  33. .mailmap
  34. CODE_OF_CONDUCT.md
  35. CONTRIBUTING.md
  36. LICENSE.TXT
  37. pyproject.toml
  38. README.md
  39. SECURITY.md
README.md

The LLVM Compiler Infrastructure

OpenSSF Scorecard OpenSSF Best Practices libc++

Welcome to the LLVM project!

This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.

The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.

C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.

Other components include: the libc++ C++ standard library, the LLD linker, and more.

Getting the Source Code and Building LLVM

Consult the Getting Started with LLVM page for information on building and running LLVM.

For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.

Getting in touch

Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.

The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.