Oh, don't mind me, LGTM!
IMHO, the documentation is fine if the readier gets some hint that they should look at it :P Sth like:

bool BestPossible = !C.hasValue();
bool SecondBest = isa_and_nonnull<UndefValue>(*C);

might do the trick. Like, they will either get it, or they will see that they don't get it and they'll check the doc. But I don't know if you like the style, maybe too verbose.

LGTM although I've missed a lot of progress in the Attributor so definitely wait for other reviewers if you want an acceptance to move it forward :)

Remove unnecessary text

Small fixes

That might be too big of a footnote and it might even be more suitable to be added in the phi doc in the LangRef. Nevertheless, it feels complete and valuable now :)

Addressed comments.

Shortened comments and moved a more detailed explanation in loop terminology/LCSSA doc.

Some resources that might help:

In D88183#2311945, @Meinersbur wrote:

With D88408 have been committed, can this be abandoned?

It would be part of the LoopSimplify normal form, ensured by the preheader and dedicated exit blocks. Otherwise, it's more a concept for CFGs than loops.

Btw, do you think it's good to desribe what is a critical edge in this doc ? I think it's mentioned quite often in anything loop-related.

I think the document is more useful as a reference than a text-book reading.

What do you think of the revision? Does it clarify things? Is it more understandable?

Thanks for taking the time to write this! I think it will help, especially beginners. I remember when I first read the loop terminology, some things were not obvious that are cleared here (e.g. why do people use backedge taken count).

In D88183#2293384, @Meinersbur wrote:

There are different definitions of loops. In the literature, such as a Dragon Book, a loop is identified by a backedge, but LLVM does it with its header. But only natural loops have a header: that is, not all cyclic control flow is represented by LoopInfo. Cyclic control flow that is is not form a natural loop is called irreducible control flow.

Anyway, using SCCs to stand for loops is bad as well since it ignores subloops. It should be a induced subgraph, not component. I think I raised this in the first review, but it was committed anyway. I'd be grateful if this could be cleaned up.

In D82895#2288745, @MaskRay wrote:

API changes may cause problems to other backends. It is a good idea to test -DLLVM_TARGETS_TO_BUILD=ALL

Address comments

@baziotis Are you going to update this diff?

In D84608#2184786, @fhahn wrote:

Thanks for taking a look @baziotis & @anemet !

In D84608#2177006, @baziotis wrote:

In D84608#2176574, @fhahn wrote:

In D84608#2174659, @baziotis wrote:

Instead of accumulating in AccessInfos, couldn't we just reiterate the alias set (if we didn't bail out)?

Yes, I think either approach is fine. The current way avoids a few repeated lookups, but in the grand scheme of things I don't think it makes a big difference.

You mean in Accesses.. Well, since the iteration in an AliasSet is deterministic we could also only save the bools in a BitVector and both save memory and not do lookups. But never mind if you consider it overthinking / nitpicking.

Yeah, this code is very unlikely to be performance critical, so IMO we should try to make the code as straight-forward as possible. I think it would be good to stick with the version in the patch initially and potentially do follow-on improvements as follow-up patches.

• Added doc.

In D84717#2179172, @Meinersbur wrote:

LGTM

In D84717#2178016, @baziotis wrote:

One proposal by a friend of mine, GeorgeLS, is that we can make a wrapper in which instead of passing a bool, we pass a BitWord.
And then we XOR with this BitWord every BitWord we read from Bits. So, the passed BitWord acts conditionally. If we want the "unset" version, we pass ~0.
If we want the "set" version, we pass 0.

An optimizing compiler might already do this if it thinks it is profitable. That is, InstCombine

if (!Set)
  Copy = ~Copy;

to

Mask = Set ? 0 : -1;
Copy ^= Mask;

and hoist Mask out of the loop.

However, unless you show that there is a relevant performance difference, I don't have a preference for either version.

In D84717#2178123, @RKSimon wrote:

Please can you add unit test coverage at llvm/unittest/ADT/BitVectorTest.cpp

One proposal by a friend of mine, GeorgeLS, is that we can make a wrapper in which instead of passing a bool, we pass a BitWord.
And then we XOR with this BitWord every BitWord we read from Bits. So, the passed BitWord acts conditionally. If we want the "unset" version, we pass ~0.
If we want the "set" version, we pass 0.

Addressed comments.

Apart from that, now that I'm seeing it again, in LAA, we probably want to move a lot of vectors out of loops and just reset() them.

In D84608#2176574, @fhahn wrote:

In D84608#2174659, @baziotis wrote:

Instead of accumulating in AccessInfos, couldn't we just reiterate the alias set (if we didn't bail out)?

Yes, I think either approach is fine. The current way avoids a few repeated lookups, but in the grand scheme of things I don't think it makes a big difference.

