[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
Nick Lewycky
nlewycky at google.com
Wed Feb 8 15:52:58 PST 2012
On 8 February 2012 15:50, Marcello Maggioni <hayarms at gmail.com> wrote:
> Well, it wasn't intended as a "real" patch to be included , but more
> as a "proof of concept" for a solution. Do you think it is a valid
> solution and I'm correct in my assumption? If so then I'll clean up
> the patch and attach a testcase for inclusion.
>
I'm not sure -- when I tried to track the IR in your screenshot through the
code in SCEV I came up with a completely different reason it would return
the CNC than the one you gave in your email. It would really help to have a
testcase in .ll format.
Nick
> Thanks!
>
> Marcello
>
> 2012/2/9 Nick Lewycky <nlewycky at google.com>:
> > Your patch should include a testcase, see test/Analysis/ScalarEvolution
> for
> > examples. "BranchInst* " should be "BranchInst *". You should have spaces
> > after the // in your comments. One of the comment lines isn't indented
> > properly.
> >
> > Nick
> >
> > On 8 February 2012 12:05, Marcello Maggioni <hayarms at gmail.com> wrote:
> >>
> >> Attached
> >>
> >> 2012/2/8 Marcello Maggioni <hayarms at gmail.com>:
> >> > Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may
> >> > be ...) , this one should be ok (and passess all the ScalarEvolution
> >> > tests in LLVM):
> >> >
> >> > diff --git a/lib/Analysis/ScalarEvolution.cpp
> >> > b/lib/Analysis/ScalarEvolution.cpp
> >> > index daf7742..b10fab2 100644
> >> > --- a/lib/Analysis/ScalarEvolution.cpp
> >> > +++ b/lib/Analysis/ScalarEvolution.cpp
> >> > @@ -4293,9 +4293,15 @@ ScalarEvolution::ComputeExitLimit(const Loop
> >> > *L, BasicBlock *ExitingBlock) {
> >> > //
> >> > // FIXME: we should be able to handle switch instructions (with a
> >> > single exit)
> >> > BranchInst *ExitBr =
> >> > dyn_cast<BranchInst>(ExitingBlock->getTerminator());
> >> > +
> >> > if (ExitBr == 0) return getCouldNotCompute();
> >> > assert(ExitBr->isConditional() && "If unconditional, it can't be in
> >> > loop!");
> >> >
> >> > + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr->
> >> > +
> >> > getSuccessor(0)->getTerminator());
> >> > + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr->
> >> > +
> >> > getSuccessor(1)->getTerminator());
> >> > +
> >> > // At this point, we know we have a conditional branch that
> >> > determines whether
> >> > // the loop is exited. However, we don't know if the branch is
> >> > executed each
> >> > // time through the loop. If not, then the execution count of the
> >> > branch will
> >> > @@ -4316,10 +4322,23 @@ ScalarEvolution::ComputeExitLimit(const Loop
> >> > *L, BasicBlock *ExitingBlock) {
> >> > if (ExitBr->getSuccessor(0) != L->getHeader() &&
> >> > ExitBr->getSuccessor(1) != L->getHeader() &&
> >> > ExitBr->getParent() != L->getHeader()) {
> >> > - // The simple checks failed, try climbing the unique predecessor
> >> > chain
> >> > - // up to the header.
> >> > +
> >> > bool Ok = false;
> >> > - for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
> >> > + //Check if the one of the successor of the exit branch has the
> is a
> >> > block
> >> > + //that has only one predecessor and has an unconditional branch
> to
> >> > the
> >> > + //loop header
> >> > + if (BrFirstSucc && BrFirstSucc->isUnconditional() &&
> >> > + BrFirstSucc->getSuccessor(0) == L->getHeader() &&
> >> > + BrFirstSucc->getParent()->getUniquePredecessor())
> >> > + Ok = true;
> >> > + if (BrSecondSucc && BrSecondSucc->isUnconditional() &&
> >> > + BrSecondSucc->getSuccessor(0) == L->getHeader() &&
> >> > + BrSecondSucc->getParent()->getUniquePredecessor())
> >> > + Ok = true;
> >> > + // The simple checks failed, try climbing the unique predecessor
> >> > chain
> >> > + // up to the header.
> >> > +
> >> > + for (BasicBlock *BB = ExitBr->getParent(); BB && !Ok; ) {
> >> > BasicBlock *Pred = BB->getUniquePredecessor();
> >> > if (!Pred)
> >> > return getCouldNotCompute();
> >> >
> >> > anyway, this patch is only "a concept" of what I'm talking about.
> >> >
> >> > PS=Sorry for the bad english in the previous post :p
> >> >
> >> > 2012/2/8 Marcello Maggioni <hayarms at gmail.com>:
> >> >> Hello, I'm finding problems with BackEdgeTaken count calculation in
> >> >> even simple fortran loops with gfortran-4.6 + DragonEgg 3.0.
> >> >>
> >> >> Even for simple double loops like this one:
> >> >>
> >> >> program test2
> >> >> integer i,j,k
> >> >> dimension k(100,100)
> >> >> do j=1,100
> >> >> do i=1,100
> >> >> k(i,j) = i
> >> >> enddo
> >> >> enddo
> >> >> write(*,*) k(1,30)
> >> >> end
> >> >>
> >> >> make the ScalarEvolution engine return "CouldNotCompute" even for the
> >> >> outer loop (the inner loop is fine).
> >> >>
> >> >> You can find a screenshot of the translation of this loop here (with
> >> >> -view-cfg Polly version):
> >> >> http://i.imgur.com/Jyaqd.png
> >> >>
> >> >> The problem seems to be the fact that the ScalarEvolution can't
> >> >> consider the outer loop exit branch instruction as the trivial case
> >> >> (where one of the successors of the exit block is the loop header or
> >> >> the exit block is the loop header itself) because of the (strange?)
> >> >> loop shape (the exit block instead of jumping to the header of the
> >> >> loop jumps instead to another block that increments the induction
> >> >> variable and has an unconditional branch to the loop header) and so
> >> >> starts backtracking the predecessors of the of the exit block and
> >> >> stops when it reaches the inner loop that has a block without a
> unique
> >> >> predecessor.
> >> >>
> >> >> What do you think about this problem? This makes , for example,
> >> >> difficult analyzing even simple fortran loops with Polly .
> >> >> I believe the case portrayed in the picture is the same to the
> trivial
> >> >> case (because the exit block jumps to a block with an unconditional
> >> >> jump to the header of the loop), am I right?
> >> >>
> >> >> I've written this little patch that adds this case to the trivial
> case
> >> >> :
> >> >>
> >> >> diff --git a/lib/Analysis/ScalarEvolution.cpp
> >> >> b/lib/Analysis/ScalarEvolution.cpp
> >> >> index daf7742..fcbaffe 100644
> >> >> --- a/lib/Analysis/ScalarEvolution.cpp
> >> >> +++ b/lib/Analysis/ScalarEvolution.cpp
> >> >> @@ -4293,6 +4293,11 @@ ScalarEvolution::ComputeExitLimit(const Loop
> >> >> *L, BasicBlock *ExitingBlock) {
> >> >> //
> >> >> // FIXME: we should be able to handle switch instructions (with a
> >> >> single exit)
> >> >> BranchInst *ExitBr =
> >> >> dyn_cast<BranchInst>(ExitingBlock->getTerminator());
> >> >> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr->
> >> >> +
> >> >> getSuccessor(0)->getTerminator());
> >> >> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr->
> >> >> +
> >> >> getSuccessor(1)->getTerminator());
> >> >> +
> >> >> if (ExitBr == 0) return getCouldNotCompute();
> >> >> assert(ExitBr->isConditional() && "If unconditional, it can't be in
> >> >> loop!");
> >> >>
> >> >> @@ -4315,8 +4320,12 @@ ScalarEvolution::ComputeExitLimit(const Loop
> >> >> *L, BasicBlock *ExitingBlock) {
> >> >> //
> >> >> if (ExitBr->getSuccessor(0) != L->getHeader() &&
> >> >> ExitBr->getSuccessor(1) != L->getHeader() &&
> >> >> - ExitBr->getParent() != L->getHeader()) {
> >> >> - // The simple checks failed, try climbing the unique predecessor
> >> >> chain
> >> >> + ExitBr->getParent() != L->getHeader() &&
> >> >> + !((BrFirstSucc && BrFirstSucc->isUnconditional() &&
> >> >> + BrFirstSucc->getSuccessor(0) == L->getHeader()) ||
> >> >> + (BrSecondSucc && BrSecondSucc->isUnconditional() &&
> >> >> + BrSecondSucc->getSuccessor(0) == L->getHeader())) ) {
> >> >> + // The simple checks failed, try climbing the unique
> predecessor
> >> >> chain
> >> >> // up to the header.
> >> >> bool Ok = false;
> >> >> for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
> >> >>
> >> >> what do you think about this? There is a better solution to the
> >> >> problem? Is the compiler itself broken?
> >> >>
> >> >> Thank you
> >> >>
> >> >> Marcello
> >>
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >>
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120208/38feb6bb/attachment.html>
More information about the llvm-dev
mailing list