llvm dev - Aug 2021 - LoopInfo Usage and Move Semantics Question

Hi all,

I’ve recently been working with the loop analysis pass and functionality when
developing my own transformation pass, and came across something with the
LoopInfo class and LoopAnalysisWrapper that I would appreciate some clarity on.

Principally, I’m interested in caching the results of
LoopInfoWrapperPass::runOnFunction as I routinely need to look at and pick apart
the loops within a given set of user-defined Functions in the input bytecode.

To get the LoopInfo for a given Function, the following Lambda is used for
brevity:
auto GetLI = [&](Function& F) -> LoopInfo & {
    return getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
};

Due to the copy semantics of the LoopInfo class being implicitly deleted and the
above LoopBase behaviour, I use std::move to add this LoopInfo object as a value
in a map, with the pointer to the Function as the key. I found a need to do this
as, if I were to call getAnalysis<LoopInfoWrapperPass.(…) multiple times in
the same scope, all of the references and loop information changes in each
LoopInfo object, e.g.:

LoopInfo& LoopsForF = GetLI(*FunctionF);
LoopInfo& LoopsForG = GetLI(*FunctionG);

The LoopInfo objects are the same, or, at least, the information within in (same
BasicBlock reference, same number of sub loops etc.) The LoopsForF object
changes. As far as I’ve read and ascertained, this is because
LoopInfoWrapperPass and LoopInfo are optimised for memory and speed.
LoopInfoWrapperPass stores a LoopInfo result object that it reassigns during
each call to its runOnFunction method. This releases the contents of the
BumpPtrAllocator memory in LoopInfo (in LoopInfoBase) for the new function's
loop information to be stored within, hence why they would be the same.


Calling std::move seems to work up until I try to reference and utilise the
LoopInfo, as in the following pseudocode example:

std::map<Function*, LoopInfo> Cache;
for (Function* Fn : getFunctions()) {
    if (Cache.find(Fn) == Cache.end()) {
        Cache.emplace(Fn, std::move(GetLI(*Fn)));
    }

    ScalarEvolution& SE = GetSE(*Fn);
    // We assume at least one loop in function body
    auto TopMostLoops = Cache[Fn].getTopLevelLoops();
    Loop* FirstLoop = TopMostLoops[0];

    PHINode* IV = FirstLoop->getInductionVariable(SE);
    // ...
}

In the above code, getInductionVariable fails, stating "LV: PHI is a
recurrence with respect to an outer loop”. However, if I reference the LoopInfo
object directly in the body of the for loop (e.g. LoopInfo& LI = GetLI(*Fn)
and replace instances of Cache[Fn] with LI) then the getInductionVariable call
succeeds and returns the appropriate PHINode. std::move - the only way to
transfer/retain the result - seems to change the LoopInfo that is returned,
making it invalid?


So a few questions I have are:

  1.  Is this expected or unusual behaviour?
  2.  Does one just need to call getAnalysis<LoopInfoWrapperPass>(…) every
time they need it (due to the memory optimisations) or is there something wrong
with my logic above that is preventing the example from working?
  3.  Are there any similar uses in the codebase (other passes or such) that
require storing loop information? I’ve not been able to find any.


I appreciate any and all input to help clarify this issue.


Thanks for your time,
Andrew L-S










-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210823/f4b7a92f/attachment.html>

Hey,
as the LoopInfo is as you depict always returned by reference, I think the 
best way to store the LoopInfo in a map, is to use a 
`map<Function*,LoopInfo*>` and store it `Cache.emplace(Fn,
&GetLI(*Fn));`
(Note: you then obviously have to make sure, not to rerun the analysis while 
using the cache, as the pointer might change then..)

Cheers,
Joachim Meyer

Am Montag, 23. August 2021, 14:02:22 CEST schrieb LAMZED-SHORT, ANDREW (PGR) 
via llvm-dev:
> Hi all,
> 
> I’ve recently been working with the loop analysis pass and functionality
> when developing my own transformation pass, and came across something with
> the LoopInfo class and LoopAnalysisWrapper that I would appreciate some
> clarity on.
 
