[Polly] Allow arbitrary function calls for debugging purposes.

[Meinersbur]

Summary

Add the switch -polly-debug-func to define the name of a debug function. This function is ignored for any validity check.

Its purpose is to allow to observe a value after transformation by a SCoP, and to follow which statements are executed in which order. For instance, consider the following code:

static void dbg_printf(int sum, int i) {
  fprintf(stderr, "The value of sum is %d, i=%d\n", sum, i);
  fflush(stderr);
}

void func(int n) {
  int sum = 0;
  for (int i = 0; i < 16; i+=1) {
    sum += i;
    dbg_printf(sum, i);
  }
}

Executing this after Polly's codegen reveals the new execution order and the assumed values at that point of execution.

[Meinersbur]

Use a ScopStmt's instruction list.

[grosser]

LGTM.

include/polly/Support/ScopHelper.h

466

Two white spaces?

include/polly/Support/ScopHelper.h

 class Pass;
 class DominatorTree;
 class RegionInfo;
 class GetElementPtrInst;
 } // namespace llvm
 
 namespace polly {
 class Scop;
+class ScopStmt;
 
 /// Type to remap values.
 using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
                                  llvm::AssertingVH<llvm::Value>>;
 
 /// Type for a set of invariant loads.
 using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
 

 // first non-boxed surrounding loop for Polly. If the loop is affine, return
 // the loop itself.
 //
 // @param BB            Pointer to the Basic Block to analyze.
 // @param LI            Reference to the LoopInfo.
 // @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
 llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
                                     const BoxedLoopsSetTy &BoxedLoops);
+
+/// Is the given instruction a call to a debug function?
+///
+/// A debug function can be used to insert output in Polly-optimized code which
+/// normally does not allow function calls with side-effects.  For instance, a
+/// printf can be inserted to check whether a value still has the expected value
+/// after Polly generated code:
+///
+///     int sum = 0;
+///     for (int i = 0; i < 16; i+=1) {
+///       sum += i;
+///       printf("The value of sum is %d, i=%d\n", sum, i);
+///     }
+bool isDebugCall(llvm::Instruction *Inst);
+
+/// Does the statement contain a call to a debug function?
+///
+/// Such a statement must not be removed, even if has no side-effects.
+bool hasDebugCall(ScopStmt *Stmt);
 } // namespace polly
 #endif

lib/Analysis/ScopBuilder.cpp

 }
 
 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
     return false;
 
-  if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
+  if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI) || isDebugCall(CI))
     return true;
 
   bool ReadOnly = false;
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
   auto *CalledFunction = CI->getCalledFunction();
   switch (AA.getModRefBehavior(CalledFunction)) {
   case FMRB_UnknownModRefBehavior:
     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");

lib/Analysis/ScopDetection.cpp

if (isValidIntrinsicInst(*II, Context))
       return true;
 
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == nullptr)
     return false;
 
+  if (isDebugCall(&CI)) {
+    DEBUG(dbgs() << "Allow call to debug function: "
+                 << CalledFunction->getName() << '\n');
+    return true;
+  }
+
   if (AllowModrefCall) {
     switch (AA.getModRefBehavior(CalledFunction)) {
     case FMRB_UnknownModRefBehavior:
       return false;
     case FMRB_DoesNotAccessMemory:
     case FMRB_OnlyReadsMemory:
       // Implicitly disable delinearization since we have an unknown
       // accesses with an unknown access function.

lib/Analysis/ScopInfo.cpp

void Scop::removeStmtNotInDomainMap() {
   auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
     return !this->DomainMap.lookup(Stmt.getEntryBlock());
   };
   removeStmts(ShouldDelete, false);
 }
 
 void Scop::simplifySCoP(bool AfterHoisting) {
   auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
+    // Never delete statements that contain calls to debug functions.
+    if (hasDebugCall(&Stmt))
+      return false;
+
     bool RemoveStmt = Stmt.isEmpty();
 
     // Remove read only statements only after invariant load hoisting.
     if (!RemoveStmt && AfterHoisting) {
       bool OnlyRead = true;
       for (MemoryAccess *MA : Stmt) {
         if (MA->isRead())
           continue;

lib/Support/ScopHelper.cpp

 
 #define DEBUG_TYPE "polly-scop-helper"
 
 static cl::opt<bool> PollyAllowErrorBlocks(
     "polly-allow-error-blocks",
     cl::desc("Allow to speculate on the execution of 'error blocks'."),
     cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::list<std::string> DebugFunctions(
+    "polly-debug-func",
+    cl::desc("Allow calls to the specified functions in SCoPs even if their "
+             "side-effects are unknown. This can be used to do debug output in "
+             "Polly-transformed code."),
+    cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
+
 // Ensures that there is just one predecessor to the entry node from outside the
 // region.
 // The identity of the region entry node is preserved.
 static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
                                 RegionInfo *RI) {
   BasicBlock *EnteringBB = R->getEnteringBlock();
   BasicBlock *Entry = R->getEntry();
 
for (auto Pred : predecessors(R.getExit()))
         DominatesAllPredecessors = false;
   }
 
   if (DominatesAllPredecessors)
     return false;
 
   for (Instruction &Inst : BB)
     if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
+      if (isDebugCall(CI))
+        continue;
+
       if (isIgnoredIntrinsic(CI))
         continue;
 
       // memset, memcpy and memmove are modeled intrinsics.
       if (isa<MemSetInst>(CI) || isa<MemTransferInst>(CI))
         continue;
 
       if (!CI->doesNotAccessMemory())

 }
 
 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
                                            llvm::LoopInfo &LI,
                                            const BoxedLoopsSetTy &BoxedLoops) {
   Loop *L = LI.getLoopFor(BB);
   return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
 }
+
+bool polly::isDebugCall(Instruction *Inst) {
+  auto *CI = dyn_cast<CallInst>(Inst);
+  if (!CI)
+    return false;
+
+  Function *CF = CI->getCalledFunction();
+  if (!CF)
+    return false;
+
+  return std::find(DebugFunctions.begin(), DebugFunctions.end(),
+                   CF->getName()) != DebugFunctions.end();
+}
+
+static bool hasDebugCall(BasicBlock *BB) {
+  for (Instruction &Inst : *BB) {
+    if (isDebugCall(&Inst))
+      return true;
+  }
+  return false;
+}
+
+static bool hasDebugCall(Region *R) {
+  for (BasicBlock *RBB : R->blocks())
+    if (hasDebugCall(RBB))
+      return true;
+  return false;
+}
+
+bool polly::hasDebugCall(ScopStmt *Stmt) {
+  // Quick skip if no debug functions have been defined.
+  if (DebugFunctions.empty())
+    return false;
+
+  if (!Stmt)
+    return false;
+
+  if (Stmt->isBlockStmt())
+    return ::hasDebugCall(Stmt->getBasicBlock());
+  return ::hasDebugCall(Stmt->getRegion());
+}

test/ScopInfo/debug_call.ll

+; RUN: opt %loadPolly -polly-debug-func=dbg_printf -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Check that the call to dbg_printf is accepted as a debug-function.
+;
+declare void @dbg_printf(i8*, ...)
+
+define void @func(i32 %n) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      call void (i8*, ...) @dbg_printf(i8* null, i32 %j)
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> [i0, 0] };
+; CHECK-NEXT:     Stmt_body_last
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body_last[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body_last[i0] -> [i0, 1] };
+; CHECK-NEXT: }