Allow PHI nodes in the exit block of regions

[jdoerfert]

Summary

A codegen approach

[Meinersbur]

It's basically like my solution: Ensure that TempScopInfo generates write accesses and that BlockGenerators adds the PHIs to EscapeMap.

lib/Analysis/TempScopInfo.cpp

114 ↗

(On Diff #32218)

What happens otherwise?

470 ↗

(On Diff #32218)

if (!R.getExitingBlock())

lib/CodeGen/BlockGenerators.cpp

495 ↗

(On Diff #32218)

assert(!OperandPHI)

499 ↗

(On Diff #32218)

assert(OperandPHI);

532 ↗

(On Diff #32218)

Is this necessary? Can't one just use the original PHI to represent the virtual memory location? It's not directly used anyway.

543 ↗

(On Diff #32218)

escape

1202 ↗

(On Diff #32218)

The last 30 lines are repetative. Refactor?

[jdoerfert]

I will push another version later.

The problematic part I encountered are PHI nodes that use values as operands. Here I tried to circumvent them by looking through the new PHI node in the exit and replacing it dynamically with the one that is now in the region [BlockGenerators.cpp:529]. However, I don't like this solution so I came up with a different one I will push here.

lib/Analysis/TempScopInfo.cpp

114 ↗

(On Diff #32218)

The PHI operands are not modeled, hence never stored into the escape location.

470 ↗

(On Diff #32218)

True.

lib/CodeGen/BlockGenerators.cpp

532 ↗

(On Diff #32218)

I don't think so as it is linked via the escape map to the rewiring at the end.

1202 ↗

(On Diff #32218)

That might be an idea for a different patch though.

[jdoerfert]

• Remove trivial condition
• Allow values to cause memory accesses
• Allow PHI nodes in the region exit block

[grosser]

Hi Johannes,

can you rebase this to get rid of the AccessVal changes?

[jdoerfert]

Rebase to upstream with only the actuall commit in the diff

[jdoerfert]

This patch fails only the pairalign lnt execution test.

@Meinersbur Does your patch pass that one? If so can you rebase your patch to the upstram I want to see the difference in the generated L__align11 function that is apperently wrong.

[jdoerfert]

Rebased and working version

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

virtual void generateScalarStores(ScopStmt &Stmt, BasicBlock *BB,
                                     ValueMapT &BBMAp);
 
   /// @brief Handle users of @p Inst outside the SCoP.
   ///
   /// @param R         The current SCoP region.
   /// @param Inst      The current instruction we check.
   /// @param InstCopy  The copy of the instruction @p Inst in the optimized
   ///                  SCoP.
-  void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy);
+  /// @param Address   If given it is used as the escape address for @p Inst.
+  void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy,
+                          AllocaInst *Address = nullptr);
 
   /// @brief Initialize the memory of demoted scalars.
   ///
   /// @param S The scop for which to generate the scalar initializers.
   void createScalarInitialization(Scop &S);
 
   /// @brief Promote the values of demoted scalars after the SCoP.
   ///

polly/trunk/include/polly/ScopDetection.h

private:
 
   /// @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 call instruction can be part of a Scop.

polly/trunk/include/polly/ScopInfo.h

private:
   ScalarEvolution *SE;
 
   /// The underlying Region.
   Region &R;
 
   /// Flag to indicate that the scheduler actually optimized the SCoP.
   bool IsOptimized;
 
+  /// @brief True if the underlying region has a single exiting block.
+  bool HasSingleExitEdge;
+
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
   typedef std::deque<ScopStmt> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
public:
   /// @param IsPHI   Are we looking for special PHI storage.
   const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, bool IsPHI = false);
 
   void setContext(isl_set *NewContext);
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();
 
+  /// @brief Return true if the underlying region has a single exiting block.
+  bool hasSingleExitEdge() const { return HasSingleExitEdge; }
+
   /// @brief Print the static control part.
   ///
   /// @param OS The output stream the static control part is printed to.
   void print(raw_ostream &OS) const;
 
   /// @brief Print the ScopStmt to stderr.
   void dump() const;
 

polly/trunk/include/polly/TempScopInfo.h

bool buildScalarDependences(Instruction *Inst, Region *R,
                               Region *NonAffineSubRegio);
 
   /// @brief Create IRAccesses for the given PHI node in the given region.
   ///
   /// @param PHI                The PHI node to be handled
   /// @param R                  The SCoP region
   /// @param Functions          The access functions of the current BB
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
+  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
   void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
-                        Region *NonAffineSubRegion);
+                        Region *NonAffineSubRegion, bool IsExitBlock = false);
 
   /// @brief Build the access functions for the subregion @p SR.
   ///
   /// @param R  The SCoP region.
   /// @param SR A subregion of @p R.
   void buildAccessFunctions(Region &R, Region &SR);
 
   /// @brief Build the access functions for the basic block @p BB
   ///
   /// @param R                  The SCoP region.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
+  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
-                            Region *NonAffineSubRegion = nullptr);
+                            Region *NonAffineSubRegion = nullptr,
+                            bool IsExitBlock = false);
 
 public:
   static char ID;
   explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
   ~TempScopInfo();
 
   /// @brief Get the temporay Scop information in LLVM IR for this region.
   ///

polly/trunk/lib/Analysis/ScopDetection.cpp

Region *ScopDetection::expandRegion(Region &R) {
 
   while (ExpandedRegion) {
     DetectionContext Context(
         *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion.get()],
         BoxedLoopsMap[ExpandedRegion.get()], 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 (!Context.Log.hasErrors()) {
       // If the exit is valid 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;
 
       // Store this region, because it is the greatest valid (encountered so
       // far).
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 {
-
-  // PHI nodes are not allowed in the exit basic block.
-  if (BasicBlock *Exit = Context.CurRegion.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(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
 
   if (CurRegion.isTopLevelRegion()) {
     DEBUG(dbgs() << "Top level region is invalid\n");
     return false;
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   // to insert alloca instruction there when translate scalar to array.
   if (CurRegion.getEntry() ==
       &(CurRegion.getEntry()->getParent()->getEntryBlock()))
     return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
 
   if (!DetectUnprofitable && !hasMoreThanOneLoop(&CurRegion))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 
-  if (!isValidExit(Context))
-    return false;
-
   if (!allBlocksValid(Context))
     return false;
 
   // We can probably not do a lot on scops that only write or only read
   // data.
   if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 

polly/trunk/lib/Analysis/ScopInfo.cpp

static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, DominatorTree &DT,
            isl_ctx *Context, unsigned MaxLoopDepth)
     : DT(DT), SE(&ScalarEvolution), R(R), IsOptimized(false),
-      MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {}
+      HasSingleExitEdge(R.getExitingBlock()), MaxLoopDepth(MaxLoopDepth),
+      IslCtx(Context), Affinator(this) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
                             AliasAnalysis &AA) {
   buildContext();
 
   buildDomains(&R, LI, SD, DT);
 
   SmallVector<Loop *, 8> NestLoops;

polly/trunk/lib/Analysis/TempScopInfo.cpp

for (const auto &CurBlock : CurR->blocks()) {
     for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
          ++AI)
       AI->first.print(OS.indent(ind + 2));
   }
 }
 
 void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
                                     AccFuncSetType &Functions,
-                                    Region *NonAffineSubRegion) {
-  if (canSynthesize(PHI, LI, SE, &R))
+                                    Region *NonAffineSubRegion,
+                                    bool IsExitBlock) {
+
+  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
+  // true, are not modeled as ordinary PHI nodes as they are not part of the
+  // region. However, we model the operands in the predecessor blocks that are
+  // part of the region as regular scalar accesses.
+
+  // If we can synthesize a PHI we can skip it, however only if it is in
+  // the region. If it is not it can only be in the exit block of the region.
+  // In this case we model the operands but not the PHI itself.
+  if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
     return;
 
   // PHI nodes are modeled as if they had been demoted prior to the SCoP
   // detection. Hence, the PHI is a load of a new memory location in which the
   // incoming value was written at the end of the incoming basic block.
   bool OnlyNonAffineSubRegionOperands = true;
   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
if (OpI) {
       }
     }
 
     // Always use the terminator of the incoming basic block as the access
     // instruction.
     OpI = OpBB->getTerminator();
 
     IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op,
-                          /* IsPHI */ true);
+                          /* IsPHI */ !IsExitBlock);
     AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
   }
 
   if (!OnlyNonAffineSubRegionOperands) {
     IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
-                          /* IsPHI */ true);
+                          /* IsPHI */ !IsExitBlock);
     Functions.push_back(std::make_pair(ScalarAccess, PHI));
   }
 }
 
 bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
                                           Region *NonAffineSubRegion) {
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
   if (isIgnoredIntrinsic(Inst))
void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildAccessFunctions(R, *I->getNodeAs<Region>());
     else
       buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
 }
 
 void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
