[Polly][PoC] First (smarter) step to remove IndependentBlocks & CodeGeneration

[jdoerfert]

Summary

This is a proof of concept that we can model the SCoP and the
dependences as accurate as before even witout IndependentBlocks
and CodePreparation. It should help to start a discussion about
Polly as analyzer and make it more applicable at some point.

Changes include:
  - Remove the CodeGeneration pass and tests
  - Remove the IndependentBlocks pass and tests
  - Removed some tests only testing the passes above (not all though)
  - Modified some tests that were failing without good reason
  - Allowed PHI nodes in ScopDetection
  - Changed the SCoP creation to allow the proper handling of PHIs
  - Modelt PHI nodes precicly in the SCoP
  - Enabled -polly-codegen-scev and disabled "DisableIntraScopScalarToArray"
  - A test case for non synthesizable PHI nodes
    (test/ScopInfo/phi_scalar_simple_1.ll)

Features include:
  - Only PHI nodes needed are represented in the SCoP, PHI chains
    can therefore be reduced if they do not change the value. This
    should also "look through" trivial PHIs, similar to the old code
    prepare pass.

Missing changes:
  - The code generation will not be able to handle PHI nodes properly

Thoughts of any kind are welcome.

[jdoerfert]

I will chuck this patch in pieces and recommit them.

include/polly/LinkAllPasses.h

 }
 
 namespace polly {
 #ifdef CLOOG_FOUND
 llvm::Pass *createCloogExporterPass();
 llvm::Pass *createCloogInfoPass();
 llvm::Pass *createCodeGenerationPass();
 #endif
-llvm::Pass *createCodePreparationPass();
 llvm::Pass *createDeadCodeElimPass();
 llvm::Pass *createDependencesPass();
 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
-llvm::Pass *createIndependentBlocksPass();
 llvm::Pass *createIndVarSimplifyPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 #ifdef PLUTO_FOUND
 llvm::Pass *createPlutoOptimizerPass();
 #endif
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createScopDetectionPass();
 llvm::Pass *createScopInfoPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createIslCodeGenerationPass();
 llvm::Pass *createIslScheduleOptimizerPass();
 llvm::Pass *createTempScopInfoPass();
-
-extern char &IndependentBlocksID;
-extern char &CodePreparationID;
 }
 
 namespace {
 struct PollyForcePassLinking {
   PollyForcePassLinking() {
     // We must reference the passes in such a way that compilers will not
     // delete it all as dead code, even with whole program optimization,
     // yet is effectively a NO-OP. As the compiler isn't smart enough
     // to know that getenv() never returns -1, this will do the job.
     if (std::getenv("bar") != (char *)-1)
       return;
 
 #ifdef CLOOG_FOUND
     polly::createCloogExporterPass();
     polly::createCloogInfoPass();
     polly::createCodeGenerationPass();
 #endif
-    polly::createCodePreparationPass();
     polly::createDeadCodeElimPass();
     polly::createDependencesPass();
     polly::createDOTOnlyPrinterPass();
     polly::createDOTOnlyViewerPass();
     polly::createDOTPrinterPass();
     polly::createDOTViewerPass();
-    polly::createIndependentBlocksPass();
     polly::createIndVarSimplifyPass();
     polly::createJSONExporterPass();
     polly::createJSONImporterPass();
     polly::createScopDetectionPass();
     polly::createScopInfoPass();
 #ifdef PLUTO_FOUND
     polly::createPlutoOptimizerPass();
 #endif
     polly::createPollyCanonicalizePass();
     polly::createIslAstInfoPass();
     polly::createIslCodeGenerationPass();
     polly::createIslScheduleOptimizerPass();
     polly::createTempScopInfoPass();
   }
 } PollyForcePassLinking; // Force link by creating a global definition.
 }
 
 namespace llvm {
 class PassRegistry;
 #ifdef CLOOG_FOUND
 void initializeCodeGenerationPass(llvm::PassRegistry &);
 #endif
-void initializeCodePreparationPass(llvm::PassRegistry &);
 void initializeDeadCodeElimPass(llvm::PassRegistry &);
-void initializeIndependentBlocksPass(llvm::PassRegistry &);
 void initializeJSONExporterPass(llvm::PassRegistry &);
 void initializeJSONImporterPass(llvm::PassRegistry &);
 void initializeIslAstInfoPass(llvm::PassRegistry &);
 void initializeIslCodeGenerationPass(llvm::PassRegistry &);
 void initializeIslScheduleOptimizerPass(llvm::PassRegistry &);
 #ifdef PLUTO_FOUND
 void initializePlutoOptimizerPass(llvm::PassRegistry &);
 #endif
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
 void initializePollyIndVarSimplifyPass(llvm::PassRegistry &);
 }
 
 #endif

include/polly/ScopDetection.h

class ScopDetection : public FunctionPass {
 
   /// @brief Check if all basic block in the region are valid.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if all blocks in R are valid, false otherwise.
   bool allBlocksValid(DetectionContext &Context) const;
 
-  /// @brief Check the exit block of a region is valid.
-  ///
-  /// @param Context The context of scop detection.
-  ///
-  /// @return True if the exit of R is valid, false otherwise.
-  bool isValidExit(DetectionContext &Context) const;
-
   /// @brief Check if a region is a Scop.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(DetectionContext &Context) const;
 
   /// @brief Check if a region is a Scop.

include/polly/ScopInfo.h

 
 namespace polly {
 
 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;
+class TempScopInfo;
 class SCEVAffFunc;
 class Comparison;
 
 /// @brief A class to store information about arrays in the SCoP.
 ///
 /// Objects are accessible via the ScoP, MemoryAccess or the id associated with
 /// the MemoryAccess access function.
 ///
public:
   ///
   /// @param Access    The memory access.
   /// @param AccInst   The access instruction.
   /// @param Statement The statement that contains the access.
   /// @param SAI       The ScopArrayInfo object for this base pointer.
   MemoryAccess(const IRAccess &Access, Instruction *AccInst,
                ScopStmt *Statement, const ScopArrayInfo *SAI);
 
+  /// @brief Create a read memory access for a PHI node.
+  ///
+  /// @param PHI       The PHI node.
+  /// @param SAI       The ScopArrayInfo object for this base pointer.
+  /// @param Statement The statement that contains the access.
+  MemoryAccess(PHINode *PHI, const ScopArrayInfo *SAI, ScopStmt *Statement);
+
   ~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; }
 
   /// @brief Is this a read memory access?
   bool isRead() const { return AccType == MemoryAccess::READ; }
 
   /// @brief Is this a must-write memory access?
   bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; }
 
   /// @brief Is this a may-write memory access?
   bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; }
 
   /// @brief Is this a write memory access?
   bool isWrite() const { return isMustWrite() || isMayWrite(); }
 
+  /// @brief TODO
+  void intersectAccessDomain(__isl_take isl_set *Domain);
+
   isl_map *getAccessRelation() const;
 
   /// @brief Return the space in which the access relation lives in.
   __isl_give isl_space *getAccessRelationSpace() const;
 
   /// @brief Get an isl string representing this access function.
   std::string getAccessRelationStr() const;
 
class ScopStmt {
   /// This information is only needed for final code generation.
   std::vector<PHINode *> IVS;
   std::vector<Loop *> NestLoops;
 
   std::string BaseName;
 
   /// Build the statement.
   //@{
-  __isl_give isl_set *buildConditionSet(const Comparison &Cmp);
   __isl_give isl_set *addConditionsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop,
                                             const Region &CurRegion);
   __isl_give isl_set *addLoopBoundsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop);
   __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion);
   void buildScattering(SmallVectorImpl<unsigned> &Scatter);
-  void buildAccesses(TempScop &tempScop, const Region &CurRegion);
+  void buildAccesses(TempScop &tempScop);
 
   /// @brief Detect and mark reductions in the ScopStmt
   void checkForReductions();
 
   /// @brief Collect loads which might form a reduction chain with @p StoreMA
   void
   collectCandiateReductionLoads(MemoryAccess *StoreMA,
                                 llvm::SmallVectorImpl<MemoryAccess *> &Loads);
private:
 
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
   typedef std::vector<ScopStmt *> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
+  /// @brief A map from basic blocks to SCoP statements.
+  DenseMap<BasicBlock *, ScopStmt *> StmtMap;
+
   /// Parameters of this Scop
   typedef SmallVector<const SCEV *, 8> ParamVecType;
   ParamVecType Parameters;
 
   /// The isl_ids that are used to represent the parameters
   typedef std::map<const SCEV *, int> ParamIdType;
   ParamIdType ParameterIds;
 
private:
   /// one for the float pointers.
   ///
   /// During code generation we will create a runtime alias check for each alias
   /// group to ensure the SCoP is executed in an alias free environment.
   MinMaxVectorVectorTy MinMaxAliasGroups;
 
   /// Create the static control part with a region, max loop depth of this
   /// region and parameters used in this region.
-  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx);
-
-  /// @brief Check if a basic block is trivial.
-  ///
-  /// A trivial basic block does not contain any useful calculation. Therefore,
-  /// it does not need to be represented as a polyhedral statement.
-  ///
-  /// @param BB The basic block to check
-  /// @param tempScop TempScop returning further information regarding the Scop.
-  ///
-  /// @return True if the basic block is trivial, otherwise false.
-  static bool isTrivialBB(BasicBlock *BB, TempScop &tempScop);
+  Scop(TempScop &TempScop, TempScopInfo &TSI, LoopInfo &LI, ScalarEvolution &SE,
+       isl_ctx *ctx);
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
+  /// @brief Create accesses for PHI nodes in the SCoP.
+  void buildPHIAccesses(TempScop &tempScop, LoopInfo &LI, TempScopInfo &TSI);
+
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// @brief Simplify the assumed context.
   void simplifyAssumedContext();
 
   /// Build the Scop and Statement with precalculated scop information.
   void buildScop(TempScop &TempScop, const Region &CurRegion,
public:
   __isl_give isl_set *getContext() const;
   __isl_give isl_space *getParamSpace() const;
 
   /// @brief Get the assumed context for this Scop.
   ///
   /// @return The assumed context of this Scop.
   __isl_give isl_set *getAssumedContext() const;
 
+  /// @brief Return the stmt for the given @p BB or nullptr if none.
+  ScopStmt *getStmtForBasicBlock(BasicBlock *BB) const;
+
   /// @brief Add assumptions to assumed context.
   ///
   /// The assumptions added will be assumed to hold during the execution of the
   /// scop. However, as they are generally not statically provable, at code
   /// generation time run-time checks will be generated that ensure the
   /// assumptions hold.
   ///
   /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
public:
 
   reverse_iterator rbegin() { return Stmts.rbegin(); }
   reverse_iterator rend() { return Stmts.rend(); }
   const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
   const_reverse_iterator rend() const { return Stmts.rend(); }
   //@}
 
   /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
-  const ScopArrayInfo *getOrCreateScopArrayInfo(const IRAccess &Access,
-                                                Instruction *AccessInst);
+  const ScopArrayInfo *
+  getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
+                           const SmallVector<const SCEV *, 4> &Sizes);
 
   /// @brief Return the cached ScopArrayInfo object for @p BasePtr.
   const ScopArrayInfo *getScopArrayInfo(Value *BasePtr);
 
   void setContext(isl_set *NewContext);
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();

include/polly/Support/ScopHelper.h

 // Small functions that help with LLVM-IR.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 namespace llvm {
+class Type;
 class Instruction;
 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class Value;
 class PHINode;
 class Region;

 /// @return If the PHINode has an incoming BB that jumps to the parent BB
 ///         of the PHINode with an invoke instruction, return true,
 ///         otherwise, return false.
 bool hasInvokeEdge(const llvm::PHINode *PN);
 
 llvm::Value *getPointerOperand(llvm::Instruction &Inst);
 llvm::BasicBlock *createSingleExitEdge(llvm::Region *R, llvm::Pass *P);
 
+/// @brief Return the type of the access.
+llvm::Type *getAccessInstType(llvm::Instruction *AccInst);
+
 /// @brief Simplify the region in a SCoP to have a single unconditional entry
 ///        edge and a single exit edge.
 ///
 /// @param S  The SCoP that is simplified.
 /// @param P  The pass that is currently running.
 ///
 /// @return The unique entering block for the region.
 llvm::BasicBlock *simplifyRegion(polly::Scop *S, llvm::Pass *P);

include/polly/TempScopInfo.h

public:
   ~TempScopInfo();
 
   /// @brief Get the temporay Scop information in LLVM IR represent
   ///        for Region R.
   ///
   /// @return The Scop information in LLVM IR represent.
   TempScop *getTempScop(const Region *R) const;
 
+  /// @brief Return the offset used for scalar accesses.
+  const SCEV *getZeroOffset() const { return ZeroOffset; }
+
   /// @name FunctionPass interface
   //@{
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
   virtual void releaseMemory() { clear(); }
   virtual bool runOnFunction(Function &F);
   virtual void print(raw_ostream &OS, const Module *) const;
   //@}
 };

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   BaseValue = BasePointer->getValue();
 
   if (isa<UndefValue>(BaseValue))
     return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, &Inst);
 
   // Check that the base address of the access is invariant in the current
   // region.
   if (!isInvariant(*BaseValue, Context.CurRegion))
-    // Verification of this property is difficult as the independent blocks
-    // pass may introduce aliasing that we did not have when running the
-    // scop detection.
     return invalid<ReportVariantBasePtr>(Context, /*Assert=*/false, BaseValue,
                                          &Inst);
 
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
   const SCEV *Size = SE->getElementSize(&Inst);
   if (Context.ElementSize.count(BasePointer)) {
     if (Context.ElementSize[BasePointer] != Size)
if (PollyDelinearize) {
     if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
       Context.NonAffineAccesses.insert(BasePointer);
   } else if (!AllowNonAffine) {
     if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
       return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
                                             AccessFunction, &Inst, BaseValue);
   }
 
-  // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
-  // created by IndependentBlocks Pass.
-  if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
-    return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
-
   if (IgnoreAliasing)
     return true;
 
   // Check if the base pointer of the memory access does alias with
   // any other pointer. This cannot be handled at the moment.
   AAMDNodes AATags;
   Inst.getAAMetadata(AATags);
   AliasSet &AS = Context.AST.getAliasSetForPointer(
       BaseValue, AliasAnalysis::UnknownSize, AATags);
 
-  // INVALID triggers an assertion in verifying mode, if it detects that a
-  // SCoP was detected by SCoP detection and that this SCoP was invalidated by
-  // a pass that stated it would preserve the SCoPs. We disable this check as
-  // the independent blocks pass may create memory references which seem to
-  // alias, if -basicaa is not available. They actually do not, but as we can
-  // not proof this without -basicaa we would fail. We disable this check to
-  // not cause irrelevant verification failures.
   if (!AS.isMustAlias()) {
     if (PollyUseRuntimeAliasChecks) {
       bool CanBuildRunTimeCheck = true;
       // The run-time alias check places code that involves the base pointer at
       // the beginning of the SCoP. This breaks if the base pointer is defined
       // inside the scop. Hence, we can only create a run-time check if we are
       // sure the base pointer is not an instruction defined inside the scop.
       for (const auto &Ptr : AS) {
if (!AS.isMustAlias()) {
     return invalid<ReportAlias>(Context, /*Assert=*/false, &Inst, AS);
   }
 
   return true;
 }
 
 bool ScopDetection::isValidInstruction(Instruction &Inst,
                                        DetectionContext &Context) const {
-  if (PHINode *PN = dyn_cast<PHINode>(&Inst))
-    if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) {
-      if (SCEVCodegen)
-        return invalid<ReportPhiNodeRefInRegion>(Context, /*Assert=*/true,
-                                                 &Inst);
-      else
-        return invalid<ReportNonCanonicalPhiNode>(Context, /*Assert=*/true,
-                                                  &Inst);
-    }
-
   // We only check the call instruction but not invoke instruction.
   if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
     if (isValidCallInst(*CI))
       return true;
 
     return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);
   }
 
Region *ScopDetection::expandRegion(Region &R) {
 
   DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
 
   while (ExpandedRegion) {
     DetectionContext Context(*ExpandedRegion, *AA, false /* verifying */);
     DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
     // Only expand when we did not collect errors.
 
-    // Check the exit first (cheap)
-    if (isValidExit(Context) && !Context.Log.hasErrors()) {
-      // If the exit is valid check all blocks
+    if (!Context.Log.hasErrors()) {
+      // Check all blocks
       //  - if true, a valid region was found => store it + keep expanding
       //  - if false, .tbd. => stop  (should this really end the loop?)
       if (!allBlocksValid(Context) || Context.Log.hasErrors())
         break;
 
       if (Context.Log.hasErrors())
         break;
 
for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
         return false;
 
   if (!hasAffineMemoryAccesses(Context))
     return false;
 
   return true;
 }
 
-bool ScopDetection::isValidExit(DetectionContext &Context) const {
-  Region &R = Context.CurRegion;
-
-  // PHI nodes are not allowed in the exit basic block.
-  if (BasicBlock *Exit = R.getExit()) {
-    BasicBlock::iterator I = Exit->begin();
-    if (I != Exit->end() && isa<PHINode>(*I))
-      return invalid<ReportPHIinExit>(Context, /*Assert=*/true, I);
-  }
-
-  return true;
-}
-
 bool ScopDetection::isValidRegion(Region &R) const {
   DetectionContext Context(R, *AA, false /*verifying*/);
 
   bool RegionIsValid = isValidRegion(Context);
   bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
 
   if (PollyTrackFailures && HasErrors)
     RejectLogs.insert(std::make_pair(&R, Context.Log));
if (L) {
         // Region entering edges come from the same loop but outside the region
         // are not allowed.
         if (L->contains(*PI) && !R.contains(*PI))
           return invalid<ReportIndEdge>(Context, /*Assert=*/true, *PI);
       }
     }
   }
 
-  // SCoP cannot contain the entry block of the function, because we need
-  // to insert alloca instruction there when translate scalar to array.
-  if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock()))
-    return invalid<ReportEntry>(Context, /*Assert=*/true, R.getEntry());
-
-  if (!isValidExit(Context))
-    return false;
-
   if (!allBlocksValid(Context))
     return false;
 
   DEBUG(dbgs() << "OK\n");
   return true;
 }
 
 void ScopDetection::markFunctionAsInvalid(Function *F) const {

lib/Analysis/ScopInfo.cpp

AccessRelation = isl_map_set_tuple_id(
       AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
   AccessRelation =
       isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
   assumeNoOutOfBound(Access);
   isl_space_free(Space);
 }
 
+MemoryAccess::MemoryAccess(PHINode *PHI, const ScopArrayInfo *SAI,
+                           ScopStmt *Statement)
+    : AccType(READ), Statement(Statement), Inst(PHI),
+      newAccessRelation(nullptr) {
+
+  isl_ctx *Ctx = Statement->getIslCtx();
+  BaseAddr = PHI;
+  BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
+
+  isl_id *BaseAddrId = SAI->getBasePtrId();
+
+  isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
+  AccessRelation = isl_map_universe(Space);
+
+  Space = Statement->getDomainSpace();
+  AccessRelation = isl_map_set_tuple_id(
+      AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
+  AccessRelation =
+      isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
+
+  isl_space_free(Space);
+}
+
+void MemoryAccess::intersectAccessDomain(isl_set *Domain) {
+  AccessRelation = isl_map_intersect_domain(AccessRelation, Domain);
+}
+
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
   AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
 }
 
 const std::string MemoryAccess::getReductionOperatorStr() const {
   return MemoryAccess::getReductionOperatorStr(getReductionType());
 }
void ScopStmt::buildScattering(SmallVectorImpl<unsigned> &Scatter) {
 
   // Fill scattering dimensions.
   for (unsigned i = 2 * NbIterators + 1; i < NbScatteringDims; ++i)
     Scattering = isl_map_fix_si(Scattering, isl_dim_out, i, 0);
 
   Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
 }
 
-void ScopStmt::buildAccesses(TempScop &tempScop, const Region &CurRegion) {
-  for (const auto &AccessPair : *tempScop.getAccessFunctions(BB)) {
+static __isl_give isl_set *buildConditionSet(ScopStmt *Stmt,
+                                             const Comparison &Comp) {
+  isl_pw_aff *L = SCEVAffinator::getPwAff(Stmt, Comp.getLHS());
+  isl_pw_aff *R = SCEVAffinator::getPwAff(Stmt, Comp.getRHS());
+
+  switch (Comp.getPred()) {
+  case ICmpInst::ICMP_EQ:
+    return isl_pw_aff_eq_set(L, R);
+  case ICmpInst::ICMP_NE:
+    return isl_pw_aff_ne_set(L, R);
+  case ICmpInst::ICMP_SLT:
+    return isl_pw_aff_lt_set(L, R);
+  case ICmpInst::ICMP_SLE:
+    return isl_pw_aff_le_set(L, R);
+  case ICmpInst::ICMP_SGT:
+    return isl_pw_aff_gt_set(L, R);
+  case ICmpInst::ICMP_SGE:
+    return isl_pw_aff_ge_set(L, R);
+  case ICmpInst::ICMP_ULT:
+  case ICmpInst::ICMP_UGT:
+  case ICmpInst::ICMP_ULE:
+  case ICmpInst::ICMP_UGE:
+    llvm_unreachable("Unsigned comparisons not yet supported");
+  default:
+    llvm_unreachable("Non integer predicate not supported");
+  }
+}
+
+void ScopStmt::buildAccesses(TempScop &tempScop) {
+  const AccFuncSetType *AFS = tempScop.getAccessFunctions(BB);
+  if (!AFS)
+    return;
+
+  for (const auto &AccessPair : *AFS) {
     const IRAccess &Access = AccessPair.first;
     Instruction *AccessInst = AccessPair.second;
+    if (isa<PHINode>(AccessInst))
+      continue;
 
-    const ScopArrayInfo *SAI =
-        getParent()->getOrCreateScopArrayInfo(Access, AccessInst);
+    Type *AccessType = getAccessInstType(AccessInst)->getPointerTo();
+    const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
+        Access.getBase(), AccessType, Access.Sizes);
     MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI));
 
     // We do not track locations for scalar memory accesses at the moment.
     //
     // We do not have a use for this information at the moment. If we need this
     // at some point, the "instruction -> access" mapping needs to be enhanced
     // as a single instruction could then possibly perform multiple accesses.
     if (!Access.isScalar()) {
       assert(!InstructionToAccess.count(AccessInst) &&
              "Unexpected 1-to-N mapping on instruction to access map!");
       InstructionToAccess[AccessInst] = MemAccs.back();
     }
   }
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
   Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
 }
 
-__isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) {
-  isl_pw_aff *L = SCEVAffinator::getPwAff(this, Comp.getLHS());
-  isl_pw_aff *R = SCEVAffinator::getPwAff(this, Comp.getRHS());
-
-  switch (Comp.getPred()) {
-  case ICmpInst::ICMP_EQ:
-    return isl_pw_aff_eq_set(L, R);
-  case ICmpInst::ICMP_NE:
-    return isl_pw_aff_ne_set(L, R);
-  case ICmpInst::ICMP_SLT:
-    return isl_pw_aff_lt_set(L, R);
-  case ICmpInst::ICMP_SLE:
-    return isl_pw_aff_le_set(L, R);
-  case ICmpInst::ICMP_SGT:
-    return isl_pw_aff_gt_set(L, R);
-  case ICmpInst::ICMP_SGE:
-    return isl_pw_aff_ge_set(L, R);
-  case ICmpInst::ICMP_ULT:
-  case ICmpInst::ICMP_UGT:
-  case ICmpInst::ICMP_ULE:
-  case ICmpInst::ICMP_UGE:
-    llvm_unreachable("Unsigned comparisons not yet supported");
-  default:
-    llvm_unreachable("Non integer predicate not supported");
-  }
-}
-
 __isl_give isl_set *ScopStmt::addLoopBoundsToDomain(__isl_take isl_set *Domain,
                                                     TempScop &tempScop) {
   isl_space *Space;
   isl_local_space *LocalSpace;
 
   Space = isl_set_get_space(Domain);
   LocalSpace = isl_local_space_from_space(Space);
 
__isl_give isl_set *ScopStmt::addConditionsToDomain(__isl_take isl_set *Domain,
   const Region *TopRegion = tempScop.getMaxRegion().getParent(),
                *CurrentRegion = &CurRegion;
   const BasicBlock *BranchingBB = BB;
 
   do {
     if (BranchingBB != CurrentRegion->getEntry()) {
       if (const BBCond *Condition = tempScop.getBBCond(BranchingBB))
         for (const auto &C : *Condition) {
-          isl_set *ConditionSet = buildConditionSet(C);
+          isl_set *ConditionSet = buildConditionSet(this, C);
           Domain = isl_set_intersect(Domain, ConditionSet);
         }
     }
     BranchingBB = CurrentRegion->getEntry();
     CurrentRegion = CurrentRegion->getParent();
   } while (TopRegion != CurrentRegion);
 
   return Domain;
for (unsigned i = 0, e = Nest.size(); i < e; ++i) {
     }
     NestLoops[i] = Nest[i];
   }
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 
   Domain = buildDomain(tempScop, CurRegion);
   buildScattering(Scatter);
-  buildAccesses(tempScop, CurRegion);
-  checkForReductions();
+  buildAccesses(tempScop);
 }
 
 /// @brief Collect loads which might form a reduction chain with @p StoreMA
 ///
 /// Check if the stored value for @p StoreMA is a binary operator with one or
 /// two loads as operands. If the binary operand is commutative & associative,
 /// used only once (by @p StoreMA) and its load operands are also used only
 /// once, we have found a possible reduction chain. It starts at an operand
for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 
+static bool isLoopCarried(__isl_take isl_map *Scattering,
+                          __isl_take isl_map *InScattering) {
+  unsigned DimIn = isl_map_dim(Scattering, isl_dim_in);
+  unsigned InDimIn = isl_map_dim(InScattering, isl_dim_in);
+  unsigned MinDimIn = std::min(DimIn, InDimIn);
+
+  isl_map *Order = isl_map_lex_gt_map(Scattering, InScattering);
+  for (unsigned u = 0; u < MinDimIn; u++)
+    Order = isl_map_equate(Order, isl_dim_in, u, isl_dim_out, u);
+
+  bool IsLoopCarried = isl_map_is_empty(Order);
+  isl_map_free(Order);
+  return IsLoopCarried;
+}
+
+static __isl_give isl_set *getInDomain(ScopStmt *Stmt, ScopStmt *InStmt) {
+
+  bool IsLC = isLoopCarried(Stmt->getScattering(), InStmt->getScattering());
+
+  isl_set *InDom = isl_set_reset_tuple_id(InStmt->getDomain());
+
+  unsigned NumIterators = Stmt->getNumIterators();
+  unsigned InNumIterators = InStmt->getNumIterators();
+  int NumIteratorsDiff = NumIterators - InNumIterators;
+
+  if (NumIteratorsDiff > 0) {
+    assert(!IsLC);
+    InDom = isl_set_add_dims(InDom, isl_dim_set, NumIteratorsDiff);
+    for (unsigned dimIt = InNumIterators; dimIt < NumIterators; dimIt++)
+      InDom = isl_set_fix_dim_si(InDom, dimIt, 0);
+  }
+
+  if (IsLC) {
+    assert(NumIteratorsDiff <= 0);
+    isl_space *InDomainSpace = isl_set_get_space(InDom);
+    isl_space *InDomainMapSpace = isl_space_map_from_set(InDomainSpace);
+
+    isl_multi_aff *LCMAff = isl_multi_aff_identity(InDomainMapSpace);
+
+    unsigned LastDim = InNumIterators - 1;
+    isl_aff *LCAff = isl_multi_aff_get_aff(LCMAff, LastDim);
+    LCAff = isl_aff_add_constant_si(LCAff, 1);
+    LCMAff = isl_multi_aff_set_aff(LCMAff, LastDim, LCAff);
+
+    isl_map *LCMap = isl_map_from_multi_aff(LCMAff);
+    InDom = isl_set_apply(InDom, LCMap);
+  }
+
+  return InDom;
+}
+
+void Scop::buildPHIAccesses(TempScop &tempScop, LoopInfo &LI,
+                            TempScopInfo &TSI) {
+  SmallVector<std::pair<PHINode *, isl_set *>, 8> TodoPHIs;
+  DenseMap<Instruction *, isl_set *> Accesses;
+  SmallPtrSet<PHINode *, 8> SeenPHIs;
+
+  const SCEV *ZeroOffset = TSI.getZeroOffset();
+  const SmallVector<const SCEV *, 4> Subscripts, Sizes;
+  SmallVector<Instruction *, 4> UserInsts;
+
+  const Region &R = getRegion();
+
+  for (BasicBlock *BB : R.blocks()) {
+    for (Instruction &Inst : *BB) {
+      PHINode *PHI = dyn_cast<PHINode>(&Inst);
+      if (!PHI)
+        continue;
+
+      if (canSynthesize(PHI, &LI, SE, &R))
+        continue;
+
+      UserInsts.clear();
+      for (User *U : PHI->users())
+        if (Instruction *I = dyn_cast<Instruction>(U))
+          if (R.contains(I->getParent()))
+            if (!isa<PHINode>(I))
+              UserInsts.push_back(I);
+
+      if (UserInsts.empty())
+        continue;
+
+      // An interesting PHI was found, we create a write for it and look
+      // through all operands.
+
+      ScopStmt *PHIStmt = getStmtForBasicBlock(BB);
+      isl_set *PHIDom = isl_set_reset_tuple_id(PHIStmt->getDomain());
+
+      // TODO caching
+      Accesses.clear();
+      SeenPHIs.clear();
+      TodoPHIs.push_back(std::make_pair(PHI, PHIDom));
+
+      while (!TodoPHIs.empty()) {
+        const auto &TodoPair = TodoPHIs.pop_back_val();
+        PHINode *CurPHI = TodoPair.first;
+
+        isl_set *CurDom = TodoPair.second;
+        unsigned CurDomDim = isl_set_n_dim(CurDom);
+
+        // Stop when we detect a PHI cycle.
+        if (!SeenPHIs.insert(CurPHI)) {
+          isl_set_free(CurDom);
+          continue;
+        }
+
+        ScopStmt *CurStmt = getStmtForBasicBlock(CurPHI->getParent());
+        unsigned CurNumIV = CurPHI->getNumIncomingValues();
+        for (unsigned u = 0; u < CurNumIV; u++) {
+          BasicBlock *InBB = CurPHI->getIncomingBlock(u);
+          ScopStmt *InStmt = getStmtForBasicBlock(InBB);
+
+          // Ignore incoming edges from outsie the SCoP.
+          if (!InStmt)
+            continue;
+
+          // Ignroe incoming constants and arguments.
+          auto *InInst = dyn_cast<Instruction>(CurPHI->getIncomingValue(u));
+          if (!InInst)
+            continue;
+
+          isl_set *InDom = getInDomain(CurStmt, InStmt);
+          unsigned InDomDim = isl_set_n_dim(InDom);
+          if (InDomDim < CurDomDim)
+            InDom = isl_set_add_dims(InDom, isl_dim_set, CurDomDim - InDomDim);
+          else if (InDomDim > CurDomDim)
+            InDom = isl_set_remove_dims(InDom, isl_dim_set, CurDomDim,
+                                        InDomDim - CurDomDim);
+
+          InDom = isl_set_intersect(InDom, isl_set_copy(CurDom));
+
+          // See through PHI operands.
+          if (PHINode *InPHI = dyn_cast<PHINode>(InInst)) {
+            TodoPHIs.push_back(std::make_pair(InPHI, InDom));
+            continue;
+          }
+
+          // Found a real accesses.
+          isl_set *&AccessDom = Accesses[InInst];
+          if (AccessDom)
+            AccessDom = isl_set_union(AccessDom, InDom);
+          else
+            AccessDom = InDom;
+        }
+        isl_set_free(CurDom);
+      }
+
+      // TODO: We could restrict the PHI writes the iterations we actually need.
+      PHIDom = PHIStmt->getDomain();
+      Type *AccessType = PHI->getType()->getPointerTo();
+      const ScopArrayInfo *PHISAI =
+          getOrCreateScopArrayInfo(PHI, AccessType, Sizes);
+
+      // For each access we create a read MemoryAccess with a restricted domain.
+      for (const auto &AccessPair : Accesses) {
+        Instruction *AccessInst = AccessPair.first;
+        isl_set *AccessDom =
+            isl_set_set_tuple_id(AccessPair.second, PHIStmt->getDomainId());
+
+        const ScopArrayInfo *SAI =
+            getOrCreateScopArrayInfo(AccessInst, AccessType, Sizes);
+        MemoryAccess *PHIReadMA = new MemoryAccess(PHI, SAI, PHIStmt);
+        PHIReadMA->intersectAccessDomain(AccessDom);
+        PHIStmt->MemAccs.push_back(PHIReadMA);
+
+        ScopStmt *AccessStmt = getStmtForBasicBlock(AccessInst->getParent());
+        // TODO: We could restrict the access writes the iterations we actually
+        // need.
+        IRAccess WriteAccess(IRAccess::MUST_WRITE, AccessInst, ZeroOffset, 1,
+                             true, Subscripts, Sizes);
+        MemoryAccess *AccessWriteMA =
+            new MemoryAccess(WriteAccess, AccessInst, AccessStmt, SAI);
+        AccessStmt->MemAccs.push_back(AccessWriteMA);
+      }
+
+      for (Instruction *UsrInst : UserInsts) {
+        ScopStmt *UsrStmt = getStmtForBasicBlock(UsrInst->getParent());
+        IRAccess ReadAccess(IRAccess::READ, UsrInst, ZeroOffset, 1, true,
+                            Subscripts, Sizes);
+        MemoryAccess *AccessReadMA =
+            new MemoryAccess(ReadAccess, UsrInst, UsrStmt, PHISAI);
+        UsrStmt->MemAccs.push_back(AccessReadMA);
+      }
+
+      // And one write MemoryAccess for the PHI node.
+      IRAccess Access(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true,
+                      Subscripts, Sizes);
+      MemoryAccess *MA = new MemoryAccess(Access, PHI, PHIStmt, PHISAI);
+      MA->intersectAccessDomain(PHIDom);
+      PHIStmt->MemAccs.push_back(MA);
+    }
+  }
+}
+
 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
   isl_set_free(Context);
   Context = NewContext;
 }
 
 void Scop::addParams(std::vector<const SCEV *> NewParameters) {
   for (const SCEV *Parameter : NewParameters) {
for (AliasGroupTy &AG : AliasGroups) {
 
     if (!Valid)
       break;
   }
 
   return Valid;
 }
 
-Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
-           isl_ctx *Context)
+Scop::Scop(TempScop &tempScop, TempScopInfo &TSI, LoopInfo &LI,
+           ScalarEvolution &ScalarEvolution, isl_ctx *Context)
     : SE(&ScalarEvolution), R(tempScop.getMaxRegion()),
       MaxLoopDepth(tempScop.getMaxLoopDepth()) {
   IslCtx = Context;
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
   SmallVector<unsigned, 8> Scatter;
 
   Scatter.assign(MaxLoopDepth + 1, 0);
 
   // Build the iteration domain, access functions and scattering functions
   // traversing the region tree.
   buildScop(tempScop, getRegion(), NestLoops, Scatter, LI);
 
+  // We delayed the building of accesses until we created all statements.
+  // This way we know the domains, thus can model PHI nodes accruate.
+  buildPHIAccesses(tempScop, LI, TSI);
+  for (auto StmtIt = Stmts.begin(); StmtIt != Stmts.end();) {
+    if ((*StmtIt)->MemAccs.empty())
+      StmtIt = Stmts.erase(StmtIt);
+    else
+      (*StmtIt++)->checkForReductions();
+  }
+
   realignParams();
   addParameterBounds();
   simplifyAssumedContext();
 
   assert(NestLoops.empty() && "NestLoops not empty at top level!");
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
 
   // Free the statements;
-  for (ScopStmt *Stmt : *this)
-    delete Stmt;
+  for (const auto &StmtMapPair : StmtMap)
+    delete StmtMapPair.second;
 
   // Free the ScopArrayInfo objects.
   for (auto &ScopArrayInfoPair : ScopArrayInfoMap)
     delete ScopArrayInfoPair.second;
 
   // Free the alias groups
   for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
     for (MinMaxAccessTy &MMA : *MinMaxAccesses) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
     delete MinMaxAccesses;
   }
 }
 
-const ScopArrayInfo *Scop::getOrCreateScopArrayInfo(const IRAccess &Access,
-                                                    Instruction *AccessInst) {
-  Value *BasePtr = Access.getBase();
+const ScopArrayInfo *
+Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
+                               const SmallVector<const SCEV *, 4> &Sizes) {
   const ScopArrayInfo *&SAI = ScopArrayInfoMap[BasePtr];
-  if (!SAI) {
-    Type *AccessType = getPointerOperand(*AccessInst)->getType();
-    SAI = new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Access.Sizes);
-  }
+  if (!SAI)
+    SAI = new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes);
   return SAI;
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr) {
   const SCEV *PtrSCEV = SE->getSCEV(BasePtr);
   const SCEVUnknown *PtrBaseSCEV =
       cast<SCEVUnknown>(SE->getPointerBase(PtrSCEV));
   const ScopArrayInfo *SAI = ScopArrayInfoMap[PtrBaseSCEV->getValue()];
if (isl_union_set_is_empty(NewStmtDomain)) {
       Stmt->restrictDomain(isl_set_from_union_set(NewStmtDomain));
   }
   isl_union_set_free(Domain);
   return Changed;
 }
 
 ScalarEvolution *Scop::getSE() const { return SE; }
 
-bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
-  if (tempScop.getAccessFunctions(BB))
-    return false;
-
-  return true;
-}
-
 void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
                      SmallVectorImpl<Loop *> &NestLoops,
                      SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI) {
   Loop *L = castToLoop(CurRegion, LI);
 
   if (L)
     NestLoops.push_back(L);
 
   unsigned loopDepth = NestLoops.size();
   assert(Scatter.size() > loopDepth && "Scatter not big enough!");
 
   for (Region::const_element_iterator I = CurRegion.element_begin(),
                                       E = CurRegion.element_end();
        I != E; ++I)
     if (I->isSubRegion())
       buildScop(tempScop, *(I->getNodeAs<Region>()), NestLoops, Scatter, LI);
     else {
       BasicBlock *BB = I->getNodeAs<BasicBlock>();
 
-      if (isTrivialBB(BB, tempScop))
-        continue;
+      ScopStmt *Stmt =
+          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
 
-      Stmts.push_back(
-          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter));
+      StmtMap[BB] = Stmt;
+      Stmts.push_back(Stmt);
 
       // Increasing the Scattering function is OK for the moment, because
       // we are using a depth first iterator and the program is well structured.
       ++Scatter[loopDepth];
     }
 
   if (!L)
     return;
 
   // Exiting a loop region.
   Scatter[loopDepth] = 0;
   NestLoops.pop_back();
   ++Scatter[loopDepth - 1];
 }
 
+ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
+  const auto &StmtMapIt = StmtMap.find(BB);
+  if (StmtMapIt == StmtMap.end())
+    return nullptr;
+  return StmtMapIt->second;
+}
+
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
   ctx = isl_ctx_alloc();
   isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
 }
 
 ScopInfo::~ScopInfo() {
   clear();
   isl_ctx_free(ctx);
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfo>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<ScalarEvolution>();
   AU.addRequired<TempScopInfo>();
   AU.addRequired<AliasAnalysis>();
   AU.setPreservesAll();
 }
 
 bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   LoopInfo &LI = getAnalysis<LoopInfo>();
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
+  TempScopInfo &TSI = getAnalysis<TempScopInfo>();
 
-  TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
+  TempScop *tempScop = TSI.getTempScop(R);
 
   // This region is no Scop.
   if (!tempScop) {
     scop = 0;
     return false;
   }
 
   // Statistics.
   ++ScopFound;
   if (tempScop->getMaxLoopDepth() > 0)
     ++RichScopFound;
 
-  scop = new Scop(*tempScop, LI, SE, ctx);
+  scop = new Scop(*tempScop, TSI, LI, SE, ctx);
 
   if (!PollyUseRuntimeAliasChecks)
     return false;
 
   // If a problem occurs while building the alias groups we need to delete
   // this SCoP and pretend it wasn't valid in the first place.
   if (scop->buildAliasGroups(AA))
     return false;

lib/Analysis/TempScopInfo.cpp

for (User *U : Inst->users()) {
 
     // Now U is used in another statement.
     AnyCrossStmtUse = true;
 
     // Do not build a read access that is not in the current SCoP
     if (!R->contains(UseParent))
       continue;
 
-    assert(!isa<PHINode>(UI) && "Non synthesizable PHINode found in a SCoP!");
+    // Skip PHI users as they are treated differently later on.
+    if (isa<PHINode>(UI))
+      continue;
 
     SmallVector<const SCEV *, 4> Subscripts, Sizes;
 
     // Use the def instruction as base address of the IRAccess, so that it will
     // become the name of the scalar access in the polyhedral form.
     IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Subscripts,
                           Sizes);
     AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));

 
 void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<DataLayoutPass>();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<PostDominatorTree>();
   AU.addRequiredTransitive<LoopInfo>();
   AU.addRequiredTransitive<ScalarEvolution>();
   AU.addRequiredTransitive<ScopDetection>();
-  AU.addRequiredID(IndependentBlocksID);
   AU.addRequired<AliasAnalysis>();
   AU.setPreservesAll();
 }
 
 TempScopInfo::~TempScopInfo() { clear(); }
 
 void TempScopInfo::clear() {
   BBConds.clear();

lib/CMakeLists.txt

add_polly_library(Polly
   ${GPGPU_CODEGEN_FILES}
   Exchange/JSONExporter.cpp
   Support/GICHelper.cpp
   Support/SCEVValidator.cpp
   Support/RegisterPasses.cpp
   Support/ScopHelper.cpp
   ${POLLY_JSON_FILES}
   Transform/Canonicalization.cpp
-  Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp
-  Transform/IndependentBlocks.cpp
   Transform/IndVarSimplify.cpp
   Transform/ScheduleOptimizer.cpp
   ${POLLY_PLUTO_FILES}
   )
 
 # Build a monolithic Polly.a and a thin module LLVMPolly.moduleext that links to
 # that static library.
 add_polly_loadable_module(LLVMPolly

lib/CodeGen/BlockGenerators.cpp

static cl::opt<bool>
     Aligned("enable-polly-aligned",
             cl::desc("Assumed aligned memory accesses."), cl::Hidden,
             cl::value_desc("OpenMP code generation enabled if true"),
             cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool, true>
     SCEVCodegenF("polly-codegen-scev",
                  cl::desc("Use SCEV based code generation."), cl::Hidden,
-                 cl::location(SCEVCodegen), cl::init(false), cl::ZeroOrMore,
+                 cl::location(SCEVCodegen), cl::init(true), cl::ZeroOrMore,
                  cl::cat(PollyCategory));
 
 bool polly::SCEVCodegen;
 
 bool polly::canSynthesize(const Instruction *I, const llvm::LoopInfo *LI,
                           ScalarEvolution *SE, const Region *R) {
   if (SCEVCodegen) {
     if (!I || !SE->isSCEVable(I->getType()))

lib/CodeGen/CodeGeneration.cpp

virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addPreserved<ScopDetection>();
     AU.addPreserved<ScalarEvolution>();
 
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
     AU.addPreserved<TempScopInfo>();
     AU.addPreserved<ScopInfo>();
-    AU.addPreservedID(IndependentBlocksID);
   }
 };
 }
 
 char CodeGeneration::ID = 1;
 
 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
 

lib/CodeGen/IslCodeGeneration.cpp

virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addPreserved<ScopDetection>();
     AU.addPreserved<ScalarEvolution>();
 
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
     AU.addPreserved<TempScopInfo>();
     AU.addPreserved<ScopInfo>();
-    AU.addPreservedID(IndependentBlocksID);
   }
 };
 }
 
 char IslCodeGeneration::ID = 1;
 
 Pass *polly::createIslCodeGenerationPass() { return new IslCodeGeneration(); }
 

lib/Makefile

SOURCES= Polly.cpp \
    Analysis/TempScopInfo.cpp \
    CodeGen/BlockGenerators.cpp \
    CodeGen/LoopGenerators.cpp \
    CodeGen/IRBuilder.cpp \
    CodeGen/Utils.cpp \
    CodeGen/RuntimeDebugBuilder.cpp \
    Exchange/JSONExporter.cpp \
    Transform/Canonicalization.cpp \
-   Transform/CodePreparation.cpp \
    Transform/DeadCodeElimination.cpp \
-   Transform/IndependentBlocks.cpp \
    Transform/IndVarSimplify.cpp \
    Transform/ScheduleOptimizer.cpp \
    ${GPGPU_FILES} \
    ${ISL_CODEGEN_FILES} \
          ${CLOOG_FILES} \
    ${POLLY_JSON_FILES} \
    ${POLLY_PLUTO_FILES}
 
 #
 # Include Makefile.common so we know what to do.
 #
 include $(LEVEL)/Makefile.common

lib/Support/RegisterPasses.cpp

 
 namespace polly {
 void initializePollyPasses(PassRegistry &Registry) {
 #ifdef CLOOG_FOUND
   initializeCloogInfoPass(Registry);
   initializeCodeGenerationPass(Registry);
 #endif
   initializeIslCodeGenerationPass(Registry);
-  initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependencesPass(Registry);
-  initializeIndependentBlocksPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyIndVarSimplifyPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoPass(Registry);

lib/Support/ScopHelper.cpp

Value *polly::getPointerOperand(Instruction &Inst) {
   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
     return store->getPointerOperand();
   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
     return gep->getPointerOperand();
 
   return 0;
 }
 
+Type *polly::getAccessInstType(Instruction *AccInst) {
+  if (StoreInst *Store = dyn_cast<StoreInst>(AccInst))
+    return Store->getValueOperand()->getType();
+  return AccInst->getType();
+}
+
 bool polly::hasInvokeEdge(const PHINode *PN) {
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
       if (II->getParent() == PN->getIncomingBlock(i))
         return true;
 
   return false;
 }
 
 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
   BasicBlock *BB = R->getExit();
 
   SmallVector<BasicBlock *, 4> Preds;
   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
     if (R->contains(*PI))
       Preds.push_back(*PI);
 
   return SplitBlockPredecessors(BB, Preds, ".region", P);
 }
 
 static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
                                       BasicBlock *NewEntry) {
-  for (polly::ScopStmt *Stmt : *S)
-    if (Stmt->getBasicBlock() == OldEntry) {
-      Stmt->setBasicBlock(NewEntry);
-      break;
-    }
+  if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
 
   S->getRegion().replaceEntryRecursive(NewEntry);
 }
 
 BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
   Region *R = &S->getRegion();
 
   // The entering block for the region.

lib/Transform/Canonicalization.cpp

void polly::registerCanonicalicationPasses(llvm::PassManagerBase &PM,
   PM.add(llvm::createTailCallEliminationPass());
   PM.add(llvm::createCFGSimplificationPass());
   PM.add(llvm::createReassociatePass());
   PM.add(llvm::createLoopRotatePass());
   PM.add(llvm::createInstructionCombiningPass());
 
   if (!SCEVCodegen)
     PM.add(polly::createIndVarSimplifyPass());
-
-  PM.add(polly::createCodePreparationPass());
 }
 
 namespace {
 class PollyCanonicalize : public ModulePass {
   PollyCanonicalize(const PollyCanonicalize &) LLVM_DELETED_FUNCTION;
   const PollyCanonicalize &
   operator=(const PollyCanonicalize &) LLVM_DELETED_FUNCTION;
 

lib/Transform/CodePreparation.cpp

-//===---- CodePreparation.cpp - Code preparation for Scop Detection -------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// The Polly code preparation pass is executed before SCoP detection. Its only
-// use is to translate all PHI nodes that can not be expressed by the code
-// generator into explicit memory dependences. Depending of the code generation
-// strategy different PHI nodes are translated:
-//
-// - indvars based code generation:
-//
-// The indvars based code generation requires explicit canonical induction
-// variables. Such variables are generated before scop detection and
-// also before the code preparation pass. All PHI nodes that are not canonical
-// induction variables are not supported by the indvars based code generation
-// and are consequently translated into explicit memory accesses.
-//
-// - scev based code generation:
-//
-// The scev based code generation can code generate all PHI nodes that do not
-// reference parameters within the scop. As the code preparation pass is run
-// before scop detection, we can not check this condition, because without
-// a detected scop, we do not know SCEVUnknowns that appear in the SCEV of
-// a PHI node may later be within or outside of the SCoP. Hence, we follow a
-// heuristic and translate all PHI nodes that are either directly SCEVUnknown
-// or SCEVCouldNotCompute. This will hopefully get most of the PHI nodes that
-// are introduced due to conditional control flow, but not the ones that are
-// referencing loop counters.
-//
-// XXX: In the future, we should remove the need for this pass entirely and
-// instead add support for scalar dependences to ScopInfo and code generation.
-//
-//===----------------------------------------------------------------------===//
-
-#include "polly/LinkAllPasses.h"
-#include "polly/CodeGen/BlockGenerators.h"
-#include "polly/Support/ScopHelper.h"
-#include "llvm/Analysis/DominanceFrontier.h"
-#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/RegionInfo.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Transforms/Utils/Local.h"
-
-using namespace llvm;
-using namespace polly;
-
-namespace {
-
-// Helper function which (for a given PHI node):
-//
-// 1) Remembers all incoming values and the associated basic blocks
-// 2) Demotes the phi node to the stack
-// 3) Remembers the correlation between the PHI node and the new alloca
-//
-// When we combine the information from 1) and 3) we know the values stored
-// in this alloca at the end of the predecessor basic blocks of the PHI.
-static void DemotePHI(
-    PHINode *PN, DenseMap<PHINode *, AllocaInst *> &PNallocMap,
-    DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> &ValueLocToPhiMap) {
-
-  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
-    auto *InVal = PN->getIncomingValue(i);
-    auto *InBB = PN->getIncomingBlock(i);
-    ValueLocToPhiMap[std::make_pair(InVal, InBB)] = PN;
-  }
-
-  PNallocMap[PN] = DemotePHIToStack(PN);
-}
-
-/// @brief Prepare the IR for the scop detection.
-///
-class CodePreparation : public FunctionPass {
-  CodePreparation(const CodePreparation &) LLVM_DELETED_FUNCTION;
-  const CodePreparation &
-  operator=(const CodePreparation &) LLVM_DELETED_FUNCTION;
-
-  LoopInfo *LI;
-  ScalarEvolution *SE;
-
-  void clear();
-
-  bool eliminatePHINodes(Function &F);
-
-public:
-  static char ID;
-
-  explicit CodePreparation() : FunctionPass(ID) {}
-  ~CodePreparation();
-
-  /// @name FunctionPass interface.
-  //@{
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-  virtual void releaseMemory();
-  virtual bool runOnFunction(Function &F);
-  virtual void print(raw_ostream &OS, const Module *) const;
-  //@}
-};
-}
-
-void CodePreparation::clear() {}
-
-CodePreparation::~CodePreparation() { clear(); }
-
-bool CodePreparation::eliminatePHINodes(Function &F) {
-  // The PHINodes that will be demoted.
-  std::vector<PHINode *> PNtoDemote;
-  // The PHINodes that will be deleted (stack slot sharing).
-  std::vector<PHINode *> PNtoDelete;
-  // The PHINodes that will be preserved.
-  std::vector<PHINode *> PNtoPreserve;
-  // Map to remember values stored in PHINodes at the end of basic blocks.
-  DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> ValueLocToPhiMap;
-  // Map from PHINodes to their alloca (after demotion) counterpart.
-  DenseMap<PHINode *, AllocaInst *> PNallocMap;
-
-  // Scan the PHINodes in this function and categorize them to be either:
-  // o Preserved, if they are (canonical) induction variables or can be
-  //              synthesized during code generation ('SCEVable')
-  // o Deleted, if they are trivial PHI nodes (one incoming value) and the
-  //            incoming value is a PHI node we will demote
-  // o Demoted, if they do not fit any of the previous categories
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
-    for (BasicBlock::iterator II = BI->begin(), IE = BI->getFirstNonPHI();
-         II != IE; ++II) {
-      PHINode *PN = cast<PHINode>(II);
-      if (SCEVCodegen) {
-        if (SE->isSCEVable(PN->getType())) {
-          const SCEV *S = SE->getSCEV(PN);
-          if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
-            PNtoPreserve.push_back(PN);
-            continue;
-          }
-        }
-      } else {
-        if (Loop *L = LI->getLoopFor(BI)) {
-          // Induction variables will be preserved.
-          if (L->getCanonicalInductionVariable() == PN) {
-            PNtoPreserve.push_back(PN);
-            continue;
-          }
-        }
-      }
-
-      // As DemotePHIToStack does not support invoke edges, we preserve
-      // PHINodes that have invoke edges.
-      if (hasInvokeEdge(PN)) {
-        PNtoPreserve.push_back(PN);
-      } else {
-        if (PN->getNumIncomingValues() == 1)
-          PNtoDelete.push_back(PN);
-        else
-          PNtoDemote.push_back(PN);
-      }
-    }
-
-  if (PNtoDemote.empty() && PNtoDelete.empty())
-    return false;
-
-  while (!PNtoDemote.empty()) {
-    PHINode *PN = PNtoDemote.back();
-    PNtoDemote.pop_back();
-    DemotePHI(PN, PNallocMap, ValueLocToPhiMap);
-  }
-
-  // For each trivial PHI we encountered (and we want to delete) we try to find
-  // the value it will hold in a alloca we already created by PHI demotion. If
-  // we succeed (the incoming value is stored in an alloca at the predecessor
-  // block), we can replace the trivial PHI by the value stored in the alloca.
-  // If not, we will demote this trivial PHI as any other one.
-  for (auto PNIt = PNtoDelete.rbegin(), PNEnd = PNtoDelete.rend();
-       PNIt != PNEnd; ++PNIt) {
-    PHINode *TrivPN = *PNIt;
-    assert(TrivPN->getNumIncomingValues() == 1 && "Assumed trivial PHI");
-
-    auto *InVal = TrivPN->getIncomingValue(0);
-    auto *InBB = TrivPN->getIncomingBlock(0);
-    const auto &ValLocIt = ValueLocToPhiMap.find(std::make_pair(InVal, InBB));
-    if (ValLocIt != ValueLocToPhiMap.end()) {
-      PHINode *InPHI = ValLocIt->second;
-      assert(PNallocMap.count(InPHI) &&
-             "Inconsitent state, PN was not demoted!");
-      auto *InPHIAlloca = PNallocMap[InPHI];
-      PNallocMap[TrivPN] = InPHIAlloca;
-      LoadInst *LI = new LoadInst(InPHIAlloca, "",
-                                  TrivPN->getParent()->getFirstInsertionPt());
-      TrivPN->replaceAllUsesWith(LI);
-      TrivPN->eraseFromParent();
-      continue;
-    }
-
-    DemotePHI(TrivPN, PNallocMap, ValueLocToPhiMap);
-  }
-
-  // Move preserved PHINodes to the beginning of the BasicBlock.
-  while (!PNtoPreserve.empty()) {
-    PHINode *PN = PNtoPreserve.back();
-    PNtoPreserve.pop_back();
-
-    BasicBlock *BB = PN->getParent();
-    if (PN == BB->begin())
-      continue;
-
-    PN->moveBefore(BB->begin());
-  }
-
-  return true;
-}
-
-void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<LoopInfo>();
-  AU.addRequired<ScalarEvolution>();
-
-  AU.addPreserved<LoopInfo>();
-  AU.addPreserved<RegionInfoPass>();
-  AU.addPreserved<DominatorTreeWrapperPass>();
-  AU.addPreserved<DominanceFrontier>();
-}
-
-bool CodePreparation::runOnFunction(Function &F) {
-  LI = &getAnalysis<LoopInfo>();
-  SE = &getAnalysis<ScalarEvolution>();
-
-  splitEntryBlockForAlloca(&F.getEntryBlock(), this);
-
-  eliminatePHINodes(F);
-
-  return false;
-}
-
-void CodePreparation::releaseMemory() { clear(); }
-
-void CodePreparation::print(raw_ostream &OS, const Module *) const {}
-
-char CodePreparation::ID = 0;
-char &polly::CodePreparationID = CodePreparation::ID;
-
-Pass *polly::createCodePreparationPass() { return new CodePreparation(); }
-
-INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare",
-                      "Polly - Prepare code for polly", false, false)
-INITIALIZE_PASS_DEPENDENCY(LoopInfo)
-INITIALIZE_PASS_END(CodePreparation, "polly-prepare",
-                    "Polly - Prepare code for polly", false, false)

lib/Transform/IndependentBlocks.cpp

-//===------ IndependentBlocks.cpp - Create Independent Blocks in Regions --===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Create independent blocks in the regions detected by ScopDetection.
-//
-//===----------------------------------------------------------------------===//
-//
-#include "polly/LinkAllPasses.h"
-#include "polly/Options.h"
-#include "polly/CodeGen/BlockGenerators.h"
-#include "polly/CodeGen/Cloog.h"
-#include "polly/ScopDetection.h"
-#include "polly/Support/ScopHelper.h"
-#include "llvm/Analysis/DominanceFrontier.h"
-#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/PostDominators.h"
-#include "llvm/Analysis/RegionInfo.h"
-#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-
-#include <vector>
-
-using namespace polly;
-using namespace llvm;
-
-#define DEBUG_TYPE "polly-independent"
-
-static cl::opt<bool> DisableIntraScopScalarToArray(
-    "disable-polly-intra-scop-scalar-to-array",
-    cl::desc("Do not rewrite scalar to array to generate independent blocks"),
-    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
-
-namespace {
-struct IndependentBlocks : public FunctionPass {
-  RegionInfo *RI;
-  ScalarEvolution *SE;
-  ScopDetection *SD;
-  LoopInfo *LI;
-
-  BasicBlock *AllocaBlock;
-
-  static char ID;
-
-  IndependentBlocks() : FunctionPass(ID) {}
-
-  // Create new code for every instruction operator that can be expressed by a
-  // SCEV.  Like this there are just two types of instructions left:
-  //
-  // 1. Instructions that only reference loop ivs or parameters outside the
-  // region.
-  //
-  // 2. Instructions that are not used for any memory modification. (These
-  //    will be ignored later on.)
-  //
-  // Blocks containing only these kind of instructions are called independent
-  // blocks as they can be scheduled arbitrarily.
-  bool createIndependentBlocks(BasicBlock *BB, const Region *R);
-  bool createIndependentBlocks(const Region *R);
-
-  // Elimination on the Scop to eliminate the scalar dependences come with
-  // trivially dead instructions.
-  bool eliminateDeadCode(const Region *R);
-
-  //===--------------------------------------------------------------------===//
-  /// Non trivial scalar dependences checking functions.
-  /// Non trivial scalar dependences occur when the def and use are located in
-  /// different BBs and we can not move them into the same one. This will
-  /// prevent use from schedule BBs arbitrarily.
-  ///
-  /// @brief This function checks if a scalar value that is part of the
-  ///        Scop is used outside of the Scop.
-  ///
-  /// @param Use  The use of the instruction.
-  /// @param R    The maximum region in the Scop.
-  ///
-  /// @return Return true if the Use of an instruction and the instruction
-  ///         itself form a non trivial scalar dependence.
-  static bool isEscapeUse(const Value *Use, const Region *R);
-
-  /// @brief This function just checks if a Value is either defined in the same
-  ///        basic block or outside the region, such that there are no scalar
-  ///        dependences between basic blocks that are both part of the same
-  ///        region.
-  ///
-  /// @param Operand  The operand of the instruction.
-  /// @param CurBB    The BasicBlock that contains the instruction.
-  /// @param R        The maximum region in the Scop.
-  ///
-  /// @return Return true if the Operand of an instruction and the instruction
-  ///         itself form a non trivial scalar (true) dependence.
-  bool isEscapeOperand(const Value *Operand, const BasicBlock *CurBB,
-                       const Region *R) const;
-
-  //===--------------------------------------------------------------------===//
-  /// Operand tree moving functions.
-  /// Trivial scalar dependences can eliminate by move the def to the same BB
-  /// that containing use.
-  ///
-  /// @brief Check if the instruction can be moved to another place safely.
-  ///
-  /// @param Inst The instruction.
-  ///
-  /// @return Return true if the instruction can be moved safely, false
-  ///         otherwise.
-  static bool isSafeToMove(Instruction *Inst);
-
-  typedef std::map<Instruction *, Instruction *> ReplacedMapType;
-
-  /// @brief Move all safe to move instructions in the Operand Tree (DAG) to
-  ///        eliminate trivial scalar dependences.
-  ///
-  /// @param Inst         The root of the operand Tree.
-  /// @param R            The maximum region in the Scop.
-  /// @param ReplacedMap  The map that mapping original instruction to the moved
-  ///                     instruction.
-  /// @param InsertPos    The insert position of the moved instructions.
-  void moveOperandTree(Instruction *Inst, const Region *R,
-                       ReplacedMapType &ReplacedMap, Instruction *InsertPos);
-
-  bool isIndependentBlock(const Region *R, BasicBlock *BB) const;
-  bool areAllBlocksIndependent(const Region *R) const;
-
-  // Split the exit block to hold load instructions.
-  bool splitExitBlock(Region *R);
-  bool onlyUsedInRegion(Instruction *Inst, const Region *R);
-  bool translateScalarToArray(BasicBlock *BB, const Region *R);
-  bool translateScalarToArray(Instruction *Inst, const Region *R);
-  bool translateScalarToArray(const Region *R);
-
-  bool runOnFunction(Function &F);
-  void verifyAnalysis() const;
-  void verifyScop(const Region *R) const;
-  void getAnalysisUsage(AnalysisUsage &AU) const;
-};
-}
-
-bool IndependentBlocks::isSafeToMove(Instruction *Inst) {
-  if (Inst->mayReadFromMemory() || Inst->mayWriteToMemory())
-    return false;
-
-  return isSafeToSpeculativelyExecute(Inst);
-}
-
-void IndependentBlocks::moveOperandTree(Instruction *Inst, const Region *R,
-                                        ReplacedMapType &ReplacedMap,
-                                        Instruction *InsertPos) {
-  BasicBlock *CurBB = Inst->getParent();
-
-  // Depth first traverse the operand tree (or operand dag, because we will
-  // stop at PHINodes, so there are no cycle).
-  typedef Instruction::op_iterator ChildIt;
-  std::vector<std::pair<Instruction *, ChildIt>> WorkStack;
-
-  WorkStack.push_back(std::make_pair(Inst, Inst->op_begin()));
-  DenseSet<Instruction *> VisitedSet;
-
-  while (!WorkStack.empty()) {
-    Instruction *CurInst = WorkStack.back().first;
-    ChildIt It = WorkStack.back().second;
-    DEBUG(dbgs() << "Checking Operand of Node:\n" << *CurInst << "\n------>\n");
-    if (It == CurInst->op_end()) {
-      // Insert the new instructions in topological order.
-      if (!CurInst->getParent()) {
-        CurInst->insertBefore(InsertPos);
-        SE->forgetValue(CurInst);
-      }
-
-      WorkStack.pop_back();
-    } else {
-      // for each node N,
-      Instruction *Operand = dyn_cast<Instruction>(*It);
-      ++WorkStack.back().second;
-
-      // Can not move no instruction value.
-      if (Operand == 0)
-        continue;
-
-      DEBUG(dbgs() << "For Operand:\n" << *Operand << "\n--->");
-
-      // If the Scop Region does not contain N, skip it and all its operands and
-      // continue: because we reach a "parameter".
-      // FIXME: we must keep the predicate instruction inside the Scop,
-      // otherwise it will be translated to a load instruction, and we can not
-      // handle load as affine predicate at this moment.
-      if (!R->contains(Operand) && !isa<TerminatorInst>(CurInst)) {
-        DEBUG(dbgs() << "Out of region.\n");
-        continue;
-      }
-
-      if (canSynthesize(Operand, LI, SE, R)) {
-        DEBUG(dbgs() << "is IV.\n");
-        continue;
-      }
-
-      // We can not move the operand, a non trivial scalar dependence found!
-      if (!isSafeToMove(Operand)) {
-        DEBUG(dbgs() << "Can not move!\n");
-        continue;
-      }
-
-      // Do not need to move instruction if it is contained in the same BB with
-      // the root instruction.
-      if (Operand->getParent() == CurBB) {
-        DEBUG(dbgs() << "No need to move.\n");
-        // Try to move its operand, but do not visit an instuction twice.
-        if (VisitedSet.insert(Operand).second)
-          WorkStack.push_back(std::make_pair(Operand, Operand->op_begin()));
-        continue;
-      }
-
-      // Now we need to move Operand to CurBB.
-      // Check if we already moved it.
-      ReplacedMapType::iterator At = ReplacedMap.find(Operand);
-      if (At != ReplacedMap.end()) {
-        DEBUG(dbgs() << "Moved.\n");
-        Instruction *MovedOp = At->second;
-        It->set(MovedOp);
-        SE->forgetValue(MovedOp);
-      } else {
-        // Note that NewOp is not inserted in any BB now, we will insert it when
-        // it popped form the work stack, so it will be inserted in topological
-        // order.
-        Instruction *NewOp = Operand->clone();
-        NewOp->setName(Operand->getName() + ".moved.to." + CurBB->getName());
-        DEBUG(dbgs() << "Move to " << *NewOp << "\n");
-        It->set(NewOp);
-        ReplacedMap.insert(std::make_pair(Operand, NewOp));
-        SE->forgetValue(Operand);
-
-        // Process its operands, but do not visit an instuction twice.
-        if (VisitedSet.insert(NewOp).second)
-          WorkStack.push_back(std::make_pair(NewOp, NewOp->op_begin()));
-      }
-    }
-  }
-
-  SE->forgetValue(Inst);
-}
-
-bool IndependentBlocks::createIndependentBlocks(BasicBlock *BB,
-                                                const Region *R) {
-  std::vector<Instruction *> WorkList;
-  for (Instruction &Inst : *BB)
-    if (!isSafeToMove(&Inst) && !canSynthesize(&Inst, LI, SE, R))
-      WorkList.push_back(&Inst);
-
-  ReplacedMapType ReplacedMap;
-  Instruction *InsertPos = BB->getFirstNonPHIOrDbg();
-
-  for (Instruction *Inst : WorkList)
-    moveOperandTree(Inst, R, ReplacedMap, InsertPos);
-
-  // The BB was changed if we replaced any operand.
-  return !ReplacedMap.empty();
-}
-
-bool IndependentBlocks::createIndependentBlocks(const Region *R) {
-  bool Changed = false;
-
-  for (BasicBlock *BB : R->blocks())
-    Changed |= createIndependentBlocks(BB, R);
-
-  return Changed;
-}
-
-bool IndependentBlocks::eliminateDeadCode(const Region *R) {
-  std::vector<Instruction *> WorkList;
-
-  // Find all trivially dead instructions.
-  for (BasicBlock *BB : R->blocks())
-    for (Instruction &Inst : *BB)
-      if (isInstructionTriviallyDead(&Inst))
-        WorkList.push_back(&Inst);
-
-  if (WorkList.empty())
-    return false;
-
-  // Delete them so the cross BB scalar dependences come with them will
-  // also be eliminated.
-  while (!WorkList.empty()) {
-    RecursivelyDeleteTriviallyDeadInstructions(WorkList.back());
-    WorkList.pop_back();
-  }
-
-  return true;
-}
-
-bool IndependentBlocks::isEscapeUse(const Value *Use, const Region *R) {
-  // Non-instruction user will never escape.
-  if (!isa<Instruction>(Use))
-    return false;
-
-  return !R->contains(cast<Instruction>(Use));
-}
-
-bool IndependentBlocks::isEscapeOperand(const Value *Operand,
-                                        const BasicBlock *CurBB,
-                                        const Region *R) const {
-  const Instruction *OpInst = dyn_cast<Instruction>(Operand);
-
-  // Non-instruction operand will never escape.
-  if (OpInst == 0)
-    return false;
-
-  // Induction variables are valid operands.
-  if (canSynthesize(OpInst, LI, SE, R))
-    return false;
-
-  // A value from a different BB is used in the same region.
-  return R->contains(OpInst) && (OpInst->getParent() != CurBB);
-}
-
-bool IndependentBlocks::splitExitBlock(Region *R) {
-  // Split the exit BB to place the load instruction of escaped users.
-  BasicBlock *ExitBB = R->getExit();
-  Region *ExitRegion = RI->getRegionFor(ExitBB);
-
-  if (ExitBB != ExitRegion->getEntry())
-    return false;
-
-  BasicBlock *NewExit = createSingleExitEdge(R, this);
-
-  std::vector<Region *> toUpdate;
-  toUpdate.push_back(R);
-
-  while (!toUpdate.empty()) {
-    Region *R = toUpdate.back();
-    toUpdate.pop_back();
-
-    for (auto &&SubRegion : *R)
-      if (SubRegion->getExit() == ExitBB)
-        toUpdate.push_back(SubRegion.get());
-
-    R->replaceExit(NewExit);
-  }
-
-  RI->setRegionFor(NewExit, R->getParent());
-  return true;
-}
-
-bool IndependentBlocks::translateScalarToArray(const Region *R) {
-  bool Changed = false;
-
-  for (BasicBlock *BB : R->blocks())
-    Changed |= translateScalarToArray(BB, R);
-
-  return Changed;
-}
-
-// Returns true when Inst is only used inside region R.
-bool IndependentBlocks::onlyUsedInRegion(Instruction *Inst, const Region *R) {
-  for (User *U : Inst->users())
-    if (Instruction *UI = dyn_cast<Instruction>(U))
-      if (isEscapeUse(UI, R))
-        return false;
-
-  return true;
-}
-
-bool IndependentBlocks::translateScalarToArray(Instruction *Inst,
-                                               const Region *R) {
-  if (canSynthesize(Inst, LI, SE, R) && onlyUsedInRegion(Inst, R))
-    return false;
-
-  SmallVector<Instruction *, 4> LoadInside, LoadOutside;
-  for (User *U : Inst->users())
-    // Inst is referenced outside or referenced as an escaped operand.
-    if (Instruction *UI = dyn_cast<Instruction>(U)) {
-      if (isEscapeUse(UI, R))
-        LoadOutside.push_back(UI);
-
-      if (DisableIntraScopScalarToArray)
-        continue;
-
-      if (canSynthesize(UI, LI, SE, R))
-        continue;
-
-      BasicBlock *UParent = UI->getParent();
-      if (R->contains(UParent) && isEscapeOperand(Inst, UParent, R))
-        LoadInside.push_back(UI);
-    }
-
-  if (LoadOutside.empty() && LoadInside.empty())
-    return false;
-
-  // Create the alloca.
-  AllocaInst *Slot = new AllocaInst(
-      Inst->getType(), 0, Inst->getName() + ".s2a", AllocaBlock->begin());
-  assert(!isa<InvokeInst>(Inst) && "Unexpect Invoke in Scop!");
-
-  // Store right after Inst, and make sure the position is after all phi nodes.
-  BasicBlock::iterator StorePos;
-  if (isa<PHINode>(Inst)) {
-    StorePos = Inst->getParent()->getFirstNonPHI();
-  } else {
-    StorePos = Inst;
-    StorePos++;
-  }
-  (void)new StoreInst(Inst, Slot, StorePos);
-
-  if (!LoadOutside.empty()) {
-    LoadInst *ExitLoad = new LoadInst(Slot, Inst->getName() + ".loadoutside",
-                                      false, R->getExit()->getFirstNonPHI());
-
-    while (!LoadOutside.empty()) {
-      Instruction *U = LoadOutside.pop_back_val();
-      SE->forgetValue(U);
-      U->replaceUsesOfWith(Inst, ExitLoad);
-    }
-  }
-
-  while (!LoadInside.empty()) {
-    Instruction *U = LoadInside.pop_back_val();
-    assert(!isa<PHINode>(U) && "Can not handle PHI node inside!");
-    SE->forgetValue(U);
-    LoadInst *L = new LoadInst(Slot, Inst->getName() + ".loadarray", false, U);
-    U->replaceUsesOfWith(Inst, L);
-  }
-
-  return true;
-}
-
-bool IndependentBlocks::translateScalarToArray(BasicBlock *BB,
-                                               const Region *R) {
-  bool changed = false;
-
-  SmallVector<Instruction *, 32> Insts;
-  for (BasicBlock::iterator II = BB->begin(), IE = --BB->end(); II != IE; ++II)
-    Insts.push_back(II);
-
-  while (!Insts.empty()) {
-    Instruction *Inst = Insts.pop_back_val();
-    changed |= translateScalarToArray(Inst, R);
-  }
-
-  return changed;
-}
-
-bool IndependentBlocks::isIndependentBlock(const Region *R,
-                                           BasicBlock *BB) const {
-  for (Instruction &Inst : *BB) {
-    if (canSynthesize(&Inst, LI, SE, R))
-      continue;
-
-    // A value inside the Scop is referenced outside.
-    for (User *U : Inst.users()) {
-      if (isEscapeUse(U, R)) {
-        DEBUG(dbgs() << "Instruction not independent:\n");
-        DEBUG(dbgs() << "Instruction used outside the Scop!\n");
-        DEBUG(Inst.print(dbgs()));
-        DEBUG(dbgs() << "\n");
-        return false;
-      }
-    }
-
-    if (DisableIntraScopScalarToArray)
-      continue;
-
-    for (Value *Op : Inst.operands()) {
-      if (isEscapeOperand(Op, BB, R)) {
-        DEBUG(dbgs() << "Instruction in function '";
-              BB->getParent()->printAsOperand(dbgs(), false);
-              dbgs() << "' not independent:\n");
-        DEBUG(dbgs() << "Uses invalid operator\n");
-        DEBUG(Inst.print(dbgs()));
-        DEBUG(dbgs() << "\n");
-        DEBUG(dbgs() << "Invalid operator is: ";
-              Op->printAsOperand(dbgs(), false); dbgs() << "\n");
-        return false;
-      }
-    }
-  }
-
-  return true;
-}
-
-bool IndependentBlocks::areAllBlocksIndependent(const Region *R) const {
-  for (BasicBlock *BB : R->blocks())
-    if (!isIndependentBlock(R, BB))
-      return false;
-
-  return true;
-}
-
-void IndependentBlocks::getAnalysisUsage(AnalysisUsage &AU) const {
-  // FIXME: If we set preserves cfg, the cfg only passes do not need to
-  // be "addPreserved"?
-  AU.addPreserved<DominatorTreeWrapperPass>();
-  AU.addPreserved<DominanceFrontier>();
-  AU.addPreserved<PostDominatorTree>();
-  AU.addRequired<RegionInfoPass>();
-  AU.addPreserved<RegionInfoPass>();
-  AU.addRequired<LoopInfo>();
-  AU.addPreserved<LoopInfo>();
-  AU.addRequired<ScalarEvolution>();
-  AU.addPreserved<ScalarEvolution>();
-  AU.addRequired<ScopDetection>();
-  AU.addPreserved<ScopDetection>();
-#ifdef CLOOG_FOUND
-  AU.addPreserved<CloogInfo>();
-#endif
-}
-
-bool IndependentBlocks::runOnFunction(llvm::Function &F) {
-  bool Changed = false;
-
-  RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
-  LI = &getAnalysis<LoopInfo>();
-  SD = &getAnalysis<ScopDetection>();
-  SE = &getAnalysis<ScalarEvolution>();
-
-  AllocaBlock = &F.getEntryBlock();
-
-  DEBUG(dbgs() << "Run IndepBlock on " << F.getName() << '\n');
-
-  for (const Region *R : *SD) {
-    Changed |= createIndependentBlocks(R);
-    Changed |= eliminateDeadCode(R);
-    // This may change the RegionTree.
-    Changed |= splitExitBlock(const_cast<Region *>(R));
-  }
-
-  DEBUG(dbgs() << "Before Scalar to Array------->\n");
-  DEBUG(F.dump());
-
-  for (const Region *R : *SD)
-    Changed |= translateScalarToArray(R);
-
-  DEBUG(dbgs() << "After Independent Blocks------------->\n");
-  DEBUG(F.dump());
-
-  verifyAnalysis();
-
-  return Changed;
-}
-
-void IndependentBlocks::verifyAnalysis() const {
-  for (const Region *R : *SD)
-    verifyScop(R);
-}
-
-void IndependentBlocks::verifyScop(const Region *R) const {
-  assert(areAllBlocksIndependent(R) && "Cannot generate independent blocks");
-}
-
-char IndependentBlocks::ID = 0;
-char &polly::IndependentBlocksID = IndependentBlocks::ID;
-
-Pass *polly::createIndependentBlocksPass() { return new IndependentBlocks(); }
-
-INITIALIZE_PASS_BEGIN(IndependentBlocks, "polly-independent",
-                      "Polly - Create independent blocks", false, false);
-INITIALIZE_PASS_DEPENDENCY(LoopInfo);
-INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
-INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
-INITIALIZE_PASS_DEPENDENCY(ScopDetection);
-INITIALIZE_PASS_END(IndependentBlocks, "polly-independent",
-                    "Polly - Create independent blocks", false, false)

test/Cloog/CodeGen/constant_condition.ll

-;RUN: opt %loadPolly -polly-prepare -polly-detect-scops-in-regions-without-loops -polly-detect-scops-in-functions-without-loops -polly-cloog -analyze < %s | FileCheck %s
+;RUN: opt %loadPolly -polly-detect-scops-in-regions-without-loops -polly-detect-scops-in-functions-without-loops -polly-cloog -analyze < %s | FileCheck %s
 
 ;#include <string.h>
 ;int A[1];
 ;
 ;void constant_condition () {
 ;  int a = 0;
 ;  int b = 0;
 ;

test/CodePreparation/if_condition.ll

-; RUN: opt %loadPolly -polly-prepare -S < %s | FileCheck %s
-; RUN: opt %loadPolly -polly-prepare -S -polly-codegen-scev < %s | FileCheck %s
-
-; void f(long A[], long N) {
-;   long i;
-;   for (i = 0; i < N; ++i)
-;     A[i] = 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"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @f(i64* %A, i64 %N) nounwind {
-entry:
-  fence seq_cst
-  br label %for.i
-; CHECK: entry:
-; CHECK: %value.reg2mem = alloca i64
-; CHECK: br label %entry.split
-
-for.i:
-  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %merge ]
-  %scevgep = getelementptr i64* %A, i64 %indvar
-  %cmp = icmp eq i64 %indvar, 3
-  br i1 %cmp, label %then, label %else
-
-then:
-  %add_two = add i64 %indvar, 2
-  br label %merge
-; CHECK: then:
-; CHECK:   %add_two = add i64 %indvar, 2
-; CHECK:   store i64 %add_two, i64* %value.reg2mem
-; CHECK:   br label %merge
-
-else:
-  %add_three = add i64 %indvar, 4
-  br label %merge
-; CHECK: else:
-; CHECK:   %add_three = add i64 %indvar, 4
-; CHECK:   store i64 %add_three, i64* %value.reg2mem
-; CHECK:   br label %merge
-
-merge:
-  %value = phi i64 [ %add_two, %then ], [ %add_three, %else ]
-  store i64 %value, i64* %scevgep
-  %indvar.next = add nsw i64 %indvar, 1
-  %exitcond = icmp eq i64 %indvar.next, %N
-  br i1 %exitcond, label %return, label %for.i
-
-return:
-  fence seq_cst
-  ret void
-}

test/CodePreparation/multiple_loops_trivial_phis.ll

-; RUN: opt %loadPolly -S -polly-prepare < %s | FileCheck %s
-; ModuleID = 'multiple_loops_trivial_phis.ll'
-;
-; int f(int * __restrict__ A) {
-;   int i, j, sum = 0;
-;   for (i = 0; i < 100; i++) {
-;     sum *= 2;
-;     for (j = 0; j < 100; j++) {
-;       sum += A[i+j];
-;     }
-;   }
-;   return sum;
-; }
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-; Function Attrs: nounwind uwtable
-define i32 @f(i32* noalias %A) #0 {
-entry:
-  br label %for.body
-
-for.body:                                         ; preds = %entry, %for.inc5
-  %sum.04 = phi i32 [ 0, %entry ], [ %add4.lcssa, %for.inc5 ]
-  %indvars.iv23 = phi i64 [ 0, %entry ], [ %2, %for.inc5 ]
-  %mul = shl nsw i32 %sum.04, 1
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body, %for.inc
-  %sum.12 = phi i32 [ %mul, %for.body ], [ %add4, %for.inc ]
-  %indvars.iv1 = phi i64 [ 0, %for.body ], [ %1, %for.inc ]
-  %0 = add i64 %indvars.iv23, %indvars.iv1
-  %arrayidx = getelementptr i32* %A, i64 %0
-  %tmp5 = load i32* %arrayidx, align 4
-  %add4 = add nsw i32 %tmp5, %sum.12
-  %1 = add nuw nsw i64 %indvars.iv1, 1
-  %exitcond5 = icmp eq i64 %1, 100
-  br i1 %exitcond5, label %for.inc5, label %for.inc
-
-for.inc5:                                         ; preds = %for.inc
-  %add4.lcssa = phi i32 [ %add4, %for.inc ]
-  %2 = add nuw nsw i64 %indvars.iv23, 1
-  %exitcond = icmp eq i64 %2, 100
-  br i1 %exitcond, label %for.end7, label %for.body
-
-for.end7:                                         ; preds = %for.inc5
-  %add4.lcssa.lcssa = phi i32 [ %add4.lcssa, %for.inc5 ]
-  ret i32 %add4.lcssa.lcssa
-}
-
-attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
-
-; Verify that only two allocas are created. (instead of 4!)
-; CHECK: alloca
-; CHECK: alloca
-; CHECK-NOT: alloca

test/CodePreparation/single_loop_trivial_phi.ll

-; RUN: opt %loadPolly -S -polly-prepare < %s | FileCheck %s
-; ModuleID = 'single_loop_trivial_phi.ll'
-;
-; int f(int *A, int N) {
-;   int i, sum = 0;
-;   for (i = 0; i < N; i++)
-;     sum += A[i];
-;   return sum;
-; }
-; ModuleID = 'stack-slots.ll'
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-; Function Attrs: nounwind uwtable
-define i32 @f(i32* %A, i32 %N) #0 {
-entry:
-  %cmp1 = icmp sgt i32 %N, 0
-  br i1 %cmp1, label %for.inc.lr.ph, label %for.end
-
-for.inc.lr.ph:                                    ; preds = %entry
-  %0 = zext i32 %N to i64
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.inc.lr.ph, %for.inc
-  %sum.03 = phi i32 [ 0, %for.inc.lr.ph ], [ %add, %for.inc ]
-  %indvars.iv2 = phi i64 [ 0, %for.inc.lr.ph ], [ %indvars.iv.next, %for.inc ]
-  %arrayidx = getelementptr i32* %A, i64 %indvars.iv2
-  %tmp1 = load i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp1, %sum.03
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv2, 1
-  %exitcond = icmp ne i64 %indvars.iv.next, %0
-  br i1 %exitcond, label %for.inc, label %for.cond.for.end_crit_edge
-
-for.cond.for.end_crit_edge:                       ; preds = %for.inc
-  %add.lcssa = phi i32 [ %add, %for.inc ]
-  br label %for.end
-
-for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
-  %sum.0.lcssa = phi i32 [ %add.lcssa, %for.cond.for.end_crit_edge ], [ 0, %entry ]
-  ret i32 %sum.0.lcssa
-}
-
-attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
-
-; Verify that only two allocas are created.
-; Both are needed for the %sum.0 PHI node and none should be created for the
-; %sum.0.lcssa PHI node
-; CHECK: alloca
-; CHECK: alloca
-; CHECK-NOT: alloca

test/IndependentBlocks/inter_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-independent -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -S < %s | FileCheck %s -check-prefix=SCALARACCESS
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev -disable-polly-intra-scop-scalar-to-array -S < %s | FileCheck %s -check-prefix=SCALARACCESS
-
-; 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"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
-entry:
-
-; CHECK: entry
-; CHECK: %init.s2a = alloca i64
-; CHECK: br label %for.i
-
-; SCALARACCESS-NOT: alloca
-  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:
-  %init = load i64* %init_ptr
-; SCALARACCESS-NOT: store
-  br label %for.j
-
-for.j:
-  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
-  %init_plus_two = add i64 %init, 2
-; CHECK: %init.loadarray = load i64* %init.s2a
-; CHECK: %init_plus_two = add i64 %init.loadarray, 2
-; SCALARACCESS: %init_plus_two = add i64 %init, 2
-  %scevgep = getelementptr 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
-}

test/IndependentBlocks/intra_and_inter_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-independent -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -S < %s | FileCheck %s -check-prefix=SCALARACCESS
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -polly-codegen-scev -S < %s | FileCheck %s -check-prefix=SCALARACCESS
-
-; 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"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
-entry:
-
-; CHECK: entry
-; CHECK: %init.s2a = alloca i64
-; CHECK: br label %for.i
-
-; SCALARACCESS-NOT: alloca
-  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:
-  %init = load i64* %init_ptr
-; SCALARACCESS-NOT: store
-  br label %for.j
-
-for.j:
-  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
-  %init_2 = load i64* %init_ptr
-  %init_sum = add i64 %init, %init_2
-; CHECK: %init_2 = load i64* %init_ptr
-; CHECK: %init.loadarray = load i64* %init.s2a
-; CHECK: %init_sum = add i64 %init.loadarray, %init_2
-
-; The SCEV of %init_sum is (%init + %init_2). It is referring to both an
-; UnknownValue in the same and in a different basic block. We want only the
-; reference to the different basic block to be replaced.
-
-; SCALARACCESS: %init_2 = load i64* %init_ptr
-; SCALARACCESS: %init_sum = add i64 %init, %init_2
-  %scevgep = getelementptr 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:
-  %exitcond.i = icmp eq i64 %indvar.i.next, %N
-  br i1 %exitcond.i, label %return, label %for.i
-
-return:
-  ret void
-}

test/IndependentBlocks/intra_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-independent -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -polly-codegen-scev -S < %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"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
-entry:
-
-; CHECK: entry
-; CHECK: br label %for.i
-  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:
-  br label %for.j
-
-for.j:
-  %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
-  %init = load i64* %init_ptr
-  %init_plus_two = add i64 %init, 2
-; The scalar evolution of %init_plus_two is (2 + %init). So we have a
-; non-trivial scalar evolution referring to a value in the same basic block.
-; We want to ensure that this scalar is not translated into a memory copy.
-  %scevgep = getelementptr 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
-}

test/IndependentBlocks/phi_outside_scop.ll

-; RUN: opt %loadPolly -basicaa -polly-independent -S < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev -S < %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-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @phi_nodes_outside() {
-entry:
-  br label %for.i.1
-
-for.i.1:
-  %i.1 = phi i32 [ %i.1.next, %for.i.1 ], [ 0, %entry ]
-  %i.1.next = add nsw i32 %i.1, 1
-  br i1 false, label %for.i.1 , label %for.i.2.preheader
-
-for.i.2.preheader:
-  br label %for.i.2
-
-for.i.2:
-; The value of %i.1.next is used outside of the scop in a PHI node.
-  %i.2 = phi i32 [ %i.2.next , %for.i.2 ], [ %i.1.next, %for.i.2.preheader ]
-  %i.2.next = add nsw i32 %i.2, 1
-  fence seq_cst
-  br i1 false, label %for.i.2, label %cleanup
-
-cleanup:
-  ret void
-}
-
-; CHECK:  store i32 %i.1.next, i32* %i.1.next.s2a
-
-; CHECK: for.i.2.preheader:
-; CHECK:    %i.1.next.loadoutside = load i32* %i.1.next.s2a
-
-; CHECK: for.i.2:
-; CHECK:    %i.2 = phi i32 [ %i.2.next, %for.i.2 ], [ %i.1.next.loadoutside, %for.i.2.preheader ]
-

test/IndependentBlocks/scalar_to_array.ll

-; RUN: opt %loadPolly -basicaa -polly-independent < %s -S | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -polly-codegen-scev < %s -S | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -S < %s | FileCheck %s -check-prefix=SCALARACCESS
-; RUN: opt %loadPolly -basicaa -polly-independent -disable-polly-intra-scop-scalar-to-array -polly-codegen-scev < %s -S | FileCheck %s -check-prefix=SCALARACCESS
-
-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"
-target triple = "x86_64-unknown-linux-gnu"
-
-@A = common global [1024 x float] zeroinitializer, align 8
-
-define i32 @empty() nounwind {
-entry:
-  fence seq_cst
-  br label %for.cond
-
-for.cond:
-  %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:
-  br label %for.inc
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  br label %for.cond
-
-return:
-  fence seq_cst
-  ret i32 0
-}
-
-
-; CHECK: @array_access()
-define i32 @array_access() nounwind {
-entry:
-  fence seq_cst
-  br label %for.cond
-; CHECK: entry:
-; CHECK-NOT: alloca
-; SCALARACCESS: entry:
-; SCALARACCESS-NOT: alloca
-
-for.cond:
-  %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:
-  %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-  %float = uitofp i64 %indvar to float
-  store float %float, float* %arrayidx
-  br label %for.inc
-
-; CHECK: for.body:
-; CHECK: %float = uitofp i64 %indvar to float
-; CHECK: store float %float, float* %arrayidx
-; SCALARACCESS: for.body:
-; SCALARACCESS: %float = uitofp i64 %indvar to float
-; SCALARACCESS: store float %float, float* %arrayidx
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  br label %for.cond
-
-return:
-  fence seq_cst
-  ret i32 0
-}
-
-; CHECK: @intra_scop_dep()
-define i32 @intra_scop_dep() nounwind {
-entry:
-  fence seq_cst
-  br label %for.cond
-
-; CHECK: entry:
-; CHECK: %scalar.s2a = alloca float
-; CHECK: fence
-; SCALARACCESS: entry:
-; SCALARACCESS-NOT: alloca
-; SCALARACCESS: fence
-
-for.cond:
-  %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:
-  %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-  %scalar = load float* %arrayidx
-  br label %for.body.b
-
-; CHECK: for.body.a:
-; CHECK: %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-; CHECK: %scalar = load float* %arrayidx
-; CHECK: store float %scalar, float* %scalar.s2a
-; CHECK: br label %for.body.b
-
-; SCALARACCESS: for.body.a:
-; SCALARACCESS: %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-; SCALARACCESS: %scalar = load float* %arrayidx
-; SCALARACCESS-NOT: store
-; SCALARACCESS: br label %for.body.b
-
-for.body.b:
-  %arrayidx2 = getelementptr [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: for.body.b:
-; CHECK: %arrayidx2 = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-; CHECK: %float = uitofp i64 %indvar to float
-; CHECK: %scalar.loadarray = load float* %scalar.s2a
-; CHECK: %sum = fadd float %scalar.loadarray, %float
-; CHECK: store float %sum, float* %arrayidx2
-; CHECK: br label %for.inc
-
-; SCALARACCESS: for.body.b:
-; SCALARACCESS: %arrayidx2 = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-; SCALARACCESS: %float = uitofp i64 %indvar to float
-; SCALARACCESS-NOT: load
-; SCALARACCESS: %sum = fadd float %scalar, %float
-; SCALARACCESS: store float %sum, float* %arrayidx2
-; SCALARACCESS: br label %for.inc
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  br label %for.cond
-
-return:
-  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: @use_after_scop()
-define i32 @use_after_scop() nounwind {
-entry:
-  fence seq_cst
-  br label %for.head
-; CHECK: entry:
-; CHECK: %scalar.s2a = alloca float
-; CHECK: fence
-
-; SCALARACCESS: entry:
-; SCALARACCESS: %scalar.s2a = alloca float
-; SCALARACCESS: fence
-
-for.head:
-  %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
-  br label %for.body
-
-for.body:
-  %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-  %scalar = load float* %arrayidx
-  br label %for.inc
-
-; CHECK: for.body:
-; CHECK: %scalar = load float* %arrayidx
-; CHECK: store float %scalar, float* %scalar.s2a
-
-; SCALARACCESS: for.body:
-; SCALARACCESS: %scalar = load float* %arrayidx
-; SCALARACCESS: store float %scalar, float* %scalar.s2a
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  %exitcond = icmp ne i64 %indvar, 1024
-  br i1 %exitcond, label %for.head, label %for.after
-
-for.after:
-  fence seq_cst
-  %return_value = fptosi float %scalar to i32
-  br label %return
-
-; CHECK: for.after:
-; CHECK: %scalar.loadoutside = load float* %scalar.s2a
-; CHECK: fence seq_cst
-; CHECK: %return_value = fptosi float %scalar.loadoutside to i32
-
-; SCALARACCESS: for.after:
-; SCALARACCESS: %scalar.loadoutside = load float* %scalar.s2a
-; SCALARACCESS: fence seq_cst
-; SCALARACCESS: %return_value = fptosi float %scalar.loadoutside to i32
-
-return:
-  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: @before_scop()
-define i32 @before_scop() nounwind {
-entry:
-  br label %preheader
-
-preheader:
-  %scalar = fadd float 4.0, 5.0
-  fence seq_cst
-  br label %for.cond
-
-for.cond:
-  %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:
-  %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-  store float %scalar, float* %arrayidx
-  br label %for.inc
-
-; CHECK: for.body:
-; CHECK: store float %scalar, float* %arrayidx
-
-; SCALARACCESS: for.body:
-; SCALARACCESS: store float %scalar, float* %arrayidx
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  br label %for.cond
-
-return:
-  fence seq_cst
-  ret i32 0
-}
-
-; Currently not working
-; CHECK: @param_before_scop(
-define i32 @param_before_scop(float %scalar) nounwind {
-entry:
-  fence seq_cst
-  br label %for.cond
-; CHECK: entry:
-; CHECK: fence
-
-for.cond:
-  %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:
-  %arrayidx = getelementptr [1024 x float]* @A, i64 0, i64 %indvar
-  store float %scalar, float* %arrayidx
-  br label %for.inc
-
-; CHECK: for.body:
-; CHECK: store float %scalar, float* %arrayidx
-
-for.inc:
-  %indvar.next = add i64 %indvar, 1
-  br label %for.cond
-
-return:
-  fence seq_cst
-  ret i32 0
-}

test/IndependentBlocks/scev-invalidated.ll

-; RUN: opt %loadPolly -polly-codegen-scev -polly-independent < %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-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @arc_either() {
-entry:
-  %ang2.2.reg2mem = alloca i64
-  br i1 undef, label %return, label %if.then6
-
-if.then6:
-  %rem7 = srem i64 undef, 1474560
-  br i1 false, label %if.else, label %return
-
-if.else:
-  %add16 = add nsw i64 %rem7, 1474560
-  %rem7.add16 = select i1 undef, i64 %rem7, i64 %add16
-  store i64 %rem7.add16, i64* %ang2.2.reg2mem
-  br label %return
-
-return:
-  ret void
-}

test/Isl/Ast/dependence_distance_parametric_expr.ll

 ; RUN: opt %loadPolly -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s
 ;
 ;        void f(int *A, int N, int c, int v) {
 ; CHECK:   #pragma minimal dependence distance: 1
 ;          for (int j = 0; j < N; j++)
-; CHECK:     #pragma minimal dependence distance: c + v >= 1 ? c + v : -c - v
+; CHECK:     #pragma minimal dependence distance: v + c >= 1 ? v + c : -v - c
 ;            for (int i = 0; i < N; i++)
 ;              A[i + c + v] = A[i] + 1;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A, i32 %N, i32 %c, i32 %v) {
 entry:

test/Isl/CodeGen/constant_condition.ll

-;RUN: opt %loadPolly -polly-prepare -polly-detect-scops-in-regions-without-loops -polly-detect-scops-in-functions-without-loops -polly-ast -analyze < %s | FileCheck %s
+;RUN: opt %loadPolly -polly-detect-scops-in-regions-without-loops -polly-detect-scops-in-functions-without-loops -polly-ast -analyze < %s | FileCheck %s
 
 ;#include <string.h>
 ;int A[1];
 ;
 ;void constant_condition () {
 ;  int a = 0;
 ;  int b = 0;
 ;

test/Isl/CodeGen/loop_with_condition_nested.ll

 ; CHECK:   } else if (c1 <= 512)
 ; CHECK:     Stmt_6(c1);
 ; CHECK:   Stmt_9(c1);
 ; CHECK: }
 
 ; LOOPS: Printing analysis 'Natural Loop Information' for function 'loop_with_condition':
 ; LOOPS: Loop at depth 1 containing: %1<header><exiting>,%2,%4,%7,%6,%8,%9,%10<latch>
 ; LOOPS: Loop at depth 1 containing:
-; LOOPS: %polly.loop_header<header>,%polly.cond,%polly.merge,%polly.then,%polly.else,%polly.stmt.,%polly.cond3,%polly.merge4,%polly.then5,%polly.else6,%polly.stmt.7,%polly.stmt.8<latch><exiting>
+; LOOPS: %polly.loop_header<header>,%polly.cond,%polly.merge,%polly.then,%polly.else,%polly.stmt.,%polly.cond3,%polly.merge4,%polly.then5,%polly.else6,%polly.stmt.7,%polly.stmt.9<latch><exiting>

test/ScopDetect/simple_loop_two_phi_nodes.ll

 ; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -polly-detect -polly-codegen-scev -analyze < %s | FileCheck %s -check-prefix=CHECK-SCEV
 
 ; void f(long A[], long N) {
 ;   long i;
 ;   long i_non_canonical = 1;
 ;   for (i = 0; i < N; ++i) {
 ;     A[i] = i_non_canonical;
 ;     i_non_canonical += 1;
 ;   }
for.i:
   %indvar_non_canonical.next = add nsw i64 %indvar_non_canonical, 1
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   ret void
 }
 
-; CHECK-NOT: Valid Region for Scop
-; CHECK-SCEV: Valid Region for Scop: for.i => return
+; CHECK: Valid Region for Scop: for.i => return

test/ScopInfo/bug_2011_1_5.ll

-; RUN: opt %loadPolly -polly-analyze-ir -analyze < %s
-
-; Bug description: Alias Analysis thinks IntToPtrInst aliases with alloca instructions created by IndependentBlocks Pass.
-;                  This will trigger the assertion when we are verifying the SCoP after IndependentBlocks.
-
-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"
-target triple = "x86_64-unknown-linux-gnu"
-
-%struct.precisionType = type { i16, i16, i16, i8, [1 x i16] }
-
-define void @main() nounwind {
-entry:
- br label %bb1.i198.i
-
-bb1.i198.i:                                       ; preds = %bb.i197.i, %psetq.exit196.i
-  %tmp51.i = inttoptr i64 0 to %struct.precisionType*
-  br i1 undef, label %bb1.i210.i, label %bb.i209.i
-
-bb.i209.i:                                        ; preds = %bb1.i198.i
-  br label %bb1.i210.i
-
-bb1.i210.i:                                       ; preds = %bb.i209.i, %bb1.i198.i
-  %0 = icmp eq i64 0, 0
-  br i1 %0, label %bb1.i216.i, label %bb.i215.i
-
-bb.i215.i:                                        ; preds = %bb1.i210.i
-  %1 = getelementptr inbounds %struct.precisionType* %tmp51.i, i64 0, i32 0
-  store i16 undef, i16* %1, align 2
-  br label %bb1.i216.i
-
-bb1.i216.i:                                       ; preds = %bb.i215.i, %bb1.i210.i
-  br i1 undef, label %psetq.exit220.i, label %bb2.i217.i
-
-bb2.i217.i:                                       ; preds = %bb1.i216.i
-  br i1 undef, label %bb3.i218.i, label %psetq.exit220.i
-
-bb3.i218.i:                                       ; preds = %bb2.i217.i
-  br label %psetq.exit220.i
-
-psetq.exit220.i:                                  ; preds = %bb3.i218.i, %bb2.i217.i, %bb1.i216.i
-  br i1 undef, label %bb14.i76, label %bb15.i77
-
-bb14.i76:                                         ; preds = %psetq.exit220.i
-  unreachable
-
-bb15.i77:                                         ; preds = %psetq.exit220.i
-  br i1 %0, label %psetq.exit238.i, label %bb2.i235.i
-
-bb2.i235.i:                                       ; preds = %bb15.i77
-  br i1 undef, label %bb3.i236.i, label %psetq.exit238.i
-
-bb3.i236.i:                                       ; preds = %bb2.i235.i
-  unreachable
-
-psetq.exit238.i:                                  ; preds = %bb2.i235.i, %bb15.i77
-  unreachable
-
-bb56.i.loopexit:                                  ; preds = %psetq.exit172.i
-  unreachable
-}

test/ScopInfo/loop_carry.ll

-; RUN: opt %loadPolly -basicaa -polly-prepare -polly-scops -analyze  < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -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-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 ;long f(long a[], long n) {
 ;  long i, k;
 ;  k = 1;
 ;  for (i = 1; i < n; ++i) {

test/ScopInfo/phi_not_grouped_at_top.ll

-; RUN: opt %loadPolly -polly-prepare  -analyze  < %s
+; RUN: opt %loadPolly -analyze  < %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-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 declare i32 @funa() align 2
 
 declare i32 @generic_personality_v0(i32, i64, i8*, i8*)
 
 define void @funb() align 2 {

test/ScopInfo/phi_scalar_simple_1.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    int jd(int *restrict A, int x) {
+;      for (int i = 0; i < 32; i++)
+;        for (int j = 0; j < 32; j++)
+;          x += A[i];
+;      return x;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @jd(i32* noalias %A, i32 %x) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc4, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1.lcssa, %for.inc4 ]
+  %cmp = icmp slt i64 %indvars.iv, 32
+  br i1 %cmp, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+; CHECK:  Domain :=
+; CHECK:      { Stmt_for_cond1[i0, i1] : i0 >= 0 and i0 <= 31 and i1 >= 0 and i1 <= 32 };
+  %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %add, %for.inc ]
+; CHECK:  MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:      { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:  ReadAccess := [Reduction Type: NONE]
+; CHECK:      { Stmt_for_cond1[i0, i1] -> MemRef_add[] : i0 >= 0 and i0 <= 31 and i1 >= 1 and i1 <= 32 };
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, 32
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+; CHECK:  Domain :=
+; CHECK:      { Stmt_for_inc[i0, i1] : i0 >= 0 and i0 <= 31 and i1 >= 0 and i1 <= 31 };
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp1 = load i32* %arrayidx, align 4
+; CHECK-DAG:  ReadAccess := [Reduction Type: NONE]
+; CHECK-DAG:      { Stmt_for_inc[i0, i1] -> MemRef_A[i0] };
+  %add = add nsw i32 %x.addr.1, %tmp1
+; CHECK-DAG:  ReadAccess := [Reduction Type: NONE]
+; CHECK-DAG:      { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK-DAG:  MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK-DAG:      { Stmt_for_inc[i0, i1] -> MemRef_add[] };
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  %x.addr.1.lcssa = phi i32 [ %x.addr.1, %for.cond1 ]
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  %x.addr.0.lcssa = phi i32 [ %x.addr.0, %for.cond ]
+  ret i32 %x.addr.0.lcssa
+}

test/ScopInfo/phi_with_invoke_edge.ll

-; RUN: opt %loadPolly -polly-prepare -polly-detect  -analyze  < %s
+; RUN: opt %loadPolly -polly-detect  -analyze  < %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-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 declare i32 @generic_personality_v0(i32, i64, i8*, i8*)
 
 define i16 @v() {
 entry:
   br i1 undef, label %bb16, label %invcont12

test/ScopInfo/scalar.ll

-; RUN: opt %loadPolly -polly-scops -analyze -disable-polly-intra-scop-scalar-to-array < %s | FileCheck %s
+; RUN: opt %loadPolly -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"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @f(i64* %a, i64 %N) {
 entry:
   br label %for
 

test/TempScop/inter_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-analyze-ir  -polly-codegen-scev -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir  -polly-codegen-scev -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;

test/TempScop/intra_and_inter_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -polly-codegen-scev -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -polly-codegen-scev -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;

test/TempScop/intra_bb_scalar_dep.ll

-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-analyze-ir  -polly-codegen-scev -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir  -polly-codegen-scev -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;

test/TempScop/scalar_to_array.ll

-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -disable-polly-intra-scop-scalar-to-array -polly-codegen-scev -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-analyze-ir -polly-codegen-scev -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"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [1024 x float] zeroinitializer, align 8
 
 ; CHECK: empty

test/TempScop/tempscop-printing.ll

 ; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze -disable-polly-intra-scop-scalar-to-array < %s | FileCheck %s -check-prefix=SCALARACCESS
 
 ; 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;

 
 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: BB: entry.next
-; SCALARACCESS: BB: entry.next
   %init = load i64* %init_ptr
-; CHECK:  Read init_ptr[0]
-; CHECK:  Write init.s2a[0]
-; SCALARACCESS: Read init_ptr[0]
-; SCALARACCESS:  Write init[0]
+; CHECK: Read init_ptr[0]
+; CHECK:  Write init[0]
   br label %for.j
 
 for.j:
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
 ; CHECK: BB: for.j
-; CHECK: Read init.s2a[0]
+; CHECK: Read init
 ; CHECK: Write A[{0,+,8}<%for.j>]
-
-; SCALARACCESS: BB: for.j
-; SCALARACCESS: Read init
-; SCALARACCESS: Write A[{0,+,8}<%for.j>]
   %init_plus_two = add i64 %init, 2
   %scevgep = getelementptr 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:
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:
-; SCALARACCESS: BB: entry.next
+; CHECK: BB: entry.next
   %init = load i64* %init_ptr
-; SCALARACCESS: Read init_ptr[0]
-; SCALARACCESS:  Write init[0]
+; CHECK: Read init_ptr[0]
+; CHECK:  Write init[0]
   br label %for.j
 
 for.j:
-; SCALARACCESS: BB: for.j
+; CHECK: BB: for.j
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
   %scevgep = getelementptr i64* %A, i64 %indvar.j
   store i64 %init, i64* %scevgep
-; SCALARACCESS: Read init
-; SCALARACCESS: Write A[{0,+,8}<%for.j>]
+; CHECK: Read init
+; CHECK: Write A[{0,+,8}<%for.j>]
   %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
 }

www/documentation/passes.html

<div id="content">
   <!--*********************************************************************-->
   <h1>The available LLVM passes</h1>
   <!--*********************************************************************-->
 
   <p>Polly consists of a set of LLVM passes.  </p>
 
 <h2>Front End</h2>
 <ul>
-<li><em>polly-prepare</em> Prepare code for Polly</li>
 <li><em>polly-detect</em> Detect SCoPs in functions</li>
 <li><em>polly-analyze-ir</em> Analyse the LLVM-IR in the detected SCoPs</li>
 <li><em>polly-independent</em> Create independent blocks</li>
 <li><em>polly-scops</em> Create polyhedral description of SCoPs</li>
 </ul>
 <h2>Middle End</h2>
 <ul>
 <li><em>polly-dependences</em> Calculate the dependences in a SCoPs</li>