[Polly] Add regression tests for DeLICM reject cases.

[Meinersbur]

Summary

These tests were not included in the main DeLICM commit. These check the cases where zone analysis cannot be successful because of assumption violations.

This uses the LLVM optimization remark infrastructure as it seems to be the best fit for this kind of messages.

Some more tests for why individual writes cannot be used as mapping target will follow.

[grosser]

Wonderful!

include/polly/Support/GICHelper.h

 // Helper functions for isl objects.
 //
 //===----------------------------------------------------------------------===//
 //
 #ifndef POLLY_SUPPORT_GIC_HELPER_H
 #define POLLY_SUPPORT_GIC_HELPER_H
 
 #include "llvm/ADT/APInt.h"
+#include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/Support/raw_ostream.h"
 #include "isl/aff.h"
 #include "isl/ctx.h"
 #include "isl/map.h"
 #include "isl/options.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
 #include "isl/union_set.h"

 }
 
 template <typename T>
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const IslPtr<T> &Obj) {
   OS << IslObjTraits<T>::to_str(Obj.keep());
   return OS;
 }
 
+template <typename T>
+llvm::DiagnosticInfoOptimizationBase &
+operator<<(llvm::DiagnosticInfoOptimizationBase &OS, const IslPtr<T> &Obj) {
+  OS << IslObjTraits<T>::to_str(Obj.keep());
+  return OS;
+}
+
 /// Smart pointer to an ISL object, but does not release it when destroyed.
 ///
 /// This is meant to be used as function parameter type. The caller guarantees
 /// that the reference is alive during the function's execution and hence
 /// doesn't need to add a reference. Therefore, it is equivalent to the
 /// __isl_keep annotation (IslPtr being equivalent to __isl_take which can be
 /// either copied or moved).
 ///

lib/Transform/DeLICM.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/DeLICM.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/ISLTools.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #define DEBUG_TYPE "polly-delicm"
 
 using namespace polly;
 using namespace llvm;
 
 namespace {
 
 cl::opt<int>
if (isl_union_set_is_disjoint(Existing.Written.keep(),
       }
       return true;
     }
 
     return false;
   }
 };
 
+std::string printIntruction(Instruction *Instr,
+                                   bool IsForDebug = false) {
+  std::string Result;
+  raw_string_ostream OS(Result);
+  Instr->print(OS, IsForDebug);
+  OS.flush();
+  size_t i = 0;
+  while (i < Result.size() && Result[i] == ' ')
+    i += 1;
+  return Result.substr(i);
+}
+
 /// Base class for algorithms based on zones, like DeLICM.
 class ZoneAlgorithm {
 protected:
   /// Hold a reference to the isl_ctx to avoid it being freed before we released
   /// all of the isl objects.
   ///
   /// This must be declared before any other member that holds an isl object.
   /// This guarantees that the shared_ptr and its isl_ctx is destructed last,
protected:
   /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
   /// { DomainMayWrite[] -> Element[] }
   IslPtr<isl_union_map> AllMayWrites;
 
   /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
   /// { DomainMustWrite[] -> Element[] }
   IslPtr<isl_union_map> AllMustWrites;
 
+  /// Used to emit optimization diagnostics (rejected scops, mapped scalars,
+  /// etc.)
+  OptimizationRemarkEmitter *ORE;
+
   /// Prepare the object before computing the zones of @p S.
-  ZoneAlgorithm(Scop *S)
-      : IslCtx(S->getSharedIslCtx()), S(S), Schedule(give(S->getSchedule())) {
+  ZoneAlgorithm(Scop *S, OptimizationRemarkEmitter *ORE)
+      : IslCtx(S->getSharedIslCtx()), S(S), Schedule(give(S->getSchedule())),
+        ORE(ORE) {
 
     auto Domains = give(S->getDomains());
 
     Schedule =
         give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
     ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
     ScatterSpace = getScatterSpace(Schedule);
   }
for (auto *MA : *Stmt) {
       if (!MA->isLatestArrayKind())
         continue;
 
       auto AccRel =
           give(isl_union_map_from_map(getAccessRelationFor(MA).take()));
 
       if (MA->isRead()) {
         // Reject store after load to same location.
-        if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep()))
+        if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())) {
+          OptimizationRemarkMissed R(DEBUG_TYPE, "LoadAfterStore",
+                                     MA->getAccessInstruction());
+          R << "load after store of same element in same statement";
+          R << " (previous stores: " << Stores;
+          R << ", loading: " << AccRel << ")";
+          ORE->emit(R);
           return false;
+        }
 
         Loads = give(isl_union_map_union(Loads.take(), AccRel.take()));
 
         continue;
       }
 
       if (!isa<StoreInst>(MA->getAccessInstruction())) {
         DEBUG(dbgs() << "WRITE that is not a StoreInst not supported\n");
+        OptimizationRemarkMissed R(DEBUG_TYPE, "UnusualStore",
+                                   MA->getAccessInstruction());
+        R << "encountered write that is not a StoreInst: "
+          << printIntruction(MA->getAccessInstruction());
+        ORE->emit(R);
         return false;
       }
 
       // In region statements the order is less clear, eg. the load and store
       // might be in a boxed loop.
       if (Stmt->isRegionStmt() &&
-          !isl_union_map_is_disjoint(Loads.keep(), AccRel.keep()))
+          !isl_union_map_is_disjoint(Loads.keep(), AccRel.keep())) {
+        OptimizationRemarkMissed R(DEBUG_TYPE, "StoreInSubregion",
+                                   MA->getAccessInstruction());
+        R << "store is in a non-affine subregion";
+        ORE->emit(R);
         return false;
+      }
 
       // Do not allow more than one store to the same location.
