[LoopUnrollAndJam] Visit phi operand dependencies in post-order
authorJoshua Cao <cao.joshua@yahoo.com>
Fri, 16 Dec 2022 09:00:56 +0000 (04:00 -0500)
committerJoshua Cao <cao.joshua@yahoo.com>
Thu, 5 Jan 2023 08:05:49 +0000 (00:05 -0800)
commit629d880dc527cd7a8d692cd24af196db4ea8646b
treef49022fb86dfa739ae46614d6963b3a5094690e4
parent6a930e889145cbfb3ff1d99f67a5382c19bc1745
[LoopUnrollAndJam] Visit phi operand dependencies in post-order

Fixes https://github.com/llvm/llvm-project/issues/58565

The previous implementation visits operands in pre-order, but this does
not guarantee an instruction is visited before its uses. This can cause
instructions to be copied in the incorrect order. For example:

```
a = ...
b = add a, 1
c = add a, b
d = add b, a
```

Pre-order visits does not guarantee the order in which `a` and `b` are
visited. LoopUnrollAndJam may incorrectly insert `b` before `a`.

This patch implements post-order visits. By visiting dependencies first,
we guarantee that an instruction's dependencies are visited first.

Differential Revision: https://reviews.llvm.org/D140255
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
llvm/test/Transforms/LoopUnrollAndJam/dependencies_visit_order.ll [new file with mode: 0644]