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.<div>
<div><br></div><div>Nick</div><br><div class="gmail_quote">On 8 February 2012 12:05, 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">
Attached<br>
<br>
2012/2/8 Marcello Maggioni <<a href="mailto:hayarms@gmail.com">hayarms@gmail.com</a>>:<br>
<div class="HOEnZb"><div class="h5">> 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 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 = dyn_cast<BranchInst>(ExitingBlock->getTerminator());<br>
> +<br>
> if (ExitBr == 0) return getCouldNotCompute();<br>
> assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");<br>
><br>
> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-><br>
> + getSuccessor(0)->getTerminator());<br>
> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-><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 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 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 block<br>
> + //that has only one predecessor and has an unconditional branch to 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 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>
>> diff --git a/lib/Analysis/ScalarEvolution.cpp 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 = dyn_cast<BranchInst>(ExitingBlock->getTerminator());<br>
>> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-><br>
>> + getSuccessor(0)->getTerminator());<br>
>> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-><br>
>> + getSuccessor(1)->getTerminator());<br>
>> +<br>
>> if (ExitBr == 0) return getCouldNotCompute();<br>
>> assert(ExitBr->isConditional() && "If unconditional, it can't be in 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 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 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>
</div></div><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></blockquote></div><br></div>