[llvm-dev] LSR/SCEV problem/question

[Geoff Berry via llvm-dev]

Hi Sanjoy,

Thanks for your interest.  I've attached a reduced reproducer of this issue.  You can trigger it by running the following opt command after applying my recently updated patch D18480 (note the change in review number since Phabricator wouldn't let me re-open the original review):

  $ opt -loop-reduce lsr-scev-hoist-insertpt.ll

Below is a call stack at the point where the insertion point is hoisted into a different block.  The line numbers are a little off because of some debugging code I've added, but they should be pretty close.
The IR instruction that gets picked as an insertion point and gets hoisted is:

  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1

The BaseReg SCEV being expanded when this happens is:

  {1,+,1}<nuw><nsw><%while.cond>

2  in llvm::SCEVExpander::hoistIVInc of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:940
3  in llvm::SCEVExpander::getAddRecExprPHILiterally of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1120
4  in llvm::SCEVExpander::expandAddRecExprLiterally of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1294
5  in llvm::SCEVExpander::visitAddRecExpr of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1382
6  in llvm::SCEVVisitor<llvm::SCEVExpander, llvm::Value*>::visit of llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:482
7  in llvm::SCEVExpander::expand of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1687
8  in llvm::SCEVExpander::expandCodeFor of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1599
9  in llvm::SCEVExpander::expandCodeFor of llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1594
10 in (anonymous namespace)::LSRInstance::Expand of llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:4498
11 in (anonymous namespace)::LSRInstance::Rewrite of llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:4725
12 in (anonymous namespace)::LSRInstance::ImplementSolution of llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:4775
13 in (anonymous namespace)::LSRInstance::LSRInstance of llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:4897
14 in (anonymous namespace)::LoopStrengthReduce::runOnLoop of llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:5022

--
Geoff Berry
Employee of Qualcomm Innovation Center, Inc.
 Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Thursday, March 24, 2016 5:06 PM
To: Geoff Berry <gberry at codeaurora.org>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; David Majnemer <david.majnemer at gmail.com>; Andrew Trick <atrick at apple.com>; Quentin Colombet <qcolombet at apple.com>
Subject: Re: LSR/SCEV problem/question

Hi Geoff,

Firstly, I think it will be great if you have a small reproducer of this issue (which I can make fail after re-applying D18001 to ToT).

> I’ve run into what appears to be a bug in ScalarEvolution, but I’m not 
> sure if it is instead caused by me missing an implicit assumption 
> between LSR and SCEV.
>
> This issue is caused by the change D18001, which is an attempt to 
> increase SCEV-inserted instruction re-use by picking a more canonical 
> insertion position in the case where a new insert position block is not found.
>
> The problem I have run into with this change is that it causes an 
> insert position instruction to be chosen which is later hoisted into a 
> different block by  SCEVExpander::hoistIVInc().  This in turn makes 
> the SCEVExpander

When is the insert position moved?  IOW, what is the "timeline" of events?

There are two calls to hoistIVInc in SCEVExpander, in getAddRecExprPHILiterally and in replaceCongruentIVs -- which one is the problematic case?

> Builder InsertPt inconsistent (the instruction and block end up not 
> matching), which leads to an invalid instruction being inserted (with 
> its parent != its containing block).

-- Sanjoy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lsr-scev-hoist-insertpt.ll
Type: application/octet-stream
Size: 1578 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/d5e632d1/attachment.obj>