[Polly] Remove Analysis Output of TempScopInfo

[Meinersbur]

Summary

After the merge of TempScopInfo into ScopInfo the analysis output remained because of the existing unit tests. These remains are removed and the units tests converted to match the equivalent output of ScopInfo's analysis output. The unit tests are also moved into the the directory of ScopInfo tests.

[grosser]

LGTM

polly/trunk/include/polly/ScopInfo.h

private:
   /// @brief The value associated with this memory access.
   ///
   ///  - For real memory accesses it is the loaded result or the stored value.
   ///  - For straight line scalar accesses it is the access instruction itself.
   ///  - For PHI operand accesses it is the operand value.
   ///
   Value *AccessValue;
 
-  /// @brief Accessed element relative to the base pointer (in bytes).
-  ///
-  /// Currently only used by printIR.
-  const SCEV *Offset;
-
   /// @brief Are all the subscripts affine expression?
   bool IsAffine;
 
   /// @brief Subscript expression for each dimension.
   SmallVector<const SCEV *, 4> Subscripts;
 
   /// @brief Relation from statment instances to the accessed array elements.
   isl_map *AccessRelation;
 
   /// @brief Updated access relation read from JSCOP file.
   isl_map *NewAccessRelation;
   // @}
 
   unsigned getElemSizeInBytes() const { return ElemBytes; }
 
   bool isAffine() const { return IsAffine; }
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return IsPHI; }
 
-  void printIR(raw_ostream &OS) const;
-
   void setStatement(ScopStmt *Stmt) { this->Statement = Stmt; }
 
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
   void assumeNoOutOfBound();
 
   /// @brief Compute bounds on an over approximated  access relation.
   ///

 
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param AccessInst The instruction doing the access.
   /// @param Id         Identifier that is guranteed to be unique within the
   ///                   same ScopStmt.
   /// @param BaseAddr   The accessed array's address.
-  /// @param Offset     Accessed memoray location relative to @p BaseAddr.
   /// @param ElemBytes  Number of accessed bytes.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param IsPHI      Are we modeling special PHI node accesses?
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type,
-               Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes,
-               bool Affine, ArrayRef<const SCEV *> Subscripts,
-               ArrayRef<const SCEV *> Sizes, Value *AccessValue, bool IsPHI,
-               StringRef BaseName);
+               Value *BaseAddress, unsigned ElemBytes, bool Affine,
+               ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
+               Value *AccessValue, bool IsPHI, StringRef BaseName);
   ~MemoryAccess();
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
 
public:
   /// @return All access functions in BB
   ///
   AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
     AccFuncMapType::iterator at = AccFuncMap.find(BB);
     return at != AccFuncMap.end() ? &(at->second) : 0;
   }
   //@}
 
-  /// @brief Print data access information.
-  ///
-  /// @param OS The output stream the access functions is printed to.
-  /// @param SE The ScalarEvolution to help printing more details.
-  /// @param LI The LoopInfo that help printing the access functions.
-  void printIRAccesses(raw_ostream &OS, ScalarEvolution *SE,
-                       LoopInfo *LI) const;
-
-  /// @brief Print the access functions and loop bounds in this Scop.
-  ///
-  /// @param OS The output stream the access functions is printed to.
-  /// @param SE The ScalarEvolution that help printing the access functions.
-  /// @param LI The LoopInfo that help printing the access functions.
-  void printIRAccessesDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI,
-                             const Region *Reg, unsigned ind) const;
-
   ScalarEvolution *getSE() const;
 
   /// @brief Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   inline ParamVecType::size_type getNumParams() const {
     return Parameters.size();
   }