-                                        Region *NonAffineSubRegion) {
+                                        Region *NonAffineSubRegion,
+                                        bool IsExitBlock) {
   AccFuncSetType Functions;
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
+
+    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    if (PHI)
+      buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock);
+
+    // For the exit block we stop modeling after the last PHI node.
+    if (!PHI && IsExitBlock)
+      break;
+
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(
           std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst));
 
     if (isIgnoredIntrinsic(Inst))
       continue;
 
-    if (PHINode *PHI = dyn_cast<PHINode>(Inst))
-      buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion);
-
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       // If the Instruction is used outside the statement, we need to build the
       // write access.
       if (!isa<StoreInst>(Inst)) {
         IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
                               Inst);
         Functions.push_back(std::make_pair(ScalarAccess, Inst));
       }
     }
   }
 
   if (Functions.empty())
     return;
 
   AccFuncSetType &Accs = AccFuncMap[&BB];
   Accs.insert(Accs.end(), Functions.begin(), Functions.end());
 }
 
 TempScop *TempScopInfo::buildTempScop(Region &R) {
   TempScop *TScop = new TempScop(R, AccFuncMap);
 
   buildAccessFunctions(R, R);
 
+  // In case the region does not have an exiting block we will later (during
+  // code generation) split the exit block. This will move potential PHI nodes
+  // from the current exit block into the new region exiting block. Hence, PHI
+  // nodes that are at this point not part of the region will be.
+  // To handle these PHI nodes later we will now model their operands as scalar
+  // accesses. Note that we do not model anything in the exit block if we have
+  // an exiting block in the region, as there will not be any splitting later.
+  if (!R.getExitingBlock())
+    buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
+
   return TScop;
 }
 
 TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }
 
 void TempScopInfo::print(raw_ostream &OS, const Module *) const {
   if (TempScopOfRegion)
     TempScopOfRegion->print(OS, SE, LI);

polly/trunk/lib/CodeGen/BlockGenerators.cpp

Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
   return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
 }
 
 Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
   return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
 }
 
 void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
