[MemorySSA] Don't sort IDF blocks.

[mzolotukhin]

Summary

After r332167 we started to sort the IDF blocks inside IDF calculation, so
there is no need to re-sort them on the user site. The test changes are due to
a slightly different order we're using now (originally we used DFSInNumber and
now the blocks are sorted by a pair (LevelFromRoot, DFSInNumber)).

[• dberlin]

Thanks for doing this!

[mzolotukhin]

Thanks!

llvm/trunk/include/llvm/Analysis/MemorySSA.h

private:
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryPhi *createMemoryPhi(BasicBlock *BB);
   MemoryUseOrDef *createNewAccess(Instruction *);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
-  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,
-                     const DenseMap<const BasicBlock *, unsigned int> &);
+  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
   void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSetImpl<BasicBlock *> &Visited,
                   bool SkipVisited = false, bool RenameAllUses = false);
   AccessList *getOrCreateAccessList(const BasicBlock *);
   DefsList *getOrCreateDefsList(const BasicBlock *);
   void renumberBlock(const BasicBlock *) const;

llvm/trunk/lib/Analysis/MemorySSA.cpp

void MemorySSA::OptimizeUses::optimizeUses() {
   unsigned long PopEpoch = 1;
   // We perform a non-recursive top-down dominator tree walk.
   for (const auto *DomNode : depth_first(DT->getRootNode()))
     optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
                         LocStackInfo);
 }
 
 void MemorySSA::placePHINodes(
-    const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks,
-    const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) {
+    const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
   // Determine where our MemoryPhi's should go
   ForwardIDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
-  llvm::sort(IDFBlocks.begin(), IDFBlocks.end(),
-             [&BBNumbers](const BasicBlock *A, const BasicBlock *B) {
-               return BBNumbers.lookup(A) < BBNumbers.lookup(B);
-             });
-
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks)
     createMemoryPhi(BB);
 }
 
 void MemorySSA::buildMemorySSA() {
   // We create an access to represent "live on entry", for things like
   // arguments or users of globals, where the memory they use is defined before
   // the beginning of the function. We do not actually insert it into the IR.
   // We do not define a live on exit for the immediate uses, and thus our
   // semantics do *not* imply that something with no immediate uses can simply
   // be removed.
   BasicBlock &StartingPoint = F.getEntryBlock();
   LiveOnEntryDef.reset(new MemoryDef(F.getContext(), nullptr, nullptr,
                                      &StartingPoint, NextID++));
-  DenseMap<const BasicBlock *, unsigned int> BBNumbers;
-  unsigned NextBBNum = 0;
 
   // We maintain lists of memory accesses per-block, trading memory for time. We
   // could just look up the memory access for every possible instruction in the
   // stream.
   SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
   // Go through each block, figure out where defs occur, and chain together all
   // the accesses.
   for (BasicBlock &B : F) {
-    BBNumbers[&B] = NextBBNum++;
     bool InsertIntoDef = false;
     AccessList *Accesses = nullptr;
     DefsList *Defs = nullptr;
     for (Instruction &I : B) {
       MemoryUseOrDef *MUD = createNewAccess(&I);
       if (!MUD)
         continue;
 
       if (!Accesses)
         Accesses = getOrCreateAccessList(&B);
       Accesses->push_back(MUD);
       if (isa<MemoryDef>(MUD)) {
         InsertIntoDef = true;
         if (!Defs)
           Defs = getOrCreateDefsList(&B);
         Defs->push_back(*MUD);
       }
     }
     if (InsertIntoDef)
       DefiningBlocks.insert(&B);
   }
-  placePHINodes(DefiningBlocks, BBNumbers);
+  placePHINodes(DefiningBlocks);
 
   // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
   // filled in with all blocks.
   SmallPtrSet<BasicBlock *, 16> Visited;
   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
 
   CachingWalker *Walker = getWalkerImpl();
 

llvm/trunk/test/Analysis/MemorySSA/cyclicphi.ll

 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
 
 %struct.hoge = type { i32, %struct.widget }
 %struct.widget = type { i64 }
 
 define hidden void @quux(%struct.hoge *%f) align 2 {
   %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
   %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
   %tmp25 = bitcast %struct.widget* %tmp24 to i64**
   br label %bb26
 
 bb26:                                             ; preds = %bb77, %0
-; CHECK:  2 = MemoryPhi({%0,liveOnEntry},{bb77,3})
+; CHECK:  3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
 ; CHECK-NEXT:   br i1 undef, label %bb68, label %bb77
   br i1 undef, label %bb68, label %bb77
 
 bb68:                                             ; preds = %bb26
 ; CHECK:  MemoryUse(liveOnEntry)
 ; CHECK-NEXT:   %tmp69 = load i64, i64* null, align 8
   %tmp69 = load i64, i64* null, align 8
-; CHECK:  1 = MemoryDef(2)
+; CHECK:  1 = MemoryDef(3)
 ; CHECK-NEXT:   store i64 %tmp69, i64* %tmp, align 8
   store i64 %tmp69, i64* %tmp, align 8
   br label %bb77
 
 bb77:                                             ; preds = %bb68, %bb26
-; CHECK:  3 = MemoryPhi({bb26,2},{bb68,1})
-; CHECK:  MemoryUse(3)
+; CHECK:  2 = MemoryPhi({bb26,3},{bb68,1})
+; CHECK:  MemoryUse(2)
 ; CHECK-NEXT:   %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef
   br label %bb26
 }
 
 ; CHECK-LABEL: define void @quux_skip
 define void @quux_skip(%struct.hoge* noalias %f, i64* noalias %g) align 2 {
   %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
   %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
   %tmp25 = bitcast %struct.widget* %tmp24 to i64**
   br label %bb26
 
 bb26:                                             ; preds = %bb77, %0
-; CHECK: 2 = MemoryPhi({%0,liveOnEntry},{bb77,3})
+; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
 ; CHECK-NEXT: br i1 undef, label %bb68, label %bb77
   br i1 undef, label %bb68, label %bb77
 
 bb68:                                             ; preds = %bb26
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(3)
 ; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8
   %tmp69 = load i64, i64* %g, align 8
-; CHECK: 1 = MemoryDef(2)
+; CHECK: 1 = MemoryDef(3)
 ; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8
   store i64 %tmp69, i64* %g, align 8
   br label %bb77
 
 bb77:                                             ; preds = %bb68, %bb26
-; CHECK: 3 = MemoryPhi({bb26,2},{bb68,1})
+; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1})
 ; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp78 = load i64*, i64** %tmp25, align 8
   br label %bb26
 }
 
 ; CHECK-LABEL: define void @quux_dominated
 define void @quux_dominated(%struct.hoge* noalias %f, i64* noalias %g) align 2 {

 ; CHECK-LABEL: define void @quux_nodominate
 define void @quux_nodominate(%struct.hoge* noalias %f, i64* noalias %g) align 2 {
   %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
   %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
   %tmp25 = bitcast %struct.widget* %tmp24 to i64**
   br label %bb26
 
 bb26:                                             ; preds = %bb77, %0
-; CHECK: 2 = MemoryPhi({%0,liveOnEntry},{bb77,3})
+; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
 ; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: load i64*, i64** %tmp25, align 8
   load i64*, i64** %tmp25, align 8
   br i1 undef, label %bb68, label %bb77
 
 bb68:                                             ; preds = %bb26
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(3)
 ; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8
   %tmp69 = load i64, i64* %g, align 8
-; CHECK: 1 = MemoryDef(2)
+; CHECK: 1 = MemoryDef(3)
 ; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8
   store i64 %tmp69, i64* %g, align 8
   br label %bb77
 
 bb77:                                             ; preds = %bb68, %bb26
-; CHECK: 3 = MemoryPhi({bb26,2},{bb68,1})
+; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1})
 ; CHECK-NEXT: br label %bb26
   br label %bb26
 }

