llvm dev - May 2013 - [LLVMdev] [polly] Polly Loop info and LoopSimplify functionality

Tobias,

  I am working on one very well hidden issue with Polly loop structure. Here
is a brief description.

In polly::createLoop() we create something like this (topology is
important):

polly.start:                                      ; preds
%polly.split_new_and_old
... <some code>
  br label %polly.loop_header

polly.loop_after:                                 ; preds %polly.loop_header
  br label %polly.merge_new_and_old  // This is exit from the loop

polly.loop_header:                                ; preds %polly.stmt.for.body6,
%polly.start
... <some code>
  br i1 %9, label %polly.loop_body, label %polly.loop_after

polly.loop_body:                                  ; preds %polly.loop_header
  br label %polly.stmt.for.body6

polly.stmt.for.body6:                             ; preds = %polly.loop_body
... <some code>
  br label %polly.loop_header

The question is - is the polly.loop_after BB supposed to be a part of the
loop or not? ...and where it should be properly placed.

The problem starts when one of the later passes calls LoopSimplify() and the
first thing it does, it performs the following
(lib/Transforms/Utils/LoopSimplify.cpp):

  // Check to see that no blocks (other than the header) in this loop have
  // predecessors that are not in the loop.  This is not valid for natural
  // loops, but can occur if the blocks are unreachable.  Since they are
  // unreachable we can just shamelessly delete those CFG edges!
  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
       BB != E; ++BB) {
    if (*BB == L->getHeader()) continue;

    SmallPtrSet<BasicBlock*, 4> BadPreds;
    for (pred_iterator PI = pred_begin(*BB),
         PE = pred_end(*BB); PI != PE; ++PI) {
      BasicBlock *P = *PI;
      if (!L->contains(P))
        BadPreds.insert(P);
    }

    // Delete each unique out-of-loop (and thus dead) predecessor.
    for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(),
         E = BadPreds.end(); I != E; ++I) {

      DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead
predecessor "
                   << (*I)->getName() << "\n");
 ...

In this case, the polly.loop_after BB is _not_ recognized as part of the
loop, so this is executed

      if (!L->contains(P))
        BadPreds.insert(P);

And the only exit edge from the loop is removed... 


Now the top level question: are we violating some implicit topology
assumption, or LoopInfo gathering has an issue? If I remember right, Polly
itself does not update LoopInfo, and it states that it preserves it (by the
way ...why?)

lib/CodeGen/CodeGeneration.cpp
 // FIXME: We do not create LoopInfo for the newly generated loops.
    AU.addPreserved<LoopInfo>();

lib/CodeGen/IslCodeGeneration.cpp:
    // FIXME: We do not create LoopInfo for the newly generated loops.
    AU.addPreservedID(LoopInfo::getClassPassID());

...or as always I might be missing a big picture here, and I appreciate if
you can explain the original intent.

Thanks a lot. 

Sergei







 

---
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation

On 05/15/2013 07:08 PM, Sergei Larin wrote:
>
> Tobias,
[..]
>
> ...or as always I might be missing a big picture here, and I appreciate if
> you can explain the original intent.
Hi Sergei,

thanks for reporting this issue in so much detail. I am afraid there is 
no bigger story. For some reason the update of the LoopInfo was not 
included in the original patch of the code generation, but we still 
claimed it is updated because otherwise the scop detection would be 
invalidated as soon as code generation is run the first time. This was 
obviously a hack and the fact that you were bitten by it shows that 
adding such hacks is not a good thing.

I am actively working on removing such hacks and this one was one of the 
larger ones remaining. I had two patches in my queue to address this. 
The first one makes Polly create loops in an already loop rotated form. 
The second patch adds the missing loop information updates. I committed 
these patches in r181986 and r181987.

Could you check if those patches work for you and possibly even post 
review the commits in general.

Thanks,
Tobias

Tobias,

  Thank you for the exceptional turnaround time. The second fix (r181987)
appears to get it. The real issue seems to be that we have never added the
newly created (child) loop to the parent loop. It in turn was confusing the
LoopInfo regeneration in some scenarios... I am still testing the fix, but
thank you again for such a prompt reaction.

Sergei

---
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation

> -----Original Message-----
> From: Tobias Grosser [mailto:tobias at grosser.es]
> Sent: Thursday, May 16, 2013 1:58 AM
> To: Sergei Larin
> Cc: 'Sebastian Pop'; llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] [polly] Polly Loop info and LoopSimplify
functionality
> 
> On 05/15/2013 07:08 PM, Sergei Larin wrote:
> >
> > Tobias,
> [..]
> >
> > ...or as always I might be missing a big picture here, and I
> > appreciate if you can explain the original intent.
> 
> Hi Sergei,
> 
> thanks for reporting this issue in so much detail. I am afraid there is no
bigger
> story. For some reason the update of the LoopInfo was not included in the
> original patch of the code generation, but we still claimed it is updated
> because otherwise the scop detection would be invalidated as soon as code
> generation is run the first time. This was obviously a hack and the fact
that
> you were bitten by it shows that adding such hacks is not a good thing.
> 
> I am actively working on removing such hacks and this one was one of the
> larger ones remaining. I had two patches in my queue to address this.
> The first one makes Polly create loops in an already loop rotated form.
> The second patch adds the missing loop information updates. I committed
> these patches in r181986 and r181987.
> 
> Could you check if those patches work for you and possibly even post
review
> the commits in general.
> 
> Thanks,
> Tobias