class ScopInfo : public RegionPass {
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
-  /// @param Offset      Accessed location relative to @p BaseAddress.
   /// @param ElemBytes   Size of accessed array element.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array diminsion's sizes.
   /// @param IsPHI       Whether this is an emulated PHI node.
   void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                        MemoryAccess::AccessType Type, Value *BaseAddress,
-                       const SCEV *Offset, unsigned ElemBytes, bool Affine,
-                       Value *AccessValue, ArrayRef<const SCEV *> Subscripts,
+                       unsigned ElemBytes, bool Affine, Value *AccessValue,
+                       ArrayRef<const SCEV *> Subscripts,
                        ArrayRef<const SCEV *> Sizes, bool IsPHI);
 
   void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                        MemoryAccess::AccessType Type, Value *BaseAddress,
-                       const SCEV *Offset, unsigned ElemBytes, bool Affine,
-                       Value *AccessValue, bool IsPHI = false) {
-    addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine,
-                    AccessValue, ArrayRef<const SCEV *>(),
-                    ArrayRef<const SCEV *>(), IsPHI);
+                       unsigned ElemBytes, bool Affine, Value *AccessValue,
+                       bool IsPHI = false) {
+    addMemoryAccess(BB, Inst, Type, BaseAddress, ElemBytes, Affine, AccessValue,
+                    ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), IsPHI);
   }
 
   void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                        MemoryAccess::AccessType Type, Value *BaseAddress,
-                       const SCEV *Offset, unsigned ElemBytes, bool Affine,
+                       unsigned ElemBytes, bool Affine,
                        ArrayRef<const SCEV *> Subscripts,
                        ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
-    addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine,
-                    AccessValue, Subscripts, Sizes, false);
+    addMemoryAccess(BB, Inst, Type, BaseAddress, ElemBytes, Affine, AccessValue,
+                    Subscripts, Sizes, false);
   }
 
 public:
   static char ID;
   explicit ScopInfo();
   ~ScopInfo();
 
   /// @brief Try to build the Polly IR of static control part on the current

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) {
   void *User = isl_id_get_user(Id);
   const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
   isl_id_free(Id);
   return SAI;
 }
 
-void MemoryAccess::printIR(raw_ostream &OS) const {
-  if (isRead())
-    OS << "Read ";
-  else {
-    if (isMayWrite())
-      OS << "May";
-    OS << "Write ";
-  }
-  OS << BaseAddr->getName() << '[' << *Offset << "]\n";
-}
-
 const std::string
 MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
   switch (RT) {
   case MemoryAccess::RT_NONE:
     llvm_unreachable("Requested a reduction operator string for a memory "
                      "access which isn't a reduction");
   case MemoryAccess::RT_ADD:
     return "+";
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
 
   assumeNoOutOfBound();
   AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
   isl_space_free(Space);
 }
 
 MemoryAccess::MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id,
                            AccessType Type, Value *BaseAddress,
-                           const SCEV *Offset, unsigned ElemBytes, bool Affine,
+                           unsigned ElemBytes, bool Affine,
                            ArrayRef<const SCEV *> Subscripts,
                            ArrayRef<const SCEV *> Sizes, Value *AccessValue,
                            bool IsPHI, StringRef BaseName)
     : Id(Id), IsPHI(IsPHI), AccType(Type), RedType(RT_NONE), Statement(nullptr),
       BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
       Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
-      AccessValue(AccessValue), Offset(Offset), IsAffine(Affine),
+      AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {}
 
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
   AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
 }
 

 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   return StmtMapIt->second;
 }
 
-void Scop::printIRAccesses(raw_ostream &OS, ScalarEvolution *SE,
-                           LoopInfo *LI) const {
-  OS << "Scop: " << R.getNameStr() << "\n";
-
-  printIRAccessesDetail(OS, SE, LI, &R, 0);
-}
-
-void Scop::printIRAccessesDetail(raw_ostream &OS, ScalarEvolution *SE,
-                                 LoopInfo *LI, const Region *CurR,
-                                 unsigned ind) const {
-  // FIXME: Print other details rather than memory accesses.
-  for (const auto &CurBlock : CurR->blocks()) {
-    AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock);
-
-    // Ignore trivial blocks that do not contain any memory access.
-    if (AccSetIt == AccFuncMap.end())
-      continue;
-
-    OS.indent(ind) << "BB: " << CurBlock->getName() << '\n';
-    typedef AccFuncSetType::const_iterator access_iterator;
-    const AccFuncSetType &AccFuncs = AccSetIt->second;
-
-    for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
-         ++AI)
-      AI->printIR(OS.indent(ind + 2));
-  }
-}
-
 int Scop::getRelativeLoopDepth(const Loop *L) const {
   Loop *OuterLoop =
       L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
   if (!OuterLoop)
     return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
 
     Instruction *OpI = dyn_cast<Instruction>(Op);
     if (OpI) {
       BasicBlock *OpIBB = OpI->getParent();
       // As we pretend there is a use (or more precise a write) of OpI in OpBB
       // we have to insert a scalar dependence from the definition of OpI to
       // OpBB if the definition is not in OpBB.
       if (OpIBB != OpBB) {
-        addMemoryAccess(OpBB, PHI, MemoryAccess::READ, OpI, ZeroOffset, 1, true,
+        addMemoryAccess(OpBB, PHI, MemoryAccess::READ, OpI, 1, true, OpI);
+        addMemoryAccess(OpIBB, OpI, MemoryAccess::MUST_WRITE, OpI, 1, true,
                         OpI);
-        addMemoryAccess(OpIBB, OpI, MemoryAccess::MUST_WRITE, OpI, ZeroOffset,
-                        1, true, OpI);
       }
     }
 
     // Always use the terminator of the incoming basic block as the access
     // instruction.
     OpI = OpBB->getTerminator();
 
-    addMemoryAccess(OpBB, OpI, MemoryAccess::MUST_WRITE, PHI, ZeroOffset, 1,
-                    true, Op, /* IsPHI */ !IsExitBlock);
+    addMemoryAccess(OpBB, OpI, MemoryAccess::MUST_WRITE, PHI, 1, true, Op,
+                    /* IsPHI */ !IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands) {
-    addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, ZeroOffset,
-                    1, true, PHI,
+    addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true,
+                    PHI,
                     /* IsPHI */ !IsExitBlock);
   }
 }
 
 bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
                                       Region *NonAffineSubRegion) {
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
   if (isIgnoredIntrinsic(Inst))
if (isa<PHINode>(UI))
       continue;
 
     // Now U is used in another statement.
     AnyCrossStmtUse = true;
 
     // Do not build a read access that is not in the current SCoP
     // Use the def instruction as base address of the MemoryAccess, so that it
     // will become the name of the scalar access in the polyhedral form.
-    addMemoryAccess(UseParent, UI, MemoryAccess::READ, Inst, ZeroOffset, 1,
-                    true, Inst);
+    addMemoryAccess(UseParent, UI, MemoryAccess::READ, Inst, 1, true, Inst);
   }
 
   if (ModelReadOnlyScalars) {
     for (Value *Op : Inst->operands()) {
       if (canSynthesize(Op, LI, SE, R))
         continue;
 
       if (Instruction *OpInst = dyn_cast<Instruction>(Op))
         if (R->contains(OpInst))
           continue;
 
       if (isa<Constant>(Op))
         continue;
 
-      addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::READ, Op,
-                      ZeroOffset, 1, true, Op);
+      addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::READ, Op, 1, true,
+                      Op);
     }
   }
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
       if (AllAffineSubcripts && Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
         SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
             IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
 
         addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(),
-                        AccessFunction, Size, true, Subscripts, SizesSCEV, Val);
+                        Size, true, Subscripts, SizesSCEV, Val);
         return;
       }
     }
   }
 
   auto AccItr = InsnToMemAcc.find(Inst);
   if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
     addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(),
-                    AccessFunction, Size, true,
-                    AccItr->second.DelinearizedSubscripts,
+                    Size, true, AccItr->second.DelinearizedSubscripts,
                     AccItr->second.Shape->DelinearizedSizes, Val);
     return;
   }
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
   if (BoxedLoops) {
     SetVector<const Loop *> Loops;
     findLoops(AccessFunction, Loops);
     for (const Loop *L : Loops)
       if (BoxedLoops->count(L))
         isVariantInNonAffineLoop = true;
   }
 
   bool IsAffine = !isVariantInNonAffineLoop &&
                   isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());
 
   SmallVector<const SCEV *, 4> Subscripts, Sizes;
   Subscripts.push_back(AccessFunction);
   Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));
 
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(),
-                  AccessFunction, Size, IsAffine, Subscripts, Sizes, Val);
+  addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), Size,
+                  IsAffine, Subscripts, Sizes, Val);
 }
 
 void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     for (BasicBlock *BB : SR.blocks())
       buildAccessFunctions(R, *BB, &SR);
     return;
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       buildMemoryAccess(Inst, L, &R, BoxedLoops);
 
     if (isIgnoredIntrinsic(Inst))
       continue;
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
-        addMemoryAccess(&BB, Inst, MemoryAccess::MUST_WRITE, Inst, ZeroOffset,
-                        1, true, Inst);
+        addMemoryAccess(&BB, Inst, MemoryAccess::MUST_WRITE, Inst, 1, true,
+                        Inst);
     }
   }
 }
 
-void ScopInfo::addMemoryAccess(
-    BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type,
-    Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes, bool Affine,
-    Value *AccessValue, ArrayRef<const SCEV *> Subscripts,
-    ArrayRef<const SCEV *> Sizes, bool IsPHI = false) {
+void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+                               MemoryAccess::AccessType Type,
+                               Value *BaseAddress, unsigned ElemBytes,
+                               bool Affine, Value *AccessValue,
+                               ArrayRef<const SCEV *> Subscripts,
+                               ArrayRef<const SCEV *> Sizes,
+                               bool IsPHI = false) {
   AccFuncSetType &AccList = AccFuncMap[BB];
   size_t Identifier = AccList.size();
 
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   std::string IdName = "__polly_array_ref_" + std::to_string(Identifier);
   isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr);
 
-  AccList.emplace_back(Inst, Id, Type, BaseAddress, Offset, ElemBytes, Affine,
+  AccList.emplace_back(Inst, Id, Type, BaseAddress, ElemBytes, Affine,
                        Subscripts, Sizes, AccessValue, IsPHI, BaseName);
 }
 
 Scop *ScopInfo::buildScop(Region &R, DominatorTree &DT) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   Scop *S = new Scop(R, AccFuncMap, *SE, DT, ctx, MaxLoopDepth);
 
   buildAccessFunctions(R, R);

 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }
 
-  scop->printIRAccesses(OS, SE, LI);
   scop->print(OS);
 }
 
 void ScopInfo::clear() {
   AccFuncMap.clear();
   if (scop) {
     delete scop;
     scop = 0;

polly/trunk/test/ScopInfo/cond_in_loop.ll

bb3:                                              ; preds = %bb2, %bb1
   %exitcond = icmp eq i64 %3, %M                  ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb3, %entry
   ret void
 }
 
 ; CHECK-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'bb => return' in function 'f':
-; CHECK-NEXT:  Scop: bb => return
+; CHECK-NEXT:      Function: f
+; CHECK-NEXT:      Region: %bb---%return

polly/trunk/test/ScopInfo/inter_bb_scalar_dep.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s
+
+; void f(long A[], int N, int *init_ptr) {
+;   long i, j;
+;
+;   for (i = 0; i < N; ++i) {
+;     init = *init_ptr;
+;     for (i = 0; i < N; ++i) {
+;       A[i] = init + 2;
+;     }
+;   }
+; }
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+; Function Attrs: nounwind
+define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 {
+entry:
+  br label %for.i
+
+for.i:                                            ; preds = %for.i.end, %entry
+  %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
+  %indvar.i.next = add nsw i64 %indvar.i, 1
+  br label %entry.next
+
+entry.next:                                       ; preds = %for.i
+  %init = load i64, i64* %init_ptr
+; CHECK-LABEL: Stmt_entry_next
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] };
+; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          [N] -> { Stmt_entry_next[i0] -> MemRef_init[] };
+  br label %for.j
+
+for.j:                                            ; preds = %for.j, %entry.next
+  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
+  %init_plus_two = add i64 %init, 2
+; CHECK-LABEL: Stmt_for_j
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
+; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
+  store i64 %init_plus_two, i64* %scevgep
+  %indvar.j.next = add nsw i64 %indvar.j, 1
+  %exitcond.j = icmp eq i64 %indvar.j.next, %N
+  br i1 %exitcond.j, label %for.i.end, label %for.j
+
+for.i.end:                                        ; preds = %for.j
+  %exitcond.i = icmp eq i64 %indvar.i.next, %N
+  br i1 %exitcond.i, label %return, label %for.i
+
+return:                                           ; preds = %for.i.end
+  ret void
+}
+
+attributes #0 = { nounwind }

polly/trunk/test/ScopInfo/intra_and_inter_bb_scalar_dep.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s
+
+; void f(long A[], int N, int *init_ptr) {
+;   long i, j;
+;
+;   for (i = 0; i < N; ++i) {
+;     init = *init_ptr;
+;     for (i = 0; i < N; ++i) {
+;       init2 = *init_ptr;
+;       A[i] = init + init2;
+;     }
+;   }
+; }
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+; Function Attrs: nounwind
+define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 {
+entry:
+  br label %for.i
+
+for.i:                                            ; preds = %for.i.end, %entry
+  %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
+  %indvar.i.next = add nsw i64 %indvar.i, 1
+  br label %entry.next
+
+entry.next:                                       ; preds = %for.i
+  %init = load i64, i64* %init_ptr
+; CHECK-LABEL: Stmt_entry_next
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] };
+; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          [N] -> { Stmt_entry_next[i0] -> MemRef_init[] };
+  br label %for.j
+
+for.j:                                            ; preds = %for.j, %entry.next
+  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
+  %init_2 = load i64, i64* %init_ptr
+  %init_sum = add i64 %init, %init_2
+; CHECK-LABEL: Stmt_for_j
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_init_ptr[0] };
+; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
+  store i64 %init_sum, i64* %scevgep
+  %indvar.j.next = add nsw i64 %indvar.j, 1
+  %exitcond.j = icmp eq i64 %indvar.j.next, %N
+  br i1 %exitcond.j, label %for.i.end, label %for.j
+
+for.i.end:                                        ; preds = %for.j
+  %exitcond.i = icmp eq i64 %indvar.i.next, %N
+  br i1 %exitcond.i, label %return, label %for.i
+
+return:                                           ; preds = %for.i.end
+  ret void
+}
+
+attributes #0 = { nounwind }

polly/trunk/test/ScopInfo/intra_bb_scalar_dep.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s
+
+; void f(long A[], int N, int *init_ptr) {
+;   long i, j;
+;
+;   for (i = 0; i < N; ++i) {
+;     for (i = 0; i < N; ++i) {
+;       init = *init_ptr;
+;       A[i] = init + 2;
+;     }
+;   }
+; }
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+; Function Attrs: nounwind
+define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 {
+entry:
+  br label %for.i
+
+for.i:                                            ; preds = %for.i.end, %entry
+  %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
+  %indvar.i.next = add nsw i64 %indvar.i, 1
+  br label %entry.next
+
+entry.next:                                       ; preds = %for.i
+  br label %for.j
+
+for.j:                                            ; preds = %for.j, %entry.next
+  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
+  %init = load i64, i64* %init_ptr
+  %init_plus_two = add i64 %init, 2
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
+  store i64 %init_plus_two, i64* %scevgep
+; CHECK-LABEL: Stmt_for_j
+; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_init_ptr[0] };
+; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+  %indvar.j.next = add nsw i64 %indvar.j, 1
+  %exitcond.j = icmp eq i64 %indvar.j.next, %N
+  br i1 %exitcond.j, label %for.i.end, label %for.j
+
+for.i.end:                                        ; preds = %for.j
+  %exitcond.i = icmp eq i64 %indvar.i.next, %N
+  br i1 %exitcond.i, label %return, label %for.i
+
+return:                                           ; preds = %for.i.end
+  ret void
+}
+
+attributes #0 = { nounwind }

polly/trunk/test/ScopInfo/nested-loops.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+define void @f(i64* nocapture %a) nounwind {
+entry:
+  br label %for.i
+
+for.i:
+  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.j ]
+  %i.inc = add nsw i64 %i, 1
+  %exitcond.i = icmp sge i64 %i.inc, 2048
+  br i1 %exitcond.i, label %return, label %for.j
+
+for.j:
+  %j = phi i64 [ 0, %for.i ], [ %j.inc, %body ]
+  %j.inc = add nsw i64 %j, 1
+  %exitcond.j = icmp slt i64 %j.inc, 1024
+  br i1 %exitcond.j, label %body, label %for.i
+
+body:
+  %scevgep = getelementptr i64, i64* %a, i64 %j
+  store i64 %j, i64* %scevgep
+  br label %for.j
+
+return:
+  ret void
+}
+
+; CHECK: body
+; CHECK:        Domain :=
+; CHECK:           { Stmt_body[i0, i1] :
+; CHECK-DAG:         i0 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:         i0 <= 2046
+; CHECK-DAG:       and
+; CHECK-DAG:         i1 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:         i1 <= 1022
+; CHECK:           }

polly/trunk/test/ScopInfo/not-a-reduction.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s 2>&1 | not FileCheck %s
+
+;#define TYPE float
+;#define NUM 4
+;
+;TYPE A[NUM];
+;TYPE B[NUM];
+;TYPE C[NUM];
+;
+;void vector_multiply(void) {
+; int i;
+; for (i = 0; i < NUM; i++) {
+;   A[i] = B[i] * C[i];
+; }
+;}
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+@B = common global [4 x float] zeroinitializer, align 16
+@C = common global [4 x float] zeroinitializer, align 16
+@A = common global [4 x float] zeroinitializer, align 16
+
+define void @vector_multiply() nounwind {
+bb:
+  br label %bb3
+
+bb3:                                              ; preds = %bb7, %bb
+  %indvar = phi i64 [ %indvar.next, %bb7 ], [ 0, %bb ]
+  %scevgep = getelementptr [4 x float], [4 x float]* @A, i64 0, i64 %indvar
+  %scevgep1 = getelementptr [4 x float], [4 x float]* @C, i64 0, i64 %indvar
+  %scevgep2 = getelementptr [4 x float], [4 x float]* @B, i64 0, i64 %indvar
+  %exitcond = icmp ne i64 %indvar, 4
+  br i1 %exitcond, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb3
+  %tmp = load float, float* %scevgep2, align 4
+  %tmp5 = load float, float* %scevgep1, align 4
+  %tmp6 = fmul float %tmp, %tmp5
+  store float %tmp6, float* %scevgep, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvar.next = add i64 %indvar, 1
+  br label %bb3
+
+bb8:                                              ; preds = %bb3
+  ret void
+}
+
+; Match any reduction type except "[Reduction Type: NONE]"
+; CHECK:     [Reduction Type: {{[^N].*}}]

polly/trunk/test/ScopInfo/scalar_to_array.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s
+
+; ModuleID = 'scalar_to_array.ll'
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+@A = common global [1024 x float] zeroinitializer, align 8
+
+; Terminating loops without side-effects will be optimzied away, hence
+; detecting a scop would be pointless.
+; CHECK-NOT: Function: empty
+; Function Attrs: nounwind
+define i32 @empty() #0 {
+entry:
+  fence seq_cst
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvar, 1024
+  br i1 %exitcond, label %for.body, label %return
+
+for.body:                                         ; preds = %for.cond
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvar.next = add i64 %indvar, 1
+  br label %for.cond
+
+return:                                           ; preds = %for.cond
+  fence seq_cst
+  ret i32 0
+}
+
+; CHECK-LABEL: Function: array_access
+; Function Attrs: nounwind
+define i32 @array_access() #0 {
+entry:
+  fence seq_cst
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvar, 1024
+  br i1 %exitcond, label %for.body, label %return
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
+  %float = uitofp i64 %indvar to float
+  store float %float, float* %arrayidx
+  br label %for.inc
+; CHECK:     Stmt_for_body
+; CHECK-NOT:     ReadAccess
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:        { Stmt_for_body[i0] -> MemRef_A[i0] };
+
+for.inc:                                          ; preds = %for.body
+  %indvar.next = add i64 %indvar, 1
+  br label %for.cond
+
+return:                                           ; preds = %for.cond
+  fence seq_cst
+  ret i32 0
+}
+
+; Function Attrs: nounwind
+; CHECK-LABEL: Function: intra_scop_dep
+define i32 @intra_scop_dep() #0 {
+entry:
+  fence seq_cst
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvar, 1024
+  br i1 %exitcond, label %for.body.a, label %return
+
+for.body.a:                                       ; preds = %for.cond
+  %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
+  %scalar = load float, float* %arrayidx
+  br label %for.body.b
+; CHECK:      Stmt_for_body_a
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         { Stmt_for_body_a[i0] -> MemRef_A[i0] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         { Stmt_for_body_a[i0] -> MemRef_scalar[] };
+
+for.body.b:                                       ; preds = %for.body.a
+  %arrayidx2 = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
+  %float = uitofp i64 %indvar to float
+  %sum = fadd float %scalar, %float
+  store float %sum, float* %arrayidx2
+  br label %for.inc
+; CHECK:      Stmt_for_body_b
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          { Stmt_for_body_b[i0] -> MemRef_scalar[] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         { Stmt_for_body_b[i0] -> MemRef_A[i0] };
+
+for.inc:                                          ; preds = %for.body.b
+  %indvar.next = add i64 %indvar, 1
+  br label %for.cond
+
+return:                                           ; preds = %for.cond
+  fence seq_cst
+  ret i32 0
+}
+
+; It is not possible to have a scop which accesses a scalar element that is
+; a global variable. All global variables are pointers containing possibly
+; a single element. Hence they do not need to be handled anyways.
+; Please note that this is still required when scalar to array rewritting is
+; disabled.
+
+; CHECK-LABEL: Function: use_after_scop
+; Function Attrs: nounwind
+define i32 @use_after_scop() #0 {
+entry:
+  %scalar.s2a = alloca float
+  fence seq_cst
+  br label %for.head
+
+for.head:                                         ; preds = %for.inc, %entry
+  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
+  br label %for.body
+
+for.body:                                         ; preds = %for.head
+  %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
+  %scalar = load float, float* %arrayidx
+  store float %scalar, float* %scalar.s2a
+; Escaped uses are still required to be rewritten to stack variable.
+; CHECK:      Stmt_for_body
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         { Stmt_for_body[i0] -> MemRef_A[i0] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         { Stmt_for_body[i0] -> MemRef_scalar_s2a[0] };
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvar.next = add i64 %indvar, 1
+  %exitcond = icmp ne i64 %indvar.next, 1024
+  br i1 %exitcond, label %for.head, label %for.after
+
+for.after:                                        ; preds = %for.inc
+  %scalar.loadoutside = load float, float* %scalar.s2a
+  fence seq_cst
+  %return_value = fptosi float %scalar.loadoutside to i32
+  br label %return
+
+return:                                           ; preds = %for.after
+  ret i32 %return_value
+}
+
+; We currently do not transform scalar references, that have only read accesses
+; in the scop. There are two reasons for this:
+;
+;  o We don't introduce additional memory references which may yield to compile
+;    time overhead.
+;  o For integer values, such a translation may block the use of scalar
+;    evolution on those values.
+;
+; CHECK-LABEL: Function: before_scop
+; Function Attrs: nounwind
+define i32 @before_scop() #0 {
+entry:
+  br label %preheader
+
+preheader:                                        ; preds = %entry
+  %scalar = fadd float 4.000000e+00, 5.000000e+00
+  fence seq_cst
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %preheader
+  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %preheader ]
+  %exitcond = icmp ne i64 %indvar, 1024
+  br i1 %exitcond, label %for.body, label %return
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
+  store float %scalar, float* %arrayidx
+  br label %for.inc
+; CHECK:      Stmt_for_body
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         { Stmt_for_body[i0] -> MemRef_A[i0] };
+
+for.inc:                                          ; preds = %for.body
+  %indvar.next = add i64 %indvar, 1
+  br label %for.cond
+
+return:                                           ; preds = %for.cond
+  fence seq_cst
+  ret i32 0
+}
+
+attributes #0 = { nounwind }

polly/trunk/test/ScopInfo/tempscop-printing.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s
+
+; void f(long A[], int N, int *init_ptr) {
+;   long i, j;
+;
+;   for (i = 0; i < N; ++i) {
+;     init = *init_ptr;
+;     for (i = 0; i < N; ++i) {
+;       A[i] = init + 2;
+;     }
+;   }
+; }
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+; CHECK-LABEL: Function: f
+define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
+entry:
+  br label %for.i
+
+for.i:
+  %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
+  %indvar.i.next = add nsw i64 %indvar.i, 1
+  br label %entry.next
+
+entry.next:
+; CHECK:      Stmt_entry_next
+  %init = load i64, i64* %init_ptr
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_entry_next[i0] -> MemRef_init[] };
+  br label %for.j
+
+for.j:
+  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
+; CHECK:      Stmt_for_j
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+  %init_plus_two = add i64 %init, 2
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
+  store i64 %init_plus_two, i64* %scevgep
+  %indvar.j.next = add nsw i64 %indvar.j, 1
+  %exitcond.j = icmp eq i64 %indvar.j.next, %N
+  br i1 %exitcond.j, label %for.i.end, label %for.j
+
+for.i.end:
+  %exitcond.i = icmp eq i64 %indvar.i.next, %N
+  br i1 %exitcond.i, label %return, label %for.i
+
+return:
+  ret void
+}
+
+; CHECK-LABEL: Function: g
+define void @g(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
+entry:
+  br label %for.i
+
+for.i:
+  %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
+  %indvar.i.next = add nsw i64 %indvar.i, 1
+  br label %entry.next
+
+entry.next:
+; CHECK:      Stmt_entry_next
+  %init = load i64, i64* %init_ptr
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_entry_next[i0] -> MemRef_init[] };
+  br label %for.j
+
+for.j:
+; CHECK:      Stmt_for_j
+  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
+  store i64 %init, i64* %scevgep
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+  %indvar.j.next = add nsw i64 %indvar.j, 1
+  %exitcond.j = icmp eq i64 %indvar.j.next, %N
+  br i1 %exitcond.j, label %for.i.end, label %for.j
+
+for.i.end:
+  %exitcond.i = icmp eq i64 %indvar.i.next, %N
+  br i1 %exitcond.i, label %return, label %for.i
+
+return:
+  ret void
+}