Instead of accumulating in AccessInfos, couldn't we just reiterate the alias set (if we didn't bail out)?

The code is quite good and clean. Most comments are on the doc so that we can make it good and clean too and move to the full patch.

A nit comment is to please start comments with caps.

In D82895#2137834, @Meinersbur wrote:

In D82895#2130151, @fhahn wrote:

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost().

There are often multiple ways for the same goal, for instance LoadInst::getPointerOperand() and LoadInst::getOperand(0). One makes the intention clearer than the other.

Same for isInnerMost()/empty().

Since these are identical, I'd tend to remove one. In these case I'd remove empty() since Loop does not represent a container.

Nit comments, I haven't yet digested the whole patch.

First of all, great patch. Reading the description and the referenced diff, I can't find an explanation about what this patch tries to do, it would be good if you added that. My assumption is:

I partially agree but also IMHO empty() is confusing enough so that introducing isInnermost/Outermost has benefit that outweighs the cost. A Loop can contain both BBs and loops which is different than DominatorTree AFAIK (which can only contain BBs).
This is a big source of confusion when one comes across it in the code (and as I said, personally I assumed it had to do with the BBs).

Added isInnermost/Outermost.

Thanks for the reviews, I'm updating.

Address comment.

In D82895#2123566, @fhahn wrote:

In D82895#2123465, @baziotis wrote:

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

I think using empty makes sense in the context of begin() and end()

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

In D80000#2055195, @george.burgess.iv wrote:

thanks for this!

if someone stamps with nits and you're confident that you've addressed the nits, feel free to commit :)

Ping :) Should I commit?

Thanks for the comments!

In D76873#1961896, @jdoerfert wrote:

I think we'll benefit from more structure and this is only one step in that direction. If there is no argument against I'd like to land this now as we have little attributor patches in the pipeline.

Differential Review: https://reviews.llvm.org/D71960/

Closed by: https://reviews.llvm.org/rGf3dd3a66d3d5643a5e6f46bb18dee3be3a5898cd

• Final update

Committed but of course I forgot again to add the differential revision. I don't why I continuously do that, sorry. :)
I'll add it to the commit in Phabricator and close this when the commit is ready.

Ty

In D75233#1951675, @Meinersbur wrote:

LGTM. Thanks for the effort!

No, problem, thanks for the review and the info!

Ping.

• Addressed SCEV behavior in loop-variant expressions.

In D75233#1948305, @Meinersbur wrote:

In D75233#1944176, @baziotis wrote:

Yes. Could you explain the part about dominator nodes ? I understand how dominators help in the identification
of loops and how dominance frontiers help in the placement of normal PHI nodes (i.e. when 2 or more paths converge). But I don't see how dominators
help with the placement of LCSSA phi nodes.

It is simple if the loop has just a single exit, but much more involved with multiple exits. Example CFG:

Header:
  %val = ...

Header->{Latch1,Latch2,Latch3}->Header

Header->Latch1->Exit1
Header->Latch2->Exit2
Header->Latch3->Exit3

Exit->Successor1

Successor1->SharedSucc
Exit2->SharedSucc

SharedSucc->CommonSucc
Exit3->CommonSucc

CommonSucc:
  use(%val)

Header dominates all other BBs in this example, hence without LCSSA, this is well-formed. However, with LCSSA we have to insert phis into Exit1,Exit2,Exit3 such that the end result has to look like:

Exit1:
  %lcssa1 = phi [%val, %Latch1]

Exit2:
  %lcssa2 = phi [%val, %Latch2]

Exit3:
  %lcssa3 = phi [%val, %Latch3]

SharedSucc:
  %sharedval = phi [%lcssa1 , %Exit1], [%lcssa2, %Exit2]

CommonSucc:
  %commonval = phi [%lcssa3 , %Exit3], [%sharedval , %SharedSucc]
  use(%commonval)

For computing %sharedval and %commonval, DominanceFrontier is needed again, hence LCSSA is not less complicated that SSA itself.

• Various typos.
• Added def-use chain info as a footnote since its used twice. Also a footnote about LCSSA construction (I consider it interesting but in a footnote because it may be irrelevant in the main text).
• Added some info about SCEV.

Personally I don't have problem with big files, sometimes they're more easy to use. But I definitely agree that we should start thinking about structure and splitting into files can help.

In D75233#1943883, @Meinersbur wrote:

In D75233#1932574, @baziotis wrote:

2 questions:

1. Is it "loop closed PHI node" or "loop closing PHI node"?

Not being an expert of the English language, I;d say "loop-closing PHI node"

2. Does LCSSA pass have to do this deep analysis? Because to me, it seems it can just use RAUW?

The most complicated thing is finding the dominator nodes to add the PHI nodes in (especially with multiple loop exits).

If possible, could you avoid "deep analysis", but instead refer the kind of analysis needed?