[DFAJumpThreading] Missed optimization for invariant condition after first iteration

[XChy]

Inspired by #70597, this issue focuses on its phi form.
For loops like:

c = a;
for(int j = 0; j < xxxxx; j += b)
  if(cmp(c))
     c = i;  // i is invariant

c become invariant after the first iteration. And therefore cmp(c) become invariant after the first iteration.
When it becomes phi, cmp(c) is equivalent to cmp(phi(a,i)).
We could peel out such condition easier when there is no load/store, but PHINode.
A proof for SSA version(without memory operation):
https://alive2.llvm.org/ce/z/TP3WDq

In this way, the loop could be unrolled:
https://godbolt.org/z/Ybnevxn9v

Actually I have no idea which pass is responsible for such fold. So feel free to change the tags.

[nikic]

Doesn't your godbolt link show that the optimization already happens?

[XChy]

Doesn't your godbolt link show that the optimization already happens?

Thanks for reminder. Link has been updated.

[nikic]

The updated link still has peeling?

[XChy]

The updated link still has peeling?

I may not clarify it well. I mean that only with the fold I want in https://alive2.llvm.org/ce/z/TP3WDq (src -> tgt) done, can we make it possible for LoopUnroll to unroll the loop. In https://godbolt.org/z/Ybnevxn9v, src cannot be unrolled, but tgt is unrolled.

The godbolt link is just to show this fold exposes optimization opportunities for other loop pass.

[nikic]

Ah, thanks, I get it now. I'm not sure where such a transform could be performed.

[XChy]

A more general example will be like https://alive2.llvm.org/ce/z/_pr6gu (a trace : 3 -> 0 -> 1 -> 2 -> 3 -> ....).
A more efficient unrolled version: https://godbolt.org/z/vefa8n4qs.

It seems like a simplification of transfering state in state-machine. I think the possible applications in real world can be optimizing handwritten lexer/parser or other handwritten state-machine.

[XChy]

A possible C code for string verifying based on state-machine: https://godbolt.org/z/nGPKj5cbP.

[nikic]

That case should be handled by DFA jump threading: https://godbolt.org/z/4PMPs5hcj

[XChy]

That case should be handled by DFA jump threading: https://godbolt.org/z/4PMPs5hcj

Thanks for reminder. I didn't learn anything about this transform and I may need to take a look. And it seems to be unrolled in a direct way (Maybe that's a phase-ordering problem?) : https://godbolt.org/z/ra6jd5zox.

[XChy]

Looking up to source, I think this issue could be categorized into DFA optimization.
DFA JumpThreading handles only switch now, which holds simply constant equality comparsion on branches.
If we get it generalized, we may want to handle all branches with constant eq/ne/lt/gt.... comparsion. Example1.
Further generalized, it could be based on symbolic comparsion of loop invariant. Example2. Title's case could be covered here.

It's profitable to perform such generalization with few branches, since it's common that flags are checked and changed inside loops.
When branches become numerous, it would take much more compile-time to build edges between states.