[Polly] Print executed statement instances at runtime.

[Meinersbur]

Summary

Add the option -polly-codegen-trace-stmts and -polly-codegen-print scalars. When enabled, adds a print to the beginning of every generated statement that prints the executed statement instance. With -polly-codegen-print scalars, it also prints the value of all scalars that are used in the statement, and PHIs defined in the beginning of the statement.

[grosser]

Hi Michael,

thanks for the patch. Looks great!

I have one interface comment, which you might to have a look at.

Otherwise, just minor comments / documentation things. While the original code is not as extensively documented, if it is low overhead you might think of completing some more.

include/polly/CodeGen/BlockGenerators.h

339 ↗

(On Diff #142854)

scalarS

include/polly/CodeGen/RuntimeDebugBuilder.h

35 ↗

(On Diff #142854)

Should we document the arguments?

39 ↗

(On Diff #142854)

Maybe add a comment?

76 ↗

(On Diff #142854)

Should we document the arguments?

IMPORTANT: I don't think we should expose this function. This is the internal interface, see below.

93 ↗

(On Diff #142854)

Nice!

110 ↗

(On Diff #142854)

IMPORTANT: I feel this function needs fixing instead of exposing the function pointed out above. It seems this function does not seem to work and apparently is not even tested, which is why you maybe exposed the other function.

An easy fix could be to change this function to.

Values.insert(Values.begin(), Array.begin(), Array.end());
createPrinter(Builder, UseGPU, Values, args...);

This changes the semantics of this function, in that the original idea was to add whitespaces between elements passed in a vector and the new variant would not do this any more. We could probably add/fix white space insertions if this is needed/useful. I don't have an opinion here, but we should likely document this slightly more explicit.

lib/CodeGen/BlockGenerators.cpp

61 ↗

(On Diff #142854)

that _print_

682 ↗

(On Diff #142854)

Add a notice to the assert?

692 ↗

(On Diff #142854)

I assume you intended to leave this in. That's fine with me, just pointing it out.

727 ↗

(On Diff #142854)

do cannot

1494 ↗

(On Diff #142854)

Remove #if 1?

[grosser]

As discussed in the phone call, I added missing functionality in 330292.

[philip.pfaffe]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

Why AddressSpace=4?

[Meinersbur]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

I don't know, this is refactored from the existing RuntimeDebugBuilderCode, and is the reason why I refactored it out instead of calling CreateGlobalStringPtr directly.

I assume this puts string constants into the .rodata segment, but I didn't care enough to look it up.

[grosser]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

This is the CUDA constant address space:

https://llvm.org/docs/NVPTXUsage.html#address-spaces

Probably comes historically when used for CUDA debugging. It also seems to work for CPUs and is used as an indicator to separate between strings and pointers (strings are printed as strings, pointers as integers).

As this is just a refactoring, we should likely document that we use address-space 4 as indicator for strings (rather than integers). It seems there is no easy way to do this differentiation, but if there is one one we should improve this in a followup patch.

[philip.pfaffe]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

Do you have a reference for this? I've never seen addrspace used in anything but GPU-Code. If it works, I'd like to be convinced that that's not by chance.

[grosser]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

The behavior of LLVM for non-zero address spaces is target specific (see langref). It seems the X86 backend does not really consider address space numbers and maps all to address space zero. So yes, it works by-chance to some extend -- meaning it works on X86.

We likely should improve this at some point. Unfortunately there is no easy way to indicate strings. A more conservative approach would be to look through the value and only identify globals which are constant and null-terminated as strings and print everything else as pointers. Maybe that would be good enough -- and would not require address space magic.

[philip.pfaffe]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

Then this should be fixed right now.

[bollu]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

I am confused, what is a "reasonable" fix for this? Isn't this _clearly_ target dependent?

[philip.pfaffe]

include/polly/CodeGen/RuntimeDebugBuilder.h

36 ↗

(On Diff #142854)

It's _clearly_ target dependent, but it's used as if it weren't. I.e., addrspace 4 ends up on the CPU side of things.

Moreover, I realized that addrspace 4 is even used further down, to identify string constants to guess the right format string option. Which needs to be fixed. I'm happy to do this in a seperate change though, so I think this diff can continue as is (remaining comments aside).

39 ↗

(On Diff #142854)

A comment is needed, but why is this on the public API? When am I supposed to use this?

polly/trunk/include/polly/CodeGen/BlockGenerators.h

protected:
   /// @param LTS   A mapping from loops virtual canonical induction
   ///              variable to their new values.
   /// @param BBMap A mapping from old values to their new values in this block.
   /// @param NewAccesses A map from memory access ids to new ast expressions.
   void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT &LTS,
                            ValueMapT &BBMap,
                            __isl_keep isl_id_to_ast_expr *NewAccesses);
 
+  /// When statement tracing is enable, build the print instructions for
+  /// printing the current statement instance and its input scalars.
+  ///
+  /// The printed output looks like:
+  ///
+  ///     Stmt1(0)
+  ///
+  /// If printing of scalars is enabled, it also appends the value of each
+  /// scalar to the line:
+  ///
+  ///     Stmt1(0) %i=1 %sum=5
+  ///
+  /// @param Stmt  The statement we generate code for.
+  /// @param LTS   A mapping from loops virtual canonical induction
+  ///              variable to their new values.
+  /// @param BBMap A mapping from old values to their new values in this block.
+  void generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
+                              ValueMapT &BBMap);
+
   /// Generate instructions that compute whether one instance of @p Set is
   /// executed.
   ///
   /// @param Stmt      The statement we generate code for.
   /// @param Subdomain A set in the space of @p Stmt's domain. Elements not in
   ///                  @p Stmt's domain are ignored.
   ///
   /// @return An expression of type i1, generated into the current builder

polly/trunk/include/polly/CodeGen/RuntimeDebugBuilder.h

 namespace polly {
 
 /// Insert function calls that print certain LLVM values at run time.
 ///
 /// This class inserts libc function calls to print certain LLVM values at
 /// run time.
 struct RuntimeDebugBuilder {
 
+  /// Generate a constant string into the builder's llvm::Module which can be
+  /// passed to createGPUPrinter() or createGPUPrinter().
+  ///
+  /// @param Builder The builder used to emit the printer calls.
+  /// @param Str     The string to be printed.
+
+  /// @return        A global containing @p Str.
+  static llvm::Value *getPrintableString(PollyIRBuilder &Builder,
+                                         llvm::StringRef Str) {
+    // TODO: Get rid of magic number 4. It it NVPTX's constant address space and
+    // works on X86 (CPU) only because its backend ignores the address space.
+    return Builder.CreateGlobalStringPtr(Str, "", 4);
+  }
+
+  /// Return whether an llvm::Value of the type @p Ty is printable for
+  /// debugging.
+  ///
+  /// That is, whether such a value can be passed to createGPUPrinter() or
+  /// createGPUPrinter() to be dumped as runtime.  If false is returned, those
+  /// functions will fail.
+  static bool isPrintable(llvm::Type *Ty);
+
   /// Print a set of LLVM-IR Values or StringRefs via printf
   ///
   ///  This function emits a call to printf that will print the given arguments.
   ///  It is useful for debugging CPU programs. All arguments given in this list
   ///  will be automatically concatenated and the resulting string will be
   ///  printed atomically. We also support ArrayRef arguments, which can be used
   ///  to provide of id values.
   ///
static void createPrinter(PollyIRBuilder &Builder, bool UseGPU,
     createPrinter(Builder, UseGPU, Values, args...);
   }
 
   /// Handle StringRefs.
   template <typename... Args>
   static void createPrinter(PollyIRBuilder &Builder, bool UseGPU,
                             std::vector<llvm::Value *> &Values,
                             llvm::StringRef String, Args... args) {
-    Values.push_back(Builder.CreateGlobalStringPtr(String, "", 4));
+    Values.push_back(getPrintableString(Builder, String));
     createPrinter(Builder, UseGPU, Values, args...);
   }
 
   /// Handle ArrayRefs.
   template <typename... Args>
   static void createPrinter(PollyIRBuilder &Builder, bool UseGPU,
                             std::vector<llvm::Value *> &Values,
                             llvm::ArrayRef<llvm::Value *> Array, Args... args) {

polly/trunk/lib/CodeGen/BlockGenerators.cpp

 
 bool PollyDebugPrinting;
 static cl::opt<bool, true> DebugPrintingX(
     "polly-codegen-add-debug-printing",
     cl::desc("Add printf calls that show the values loaded/stored."),
     cl::location(PollyDebugPrinting), cl::Hidden, cl::init(false),
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<bool> TraceStmts(
+    "polly-codegen-trace-stmts",
+    cl::desc("Add printf calls that print the statement being executed"),
+    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<bool> TraceScalars(
+    "polly-codegen-trace-scalars",
+    cl::desc("Add printf calls that print the values of all scalar values "
+             "used in a statement. Requires -polly-codegen-trace-stmts."),
+    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+
 BlockGenerator::BlockGenerator(
     PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
     AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,
     ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
     : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
       EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
       GlobalMap(GlobalMap), StartBlock(StartBlock) {}
 

 }
 
 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
                                    isl_id_to_ast_expr *NewAccesses) {
   BasicBlock *CopyBB = splitBB(BB);
   Builder.SetInsertPoint(&CopyBB->front());
   generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
+  generateBeginStmtTrace(Stmt, LTS, BBMap);
 
   copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
 
   // After a basic block was copied store all scalars that escape this block in
   // their alloca.
   generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
   return CopyBB;
 }
void BlockGenerator::generateConditionalExecution(
 
   // Put the client code into the conditional block and continue in the merge
   // block afterwards.
   Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
   GenThenFunc();
   Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
 }
 
+static std::string getInstName(Value *Val) {
+  std::string Result;
+  raw_string_ostream OS(Result);
+  Val->printAsOperand(OS, false);
+  return OS.str();
+}
+
+void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
+                                            ValueMapT &BBMap) {
+  if (!TraceStmts)
+    return;
+
+  Scop *S = Stmt.getParent();
+  const char *BaseName = Stmt.getBaseName();
+
+  isl::ast_build AstBuild = Stmt.getAstBuild();
+  isl::set Domain = Stmt.getDomain();
+
+  isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain);
+  isl::map Schedule = isl::map::from_union_map(USchedule);
+  assert(Schedule.is_empty().is_false() &&
+         "The stmt must have a valid instance");
+
+  isl::multi_pw_aff ScheduleMultiPwAff =
+      isl::pw_multi_aff::from_map(Schedule.reverse());
+  isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range());
+
+  // Sequence of strings to print.
+  SmallVector<llvm::Value *, 8> Values;
+
+  // Print the name of the statement.
+  // TODO: Indent by the depth of the statement instance in the schedule tree.
+  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName));
+  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "("));
+
+  // Add the coordinate of the statement instance.
+  int DomDims = ScheduleMultiPwAff.dim(isl::dim::out);
+  for (int i = 0; i < DomDims; i += 1) {
+    if (i > 0)
+      Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ","));
+
+    isl::ast_expr IsInSet =
+        RestrictedBuild.expr_from(ScheduleMultiPwAff.get_pw_aff(i));
+    Values.push_back(ExprBuilder->create(IsInSet.copy()));
+  }
+
+  if (TraceScalars) {
+    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")"));
+    DenseSet<Instruction *> Encountered;
+
+    // Add the value of each scalar (and the result of PHIs) used in the
+    // statement.
+    // TODO: Values used in region-statements.
+    for (Instruction *Inst : Stmt.insts()) {
+      if (!RuntimeDebugBuilder::isPrintable(Inst->getType()))
+        continue;
+
+      if (isa<PHINode>(Inst)) {
+        Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " "));
+        Values.push_back(RuntimeDebugBuilder::getPrintableString(
+            Builder, getInstName(Inst)));
+        Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "="));
+        Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS,
+                                     LI.getLoopFor(Inst->getParent())));
+      } else {
+        for (Value *Op : Inst->operand_values()) {
+          // Do not print values that cannot change during the execution of the
+          // SCoP.
+          auto *OpInst = dyn_cast<Instruction>(Op);
+          if (!OpInst)
+            continue;
+          if (!S->contains(OpInst))
+            continue;
+
+          // Print each scalar at most once, and exclude values defined in the
+          // statement itself.
+          if (Encountered.count(OpInst))
+            continue;
+
+          Values.push_back(
+              RuntimeDebugBuilder::getPrintableString(Builder, " "));
+          Values.push_back(RuntimeDebugBuilder::getPrintableString(
+              Builder, getInstName(OpInst)));
+          Values.push_back(
+              RuntimeDebugBuilder::getPrintableString(Builder, "="));
+          Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS,
+                                       LI.getLoopFor(Inst->getParent())));
+          Encountered.insert(OpInst);
+        }
+      }
+
+      Encountered.insert(Inst);
+    }
+
+    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n"));
+  } else {
+    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n"));
+  }
+
+  RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values));
+}
+
 void BlockGenerator::generateScalarStores(
     ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
     __isl_keep isl_id_to_ast_expr *NewAccesses) {
   Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 
   assert(Stmt.isBlockStmt() &&
          "Region statements need to use the generateScalarStores() function in "
          "the RegionGenerator");
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                        &*Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(&EntryBBCopy->front());
 
   ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
   generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
+  generateBeginStmtTrace(Stmt, LTS, EntryBBMap);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI)) {
       StartBlockMap[*PI] = EntryBBCopy;
       EndBlockMap[*PI] = EntryBBCopy;
     }
 
   // Iterate over all blocks in the region in a breadth-first search.