> Principally, I’m interested in caching the results of
> LoopInfoWrapperPass::runOnFunction as I routinely need to look at and pick
> apart the loops within a given set of user-defined Functions in the input
> bytecode.
 
> To get the LoopInfo for a given Function, the following Lambda is used for
> brevity:
 auto GetLI = [&](Function& F) -> LoopInfo &
{
>     return getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
> };
> 
> Due to the copy semantics of the LoopInfo class being implicitly deleted
and
> the above LoopBase behaviour, I use std::move to add this LoopInfo object
> as a value in a map, with the pointer to the Function as the key. I found a
> need to do this as, if I were to call
getAnalysis<LoopInfoWrapperPass.(…)
> multiple times in the same scope, all of the references and loop
> information changes in each LoopInfo object, e.g.:
 
> LoopInfo& LoopsForF = GetLI(*FunctionF);
> LoopInfo& LoopsForG = GetLI(*FunctionG);
> 
> The LoopInfo objects are the same, or, at least, the information within in
> (same BasicBlock reference, same number of sub loops etc.) The LoopsForF
> object changes. As far as I’ve read and ascertained, this is because
> LoopInfoWrapperPass and LoopInfo are optimised for memory and speed.
> LoopInfoWrapperPass stores a LoopInfo result object that it reassigns
> during each call to its runOnFunction method. This releases the contents of
> the BumpPtrAllocator memory in LoopInfo (in LoopInfoBase) for the new
> function's loop information to be stored within, hence why they would
be
> the same.
 
> 
> Calling std::move seems to work up until I try to reference and utilise the
> LoopInfo, as in the following pseudocode example:
 
> std::map<Function*, LoopInfo> Cache;
> for (Function* Fn : getFunctions()) {
>     if (Cache.find(Fn) == Cache.end()) {
>         Cache.emplace(Fn, std::move(GetLI(*Fn)));
>     }
> 
>     ScalarEvolution& SE = GetSE(*Fn);
>     // We assume at least one loop in function body
>     auto TopMostLoops = Cache[Fn].getTopLevelLoops();
>     Loop* FirstLoop = TopMostLoops[0];
> 
>     PHINode* IV = FirstLoop->getInductionVariable(SE);
>     // ...
> }
> 
> In the above code, getInductionVariable fails, stating "LV: PHI is a
> recurrence with respect to an outer loop”. However, if I reference the
> LoopInfo object directly in the body of the for loop (e.g. LoopInfo& LI
> GetLI(*Fn) and replace instances of Cache[Fn] with LI) then the
> getInductionVariable call succeeds and returns the appropriate PHINode.
> std::move - the only way to transfer/retain the result - seems to change
> the LoopInfo that is returned, making it invalid?
 
> 
> So a few questions I have are:
> 
>   1.  Is this expected or unusual behaviour?
>   2.  Does one just need to call getAnalysis<LoopInfoWrapperPass>(…)
every
> time they need it (due to the memory optimisations) or is there something
> wrong with my logic above that is preventing the example from working?
 3. 
> Are there any similar uses in the codebase (other passes or such) that
> require storing loop information? I’ve not been able to find any. 
> 
> I appreciate any and all input to help clarify this issue.
> 
> 
> Thanks for your time,
> Andrew L-S
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part.
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210823/249ecd68/attachment.sig>

In addition to the LoopInfo itself, LoopInfoWrapperPass has
dependencies such as DominatorTree and ScalarEvolution. Using The
getAnalysis<T>(Function*) method will run LoopInfo and its
dependencies on-the-fly. However, this On-the-fly mechanism holds the
results for only one function at a time. Calling it for another one
will delete the result for the previous function. You saved the
LoopInfo using std::move, but it still requires some dependent
analysis even after LoopInfo has been computed, what the legacy pass
manager calls (in your case: ScalarEvolution). ScalarEvolution will
also been released after the call of getAnalysis for another function.
And using LoopInfo after it will result in use-after-free errors.

