Index: llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h +++ llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h @@ -629,7 +629,8 @@ MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); void removeFromLookups(MemoryAccess *); - void placePHINodes(const SmallPtrSetImpl &); + void placePHINodes(const SmallPtrSetImpl &, + const DenseMap &); MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, SmallPtrSet &Visited); Index: llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp @@ -1463,13 +1463,19 @@ } void MemorySSA::placePHINodes( - const SmallPtrSetImpl &DefiningBlocks) { + const SmallPtrSetImpl &DefiningBlocks, + const DenseMap &BBNumbers) { // Determine where our MemoryPhi's should go ForwardIDFCalculator IDFs(*DT); IDFs.setDefiningBlocks(DefiningBlocks); SmallVector IDFBlocks; IDFs.calculate(IDFBlocks); + std::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) { // Insert phi node @@ -1491,6 +1497,8 @@ BasicBlock &StartingPoint = F.getEntryBlock(); LiveOnEntryDef = make_unique(F.getContext(), nullptr, nullptr, &StartingPoint, NextID++); + DenseMap 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 @@ -1500,6 +1508,7 @@ // 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; for (Instruction &I : B) { @@ -1517,7 +1526,7 @@ if (Accesses) DefUseBlocks.insert(&B); } - placePHINodes(DefiningBlocks); + placePHINodes(DefiningBlocks, BBNumbers); // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get // filled in with all blocks. Index: llvm/trunk/test/Transforms/Util/MemorySSA/cyclicphi.ll =================================================================== --- llvm/trunk/test/Transforms/Util/MemorySSA/cyclicphi.ll +++ llvm/trunk/test/Transforms/Util/MemorySSA/cyclicphi.ll @@ -11,7 +11,7 @@ br label %bb26 bb26: ; preds = %bb77, %0 -; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; CHECK: 2 = MemoryPhi({%0,liveOnEntry},{bb77,3}) ; CHECK-NEXT: br i1 undef, label %bb68, label %bb77 br i1 undef, label %bb68, label %bb77 @@ -19,14 +19,14 @@ ; CHECK: MemoryUse(liveOnEntry) ; CHECK-NEXT: %tmp69 = load i64, i64* null, align 8 %tmp69 = load i64, i64* null, align 8 -; CHECK: 1 = MemoryDef(3) +; CHECK: 1 = MemoryDef(2) ; CHECK-NEXT: store i64 %tmp69, i64* %tmp, align 8 store i64 %tmp69, i64* %tmp, align 8 br label %bb77 bb77: ; preds = %bb68, %bb26 -; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1}) -; CHECK: MemoryUse(2) +; CHECK: 3 = MemoryPhi({bb26,2},{bb68,1}) +; CHECK: MemoryUse(3) ; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8 %tmp78 = load i64*, i64** %tmp25, align 8 %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef @@ -41,21 +41,21 @@ br label %bb26 bb26: ; preds = %bb77, %0 -; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; CHECK: 2 = MemoryPhi({%0,liveOnEntry},{bb77,3}) ; CHECK-NEXT: br i1 undef, label %bb68, label %bb77 br i1 undef, label %bb68, label %bb77 bb68: ; preds = %bb26 -; CHECK: MemoryUse(3) +; CHECK: MemoryUse(2) ; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8 %tmp69 = load i64, i64* %g, align 8 -; CHECK: 1 = MemoryDef(3) +; CHECK: 1 = MemoryDef(2) ; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8 store i64 %tmp69, i64* %g, align 8 br label %bb77 bb77: ; preds = %bb68, %bb26 -; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1}) +; CHECK: 3 = MemoryPhi({bb26,2},{bb68,1}) ; CHECK: MemoryUse(liveOnEntry) ; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8 %tmp78 = load i64*, i64** %tmp25, align 8 @@ -70,24 +70,24 @@ br label %bb26 bb26: ; preds = %bb77, %0 -; CHECK: 4 = MemoryPhi({%0,liveOnEntry},{bb77,2}) -; CHECK: MemoryUse(4) +; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; CHECK: MemoryUse(3) ; 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(4) +; CHECK: MemoryUse(3) ; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8 %tmp69 = load i64, i64* %g, align 8 -; CHECK: 1 = MemoryDef(4) +; 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,4},{bb68,1}) -; CHECK: 2 = MemoryDef(3) +; CHECK: 4 = MemoryPhi({bb26,3},{bb68,1}) +; CHECK: 2 = MemoryDef(4) ; CHECK-NEXT: store i64* null, i64** %tmp25, align 8 store i64* null, i64** %tmp25, align 8 br label %bb26 @@ -101,23 +101,23 @@ br label %bb26 bb26: ; preds = %bb77, %0 -; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; CHECK: 2 = MemoryPhi({%0,liveOnEntry},{bb77,3}) ; 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(3) +; CHECK: MemoryUse(2) ; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8 %tmp69 = load i64, i64* %g, align 8 -; CHECK: 1 = MemoryDef(3) +; CHECK: 1 = MemoryDef(2) ; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8 store i64 %tmp69, i64* %g, align 8 br label %bb77 bb77: ; preds = %bb68, %bb26 -; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1}) +; CHECK: 3 = MemoryPhi({bb26,2},{bb68,1}) ; CHECK-NEXT: br label %bb26 br label %bb26 } Index: llvm/trunk/test/Transforms/Util/MemorySSA/many-dom-backedge.ll =================================================================== --- llvm/trunk/test/Transforms/Util/MemorySSA/many-dom-backedge.ll +++ llvm/trunk/test/Transforms/Util/MemorySSA/many-dom-backedge.ll @@ -11,7 +11,7 @@ br label %loopbegin loopbegin: -; CHECK: 9 = 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 @@ -23,42 +23,42 @@ ] sw.bb: -; CHECK: 1 = MemoryDef(9) +; 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(9) +; 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(9) +; CHECK: 3 = MemoryDef(8) ; CHECK-NEXT: store i32 3 store i32 3, i32* %m, align 4 br label %sw.epilog sw.bb3: -; CHECK: 10 = MemoryPhi({loopbegin,9},{sw.almostexit,6}) -; CHECK: 4 = MemoryDef(10) +; CHECK: 9 = MemoryPhi({loopbegin,8},{sw.almostexit,6}) +; CHECK: 4 = MemoryDef(9) ; CHECK-NEXT: store i32 4 store i32 4, i32* %m, align 4 br label %sw.epilog sw.default: -; CHECK: 5 = MemoryDef(9) +; 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.bb3,4},{sw.bb,1},{sw.bb1,2},{sw.bb2,3}) -; CHECK-NEXT: MemoryUse(8) +; CHECK: 10 = MemoryPhi({sw.default,5},{sw.bb3,4},{sw.bb,1},{sw.bb1,2},{sw.bb2,3}) +; CHECK-NEXT: MemoryUse(10) ; CHECK-NEXT: %0 = %0 = load i32, i32* %m, align 4 -; CHECK: 6 = MemoryDef(8) +; CHECK: 6 = MemoryDef(10) ; CHECK-NEXT: %1 = %1 = load volatile i32, i32* %p, align 4 %2 = icmp eq i32 %0, %1 Index: llvm/trunk/test/Transforms/Util/MemorySSA/many-doms.ll =================================================================== --- llvm/trunk/test/Transforms/Util/MemorySSA/many-doms.ll +++ llvm/trunk/test/Transforms/Util/MemorySSA/many-doms.ll @@ -10,7 +10,7 @@ br label %loopbegin loopbegin: -; CHECK: 8 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6}) +; CHECK: 7 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6}) ; CHECK-NEXT: %n = %n = phi i32 [ 0, %entry ], [ %1, %sw.epilog ] %m = alloca i32, align 4 @@ -22,41 +22,41 @@ ] sw.bb: -; CHECK: 1 = MemoryDef(8) +; CHECK: 1 = MemoryDef(7) ; 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(7) ; 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(7) ; CHECK-NEXT: store i32 3 store i32 3, i32* %m, align 4 br label %sw.epilog sw.bb3: -; CHECK: 4 = MemoryDef(8) +; CHECK: 4 = MemoryDef(7) ; 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(7) ; CHECK-NEXT: store i32 5 store i32 5, i32* %m, align 4 br label %sw.epilog sw.epilog: -; CHECK: 7 = MemoryPhi({sw.default,5},{sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4}) -; CHECK-NEXT: MemoryUse(7) +; CHECK: 8 = MemoryPhi({sw.default,5},{sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4}) +; CHECK-NEXT: MemoryUse(8) ; CHECK-NEXT: %0 = %0 = load i32, i32* %m, align 4 -; CHECK: 6 = MemoryDef(7) +; CHECK: 6 = MemoryDef(8) ; CHECK-NEXT: %1 = %1 = load volatile i32, i32* %p, align 4 %2 = icmp eq i32 %0, %1 Index: llvm/trunk/test/Transforms/Util/MemorySSA/phi-translation.ll =================================================================== --- llvm/trunk/test/Transforms/Util/MemorySSA/phi-translation.ll +++ llvm/trunk/test/Transforms/Util/MemorySSA/phi-translation.ll @@ -45,15 +45,15 @@ br i1 %val2, label %phi.2, label %phi.3 phi.3: -; CHECK: 6 = MemoryPhi({entry,1},{if.then,2}) -; CHECK: 3 = MemoryDef(6) +; CHECK: 5 = MemoryPhi({entry,1},{if.then,2}) +; CHECK: 3 = MemoryDef(5) ; CHECK-NEXT: store i8 3, i8* %local2 store i8 3, i8* %local2 br i1 %val3, label %phi.2, label %phi.1 phi.2: -; CHECK: 5 = MemoryPhi({if.then,2},{phi.3,3}) -; CHECK: 4 = MemoryDef(5) +; CHECK: 6 = MemoryPhi({if.then,2},{phi.3,3}) +; CHECK: 4 = MemoryDef(6) ; CHECK-NEXT: store i8 4, i8* %local2 store i8 4, i8* %local2 br label %phi.1 @@ -120,8 +120,8 @@ br label %loop.1 loop.1: -; CHECK: 7 = MemoryPhi({%0,1},{loop.3,4}) -; CHECK: 2 = MemoryDef(7) +; CHECK: 5 = MemoryPhi({%0,1},{loop.3,4}) +; CHECK: 2 = MemoryDef(5) ; CHECK-NEXT: store i8 0, i8* %p2 store i8 0, i8* %p2 br i1 undef, label %loop.2, label %loop.3 @@ -134,8 +134,8 @@ br label %loop.3 loop.3: -; CHECK: 5 = MemoryPhi({loop.1,2},{loop.2,3}) -; CHECK: 4 = MemoryDef(5) +; 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) @@ -149,12 +149,12 @@ br label %while.cond while.cond: -; CHECK: 5 = MemoryPhi({%0,liveOnEntry},{if.end,3}) +; CHECK: 4 = 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(5) +; CHECK: 1 = MemoryDef(4) ; CHECK-NEXT: store i8 0, i8* %p1 store i8 0, i8* %p1 br i1 undef, label %if.end, label %if.then2 @@ -166,14 +166,14 @@ br label %if.end if.end: -; CHECK: 4 = MemoryPhi({while.cond,5},{if.then,1},{if.then2,2}) -; CHECK: MemoryUse(4) +; CHECK: 5 = MemoryPhi({while.cond,4},{if.then,1},{if.then2,2}) +; CHECK: MemoryUse(5) ; CHECK-NEXT: load i8, i8* %p1 load i8, i8* %p1 -; CHECK: 3 = MemoryDef(4) +; CHECK: 3 = MemoryDef(5) ; CHECK-NEXT: store i8 2, i8* %p2 store i8 2, i8* %p2 -; CHECK: MemoryUse(4) +; CHECK: MemoryUse(5) ; CHECK-NEXT: load i8, i8* %p1 load i8, i8* %p1 br label %while.cond