polly/trunk/lib/CodeGen/RuntimeDebugBuilder.cpp

 void RuntimeDebugBuilder::createPrinter(PollyIRBuilder &Builder, bool IsGPU,
                                         ArrayRef<Value *> Values) {
   if (IsGPU)
     createGPUPrinterT(Builder, Values);
   else
     createCPUPrinterT(Builder, Values);
 }
 
+bool RuntimeDebugBuilder::isPrintable(Type *Ty) {
+  if (Ty->isFloatingPointTy())
+    return true;
+
+  if (Ty->isIntegerTy())
+    return Ty->getIntegerBitWidth() <= 64;
+
+  if (isa<PointerType>(Ty))
+    return true;
+
+  return false;
+}
+
 static std::tuple<std::string, std::vector<Value *>>
 prepareValuesForPrinting(PollyIRBuilder &Builder, ArrayRef<Value *> Values) {
   std::string FormatString;
   std::vector<Value *> ValuesToPrint;
 
   for (auto Val : Values) {
     Type *Ty = Val->getType();
 

polly/trunk/test/Isl/CodeGen/RuntimeDebugBuilder/stmt_tracing.ll

+; RUN: opt %loadPolly -polly-codegen-trace-stmts -polly-codegen-trace-scalars -polly-codegen -S < %s | FileCheck %s
+;
+
+define void @func(i32 %n, double* %A) {
+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:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double 0.0, double* %A_idx
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: @0 = private unnamed_addr addrspace(4) constant [10 x i8] c"Stmt_body\00"
+; CHECK: @1 = private unnamed_addr addrspace(4) constant [2 x i8] c"(\00"
+; CHECK: @2 = private unnamed_addr addrspace(4) constant [2 x i8] c")\00"
+; CHECK: @3 = private unnamed_addr addrspace(4) constant [2 x i8] c"\0A\00"
+; CHECK: @4 = private unnamed_addr constant [12 x i8] c"%s%s%ld%s%s\00"
+
+; CHECK:      polly.stmt.body:
+; CHECK:        call i32 (...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @4, i32 0, i32 0), i8 addrspace(4)* getelementptr inbounds ([10 x i8], [10 x i8] addrspace(4)* @0, i32 0, i32 0), i8 addrspace(4)* getelementptr inbounds ([2 x i8], [2 x i8] addrspace(4)* @1, i32 0, i32 0), i64 %polly.indvar, i8 addrspace(4)* getelementptr inbounds ([2 x i8], [2 x i8] addrspace(4)* @2, i32 0, i32 0), i8 addrspace(4)* getelementptr inbounds ([2 x i8], [2 x i8] addrspace(4)* @3, i32 0, i32 0))
+; CHECK-NEXT:   call i32 @fflush(i8* null)