invariant.group handling in GVN

[Prazek]

Summary

The most important part required to make clang

devirtualization works ( ͡°͜ʖ ͡°).
The code is able to find non local dependencies, but unfortunatelly
because the caller can only handle local dependencies, I had to add
some restrictions to look for dependencies only in the same

[rsmith]

include/llvm/Analysis/MemoryDependenceAnalysis.h

420

Typo "Incariant"; use \brief insteaed of repeating the function name here.

422

will -> does

423

loads or stores -> load or store

lib/Analysis/MemoryDependenceAnalysis.cpp

379

Revert this blank line insertion.

lib/Transforms/Utils/Local.cpp

1433

instruction has -> instructions have

1434

Maybe add a FIXME stating that we should try to preserve both groups in this case.

[• dberlin]

lib/Analysis/MemoryDependenceAnalysis.cpp

402

Well, it's safe, if you verify the use is in LI->getParent()->getParent(), no?

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

402

Yes, but nobody guarantee that uses list won't change when I will iterate over it.

[Prazek]

Forgot to include test!

[Prazek]

Fixed combine metadata

[nlewycky]

include/llvm/Analysis/MemoryDependenceAnalysis.h

399–400

I don't think that's "brief". "[A] brief description is a short one-liner" -- https://www.stack.nl/~dimitri/doxygen/manual/docblocks.html

420

Brief again.

lib/Analysis/MemoryDependenceAnalysis.cpp

399

"use list" not "uses list" (two occurrences in this line).

402

It's the 'function passes aren't allowed to look outside their functions' rule, as-if we had function passes running in parallel.

419

Hold up. If there's three loads, A B and C, all of them in the same invariant group, and C is the QueryInst for getPointerDependencyFrom, and A and B both dominate C, doesn't the value returned right here depend on the order of the use list? That seems undesirable, but I'm not sure whether that's considered a serious problem or not.

lib/Transforms/Scalar/GVN.cpp

2480

Spurious change

lib/Transforms/Utils/Local.cpp

1440–1441

Just move this part into the "case LLVMContext::MD_invariant_group:" ?

test/Transforms/GVN/invariant.group.ll

147

Space after colon

[Prazek]

You call it devirtualization? This is devirtualization

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

419

it doesn't matter if we will return Def for A or B, because they will load the same value. The second thing is that we will process them in order which they are in the block, which means that for A we will do nothing, for B we will return Def(A) and remove B, and for C the same thing (because B will not longer exist)

lib/Transforms/Utils/Local.cpp

1440–1441

It won't work because we iterate over K metadata

[Prazek]

reformated

[Prazek]

small fixes

[Prazek]

Works only on single block, I don't think I will make it to work non locally

[nlewycky]

LGTM, thanks for the extensive gvn test!

include/llvm/Analysis/MemoryDependenceAnalysis.h

422

... if *it* does not find ...

426

Either "on the caller" or "at the call site".

lib/Analysis/MemoryDependenceAnalysis.cpp

398

Extra newline.

411

"equivalent"