llvm/trunk/test/Analysis/MemorySSA/invariant-groups.ll

 
 ; CHECK: 3 = MemoryDef(2)
 ; CHECK-NEXT: %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   br i1 undef, label %Loop.Body, label %Loop.End
 
 Loop.Body:
 ; 5 = MemoryPhi({entry,3},{Loop.Body,4},{Loop.End,6})
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
 ; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %p, !invariant.group !0
 
-; CHECK: 4 = MemoryDef(5)
+; CHECK: 4 = MemoryDef(6)
   store i8 4, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; 6 = MemoryPhi({entry,3},{Loop.Body,4})
-; CHECK: MemoryUse(6)
+; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %2 = load
   %2 = load i8, i8* %after, align 4, !invariant.group !0
 
 ; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(6)
+; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %p, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 
 
 define i8 @loop3(i8* %p) {
 entry:
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8
   store i8 4, i8* %p, !invariant.group !0
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: call void @clobber
   call void @clobber8(i8* %p)
 
 ; CHECK: 3 = MemoryDef(2)
 ; CHECK-NEXT: %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   br i1 undef, label %Loop.Body, label %Loop.End
 
 Loop.Body:
-; CHECK: 7 = MemoryPhi({entry,3},{Loop.Body,4},{Loop.next,5},{Loop.End,6})
-; CHECK: MemoryUse(7)
+; CHECK: 8 = MemoryPhi({entry,3},{Loop.Body,4},{Loop.next,5},{Loop.End,6})
+; CHECK: MemoryUse(8)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
-; CHECK: 4 = MemoryDef(7)
+; CHECK: 4 = MemoryDef(8)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(7)
+; FIXME: MemoryUse(8)
 ; CHECK: MemoryUse(4)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.next, label %Loop.Body
 Loop.next:
 ; CHECK: 5 = MemoryDef(4)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(7)
+; FIXME: MemoryUse(8)
 ; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %2 = load i8
   %2 = load i8, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
-; CHECK: 8 = MemoryPhi({entry,3},{Loop.next,5})
-; CHECK: MemoryUse(8)
+; CHECK: 7 = MemoryPhi({entry,3},{Loop.next,5})
+; CHECK: MemoryUse(7)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
-; CHECK: 6 = MemoryDef(8)
+; CHECK: 6 = MemoryDef(7)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(8)
+; FIXME: MemoryUse(7)
 ; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %4 = load
   %4 = load i8, i8* %after, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
; CHECK-NEXT: %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   br i1 undef, label %Loop.Pre, label %Loop.End
 
 Loop.Pre:
 ; CHECK: MemoryUse(2)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
   br label %Loop.Body
 Loop.Body:
-; CHECK: 5 = MemoryPhi({Loop.Pre,3},{Loop.Body,4},{Loop.End,6})
-; CHECK-NEXT: MemoryUse(5)
+; CHECK: 6 = MemoryPhi({Loop.Pre,3},{Loop.Body,4},{Loop.End,5})
+; CHECK-NEXT: MemoryUse(6)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %after, !invariant.group !0
 
 ; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %2 = load i8
   %2 = load i8, i8* %p, !invariant.group !0
 
-; CHECK: 4 = MemoryDef(5)
+; CHECK: 4 = MemoryDef(6)
   store i8 4, i8* %after, !invariant.group !0
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
-; CHECK: 6 = MemoryPhi({entry,3},{Loop.Body,4})
-; CHECK-NEXT: MemoryUse(6)
+; CHECK: 5 = MemoryPhi({entry,3},{Loop.Body,4})
+; CHECK-NEXT: MemoryUse(5)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
 ; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(6)
+; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %4 = load
   %4 = load i8, i8* %p, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 

llvm/trunk/test/Analysis/MemorySSA/many-dom-backedge.ll

 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
 ;
 ; many-dom.ll, with an added back-edge back into the switch.
 ; Because people love their gotos.
 
 declare i1 @getBool() readnone
 
 define i32 @foo(i32* %p) {
 entry:
   br label %loopbegin
 
 loopbegin:
-; CHECK: 8 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
+; CHECK: 9 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
 ; CHECK-NEXT: %n =
   %n = phi i32 [ 0, %entry ], [ %1, %sw.epilog ]
   %m = alloca i32, align 4
   switch i32 %n, label %sw.default [
     i32 0, label %sw.bb
     i32 1, label %sw.bb1
     i32 2, label %sw.bb2
     i32 3, label %sw.bb3
   ]
 
 sw.bb:
-; CHECK: 1 = MemoryDef(8)
+; CHECK: 1 = MemoryDef(9)
 ; CHECK-NEXT: store i32 1
   store i32 1, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb1:
-; CHECK: 2 = MemoryDef(8)
+; CHECK: 2 = MemoryDef(9)
 ; CHECK-NEXT: store i32 2
   store i32 2, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb2:
-; CHECK: 3 = MemoryDef(8)
+; CHECK: 3 = MemoryDef(9)
 ; CHECK-NEXT: store i32 3
   store i32 3, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb3:
-; CHECK: 9 = MemoryPhi({loopbegin,8},{sw.almostexit,6})
-; CHECK: 4 = MemoryDef(9)
+; CHECK: 10 = MemoryPhi({loopbegin,9},{sw.almostexit,6})
+; CHECK: 4 = MemoryDef(10)
 ; CHECK-NEXT: store i32 4
   store i32 4, i32* %m, align 4
   br label %sw.epilog
 
 sw.default:
-; CHECK: 5 = MemoryDef(8)
+; CHECK: 5 = MemoryDef(9)
 ; CHECK-NEXT: store i32 5
   store i32 5, i32* %m, align 4
   br label %sw.epilog
 
 sw.epilog:
-; CHECK: 10 = MemoryPhi({sw.default,5},{sw.bb3,4},{sw.bb,1},{sw.bb1,2},{sw.bb2,3})
-; CHECK-NEXT: MemoryUse(10)
+; CHECK: 8 = MemoryPhi({sw.default,5},{sw.bb3,4},{sw.bb,1},{sw.bb1,2},{sw.bb2,3})
+; CHECK-NEXT: MemoryUse(8)
 ; CHECK-NEXT: %0 =
   %0 = load i32, i32* %m, align 4
-; CHECK: 6 = MemoryDef(10)
+; CHECK: 6 = MemoryDef(8)
 ; CHECK-NEXT: %1 =
   %1 = load volatile i32, i32* %p, align 4
   %2 = icmp eq i32 %0, %1
   br i1 %2, label %sw.almostexit, label %loopbegin
 
 sw.almostexit:
   %3 = icmp eq i32 0, %1
   br i1 %3, label %exit, label %sw.bb3
 
 exit:
 ; CHECK: 7 = MemoryDef(6)
 ; CHECK-NEXT: %4 = load volatile i32
   %4 = load volatile i32, i32* %p, align 4
   %5 = add i32 %4, %1
   ret i32 %5
 }

llvm/trunk/test/Analysis/MemorySSA/many-doms.ll

 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
 ;
 ; Testing many dominators, specifically from a switch statement in C.
 
 declare i1 @getBool() readnone
 
 define i32 @foo(i32* %p) {
 entry:
   br label %loopbegin
 
 loopbegin:
-; CHECK: 7 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
+; CHECK: 8 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
 ; CHECK-NEXT: %n =
   %n = phi i32 [ 0, %entry ], [ %1, %sw.epilog ]
   %m = alloca i32, align 4
   switch i32 %n, label %sw.default [
     i32 0, label %sw.bb
     i32 1, label %sw.bb1
     i32 2, label %sw.bb2
     i32 3, label %sw.bb3
   ]
 
 sw.bb:
-; CHECK: 1 = MemoryDef(7)
+; CHECK: 1 = MemoryDef(8)
 ; CHECK-NEXT: store i32 1
   store i32 1, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb1:
-; CHECK: 2 = MemoryDef(7)
+; CHECK: 2 = MemoryDef(8)
 ; CHECK-NEXT: store i32 2
   store i32 2, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb2:
-; CHECK: 3 = MemoryDef(7)
+; CHECK: 3 = MemoryDef(8)
 ; CHECK-NEXT: store i32 3
   store i32 3, i32* %m, align 4
   br label %sw.epilog
 
 sw.bb3:
-; CHECK: 4 = MemoryDef(7)
+; CHECK: 4 = MemoryDef(8)
 ; CHECK-NEXT: store i32 4
   store i32 4, i32* %m, align 4
   br label %sw.epilog
 
 sw.default:
-; CHECK: 5 = MemoryDef(7)
+; CHECK: 5 = MemoryDef(8)
 ; CHECK-NEXT: store i32 5
   store i32 5, i32* %m, align 4
   br label %sw.epilog
 
 sw.epilog:
-; CHECK: 8 = MemoryPhi({sw.default,5},{sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4})
-; CHECK-NEXT: MemoryUse(8)
+; CHECK: 7 = MemoryPhi({sw.default,5},{sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4})
+; CHECK-NEXT: MemoryUse(7)
 ; CHECK-NEXT: %0 =
   %0 = load i32, i32* %m, align 4
-; CHECK: 6 = MemoryDef(8)
+; CHECK: 6 = MemoryDef(7)
 ; CHECK-NEXT: %1 =
   %1 = load volatile i32, i32* %p, align 4
   %2 = icmp eq i32 %0, %1
   br i1 %2, label %exit, label %loopbegin
 
 exit:
   ret i32 %1
 }

llvm/trunk/test/Analysis/MemorySSA/multi-edges.ll

 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
 ;
 ; Makes sure we have a sane model if both successors of some block is the same
 ; block.
 
 define i32 @foo(i1 %a) {
 entry:
   %0 = alloca i32, align 4
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 4
   store i32 4, i32* %0
   br i1 %a, label %Loop.Body, label %Loop.End
 
 Loop.Body:
-; CHECK: 3 = MemoryPhi({entry,1},{Loop.End,4})
-; CHECK-NEXT: 2 = MemoryDef(3)
+; CHECK: 4 = MemoryPhi({entry,1},{Loop.End,3})
+; CHECK-NEXT: 2 = MemoryDef(4)
 ; CHECK-NEXT: store i32 5
   store i32 5, i32* %0, align 4
   br i1 %a, label %Loop.End, label %Loop.End ; WhyDoWeEvenHaveThatLever.gif
 
 Loop.End:
-; CHECK: 4 = MemoryPhi({entry,1},{Loop.Body,2},{Loop.Body,2})
-; CHECK-NEXT: MemoryUse(4)
+; CHECK: 3 = MemoryPhi({entry,1},{Loop.Body,2},{Loop.Body,2})
+; CHECK-NEXT: MemoryUse(3)
 ; CHECK-NEXT: %1 = load
   %1 = load i32, i32* %0, align 4
   %2 = icmp eq i32 5, %1
   br i1 %2, label %Ret, label %Loop.Body
 
 Ret:
   ret i32 %1
 }

llvm/trunk/test/Analysis/MemorySSA/multiple-backedges-hal.ll

Entry:
   %Val.Entry = call i8 @getValue()
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8 %Val.Entry
   store i8 %Val.Entry, i8* %Arg
   call void @doThingWithoutReading()
   br label %OuterLoop
 
 OuterLoop:
-; CHECK: 4 = MemoryPhi({Entry,1},{InnerLoop.Tail,3})
+; CHECK: 5 = MemoryPhi({Entry,1},{InnerLoop.Tail,3})
 ; CHECK-NEXT: %Val.Outer =
   %Val.Outer = call i8 @getValue()
-; CHECK: 2 = MemoryDef(4)
+; CHECK: 2 = MemoryDef(5)
 ; CHECK-NEXT: store i8 %Val.Outer
   store i8 %Val.Outer, i8* %Arg
   call void @doThingWithoutReading()
   br label %InnerLoop
 
 InnerLoop:
-; CHECK: 5 = MemoryPhi({OuterLoop,2},{InnerLoop,3})
-; CHECK-NEXT: ; MemoryUse(5)
+; CHECK: 4 = MemoryPhi({OuterLoop,2},{InnerLoop,3})
+; CHECK-NEXT: ; MemoryUse(4)
 ; CHECK-NEXT: %StartingAccess = load
   %StartingAccess = load i8, i8* %Arg, align 4
   %Val.Inner = call i8 @getValue()
-; CHECK: 3 = MemoryDef(5)
+; CHECK: 3 = MemoryDef(4)
 ; CHECK-NEXT: store i8 %Val.Inner
   store i8 %Val.Inner, i8* %Arg
   call void @doThingWithoutReading()
   %KeepGoing = call i1 @getBool()
   br i1 %KeepGoing, label %InnerLoop.Tail, label %InnerLoop
 
 InnerLoop.Tail:
   %KeepGoing.Tail = call i1 @getBool()
   br i1 %KeepGoing.Tail, label %End, label %OuterLoop
 
 End:
   ret void
 }

