[Polly] Take a PHI's incoming block as value user

[Meinersbur]

Summary

Before this patch, we determine whether a value escapes the SCoP by checking whether it the instruction itself is within the scop. This is wrong for PHINodes because the value must be available in the incoming block instead of of where the PHI is.

To fix this, we introduce a function "getUseBlock" to determine the location of a value's use for PHIs and other instructions. It will also be used in subsequent patches.

I could not produce a test case because of region simplification and loop versioning which adds additional block between the PHIs and the SCoP region. Nonetheless, it happend during debugging of preliminary code and is in general the correct way.

[grosser]

LGTM.

[jdoerfert]

Meinersbur created this revision.
Meinersbur added reviewers: grosser, jdoerfert.
Meinersbur added subscribers: llvm-commits, pollydev.
Meinersbur added a project: Polly.

Before this patch, we determine whether a value escapes the SCoP by checking whether it the instruction itself is within the scop. This is wrong for PHINodes because the value must be available in the incoming block instead of of where the PHI is.

I don't get it. A PHI (here Inst in the BlockGenerators) which is in the
SCoP escapes the SCoP, if it is used outside the SCoP, or not? Where is
the difference to any other instruction? Or do you talk about a user
PHI? In that case I would say an instruction (here Inst) escapes the
SCoP, if the user PHI is not in the SCoP. Either way the code we had
seems fine to me but I could have missed something here...

To fix this, we introduce a function "getUseBlock" to determine the location of a value's use for PHIs and other instructions. It will also be used in subsequent patches.

I could not produce a test case because of region simplification and loop versioning which adds additional block between the PHIs and the SCoP region. Nonetheless, it happend during debugging of preliminary code and is in general the correct way.

http://reviews.llvm.org/D15693

Files:

include/polly/Support/ScopHelper.h
lib/CodeGen/BlockGenerators.cpp
lib/Support/ScopHelper.cpp

Index: lib/Support/ScopHelper.cpp

• lib/Support/ScopHelper.cpp

+++ lib/Support/ScopHelper.cpp
@@ -453,3 +453,14 @@

return false;

}
+
+llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
+ Instruction *UI = dyn_cast<Instruction>(U.getUser());
+ if (!UI)
+ return nullptr;
+
+ if (PHINode *PHI = dyn_cast<PHINode>(UI))
+ return PHI->getIncomingBlock(U);
+
+ return UI->getParent();
+}

Index: lib/CodeGen/BlockGenerators.cpp

• lib/CodeGen/BlockGenerators.cpp

+++ lib/CodeGen/BlockGenerators.cpp
@@ -365,14 +365,14 @@

  return;
 
EscapeUserVectorTy EscapeUsers;

• for (User *U : Inst->users()) {

+ for (Use &U : Inst->uses()) {

// Non-instruction user will never escape.

• Instruction *UI = dyn_cast<Instruction>(U);

+ Instruction *UI = dyn_cast<Instruction>(U.getUser());

if (!UI)
  continue;

• if (R.contains(UI))

+ if (R.contains(getUseBlock(U)))

  continue;
 
EscapeUsers.push_back(UI);

Index: include/polly/Support/ScopHelper.h

• include/polly/Support/ScopHelper.h

+++ include/polly/Support/ScopHelper.h
@@ -164,5 +164,14 @@
/// otherwise return false.
bool canSynthesize(const llvm::Value *V, const llvm::LoopInfo *LI,

llvm::ScalarEvolution *SE, const llvm::Region *R);

+
+/ @brief Return the block in which a value is used.
+/
+/ For normal instructions, this is the instruction's parent block. For PHI
+/ nodes, this is the incoming block of that use, because this is where the
+/ operand must be defined (i.e. its definition dominates this block).
+/ Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(llvm::Use &U);
}
#endif

You received this message because you are subscribed to the Google Groups "Polly Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [e-mail].
For more options, visit https://groups.google.com/d/optout.

Index: lib/Support/ScopHelper.cpp

• lib/Support/ScopHelper.cpp

+++ lib/Support/ScopHelper.cpp
@@ -453,3 +453,14 @@

return false;

}
+
+llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
+ Instruction *UI = dyn_cast<Instruction>(U.getUser());
+ if (!UI)
+ return nullptr;
+
+ if (PHINode *PHI = dyn_cast<PHINode>(UI))
+ return PHI->getIncomingBlock(U);
+
+ return UI->getParent();
+}

