[llvm-dev] Not creating irreducible loops in jump threading

[ZheYu Wu via llvm-dev]

Hi all,

I'm now studying the jump threading algorithm of LLVM.

I see the current jump threading algorithm prevents from creating
irreducible loops.

The comment says:

FindLoopHeaders - We do not want jump threading to turn proper loop
structures into irreducible loops.  Doing this breaks up the loop
nesting hierarchy and pessimizes later transformations.  To prevent
this from happening, we first have to find the loop headers.

I have two questions:
1. What's the irreducible loop ?
2. What's the penalty if we create it ? (any example ?)


And the comment below says:

This simple analysis is not rich enough to track all of these
properties and keep it up-to-date as the CFG mutates, so we don't
allow any of these transformations.

My third question is what's the meaning of "track all of these
properties and keep it up-to-date as the CFG mutates" ? What is it
expected to do ?


Thanks,
Wu, Zhe Yu