[LLVMdev] [polly] Polly Loop info and LoopSimplify functionality

[Sergei Larin]

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