Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -31,6 +31,7 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SparseBitVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" @@ -184,6 +185,13 @@ DenseMap ValueToClass; DenseMap ValueToExpression; + // A table storing which memorydefs/phis represent a memory state provably + // equivalent to another memory state. + // We could use the congruence class machinery, but the MemoryAccess's are + // abstract memory states, so they can only ever be equivalent to each other, + // and not to constants, etc. + DenseMap MemoryAccessEquiv; + // Expression to class mapping. typedef DenseMap ExpressionClassMap; ExpressionClassMap ExpressionToClass; @@ -219,7 +227,7 @@ // DFS info. DenseMap> DFSDomMap; DenseMap InstrDFS; - std::vector DFSToInstr; + std::vector DFSToInstr; // Deletion info. SmallPtrSet InstructionsToErase; @@ -284,6 +292,10 @@ } void initializeCongruenceClasses(Function &F); + // Value number an Instruction or MemoryPhi. + void valueNumberMemoryPhi(MemoryPhi *); + void valueNumberInstruction(Instruction *); + // Symbolic evaluation. const Expression *checkSimplificationResults(Expression *, Instruction *, Value *); @@ -296,6 +308,7 @@ const BasicBlock *); const Expression *performSymbolicPHIEvaluation(Instruction *, const BasicBlock *); + bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To); const Expression *performSymbolicAggrValueEvaluation(Instruction *, const BasicBlock *); @@ -310,6 +323,7 @@ void processOutgoingEdges(TerminatorInst *, BasicBlock *); bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const; Value *findConditionEquivalence(Value *, BasicBlock *) const; + MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const; // Elimination. struct ValueDFS; @@ -663,6 +677,11 @@ return V; } +MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const { + MemoryAccess *Result = MemoryAccessEquiv.lookup(MA); + return Result ? Result : MA; +} + LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp, LoadInst *LI, MemoryAccess *DA, const BasicBlock *B) { @@ -704,8 +723,22 @@ const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I, const BasicBlock *B) { StoreInst *SI = cast(I); - const Expression *E = createStoreExpression(SI, MSSA->getMemoryAccess(SI), B); - return E; + // If this store's memorydef stores the same value as the last store, the + // memory accesses are equivalent. + // Get the expression, if any, for the RHS of the MemoryDef. + MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI); + MemoryAccess *StoreRHS = lookupMemoryAccessEquiv( + cast(StoreAccess)->getDefiningAccess()); + const Expression *OldStore = createStoreExpression(SI, StoreRHS, B); + // See if this store expression already has a value, and it's the same as our + // current store. + CongruenceClass *CC = ExpressionToClass.lookup(OldStore); + if (CC && + CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B)) { + setMemoryAccessEquivTo(StoreAccess, StoreRHS); + return OldStore; + } + return createStoreExpression(SI, StoreAccess, B); } const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I, @@ -734,8 +767,9 @@ } } - const Expression *E = createLoadExpression( - LI->getType(), LI->getPointerOperand(), LI, DefiningAccess, B); + const Expression *E = + createLoadExpression(LI->getType(), LI->getPointerOperand(), LI, + lookupMemoryAccessEquiv(DefiningAccess), B); return E; } @@ -752,6 +786,29 @@ return nullptr; } +// Update the memory access equivalence table to say that From is equal to To, +// and return true if this is different from what already existed in the table. +bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To) { + auto LookupResult = MemoryAccessEquiv.insert({From, nullptr}); + bool Changed = false; + // If it's already in the table, see if the value changed. + if (LookupResult.second) { + if (To && LookupResult.first->second != To) { + // It wasn't equivalent before, and now it is. + LookupResult.first->second = To; + Changed = true; + } else if (!To) { + // It used to be equivalent to something, and now it's not. + MemoryAccessEquiv.erase(LookupResult.first); + Changed = true; + } + } else if (To) { + // It wasn't in the table, but is equivalent to something. + LookupResult.first->second = To; + Changed = true; + } + return Changed; +} // Evaluate PHI nodes symbolically, and create an expression result. const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I, const BasicBlock *B) { @@ -1214,11 +1271,17 @@ BlockInstRange.clear(); TouchedInstructions.clear(); DominatedInstRange.clear(); + MemoryAccessEquiv.clear(); } std::pair NewGVN::assignDFSNumbers(BasicBlock *B, unsigned Start) { unsigned End = Start; + if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) { + InstrDFS[MemPhi] = End++; + DFSToInstr.emplace_back(MemPhi); + } + for (auto &I : *B) { InstrDFS[&I] = End++; DFSToInstr.emplace_back(&I); @@ -1241,6 +1304,61 @@ } #endif } +// Evaluate MemoryPhi nodes symbolically, just like PHI nodes +void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) { + // If all the arguments are the same, the MemoryPhi has the same value as the + // argument. + // Filter out unreachable blocks from our operands. + auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) { + return ReachableBlocks.count(MP->getIncomingBlock(U)); + }); + + assert(Filtered.begin() != Filtered.end() && + "We should not be processing a MemoryPhi in a completely " + "unreachable block"); + + // Transform the remaining operands into operand leaders. + // FIXME: mapped_iterator should have a range version + auto LookupFunc = [&](const Use &U) { + return lookupMemoryAccessEquiv(cast(U)); + }; + auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc); + auto MappedEnd = map_iterator(Filtered.end(), LookupFunc); + + // and now check if all the elements are equal. + // Sadly, we can't use std::equals since these are random access iterators. + MemoryAccess *AllSameValue = *MappedBegin; + ++MappedBegin; + bool AllEqual = std::all_of( + MappedBegin, MappedEnd, + [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; }); + + if (AllEqual) + DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n"); + else + DEBUG(dbgs() << "Memory Phi value numbered to itself\n"); + + if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr)) + markMemoryUsersTouched(MP); +} + +// Value number a single instruction, symbolically evaluating, performing +// congruence finding, and updating mappings. +void NewGVN::valueNumberInstruction(Instruction *I) { + DEBUG(dbgs() << "Processing instruction " << *I << "\n"); + if (I->use_empty() && !I->getType()->isVoidTy()) { + DEBUG(dbgs() << "Skipping unused instruction\n"); + if (isInstructionTriviallyDead(I, TLI)) + markInstructionForDeletion(I); + return; + } + if (!I->isTerminator()) { + const Expression *Symbolized = performSymbolicEvaluation(I, I->getParent()); + performCongruenceFinding(I, Symbolized); + } else { + processOutgoingEdges(dyn_cast(I), I->getParent()); + } +} // This is the main transformation entry point. bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC, @@ -1304,8 +1422,15 @@ // Walk through all the instructions in all the blocks in RPO. for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1; InstrNum = TouchedInstructions.find_next(InstrNum)) { - Instruction *I = DFSToInstr[InstrNum]; - BasicBlock *CurrBlock = I->getParent(); + Value *V = DFSToInstr[InstrNum]; + BasicBlock *CurrBlock = nullptr; + + if (Instruction *I = dyn_cast(V)) + CurrBlock = I->getParent(); + else if (MemoryPhi *MP = dyn_cast(V)) + CurrBlock = MP->getBlock(); + else + llvm_unreachable("DFSToInstr gave us an unknown type of instruction"); // If we hit a new block, do reachability processing. if (CurrBlock != LastBlock) { @@ -1323,22 +1448,16 @@ } updateProcessedCount(CurrBlock); } - DEBUG(dbgs() << "Processing instruction " << *I << "\n"); - if (I->use_empty() && !I->getType()->isVoidTy()) { - DEBUG(dbgs() << "Skipping unused instruction\n"); - if (isInstructionTriviallyDead(I, TLI)) - markInstructionForDeletion(I); - TouchedInstructions.reset(InstrNum); - continue; - } - updateProcessedCount(I); - if (!I->isTerminator()) { - const Expression *Symbolized = performSymbolicEvaluation(I, CurrBlock); - performCongruenceFinding(I, Symbolized); + if (MemoryPhi *MP = dyn_cast(V)) { + DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n"); + valueNumberMemoryPhi(MP); + } else if (Instruction *I = dyn_cast(V)) { + valueNumberInstruction(I); } else { - processOutgoingEdges(dyn_cast(I), CurrBlock); + llvm_unreachable("Should have been a MemoryPhi or Instruction"); } + updateProcessedCount(V); // Reset after processing (because we may mark ourselves as touched when // we propagate equalities). TouchedInstructions.reset(InstrNum); Index: test/Transforms/NewGVN/storeoverstore.ll =================================================================== --- /dev/null +++ test/Transforms/NewGVN/storeoverstore.ll @@ -0,0 +1,80 @@ +; RUN: opt -newgvn -S < %s | FileCheck %s +; RUN: opt -passes=newgvn -S -o - %s | FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" + +;; All the loads in this testcase are useless, but it requires understanding that repeated +;; stores of the same value do not change the memory state to eliminate them. + +define i32 @foo(i32*, i32) { +; CHECK-LABEL: @foo + store i32 5, i32* %0, align 4 + %3 = icmp ne i32 %1, 0 + br i1 %3, label %4, label %7 + +;