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