-      if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep()))
+      if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())) {
+        OptimizationRemarkMissed R(DEBUG_TYPE, "StoreAfterStore",
+                                   MA->getAccessInstruction());
+        R << "store after store of same element in same statement";
+        R << " (previous stores: " << Stores;
+        R << ", storing: " << AccRel << ")";
+        ORE->emit(R);
         return false;
+      }
 
       Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
     }
 
     return true;
   }
 
   void addArrayReadAccess(MemoryAccess *MA) {
private:
   ///         different elements are accessed.
   bool isScalarAccess(MemoryAccess *MA) {
     auto Map = getAccessRelationFor(MA);
     auto Set = give(isl_map_range(Map.take()));
     return isl_set_is_singleton(Set.keep()) == isl_bool_true;
   }
 
 public:
-  DeLICMImpl(Scop *S) : ZoneAlgorithm(S) {}
+  DeLICMImpl(Scop *S, OptimizationRemarkEmitter *ORE) : ZoneAlgorithm(S, ORE) {}
 
   /// Calculate the lifetime (definition to last use) of every array element.
   ///
   /// @return True if the computed lifetimes (#Zone) is usable.
   bool computeZone() {
     // Check that nothing strange occurs.
     if (!isCompatibleScop()) {
       DeLICMIncompatible++;
IslPtr<isl_union_set> EltUnused, EltWritten;
 
       EltUnused = computeLifetime();
       EltWritten = computeWritten();
     }
 
     if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {
       DeLICMOutOfQuota++;
       DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
+      DebugLoc Begin, End;
+      getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End);
+      OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
+                                   S->getEntry());
+      R << "maximal number of operations exceeded during zone analysis";
+      ORE->emit(R);
     }
 
     DeLICMAnalyzed++;
     OriginalZone = Knowledge(nullptr, EltUnused, EltWritten);
     DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
 
     Zone = OriginalZone;
 

 private:
   DeLICM(const DeLICM &) = delete;
   const DeLICM &operator=(const DeLICM &) = delete;
 
   /// The pass implementation, also holding per-scop data.
   std::unique_ptr<DeLICMImpl> Impl;
 
   void collapseToUnused(Scop &S) {
-    Impl = make_unique<DeLICMImpl>(&S);
+    Impl = make_unique<DeLICMImpl>(
+        &S, &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
 
     if (!Impl->computeZone()) {
       DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
       return;
     }
 
     DEBUG(dbgs() << "Collapsing scalars to unused array elements...\n");
     Impl->greedyCollapse();
 
     DEBUG(dbgs() << "\nFinal Scop:\n");
     DEBUG(S.print(dbgs()));
   }
 
 public:
   static char ID;
   explicit DeLICM() : ScopPass(ID) {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
     AU.setPreservesAll();
   }
 
   virtual bool runOnScop(Scop &S) override {
     // Free resources for previous scop's computation, if not yet done.
     releaseMemory();
 
     collapseToUnused(S);

test/DeLICM/reject_loadafterstore.ll

+; RUN: opt %loadPolly -polly-delicm -analyze -pass-remarks-missed=polly-delicm < %s 2>&1 | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      %dummy = load double, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: load after store of same element in same statement

test/DeLICM/reject_outofquota.ll

+; RUN: opt %loadPolly -polly-delicm -analyze -pass-remarks-analysis=polly-delicm -polly-delicm-max-ops=1 < %s 2>&1 | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: maximal number of operations exceeded during zone analysis

test/DeLICM/reject_storeafterstore.ll

+; RUN: opt %loadPolly -polly-delicm -analyze -pass-remarks-missed=polly-delicm < %s 2>&1 | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double 0.0, double* %A_idx
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: store after store of same element in same statement

test/DeLICM/reject_storeinsubregion.ll

+; RUN: opt %loadPolly -polly-delicm -analyze -pass-remarks-missed=polly-delicm < %s 2>&1 | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          %A_idxp = getelementptr inbounds double, double* %A, i32 %j
+          %add.cmp = fcmp ogt double %add, 42.0
+          br i1 %add.cmp , label %body_true, label %body_false
+
+        body_true:
+          %dummy = load double, double* %A_idxp
+          br label %reduction.inc
+
+        body_false:
+          store double 0.0, double* %A_idxp
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: store is in a non-affine subregion

test/DeLICM/reject_unusualstore.ll

+; RUN: opt %loadPolly -polly-delicm -analyze -pass-remarks-missed=polly-delicm < %s 2>&1 | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
+
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      %tmp = bitcast double* %A_idx to i8*
+      call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 8, i32 1, i1 false)
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      store double %phi, double* %A_idx
+      %dummy = load double, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: encountered write that is not a StoreInst: call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 8, i32 1, i1 false)