Index: lib/CodeGen/BlockGenerators.cpp

• lib/CodeGen/BlockGenerators.cpp

+++ lib/CodeGen/BlockGenerators.cpp
@@ -365,14 +365,14 @@

  return;
 
EscapeUserVectorTy EscapeUsers;

• for (User *U : Inst->users()) {

+ for (Use &U : Inst->uses()) {

// Non-instruction user will never escape.

• Instruction *UI = dyn_cast<Instruction>(U);

+ Instruction *UI = dyn_cast<Instruction>(U.getUser());

if (!UI)
  continue;

• if (R.contains(UI))

+ if (R.contains(getUseBlock(U)))

  continue;
 
EscapeUsers.push_back(UI);

Index: include/polly/Support/ScopHelper.h

• include/polly/Support/ScopHelper.h

+++ include/polly/Support/ScopHelper.h
@@ -164,5 +164,14 @@
/// otherwise return false.
bool canSynthesize(const llvm::Value *V, const llvm::LoopInfo *LI,

llvm::ScalarEvolution *SE, const llvm::Region *R);

+
+/ @brief Return the block in which a value is used.
+/
+/ For normal instructions, this is the instruction's parent block. For PHI
+/ nodes, this is the incoming block of that use, because this is where the
+/ operand must be defined (i.e. its definition dominates this block).
+/ Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(llvm::Use &U);
}
#endif

• signature.asc219 BDownload

[grosser]

Hi Michael,

I just went again over the patch and debugged a simple example. I have the feeling this patch is in fact not the right approach. Assume there is a PHI node in an exit block of the scop, which uses values that are defined inside the scop and for which the incoming block of the PHI node is also part of the scop. In this case, I would still expect the values used by this PHI node to be marked as escaping. With your patch this would generally not be the case (and just happens to still be the case because we first run executeScopConditionally and only then generate the list escaping values). I also do not see how handleOutsideUsers could ever have caused a bug in its current shape.

Assuming I did not misunderstand something and assuming that getUseBlock is useful in the context of another patch, we should probably leave handleOutsideUsers as it is and introduce getUseBlock with the code that actually needs it.

Best,
Tobias

[Meinersbur]

In D15693#315190, @jdoerfert wrote:

Before this patch, we determine whether a value escapes the SCoP by checking whether it the instruction itself is within the scop. This is wrong for PHINodes because the value must be available in the incoming block instead of of where the PHI is.

I don't get it. A PHI (here Inst in the BlockGenerators) which is in the
SCoP escapes the SCoP, if it is used outside the SCoP, or not? Where is
the difference to any other instruction? Or do you talk about a user
PHI? In that case I would say an instruction (here Inst) escapes the
SCoP, if the user PHI is not in the SCoP. Either way the code we had
seems fine to me but I could have missed something here...

Yes, it is about the PHI as a user of a potentially escaping value (which by itself may or may not be defined by a PHI).

Think of the following case:

scop_enter:
  phi float [%v, %outofscop]
  %v = ...

scop_exit:

outofscop:
  br label %scop_enter

Is %v escaping? The answer is yes, because otherwise we'd need to add a MK_PHI WRITE to br label %scop_enter, which we cannot do because it is not a ScopStmt. Also see the comment in bool DominatorTree::dominates(const Instruction *Def, const Use &U). ("PHI nodes use their operands on edges")

We had this problem before when creating ScopInfo. There is this code to workaround this which I intend to replace in D15706:

// Uses by PHI nodes in the entry node count as external uses in case the
// use is through an incoming block that is itself not contained in the
// region.
if (R->getEntry() == UseParent) {
  if (auto *PHI = dyn_cast<PHINode>(UI)) {
    bool ExternalUse = false;
    for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
      if (PHI->getIncomingValue(i) == Inst &&
          !R->contains(PHI->getIncomingBlock(i))) {
        ExternalUse = true;
        break;
      }
    }
 
    if (ExternalUse) {
      AnyCrossStmtUse = true;
      continue;
    }
  }
}