Solutions:

1. Instantiate your own pass manager for each function instead using
the on-the-fly mechanism, so you control the lifetime.

2. Use the new pass manager, which does not free any analyses until
explicitly invalidated.

MIchael


Am Mo., 23. Aug. 2021 um 07:02 Uhr schrieb LAMZED-SHORT, ANDREW (PGR)
via llvm-dev <llvm-dev at lists.llvm.org>:
>
> Hi all,
>
> I’ve recently been working with the loop analysis pass and functionality
when developing my own transformation pass, and came across something with the
LoopInfo class and LoopAnalysisWrapper that I would appreciate some clarity on.
>
> Principally, I’m interested in caching the results of
LoopInfoWrapperPass::runOnFunction as I routinely need to look at and pick apart
the loops within a given set of user-defined Functions in the input bytecode.
>
> To get the LoopInfo for a given Function, the following Lambda is used for
brevity:
> auto GetLI = [&](Function& F) -> LoopInfo & {
>     return getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
> };
>
> Due to the copy semantics of the LoopInfo class being implicitly deleted
and the above LoopBase behaviour, I use std::move to add this LoopInfo object as
a value in a map, with the pointer to the Function as the key. I found a need to
do this as, if I were to call getAnalysis<LoopInfoWrapperPass.(…) multiple
times in the same scope, all of the references and loop information changes in
each LoopInfo object, e.g.:
>
> LoopInfo& LoopsForF = GetLI(*FunctionF);
> LoopInfo& LoopsForG = GetLI(*FunctionG);
>
> The LoopInfo objects are the same, or, at least, the information within in
(same BasicBlock reference, same number of sub loops etc.) The LoopsForF object
changes. As far as I’ve read and ascertained, this is because
LoopInfoWrapperPass and LoopInfo are optimised for memory and speed.
LoopInfoWrapperPass stores a LoopInfo result object that it reassigns during
each call to its runOnFunction method. This releases the contents of the
BumpPtrAllocator memory in LoopInfo (in LoopInfoBase) for the new function's
loop information to be stored within, hence why they would be the same.
>
>
> Calling std::move seems to work up until I try to reference and utilise the
LoopInfo, as in the following pseudocode example:
>
> std::map<Function*, LoopInfo> Cache;
> for (Function* Fn : getFunctions()) {
>     if (Cache.find(Fn) == Cache.end()) {
>         Cache.emplace(Fn, std::move(GetLI(*Fn)));
>     }
>
>     ScalarEvolution& SE = GetSE(*Fn);
>     // We assume at least one loop in function body
>     auto TopMostLoops = Cache[Fn].getTopLevelLoops();
>     Loop* FirstLoop = TopMostLoops[0];
>
>     PHINode* IV = FirstLoop->getInductionVariable(SE);
>     // ...
> }
>
> In the above code, getInductionVariable fails, stating "LV: PHI is a
recurrence with respect to an outer loop”. However, if I reference the LoopInfo
object directly in the body of the for loop (e.g. LoopInfo& LI = GetLI(*Fn)
and replace instances of Cache[Fn] with LI) then the getInductionVariable call
succeeds and returns the appropriate PHINode. std::move - the only way to
transfer/retain the result - seems to change the LoopInfo that is returned,
making it invalid?
>
>
> So a few questions I have are:
>
> Is this expected or unusual behaviour?
> Does one just need to call getAnalysis<LoopInfoWrapperPass>(…) every
time they need it (due to the memory optimisations) or is there something wrong
with my logic above that is preventing the example from working?
> Are there any similar uses in the codebase (other passes or such) that
require storing loop information? I’ve not been able to find any.
>
>
>
> I appreciate any and all input to help clarify this issue.
>
>
> Thanks for your time,
> Andrew L-S
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev