[Polly][PoC] First 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)

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

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 Domain    A restricted domain for this access if applicable.
+  /// @param Statement The statement that contains the access.
+  MemoryAccess(PHINode *PHI, const ScopArrayInfo *SAI,
+               __isl_keep isl_set *Domain, 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; }
 
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);
+  void buildPHIAccesses(PHINode *PHI, const IRAccess &Access,
+                        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;
 
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);

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

for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) {
     }
 
     isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
 
     AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
   }
 
   Space = Statement->getDomainSpace();
+  AccessRelation = isl_map_align_params(AccessRelation, isl_space_copy(Space));
   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,
+                           isl_set *Domain, 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);
+  AccessRelation = isl_map_intersect_domain(AccessRelation, Domain);
+
+  isl_space_free(Space);
+}
+
 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");
+  }
+}
+
+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;
+}
+
+void ScopStmt::buildPHIAccesses(PHINode *PHI, const IRAccess &Access,
+                                TempScop &tempScop) {
+  const SmallVector<const SCEV *, 4> Sizes;
+
+  unsigned NumIncomingValues = PHI->getNumIncomingValues();
+  if (NumIncomingValues == 1) {
+    if (auto *InValueInst = dyn_cast<Instruction>(PHI->getIncomingValue(0))) {
+      const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
+          InValueInst, PHI->getType(), Sizes);
+      MemAccs.push_back(new MemoryAccess(PHI, SAI, getDomain(), this));
+    }
+    return;
+  }
+
+  Scop *S = getParent();
+  unsigned NumIterators = getNumIterators();
+  for (unsigned u = 0, e = NumIncomingValues; u < e; u++) {
+    BasicBlock *InBB = PHI->getIncomingBlock(u);
+    ScopStmt *InStmt = S->getStmtForBasicBlock(InBB);
+    if (!InStmt)
+      continue;
+
+    Instruction *InValueInst = dyn_cast<Instruction>(PHI->getIncomingValue(u));
+    if (!InValueInst)
+      continue;
+
+    bool IsLC = isLoopCarried(getScattering(), InStmt->getScattering());
+
+    isl_set *InDomain = isl_set_reset_tuple_id(InStmt->getDomain());
+    if (const BBCond *Condition = tempScop.getBBCond(InBB)) {
+      for (const auto &C : *Condition) {
+        isl_set *ConditionSet = buildConditionSet(InStmt, C);
+        InDomain = isl_set_intersect(InDomain, ConditionSet);
+      }
+    }
+
+    unsigned InNumIterators = InStmt->getNumIterators();
+    unsigned NumIteratorsDiff = NumIterators - InNumIterators;
+    assert(NumIterators >= InNumIterators && "In Stmt has more iterators!");
+
+    if (IsLC) {
+      assert(NumIteratorsDiff == 0 &&
+             "Found loop carried PHI with different dimension");
+      assert(InNumIterators > 0 &&
+             "Found loop carried PHI without loop dimension");
+
+      isl_space *InDomainSpace = isl_set_get_space(InDomain);
+      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);
+      InDomain = isl_set_apply(InDomain, LCMap);
+    }
+
+    if (NumIteratorsDiff) {
+      assert(!IsLC && "Found loop carried PHI with different dimension");
+      InDomain = isl_set_add_dims(InDomain, isl_dim_set, NumIteratorsDiff);
+      for (unsigned dimIt = InNumIterators; dimIt < NumIterators; dimIt++)
+        InDomain = isl_set_fix_dim_si(InDomain, dimIt, 0);
+    }
+
+    InDomain = isl_set_set_tuple_id(InDomain, getDomainId());
+    const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
+        InValueInst, PHI->getType(), Sizes);
+    MemAccs.push_back(new MemoryAccess(PHI, SAI, InDomain, this));
+  }
+}
+
+void ScopStmt::buildAccesses(TempScop &tempScop) {
+  const AccFuncSetType *AFS = tempScop.getAccessFunctions(BB);
+  assert(AFS && "Cannot build accesses for trivial statement");
+
+  for (const auto &AccessPair : *AFS) {
     const IRAccess &Access = AccessPair.first;
     Instruction *AccessInst = AccessPair.second;
 
-    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));
+    if (PHINode *PHI = dyn_cast<PHINode>(AccessInst))
+      buildPHIAccesses(PHI, Access, tempScop);
 
     // 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();
 }
 
 /// @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
Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
   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.
+  for (ScopStmt *Stmt : Stmts) {
+    Stmt->buildAccesses(tempScop);
+    Stmt->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()];
void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
   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>();
 
+      ScopStmt *Stmt =
+          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
+
+      // Insert all statements (trivial or not) into the statement map.
+      StmtMap[BB] = Stmt;
+
       if (isTrivialBB(BB, tempScop))
         continue;
 
-      Stmts.push_back(
-          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter));
+      // But only non trivial into the statement vector.
+      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();

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
+; CHECK:  Domain :=
+; CHECK:      { Stmt_for_cond[i0] : i0 >= 0 and i0 <= 32 };
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1.lcssa, %for.inc4 ]
+; CHECK:  MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:      { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
+; CHECK:  ReadAccess := [Reduction Type: NONE]
+; CHECK:      { Stmt_for_cond[i0] -> MemRef_x_addr_1_lcssa[] : i0 >= 1 and i0 <= 32 };
+  %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, 0] -> MemRef_x_addr_0[] : i0 >= 0 and i0 <= 31 };
+; 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
+; CHECK:  Domain :=
+; CHECK:      { Stmt_for_end[i0] : i0 >= 0 and i0 <= 31 };
+  %x.addr.1.lcssa = phi i32 [ %x.addr.1, %for.cond1 ]
+; CHECK:  MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:      { Stmt_for_end[i0] -> MemRef_x_addr_1_lcssa[] };
+; CHECK:  ReadAccess := [Reduction Type: NONE]
+; CHECK:      { Stmt_for_end[i0] -> MemRef_x_addr_1[] : i0 >= 0 and i0 <= 31 };
+  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>