[Meinersbur]

In D15693#315252, @grosser wrote:

Hi Michael,

I just went again over the patch and debugged a simple example. I have the feeling this patch is in fact not the right approach. Assume there is a PHI node in an exit block of the scop, which uses values that are defined inside the scop and for which the incoming block of the PHI node is also part of the scop. In this case, I would still expect the values used by this PHI node to be marked as escaping. With your patch this would generally not be the case (and just happens to still be the case because we first run executeScopConditionally and only then generate the list escaping values).

There is some special handling for exit block PHIs, which in this case are handled more like MK_Values, not MK_PHIs. MK_Value's are have a final_reload and it does not matter whether there is a single write (in case of MK_Value) or multiple (MK_PHI). It is the the value defined by the PHI which is checked whether escaping (if I'm not mistaken)

I also do not see how handleOutsideUsers could ever have caused a bug in its current shape.

Yes, because of executeScopConditionally. But it doesn't change that PHI's use values on edges and not in the BB where the PHI is as assumed in this code.

[llvm-commits]

• signature.asc219 BDownload
• msg-22488-492.txt162 BDownload

[Meinersbur]

currently unexploitable; getUseBlock() will integrated into D15706.

include/polly/Support/ScopHelper.h

 /// @param LI The LoopInfo analysis.
 /// @param SE The scalar evolution database.
 /// @param R The region out of which SSA names are parameters.
 /// @return If the instruction I can be regenerated from its
 ///         scalar evolution representation, return true,
 ///         otherwise return false.
 bool canSynthesize(const llvm::Value *V, const llvm::LoopInfo *LI,
                    llvm::ScalarEvolution *SE, const llvm::Region *R);
+
+/// @brief Return the block in which a value is used.
+///
+/// For normal instructions, this is the instruction's parent block. For PHI
+/// nodes, this is the incoming block of that use, because this is where the
+/// operand must be defined (i.e. its definition dominates this block).
+/// Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(llvm::Use &U);
 }
 #endif

lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
                                         Value *Address) {
   // If there are escape users we get the alloca for this instruction and put it
   // in the EscapeMap for later finalization. Lastly, if the instruction was
   // copied multiple times we already did this and can exit.
   if (EscapeMap.count(Inst))
     return;
 
   EscapeUserVectorTy EscapeUsers;
-  for (User *U : Inst->users()) {
+  for (Use &U : Inst->uses()) {
 
     // Non-instruction user will never escape.
-    Instruction *UI = dyn_cast<Instruction>(U);
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
     if (!UI)
       continue;
 
-    if (R.contains(UI))
+    if (R.contains(getUseBlock(U)))
       continue;
 
     EscapeUsers.push_back(UI);
   }
 
   // Exit if no escape uses were found.
   if (EscapeUsers.empty())
     return;

lib/Support/ScopHelper.cpp

bool polly::canSynthesize(const Value *V, const llvm::LoopInfo *LI,
 
   if (const SCEV *Scev = SE->getSCEV(const_cast<Value *>(V)))
     if (!isa<SCEVCouldNotCompute>(Scev))
       if (!hasScalarDepsInsideRegion(Scev, R))
         return true;
 
   return false;
 }
+
+llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
+  Instruction *UI = dyn_cast<Instruction>(U.getUser());
+  if (!UI)
+    return nullptr;
+
+  if (PHINode *PHI = dyn_cast<PHINode>(UI))
+    return PHI->getIncomingBlock(U);
+
+  return UI->getParent();
+}