[llvm-dev] Why does LLVM keep some loads in the loops even after applying the O3 optimization?

[Tim Northover via llvm-dev]

On Fri, 29 Mar 2019 at 20:49, Fami H via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Is there any structure at the LLVM backend that holds this information?

The general topic is known as alias analysis. Within a function it's
designed to answer the question, given two instructions, of whether
they could be accessing the same memory. The answers are often
approximate though; if the compiler can't prove two accesses
definitely don't overlap it'll respond with something like MayAlias.

When function calls are involved things get a lot cruder. Basically
LLVM may sometimes know that a function doesn't access any memory, or
only accesses memory through its arguments, but that's not terribly
common or easy to prove. In the general case it assumes function might
modify any pointer that's not strictly local to the caller.

For example:

   void foo(int *in) { // "in" could be modified by any call; who
knows where it really lives?
     int var = 42;
     bar(); // var hasn't escaped yet, so we wouldn't have to reload
after this call.

     myGlobal = &var; // Bad: var is now accessible from any function call.
     baz(&var); // Bad: baz could save a copy of &var for use by any
other function.
     myStruct.thing = &var;
     baz1(myStruct); // Bad: basically the same as baz above but
slightly more hidden.
   }

> I mean, can I get one machine instruction load and find out which other instructions in this function or even in other functions may modify its accessed memory location?

There's no specific interface like you're describing. You might be
able to enumerate all accesses in the same function that could
interfere, but it sounds potentially expensive. If possible you should
rethink your algorithm in terms of just comparing two MachineInstrs
you care about.

To do that you'd use MachineInstr::mayAlias, and your pass would have
to declare that it requires valid alias analysis (it's sometimes
costly to keep, so LLVM doesn't maintain that unless requested). Take
a look at (for example)
lib/Target/AArch64/AArch64LoadStoreOptimizer.cpp:getAnalysisUsage for
how it's done.

Cheers.

Tim.