llvm/trunk/test/Analysis/MemorySSA/phi-translation.ll

 
 if.then:
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i8 2, i8* %local2
   store i8 2, i8* %local2
   br i1 %val2, label %phi.2, label %phi.3
 
 phi.3:
-; CHECK: 5 = MemoryPhi({entry,1},{if.then,2})
-; CHECK: 3 = MemoryDef(5)
+; CHECK: 7 = MemoryPhi({entry,1},{if.then,2})
+; CHECK: 3 = MemoryDef(7)
 ; CHECK-NEXT: store i8 3, i8* %local2
   store i8 3, i8* %local2
   br i1 %val3, label %phi.2, label %phi.1
 
 phi.2:
-; CHECK: 6 = MemoryPhi({if.then,2},{phi.3,3})
-; CHECK: 4 = MemoryDef(6)
+; CHECK: 5 = MemoryPhi({if.then,2},{phi.3,3})
+; CHECK: 4 = MemoryDef(5)
 ; CHECK-NEXT: store i8 4, i8* %local2
   store i8 4, i8* %local2
   br label %phi.1
 
 phi.1:
 ; Order matters here; phi.2 needs to come before phi.3, because that's the order
 ; they're visited in.
-; CHECK: 7 = MemoryPhi({phi.2,4},{phi.3,3})
+; CHECK: 6 = MemoryPhi({phi.2,4},{phi.3,3})
 ; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i8, i8* %local
   load i8, i8* %local
   ret void
 }
 
 ; CHECK-LABEL: define void @cross_phi
 define void @cross_phi(i8* noalias %p1, i8* noalias %p2) {

 ; CHECK-LABEL: define void @looped
 define void @looped(i8* noalias %p1, i8* noalias %p2) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8 0, i8* %p1
   store i8 0, i8* %p1
   br label %loop.1
 
 loop.1:
-; CHECK: 5 = MemoryPhi({%0,1},{loop.3,4})
-; CHECK: 2 = MemoryDef(5)
+; CHECK: 6 = MemoryPhi({%0,1},{loop.3,4})
+; CHECK: 2 = MemoryDef(6)
 ; CHECK-NEXT: store i8 0, i8* %p2
   store i8 0, i8* %p2
   br i1 undef, label %loop.2, label %loop.3
 
 loop.2:
-; CHECK: 6 = MemoryPhi({loop.1,2},{loop.3,4})
-; CHECK: 3 = MemoryDef(6)
+; CHECK: 5 = MemoryPhi({loop.1,2},{loop.3,4})
+; CHECK: 3 = MemoryDef(5)
 ; CHECK-NEXT: store i8 1, i8* %p2
   store i8 1, i8* %p2
   br label %loop.3
 
 loop.3:
 ; CHECK: 7 = MemoryPhi({loop.1,2},{loop.2,3})
 ; CHECK: 4 = MemoryDef(7)
 ; CHECK-NEXT: store i8 2, i8* %p2
   store i8 2, i8* %p2
 ; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   br i1 undef, label %loop.2, label %loop.1
 }
 
 ; CHECK-LABEL: define void @looped_visitedonlyonce
 define void @looped_visitedonlyonce(i8* noalias %p1, i8* noalias %p2) {
   br label %while.cond
 
 while.cond:
-; CHECK: 4 = MemoryPhi({%0,liveOnEntry},{if.end,3})
+; CHECK: 5 = MemoryPhi({%0,liveOnEntry},{if.end,3})
 ; CHECK-NEXT: br i1 undef, label %if.then, label %if.end
   br i1 undef, label %if.then, label %if.end
 
 if.then:
-; CHECK: 1 = MemoryDef(4)
+; CHECK: 1 = MemoryDef(5)
 ; CHECK-NEXT: store i8 0, i8* %p1
   store i8 0, i8* %p1
   br i1 undef, label %if.end, label %if.then2
 
 if.then2:
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i8 1, i8* %p2
   store i8 1, i8* %p2
   br label %if.end
 
 if.end:
-; CHECK: 5 = MemoryPhi({while.cond,4},{if.then,1},{if.then2,2})
-; CHECK: MemoryUse(5)
+; CHECK: 4 = MemoryPhi({while.cond,5},{if.then,1},{if.then2,2})
+; CHECK: MemoryUse(4)
 ; CHECK-NEXT: load i8, i8* %p1
   load i8, i8* %p1
-; CHECK: 3 = MemoryDef(5)
+; CHECK: 3 = MemoryDef(4)
 ; CHECK-NEXT: store i8 2, i8* %p2
   store i8 2, i8* %p2
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(4)
 ; CHECK-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   br label %while.cond
 }