-                                        Value *InstCopy) {
+                                        Value *InstCopy, AllocaInst *Address) {
   // If there are escape users we get the alloca for this instruction and put it
   // in the EscapeMap for later finalization. Lastly, if the instruction was
   // copied multiple times we already did this and can exit.
   if (EscapeMap.count(Inst))
     return;
 
   EscapeUserVectorTy EscapeUsers;
   for (User *U : Inst->users()) {
for (User *U : Inst->users()) {
     EscapeUsers.push_back(UI);
   }
 
   // Exit if no escape uses were found.
   if (EscapeUsers.empty())
     return;
 
   // Get or create an escape alloca for this instruction.
-  auto *ScalarAddr = cast<AllocaInst>(getOrCreateScalarAlloca(Inst));
+  auto *ScalarAddr =
+      Address ? Address : cast<AllocaInst>(getOrCreateScalarAlloca(Inst));
 
   // Remember that this instruction has escape uses and the escape alloca.
   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 }
 
 void BlockGenerator::generateScalarLoads(ScopStmt &Stmt,
                                          const Instruction *Inst,
                                          ValueMapT &BBMap) {
if (Array->isPHI()) {
       continue;
     }
 
     auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
 
     if (Inst && R.contains(Inst))
       continue;
 
+    // PHI nodes that are not marked as such in their SAI object are exit PHI
+    // nodes we model as common scalars but do not need to initialize.
+    if (Inst && isa<PHINode>(Inst))
+      continue;
+
     ValueMapT EmptyMap;
     Builder.CreateStore(Array->getBasePtr(),
                         getOrCreateScalarAlloca(Array->getBasePtr()));
   }
 }
 
 void BlockGenerator::createScalarFinalization(Region &R) {
   // The exit block of the __unoptimized__ region.
for (const auto &EscapeMapping : EscapeMap) {
 
     // Replace all uses of the demoted instruction with the merge PHI.
     for (Instruction *EUser : EscapeUsers)
       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
   }
 }
 
 void BlockGenerator::finalizeSCoP(Scop &S) {
+
+  // Handle PHI nodes that were in the original exit and are now
+  // moved into the region exiting block.
+  if (!S.hasSingleExitEdge()) {
+    for (Instruction &I : *S.getRegion().getExitingBlock()) {
+      PHINode *PHI = dyn_cast<PHINode>(&I);
+      if (!PHI)
+        break;
+
+      assert(PHI->getNumUses() == 1);
+      assert(ScalarMap.count(PHI->user_back()));
+
+      handleOutsideUsers(S.getRegion(), PHI, nullptr,
+                         ScalarMap[PHI->user_back()]);
+    }
+  }
+
   createScalarInitialization(S);
   createScalarFinalization(S.getRegion());
 }
 
 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                            std::vector<LoopToScevMapT> &VLTS,
                                            isl_map *Schedule)
     : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {

polly/trunk/test/Isl/CodeGen/phi_in_exit_early_lnt_failure_1.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This caused an lnt crash at some point, just verify it will run through.
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK-NEXT:    br label %for.body.6
+;
+; CHECK-LABEL: for.body.6:
+; CHECK-NEXT:    %i.14 = phi i32 [ undef, %for.body.6 ], [ 0, %polly.merge_new_and_old ]
+;
+@recd = external hidden global [255 x i32], align 16
+
+define void @rsdec_204(i8* %data_in) {
+entry:
+  br i1 undef, label %if.then, label %for.body
+
+if.then:                                          ; preds = %entry
+  unreachable
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i8, i8* %data_in, i64 0
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %arrayidx2 = getelementptr inbounds [255 x i32], [255 x i32]* @recd, i64 0, i64 0
+  store i32 %conv, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %i.05, 1
+  br i1 false, label %for.body, label %for.body.6
+
+for.body.6:                                       ; preds = %for.body.6, %for.body
+  %i.14 = phi i32 [ undef, %for.body.6 ], [ 0, %for.body ]
+  br i1 undef, label %for.body.6, label %for.body.16
+
+for.body.16:                                      ; preds = %for.body.16, %for.body.6
+  br i1 undef, label %for.body.16, label %for.body.29
+
+for.body.29:                                      ; preds = %for.body.29, %for.body.16
+  br i1 undef, label %for.body.29, label %for.end.38
+
+for.end.38:                                       ; preds = %for.body.29
+  unreachable
+}

polly/trunk/test/Isl/CodeGen/phi_in_exit_early_lnt_failure_2.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This caused an lnt crash at some point, just verify it will run through and
+; produce the PHI node in the exit we are looking for.
+;
+; CHECK:       %eps1.addr.0.s2a = alloca double
+; CHECK-NOT:   %eps1.addr.0.ph.s2a = alloca double
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK:          %eps1.addr.0.ph.merge = phi double [ %eps1.addr.0.ph.final_reload, %polly.stmt.if.end.47.region_exiting.exit ], [ %eps1.addr.0.ph, %if.end.47.region_exiting ]
+;
+; CHECK-LABEL: polly.start:
+; CHECK-NEXT:    store double %eps1, double* %eps1.s2a
+;
+; CHECK-LABEL: polly.stmt.if.end.47.region_exiting.exit:
+; CEHCK-NEXT:     %eps1.addr.0.ph.final_reload = load double, double* %eps1.addr.0.s2a
+;
+define void @dbisect(double* %c, double* %b, double %eps1, double* %eps2) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  store double 0.000000e+00, double* %b, align 8
+  br i1 false, label %for.inc, label %for.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  %arrayidx33 = getelementptr inbounds double, double* %c, i64 0
+  %0 = load double, double* %arrayidx33, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then.36, %if.end
+  br i1 false, label %if.end, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  %cmp45 = fcmp ugt double %eps1, 0.000000e+00
+  br i1 %cmp45, label %if.end.47, label %if.then.46
+
+if.then.46:                                       ; preds = %for.end
+  %1 = load double, double* %eps2, align 8
+  br label %if.end.47
+
+if.end.47:                                        ; preds = %if.then.46, %for.end
+  %eps1.addr.0 = phi double [ %1, %if.then.46 ], [ %eps1, %for.end ]
+  ret void
+}

