llvm dev - Oct 2019 - How to make ScalarEvolution recompute SCEV values?

Hello all,

I’m pretty new to LLVM.

I'm writing a pass for loop optimization. I clone and rearrange loops,
setting the cloned loop as the original loop’s parent. This can be done multiple
times, until there is no more work to do. The trouble is, after the first time I
do this, the cloned loop's SCEVs become unknown types when they should be
AddRecExpr.

If I re-run the whole pass on the IR outputted by the first iteration, it will
correctly identify them as  AddRecExpr.

I've already tried called Scalar Evolution’s *ForgetAllLoops* function, but
that doesn't work. I also tried calling the *runOnFunction* from the
ScalarEvolution pass, but that also didn't work.

My question is: how can I make ScalarEvolution re-calculate the SCEV values for
the unknown SCEVs, or, is there a way to re-run ScalarEvolution and LoopInfo 
analysis pass during my pass?

This is my current CloneLoop function:

Loop *cloneLoop(Function *F, Loop *L, LoopInfo *LI, const Twine &NameSuffix,
                ValueToValueMapTy &VMap) {
    
    // original preheader of the loop
    const auto PreHeader = L->getLoopPreheader();
    
    // keep track of the original predecessors
    std::set<BasicBlock *> AllPredecessors;
    for (auto PredIt = pred_begin(PreHeader), E = pred_end(PreHeader);
         PredIt != E; PredIt++)
        AllPredecessors.insert(*PredIt);
    
    BasicBlock *ExitBlock = L->getExitBlock();
    
    auto DT = DominatorTree(*F);
    
    SmallVector<BasicBlock *, 8> Blocks;
    const auto ClonedLoop = cloneLoopWithPreheader(PreHeader, PreHeader, L,
VMap, NameSuffix, LI, &DT, Blocks);
    VMap[ExitBlock] = PreHeader; // chain: cloned loop -> original loop
    remapInstructionsInBlocks(Blocks, VMap);
    
    // remap original predecessors to the cloned loop
    for (BasicBlock *PredBB : AllPredecessors) {
        Instruction *TI = PredBB->getTerminator();
        for (unsigned i = 0; i < TI->getNumOperands(); i++) {
            if (TI->getOperand(i) == PreHeader)
                TI->setOperand(i, ClonedLoop->getLoopPreheader());
        }
    }
    
    return ClonedLoop;
}

Regards,
Augusto Noronha

It looks like you're passing the wrong DominatorTree to
cloneLoopWithPreheader.  ScalarEvolutionWrapperPass depends on
LoopInfoWrapperPass and DominatorTreeWrapperPass; if those are outdated, SCEV
won't recognize your loops at all.

ScalarEvolution::forgetAllLoops should clear out all the cached data in SCEV
itself.

-Eli
> -----Original Message-----
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of
Augusto
> Noronha via llvm-dev
> Sent: Wednesday, October 30, 2019 4:19 AM
> To: llvm-dev at lists.llvm.org
> Subject: [EXT] [llvm-dev] How to make ScalarEvolution recompute SCEV
values?
>
> Hello all,
>
> I’m pretty new to LLVM.
>
> I'm writing a pass for loop optimization. I clone and rearrange loops,
setting the
> cloned loop as the original loop’s parent. This can be done multiple times,
until
> there is no more work to do. The trouble is, after the first time I do
this, the
> cloned loop's SCEVs become unknown types when they should be
AddRecExpr.
>
> If I re-run the whole pass on the IR outputted by the first iteration, it
will
> correctly identify them as  AddRecExpr.
>
> I've already tried called Scalar Evolution’s *ForgetAllLoops* function,
but that
> doesn't work. I also tried calling the *runOnFunction* from the
ScalarEvolution
> pass, but that also didn't work.
>
> My question is: how can I make ScalarEvolution re-calculate the SCEV values
for
> the unknown SCEVs, or, is there a way to re-run ScalarEvolution and
LoopInfo
> analysis pass during my pass?
>
> This is my current CloneLoop function:
>
> Loop *cloneLoop(Function *F, Loop *L, LoopInfo *LI, const Twine
&NameSuffix,
>                 ValueToValueMapTy &VMap) {
>
>     // original preheader of the loop
>     const auto PreHeader = L->getLoopPreheader();
>
>     // keep track of the original predecessors
>     std::set<BasicBlock *> AllPredecessors;
>     for (auto PredIt = pred_begin(PreHeader), E = pred_end(PreHeader);
>          PredIt != E; PredIt++)
>         AllPredecessors.insert(*PredIt);
>
>     BasicBlock *ExitBlock = L->getExitBlock();
>
>     auto DT = DominatorTree(*F);
>
>     SmallVector<BasicBlock *, 8> Blocks;
>     const auto ClonedLoop = cloneLoopWithPreheader(PreHeader, PreHeader, L,
> VMap, NameSuffix, LI, &DT, Blocks);
>     VMap[ExitBlock] = PreHeader; // chain: cloned loop -> original loop
>     remapInstructionsInBlocks(Blocks, VMap);
>
>     // remap original predecessors to the cloned loop
>     for (BasicBlock *PredBB : AllPredecessors) {
>         Instruction *TI = PredBB->getTerminator();
>         for (unsigned i = 0; i < TI->getNumOperands(); i++) {
>             if (TI->getOperand(i) == PreHeader)
>                 TI->setOperand(i, ClonedLoop->getLoopPreheader());
>         }
>     }
>
>     return ClonedLoop;
> }
>
> Regards,
> Augusto Noronha
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Thanks Eli! 

That was it, I got the DominatorTree by calling 

getAnalysis<DominatorTreeWrapperPass>().getDomTree()

and it worked.

Regards,
Augusto Noronha
> On 30 Oct 2019, at 15:55, Eli Friedman <efriedma at quicinc.com>
wrote:
> 
> It looks like you're passing the wrong DominatorTree to
cloneLoopWithPreheader.  ScalarEvolutionWrapperPass depends on
LoopInfoWrapperPass and DominatorTreeWrapperPass; if those are outdated, SCEV
won't recognize your loops at all.
> 
> ScalarEvolution::forgetAllLoops should clear out all the cached data in
SCEV itself.
> 
> -Eli
> 
>> -----Original Message-----
>> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of
Augusto
>> Noronha via llvm-dev
>> Sent: Wednesday, October 30, 2019 4:19 AM
>> To: llvm-dev at lists.llvm.org
>> Subject: [EXT] [llvm-dev] How to make ScalarEvolution recompute SCEV
values?
>> 
>> Hello all,
>> 
>> I’m pretty new to LLVM.
>> 
>> I'm writing a pass for loop optimization. I clone and rearrange
loops, setting the
>> cloned loop as the original loop’s parent. This can be done multiple
times, until
>> there is no more work to do. The trouble is, after the first time I do
this, the
>> cloned loop's SCEVs become unknown types when they should be
AddRecExpr.
>> 
>> If I re-run the whole pass on the IR outputted by the first iteration,
it will
>> correctly identify them as  AddRecExpr.
>> 
>> I've already tried called Scalar Evolution’s *ForgetAllLoops*
function, but that
>> doesn't work. I also tried calling the *runOnFunction* from the
ScalarEvolution
>> pass, but that also didn't work.
>> 
>> My question is: how can I make ScalarEvolution re-calculate the SCEV
values for
>> the unknown SCEVs, or, is there a way to re-run ScalarEvolution and
LoopInfo
>> analysis pass during my pass?
>> 
>> This is my current CloneLoop function:
>> 
>> Loop *cloneLoop(Function *F, Loop *L, LoopInfo *LI, const Twine
&NameSuffix,
>>                ValueToValueMapTy &VMap) {
>> 
>>    // original preheader of the loop
>>    const auto PreHeader = L->getLoopPreheader();
>> 
>>    // keep track of the original predecessors
>>    std::set<BasicBlock *> AllPredecessors;
>>    for (auto PredIt = pred_begin(PreHeader), E = pred_end(PreHeader);
>>         PredIt != E; PredIt++)
>>        AllPredecessors.insert(*PredIt);
>> 
>>    BasicBlock *ExitBlock = L->getExitBlock();
>> 
>>    auto DT = DominatorTree(*F);
>> 
>>    SmallVector<BasicBlock *, 8> Blocks;
>>    const auto ClonedLoop = cloneLoopWithPreheader(PreHeader, PreHeader,
L,
>> VMap, NameSuffix, LI, &DT, Blocks);
>>    VMap[ExitBlock] = PreHeader; // chain: cloned loop -> original
loop
>>    remapInstructionsInBlocks(Blocks, VMap);
>> 
>>    // remap original predecessors to the cloned loop
>>    for (BasicBlock *PredBB : AllPredecessors) {
>>        Instruction *TI = PredBB->getTerminator();
>>        for (unsigned i = 0; i < TI->getNumOperands(); i++) {
>>            if (TI->getOperand(i) == PreHeader)
>>                TI->setOperand(i, ClonedLoop->getLoopPreheader());
>>        }
>>    }
>> 
>>    return ClonedLoop;
>> }
>> 
>> Regards,
>> Augusto Noronha
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev