LGTM

LGTM

Address code review comment.

Adapting test for -b option processing on AIX

I am referring to the summary:

The llvm.annotation intrinsic returns the first argument passed to it.

As mentioned, this is not a sufficient condition to be just ignored. The summary should also mention that by the LLVM language reference, " are ignored by code generation and optimization."

Suggestion:

As by the LLVM language reference, the llvm.annotation intrinsic and no effect on code generation and optimization (https://llvm.org/docs/LangRef.html) and therefore can be safely replaced by its first argument. This patch 'teaches' SCEV the semantics of that builtin function.

That depends on the precise semantics @llvm.annotation is supposed to have, with which I'm not familiar, and which LangRef does not specify particularly clearly. Is it okay to drop an @llvm.annotation() whose return value is not used? If "no", then marking it readonly is not possible, it will be dropped as dead code. Is it okay to hoist @llvm.annotation() inside an unconditional loop header out of the loop? If "no", then dropping inaccessiblememonly is not possible either (being non-speculatable would prevent hoisting out of a conditional loop header, but not an unconditional one).

In D102344#2755915, @Meinersbur wrote:

From the language reference:

they are ignored by code generation and optimization.

I agree that this means the annotation can be ignored. But it returning the first argument (as mentioned in the summary) is not sufficient to conclude that, e.g. it could have side effects.

In D102348#2755223, @nikic wrote:

This looks wrong to me. To give one example: Accessing inaccessible memory is the typical way to model side-effects. mayHaveSideEffects() is defined in terms of mayWriteToMemory(). This change makes inaccessiblememonly side-effect free. Oops.

I do think that "only writes accessible memory" is a useful predicate, and many -- but not all -- current callers of mayWriteToMemory() can be switched to it. I would recommend to introduce mayWriteAccessibleMemory() / mayReadAccessibleMemory() and then migrate call-sites after review of the guarantees they actually need.

In D102348#2754951, @bmahjour wrote:

I'm not exactly sure what it means to "access memory that is not accessible by the module being compiled.". My guess is that it's for things like intrinsics that take a global string as argument (eg. the file name), for compile-time mapping, but don't get lowered to any instructions that actually access that memory in the final generated assembly. Is that correct, or are there other examples to consider?

LGTM.

Address code review comments.

ping

Fix formatting.

Add LLVM_DEBUG stmts.

Note: this failure looks bogus to me as it also happens in other PRs like https://reviews.llvm.org/D89964

linux > HWAddressSanitizer-x86_64.TestCases::sizes.cpp
Script:
--
: 'RUN: at line 3';      /mnt/disks/ssd0/agent/llvm-project/build/./bin/clang  --driver-mode=g++  -m64  -gline-tables-only -fsanitize=hwaddress -fuse-ld=lld -mcmodel=large -mllvm -hwasan-globals -mllvm -hwasan-use-short-granules -mllvm -hwasan-instrument-landing-pads=0 -mllvm -hwasan-instrument-personality-functions /mnt/disks/ssd0/agent/llvm-project/compiler-rt/test/hwasan/TestCases/sizes.cpp -nostdlib++ -lstdc++ -o /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/hwasan/X86_64/TestCases/Output/sizes.cpp.tmp

Address comments.

Address comments

Fix clang-format

Look OK to me but you should also add other reviewers.

ping

Address code review comments.

Fix quotes in profile.ll

Here are a couple of programs to test the performance of a simple memset vs a simple initialization loop. On my system (PPC) even this short init. loop is slower than the memset.

% cat loop.c
#include <string.h>
int main() {
  int A[N];
  for (int n=0; n<STEPS; ++n)
    for(int i=0;i<N;++i)
      A[i] = 0;
  return A[0];
}

% gcc -O0 loop.c -DN=10 -DSTEPS=1000000; time ./a.out
./a.out 0.10s user 0.00s system 99% cpu 0.099 total

% cat memset.c
#include <string.h>
int main() {
  int A[N];
  for (int n=0; n<STEPS; ++n)
    memset(A, 0, N * sizeof(int));
  return A[0];
}

% gcc -O0 memset.c -DN=10 -DSTEPS=1000000; time ./a.out
./a.out 0.02s user 0.00s system 99% cpu 0.022 total

Transforming a loop into a memset or memcpy is not *always* profitable (it depends on how many elements are initialized/copied and on the efficiency of the target architecture implementation for those libraries) but is often better than a loop. The low level optimizer should change short memset/memcpy back into a sequence of assignments, IMO this should not be done in opt because the exact length for which memset is less profitable than individual assignment is a function of the target architecture. As for this PR, adding an option to disable the optimization is a good thing as it provides more flexibility to users that for whatever reason do not want the transformation to run (and is also handy for compiler developers when debugging code). And more flexibility is a good thing.

In D86262#2231209, @lebedev.ri wrote:

I'd like to see a PhaseOrdering test showing the IR that is not optimized due to the DA being unaware about these intrinsics.

In D68789#2216266, @ychen wrote:

I have trouble finding the definition of LoopNestAnalysis::run.

@uweigand and @Kai I forgot to fix a test case. Now fixed are you still ok with the test case change?

Fix test case for PPC64 and SystemZ

Fix formatting

In D82895#2129028, @jdoerfert wrote:

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

LGTM

I choose to name the pass Loop Fission to avoid confusion with the existing LoopDistribution pass (eventually Loop Fission should replace that pass). Also Loop Fission is the opposite of Loop Fusion :-) ?

Addressed review comments from @Meinersbur

ping

ping

Addressing code review comments.

Based on the feedback received during code review I have added a new public member function called 'getPerfectLoops' which can be used to retrieve a list of loops that are perfect with respect to each other.
For example, given the following loop nest containing 4 loops, 'getPerfectLoops' would return {{L1,L2},{L3,L4}}.

for(i) // L1
  for(j) // L2
    <code>
    for(k) // L3
       for(l) // L4

In D68789#1753797, @bmahjour wrote:

In D68789#1753777, @Meinersbur wrote:

[suggestion] Add a methods that returns/fills a vector with all the Loop*s that are part of the perfect loop nest.

That sounds like a good idea. I'd suggest returning a vector of vectors actually in case where there are multiple perfect sub nests in a loop nest. ie:

L1
  L2
   <code>
    L3
      L4
        L5

return:
{{L1,L2},{L3,L4,L5}}

Addressing code review comments from Michael.

In D63459#1731032, @Meinersbur wrote:

In D63459#1731015, @xbolva00 wrote:

/home/xbolva00/LLVM/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp 353 warn V612 An unconditional 'return' within a loop.

This indeed does not look right. There are beaks and returns in the loop, but no continue. Meaning the loop is only iterated for one element (in this case: the innermost loop). I think nothing else than the innermost loop is needed for delinearization, in which case it could be made a conditional instead of a for-statement.

/home/xbolva00/LLVM/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp 456 err V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '==' operator.

TRT(TRT == None ? Optional<unsigned>(TemporalReuseThreshold) : TRT),

Could add parens around TRT == None to silence the analyzer.