polly/trunk/test/Isl/CodeGen/phi_in_exit_early_lnt_failure_3.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This caused an lnt crash at some point, just verify it will run through and
+; produce the PHI node in the exit we are looking for.
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK-NEXT:     %n2ptr.2.ph.merge = phi i8* [ %n2ptr.2.ph.final_reload, %polly.merge ], [ %n2ptr.2.ph, %if.end.45.region_exiting ]
+;
+; CHECK-LABEL: if.end.45:
+; CHECK-NEXT:     %n2ptr.2 = phi i8* [ %add.ptr25, %entry ], [ %add.ptr25, %while.cond.preheader ], [ %n2ptr.2.ph.merge, %polly.merge_new_and_old ]
+
+%struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121 = type { i32, i32, i32, i32, [1024 x i8] }
+
+; Function Attrs: nounwind uwtable
+declare %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121* @new_num() #0
+
+; Function Attrs: nounwind uwtable
+define void @_do_add(%struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121* %n2) #0 {
+entry:
+  %call = tail call %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121* @new_num()
+  %0 = load i32, i32* undef, align 4
+  %add.ptr22 = getelementptr inbounds %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121, %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121* %n2, i64 0, i32 4, i64 0
+  %add.ptr24 = getelementptr inbounds i8, i8* %add.ptr22, i64 0
+  %add.ptr25 = getelementptr inbounds i8, i8* %add.ptr24, i64 -1
+  %add.ptr29 = getelementptr inbounds %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121, %struct.bc_struct.0.2.4.6.8.15.24.27.29.32.38.46.48.92.93.94.95.97.99.100.102.105.107.111.118.119.121* %call, i64 0, i32 4, i64 0
+  %add.ptr31 = getelementptr inbounds i8, i8* %add.ptr29, i64 0
+  %add.ptr32 = getelementptr inbounds i8, i8* %add.ptr31, i64 -1
+  br i1 undef, label %if.end.45, label %if.then
+
+if.then:                                          ; preds = %entry
+  br i1 undef, label %while.cond.preheader, label %while.cond.38.preheader
+
+while.cond.38.preheader:                          ; preds = %if.then
+  %cmp39.39 = icmp sgt i32 %0, 0
+  br i1 %cmp39.39, label %while.body.40.lr.ph, label %if.end.45
+
+while.body.40.lr.ph:                              ; preds = %while.cond.38.preheader
+  br label %while.body.40
+
+while.cond.preheader:                             ; preds = %if.then
+  br i1 undef, label %while.body.lr.ph, label %if.end.45
+
+while.body.lr.ph:                                 ; preds = %while.cond.preheader
+  br label %while.body
+
+while.body:                                       ; preds = %while.body, %while.body.lr.ph
+  br label %while.body
+
+while.body.40:                                    ; preds = %while.body.40, %while.body.40.lr.ph
+  %sumptr.141 = phi i8* [ %add.ptr32, %while.body.40.lr.ph ], [ %incdec.ptr42, %while.body.40 ]
+  %n2ptr.040 = phi i8* [ %add.ptr25, %while.body.40.lr.ph ], [ %incdec.ptr41, %while.body.40 ]
+  %incdec.ptr41 = getelementptr inbounds i8, i8* %n2ptr.040, i64 -1
+  %1 = load i8, i8* %n2ptr.040, align 1
+  %incdec.ptr42 = getelementptr inbounds i8, i8* %sumptr.141, i64 -1
+  store i8 %1, i8* %sumptr.141, align 1
+  br i1 false, label %while.body.40, label %while.cond.38.if.end.45.loopexit9_crit_edge
+
+while.cond.38.if.end.45.loopexit9_crit_edge:      ; preds = %while.body.40
+  br label %if.end.45
+
+if.end.45:                                        ; preds = %while.cond.38.if.end.45.loopexit9_crit_edge, %while.cond.preheader, %while.cond.38.preheader, %entry
+  %n2ptr.2 = phi i8* [ %add.ptr25, %entry ], [ %add.ptr25, %while.cond.preheader ], [ undef, %while.cond.38.if.end.45.loopexit9_crit_edge ], [ %add.ptr25, %while.cond.38.preheader ]
+  ret void
+}

polly/trunk/test/Isl/CodeGen/phi_in_exit_early_lnt_failure_4.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This caused an lnt crash at some point, just verify it will run through and
+; produce the PHI node in the exit we are looking for.
+;
+; CHECK-LABEL:  polly.merge_new_and_old:
+; CHECK-NEXT:     %.merge = phi %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826* [ %.final_reload, %polly.stmt.for.end.298 ], [ %13, %for.end.298 ]
+;
+%struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826 = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, float, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i8**, i8**, i32, i32***, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [9 x [16 x [16 x i16]]], [5 x [16 x [16 x i16]]], [9 x [8 x [8 x i16]]], [2 x [4 x [16 x [16 x i16]]]], [16 x [16 x i16]], [16 x [16 x i32]], i32****, i32***, i32***, i32***, i32****, i32****, %struct.Picture.8.32.56.80.104.320.536.752.1016.1040.1184.1232.1352.1376.1400.1424.1496.1568.1664.1736.1832.2048.2120.2336.2384.2840.2864.2888.2912.3584.3800.3823*, %struct.Slice.7.31.55.79.103.319.535.751.1015.1039.1183.1231.1351.1375.1399.1423.1495.1567.1663.1735.1831.2047.2119.2335.2383.2839.2863.2887.2911.3583.3799.3822*, %struct.macroblock.9.33.57.81.105.321.537.753.1017.1041.1185.1233.1353.1377.1401.1425.1497.1569.1665.1737.1833.2049.2121.2337.2385.2841.2865.2889.2913.3585.3801.3824*, i32*, i32*, i32, i32, i32, i32, [4 x [4 x i32]], i32, i32, i32, i32, i32, double, i32, i32, i32, i32, i16******, i16******, i16******, i16******, [15 x i16], i32, i32, i32, i32, i32, i32, i32, i32, [6 x [32 x i32]], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [1 x i32], i32, i32, [2 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %struct.DecRefPicMarking_s.10.34.58.82.106.322.538.754.1018.1042.1186.1234.1354.1378.1402.1426.1498.1570.1666.1738.1834.2050.2122.2338.2386.2842.2866.2890.2914.3586.3802.3825*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double**, double***, i32***, double**, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x [2 x i32]], [2 x i32], i32, i32, i16, i32, i32, i32, i32, i32 }
+%struct.Picture.8.32.56.80.104.320.536.752.1016.1040.1184.1232.1352.1376.1400.1424.1496.1568.1664.1736.1832.2048.2120.2336.2384.2840.2864.2888.2912.3584.3800.3823 = type { i32, i32, [100 x %struct.Slice.7.31.55.79.103.319.535.751.1015.1039.1183.1231.1351.1375.1399.1423.1495.1567.1663.1735.1831.2047.2119.2335.2383.2839.2863.2887.2911.3583.3799.3822*], i32, float, float, float }
+%struct.Slice.7.31.55.79.103.319.535.751.1015.1039.1183.1231.1351.1375.1399.1423.1495.1567.1663.1735.1831.2047.2119.2335.2383.2839.2863.2887.2911.3583.3799.3822 = type { i32, i32, i32, i32, i32, i32, %struct.datapartition.3.27.51.75.99.315.531.747.1011.1035.1179.1227.1347.1371.1395.1419.1491.1563.1659.1731.1827.2043.2115.2331.2379.2835.2859.2883.2907.3579.3795.3818*, %struct.MotionInfoContexts.5.29.53.77.101.317.533.749.1013.1037.1181.1229.1349.1373.1397.1421.1493.1565.1661.1733.1829.2045.2117.2333.2381.2837.2861.2885.2909.3581.3797.3820*, %struct.TextureInfoContexts.6.30.54.78.102.318.534.750.1014.1038.1182.1230.1350.1374.1398.1422.1494.1566.1662.1734.1830.2046.2118.2334.2382.2838.2862.2886.2910.3582.3798.3821*, i32, i32*, i32*, i32*, i32, i32*, i32*, i32*, i32 (i32)*, [3 x [2 x i32]] }
+%struct.datapartition.3.27.51.75.99.315.531.747.1011.1035.1179.1227.1347.1371.1395.1419.1491.1563.1659.1731.1827.2043.2115.2331.2379.2835.2859.2883.2907.3579.3795.3818 = type { %struct.Bitstream.1.25.49.73.97.313.529.745.1009.1033.1177.1225.1345.1369.1393.1417.1489.1561.1657.1729.1825.2041.2113.2329.2377.2833.2857.2881.2905.3577.3793.3816*, %struct.EncodingEnvironment.2.26.50.74.98.314.530.746.1010.1034.1178.1226.1346.1370.1394.1418.1490.1562.1658.1730.1826.2042.2114.2330.2378.2834.2858.2882.2906.3578.3794.3817, %struct.EncodingEnvironment.2.26.50.74.98.314.530.746.1010.1034.1178.1226.1346.1370.1394.1418.1490.1562.1658.1730.1826.2042.2114.2330.2378.2834.2858.2882.2906.3578.3794.3817 }
+%struct.Bitstream.1.25.49.73.97.313.529.745.1009.1033.1177.1225.1345.1369.1393.1417.1489.1561.1657.1729.1825.2041.2113.2329.2377.2833.2857.2881.2905.3577.3793.3816 = type { i32, i32, i8, i32, i32, i8, i8, i32, i32, i8*, i32 }
+%struct.EncodingEnvironment.2.26.50.74.98.314.530.746.1010.1034.1178.1226.1346.1370.1394.1418.1490.1562.1658.1730.1826.2042.2114.2330.2378.2834.2858.2882.2906.3578.3794.3817 = type { i32, i32, i32, i32, i32, i8*, i32*, i32, i32 }
+%struct.MotionInfoContexts.5.29.53.77.101.317.533.749.1013.1037.1181.1229.1349.1373.1397.1421.1493.1565.1661.1733.1829.2045.2117.2333.2381.2837.2861.2885.2909.3581.3797.3820 = type { [3 x [11 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [2 x [9 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [2 x [10 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [2 x [6 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [4 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819], [4 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819], [3 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819] }
+%struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819 = type { i16, i8, i64 }
+%struct.TextureInfoContexts.6.30.54.78.102.318.534.750.1014.1038.1182.1230.1350.1374.1398.1422.1494.1566.1662.1734.1830.2046.2118.2334.2382.2838.2862.2886.2910.3582.3798.3821 = type { [2 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819], [4 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819], [3 x [4 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [4 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [15 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [15 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [5 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [5 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [15 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]], [10 x [15 x %struct.BiContextType.4.28.52.76.100.316.532.748.1012.1036.1180.1228.1348.1372.1396.1420.1492.1564.1660.1732.1828.2044.2116.2332.2380.2836.2860.2884.2908.3580.3796.3819]] }
+%struct.macroblock.9.33.57.81.105.321.537.753.1017.1041.1185.1233.1353.1377.1401.1425.1497.1569.1665.1737.1833.2049.2121.2337.2385.2841.2865.2889.2913.3585.3801.3824 = type { i32, i32, i32, [2 x i32], i32, [8 x i32], %struct.macroblock.9.33.57.81.105.321.537.753.1017.1041.1185.1233.1353.1377.1401.1425.1497.1569.1665.1737.1833.2049.2121.2337.2385.2841.2865.2889.2913.3585.3801.3824*, %struct.macroblock.9.33.57.81.105.321.537.753.1017.1041.1185.1233.1353.1377.1401.1425.1497.1569.1665.1737.1833.2049.2121.2337.2385.2841.2865.2889.2913.3585.3801.3824*, i32, [2 x [4 x [4 x [2 x i32]]]], [16 x i8], [16 x i8], i32, i64, [4 x i32], [4 x i32], i64, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i16, double, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
+%struct.DecRefPicMarking_s.10.34.58.82.106.322.538.754.1018.1042.1186.1234.1354.1378.1402.1426.1498.1570.1666.1738.1834.2050.2122.2338.2386.2842.2866.2890.2914.3586.3802.3825 = type { i32, i32, i32, i32, i32, %struct.DecRefPicMarking_s.10.34.58.82.106.322.538.754.1018.1042.1186.1234.1354.1378.1402.1426.1498.1570.1666.1738.1834.2050.2122.2338.2386.2842.2866.2890.2914.3586.3802.3825* }
+
+@img = external global %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826*, align 8
+
+; Function Attrs: nounwind uwtable
+define void @intrapred_luma() #0 {
+entry:
+  %PredPel = alloca [13 x i16], align 16
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  br i1 undef, label %for.body, label %for.body.262
+
+for.body.262:                                     ; preds = %for.body
+  %0 = load %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826*, %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826** @img, align 8
+  br label %for.body.280
+
+for.body.280:                                     ; preds = %for.body.280, %for.body.262
+  %indvars.iv66 = phi i64 [ 0, %for.body.262 ], [ %indvars.iv.next67, %for.body.280 ]
+  %arrayidx282 = getelementptr inbounds [13 x i16], [13 x i16]* %PredPel, i64 0, i64 1
+  %arrayidx283 = getelementptr inbounds i16, i16* %arrayidx282, i64 %indvars.iv66
+  %1 = load i16, i16* %arrayidx283, align 2
+  %arrayidx289 = getelementptr inbounds %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826, %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826* %0, i64 0, i32 47, i64 0, i64 2, i64 %indvars.iv66
+  store i16 %1, i16* %arrayidx289, align 2
+  %indvars.iv.next67 = add nuw nsw i64 %indvars.iv66, 1
+  br i1 false, label %for.body.280, label %for.end.298
+
+for.end.298:                                      ; preds = %for.body.280
+  %2 = load %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826*, %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826** @img, align 8
+  br label %for.body.310
+
+for.body.310:                                     ; preds = %for.body.310, %for.end.298
+  %indvars.iv = phi i64 [ 0, %for.end.298 ], [ %indvars.iv.next, %for.body.310 ]
+  %arrayidx312 = getelementptr inbounds [13 x i16], [13 x i16]* %PredPel, i64 0, i64 9
+  %arrayidx313 = getelementptr inbounds i16, i16* %arrayidx312, i64 %indvars.iv
+  %3 = load i16, i16* %arrayidx313, align 2
+  %arrayidx322 = getelementptr inbounds %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826, %struct.ImageParameters.11.35.59.83.107.323.539.755.1019.1043.1187.1235.1355.1379.1403.1427.1499.1571.1667.1739.1835.2051.2123.2339.2387.2843.2867.2891.2915.3587.3803.3826* %2, i64 0, i32 47, i64 1, i64 %indvars.iv, i64 1
+  store i16 %3, i16* %arrayidx322, align 2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 false, label %for.body.310, label %for.end.328
+
+for.end.328:                                      ; preds = %for.body.310
+  ret void
+}

polly/trunk/test/Isl/CodeGen/phi_in_exit_early_lnt_failure_5.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This caused an lnt crash at some point, just verify it will run through and
+; produce the PHI node in the exit we are looking for.
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK-NEXT:    %eps1.addr.0.ph.merge = phi double [ %eps1.addr.0.ph.final_reload, %polly.stmt.if.end.47.region_exiting.exit ], [ %eps1.addr.0.ph, %if.end.47.region_exiting ]
+; CHECK-NEXT:      br label %if.end.47
+;
+; CHECK-LABEL: if.end.47:
+; CHECK-NEXT:        %eps1.addr.0 = phi double [ %eps1.addr.0.ph.merge, %polly.merge_new_and_old ]
+;
+define void @dbisect(double* %c, double* %b, double %eps1, double* %eps2) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  store double 0.000000e+00, double* %b, align 8
+  %arrayidx9 = getelementptr inbounds double, double* %c, i64 0
+  %0 = load double, double* %arrayidx9, align 8
+  br i1 false, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc, %for.body.lr.ph
+  br i1 false, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  br i1 false, label %if.then.36, label %for.inc
+
+if.then.36:                                       ; preds = %if.end
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then.36, %if.end
+  br i1 false, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  store double undef, double* %eps2, align 8
+  %cmp45 = fcmp ugt double %eps1, 0.000000e+00
+  br i1 %cmp45, label %if.end.47, label %if.then.46
+
+if.then.46:                                       ; preds = %for.end
+  br label %if.end.47
+
+if.end.47:                                        ; preds = %if.then.46, %for.end
+  %eps1.addr.0 = phi double [ undef, %if.then.46 ], [ %eps1, %for.end ]
+  br i1 undef, label %if.then.55, label %for.cond.58.preheader
+
+for.cond.58.preheader:                            ; preds = %if.end.47
+  br i1 undef, label %for.end.68, label %for.body.61.lr.ph
+
+for.body.61.lr.ph:                                ; preds = %for.cond.58.preheader
+  br label %for.body.61
+
+if.then.55:                                       ; preds = %if.end.47
+  unreachable
+
+for.body.61:                                      ; preds = %for.body.61, %for.body.61.lr.ph
+  br i1 undef, label %for.body.61, label %for.cond.58.for.end.68_crit_edge
+
+for.cond.58.for.end.68_crit_edge:                 ; preds = %for.body.61
+  br label %for.end.68
+
+for.end.68:                                       ; preds = %for.cond.58.for.end.68_crit_edge, %for.cond.58.preheader
+  br i1 undef, label %for.end.137, label %for.cond.73.preheader.lr.ph
+
+for.cond.73.preheader.lr.ph:                      ; preds = %for.end.68
+  br label %for.cond.73.preheader
+
+for.cond.73.preheader:                            ; preds = %while.end, %for.cond.73.preheader.lr.ph
+  br i1 undef, label %for.end.87.loopexit, label %for.body.76.lr.ph
+
+for.body.76.lr.ph:                                ; preds = %for.cond.73.preheader
+  br label %for.body.76
+
+for.body.76:                                      ; preds = %for.inc.85, %for.body.76.lr.ph
+  br i1 undef, label %if.then.81, label %for.inc.85
+
+if.then.81:                                       ; preds = %for.body.76
+  br label %for.end.87
+
+for.inc.85:                                       ; preds = %for.body.76
+  br i1 undef, label %for.body.76, label %for.cond.73.for.end.87.loopexit_crit_edge
+
+for.cond.73.for.end.87.loopexit_crit_edge:        ; preds = %for.inc.85
+  br label %for.end.87.loopexit
+
+for.end.87.loopexit:                              ; preds = %for.cond.73.for.end.87.loopexit_crit_edge, %for.cond.73.preheader
+  br label %for.end.87
+
+for.end.87:                                       ; preds = %for.end.87.loopexit, %if.then.81
+  br i1 undef, label %if.then.92, label %if.end.95
+
+if.then.92:                                       ; preds = %for.end.87
+  br label %if.end.95
+
+if.end.95:                                        ; preds = %if.then.92, %for.end.87
+  br i1 undef, label %while.body.lr.ph, label %while.end
+
+while.body.lr.ph:                                 ; preds = %if.end.95
+  br label %while.body
+
+while.body:                                       ; preds = %if.end.128, %while.body.lr.ph
+  br i1 undef, label %if.then.109, label %if.end.128
+
+if.then.109:                                      ; preds = %while.body
+  br i1 undef, label %if.then.112, label %if.else
+
+if.then.112:                                      ; preds = %if.then.109
+  br label %if.end.128
+
+if.else:                                          ; preds = %if.then.109
+  br i1 undef, label %if.then.122, label %if.end.128
+
+if.then.122:                                      ; preds = %if.else
+  br label %if.end.128
+
+if.end.128:                                       ; preds = %if.then.122, %if.else, %if.then.112, %while.body
+  br i1 undef, label %while.body, label %while.cond.while.end_crit_edge
+
+while.cond.while.end_crit_edge:                   ; preds = %if.end.128
+  br label %while.end
+
+while.end:                                        ; preds = %while.cond.while.end_crit_edge, %if.end.95
+  br i1 undef, label %for.cond.73.preheader, label %for.cond.69.for.end.137_crit_edge
+
+for.cond.69.for.end.137_crit_edge:                ; preds = %while.end
+  br label %for.end.137
+
+for.end.137:                                      ; preds = %for.cond.69.for.end.137_crit_edge, %for.end.68
+  ret void
+}

polly/trunk/test/Isl/CodeGen/phi_with_multi_exiting_edges_2.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; CHECK: polly.merge_new_and_old:
+; CHECK:   %result.ph.merge = phi float [ %result.ph.final_reload, %polly.merge ], [ %result.ph, %next.region_exiting ]
+; CHECK:   br label %next
+;
+; CHECK: next:
+; CHECK:   %result = phi float [ %result.ph.merge, %polly.merge_new_and_old ]
+; CHECK:   ret float %result
+
+define float @foo(float* %A, i64 %param) {
+entry:
+  br label %entry.split
+
+entry.split:
+  %branchcond = icmp slt i64 %param, 64
+  br i1 %branchcond, label %loopA, label %loopB
+
+loopA:
+  %indvarA = phi i64 [0, %entry.split], [%indvar.nextA, %loopA]
+  %indvar.nextA = add i64 %indvarA, 1
+  %valA = load float, float* %A
+  %sumA = fadd float %valA, %valA
+  store float %valA, float* %A
+  %cndA = icmp eq i64 %indvar.nextA, 100
+  br i1 %cndA, label %next, label %loopA
+
+loopB:
+  %indvarB = phi i64 [0, %entry.split], [%indvar.nextB, %loopB]
+  %indvar.nextB = add i64 %indvarB, 1
+  %valB = load float, float* %A
+  %sumB = fadd float %valB, %valB
+  store float %valB, float* %A
+  %cndB = icmp eq i64 %indvar.nextB, 100
+  br i1 %cndB, label %next, label %loopB
+
+next:
+  %result = phi float [%sumA, %loopA], [%sumB, %loopB]
+  ret float %result
+
+}

polly/trunk/test/Isl/CodeGen/phi_with_one_exit_edge.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+;
+; CHECK: polly.merge_new_and_old:
+; CHECK:   %sumA.merge = phi float [ %sumA.final_reload, %polly.loop_exit ], [ %sumA, %loopA ]
+; CHECK:   br label %next
+;
+; CHECK: next:
+; CHECK:   %result = phi float [ %sumA.merge, %polly.merge_new_and_old ]
+; CHECK:   ret float %result
+;
+define float @foo(float* %A, i64 %param) {
+entry:
+  br label %entry.split
+
+entry.split:
+  br label %loopA
+
+loopA:
+  %indvarA = phi i64 [0, %entry.split], [%indvar.nextA, %loopA]
+  %indvar.nextA = add i64 %indvarA, 1
+  %valA = load float, float* %A
+  %sumA = fadd float %valA, %valA
+  store float %valA, float* %A
+  %cndA = icmp eq i64 %indvar.nextA, 100
+  br i1 %cndA, label %next, label %loopA
+
+next:
+  %result = phi float [%sumA, %loopA]
+  ret float %result
+
+}

polly/trunk/test/ScopDetect/keep_going_expansion.ll

for.end9:                                         ; preds = %for.body4
   %2 = load i32, i32* %arrayidx11, align 4
   %idxprom12 = sext i32 %n to i64
   %arrayidx13 = getelementptr inbounds i32, i32* %B, i64 %idxprom12
   %3 = load i32, i32* %arrayidx13, align 4
   %add = add nsw i32 %3, %2
   ret i32 %add
 }
 
-; CHECK: Valid Region for Scop: for.body => for.cond2.preheader
+; CHECK: Valid Region for Scop: for.body => for.body4

polly/trunk/test/ScopDetect/multidim_indirect_access.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze < %s | FileCheck %s
 ;
-; The outer loop of this function will correctly not be recognized with the
-; message:
-;
-;   Non affine access function: (sext i32 %tmp to i64)
-;
-; The access A[x] might mistakenly be treated as a multidimensional access with
-; dimension size x. This test will check that we correctly invalidate the
-; region and do not detect an outer SCoP.
-;
-; FIXME:
-; We should detect the inner region but the PHI node in the exit blocks
-; prohibits that.
+; Check that we will recognize this SCoP.
 ;
 ;    void f(int *A, long N) {
 ;      int j = 0;
 ;      while (N > j) {
 ;        int x = A[0];
 ;        int i = 1;
 ;        do {
 ;          A[x] = 42;
 ;          A += x;
 ;        } while (i++ < N);
 ;      }
 ;    }
 ;
-; CHECK-NOT: Valid Region for Scop: bb0 => bb13
+; CHECK: Valid Region for Scop: bb1 => bb0
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i64 %N) {
 bb:
   br label %bb0
 
 bb0:

polly/trunk/test/ScopDetect/non-affine-loop-condition-dependent-access_2.ll

 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=false -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -polly-detect-unprofitable -polly-detect-unprofitable -analyze < %s \
 ; RUN:     | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPSANDACCESSES
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always detect the
 ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not
 ; both, non-affine loops as well as non-affine accesses are allowed.
 ;
-; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb26
+; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb13
 ; REJECTNONAFFINELOOPS-NOT:       Valid
-; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb26
+; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb13
 ; ALLOWNONAFFINELOOPS-NOT:        Valid
 ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ;          for (int k = i *j;  k < 1024; k++)
 ;            A[k] += A[i] + A[j];

polly/trunk/test/ScopDetect/non-affine-loop-condition-dependent-access_3.ll

 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=false -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -polly-detect-unprofitable -analyze < %s | FileCheck %s \
 ; RUN:     --check-prefix=ALLOWNONAFFINELOOPSANDACCESSES
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always detect the
 ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not
 ; both, non-affine loops as well as non-affine accesses are allowed.
 ;
-; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb26
+; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb13
 ; REJECTNONAFFINELOOPS-NOT:       Valid
-; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb26
+; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb13
 ; ALLOWNONAFFINELOOPS-NOT:        Valid
 ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ;          for (int k = 0; k < i * j; k++)
 ;            A[k] += A[i] + A[j];

polly/trunk/test/ScopDetect/phi_with_multi_exiting_edges.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze -S < %s | FileCheck %s
 ;
-; XFAIL: *
-;
 ; Region with an exit node that has a PHI node multiple incoming edges from
 ; inside the region. Motivation for supporting such cases in Polly.
 ;
 ;    float test(long n, float A[static const restrict n]) {
 ;      float sum = 0;
 ;      for (long i = 0; i < n; i += 1)
 ;        sum += A[i];
 ;      for (long i = 0; i < n; i += 1)

polly/trunk/test/ScopDetect/simple_non_single_entry.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect-unprofitable -polly-detect -analyze < %s | FileCheck %s
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect-unprofitable -polly-detect -analyze < %s | FileCheck %s
 
 ; void f(long A[], long N) {
 ;   long i;
 ;
 ;  if (true){
 ;    i = 0;
 ;    goto next;
 ;  }else{
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Valid Region for Scop: next => for.i.head1
+; CHECK: Valid Region for Scop: next => for.i

polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll

 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always model the
 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb15---%bb26
+; INNERMOST:    Region: %bb15---%bb13
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST:    p1: {0,+,{0,+,-1}<nw><%bb11>}<nw><%bb13>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p3: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    p4: {0,+,{0,+,4}<nuw><nsw><%bb11>}<%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
 ; TODO-INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : i0 <= 1023 - p_0 and i0 >= 0 }
 ; INNERMOST:            Schedule :=
 ; TODO-INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] }
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_3 };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };
 ; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };
+; INNERMOST:      Stmt_bb26
+; INNERMOST:            Domain :=
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb26[] };
+; INNERMOST:            Schedule :=
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb26[] -> [1, 0] };
+; INNERMOST:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb26[] -> MemRef_indvars_iv_next6[] };
+; INNERMOST:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb26[] -> MemRef_indvars_iv_next4[] };
 ; INNERMOST:    }
 ;
 ; ALL:    Function: f
 ; ALL:    Region: %bb11---%bb29
 ; ALL:    Max Loop Depth:  2
 ; ALL:    Context:
 ; ALL:    {  :  }
 ; ALL:    Assumed Context:

polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always model the
 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb15---%bb26
+; INNERMOST:    Region: %bb15---%bb13
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    Context:
 ; INNERMOST:      [p_0, p_1, p_2] -> {  : p_0 >= 0 and p_0 <= 2147483647 and p_1 >= 0 and p_1 <= 4096 and p_2 >= 0 and p_2 <= 4096 }
 ; INNERMOST:    Assumed Context:
 ; INNERMOST:      [p_0, p_1, p_2] -> {  :  }
 ; INNERMOST:    p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST:    p1: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] :
 ; INNERMOST-DAG:               i0 >= 0
 ; INNERMOST-DAG:             and
 ; INNERMOST-DAG:               i0 <= -1 + p_0
 ; INNERMOST-DAG:             };
 ; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [i0] };
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_1 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };
 ; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };
+; INNERMOST:      Stmt_bb26
+; INNERMOST:            Domain :=
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb26[] };
+; INNERMOST:            Schedule :=
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb26[] -> [1, 0] };
+; INNERMOST:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next6[] };
+; INNERMOST:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next4[] };
 ; INNERMOST:    }
 ;
 ; ALL:    Function: f
 ; ALL:    Region: %bb11---%bb29
 ; ALL:    Max Loop Depth:  2
 ; ALL:    Context:
 ; ALL:    {  :  }
 ; ALL:    Assumed Context: