Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -183,6 +183,7 @@ // Value Mappings. DenseMap ValueToClass; DenseMap ValueToExpression; + DenseMap MemoryAccessEquiv; // Expression to class mapping. typedef DenseMap ExpressionClassMap; @@ -219,7 +220,7 @@ // DFS info. DenseMap> DFSDomMap; DenseMap InstrDFS; - std::vector DFSToInstr; + std::vector DFSToInstr; // Deletion info. SmallPtrSet InstructionsToErase; @@ -284,6 +285,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 +301,7 @@ const BasicBlock *); const Expression *performSymbolicPHIEvaluation(Instruction *, const BasicBlock *); + bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To); const Expression *performSymbolicAggrValueEvaluation(Instruction *, const BasicBlock *); @@ -310,6 +316,7 @@ void processOutgoingEdges(TerminatorInst *, BasicBlock *); bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const; Value *findConditionEquivalence(Value *, BasicBlock *) const; + MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const; // Elimination. struct ValueDFS; @@ -663,6 +670,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 +716,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 +760,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 +779,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) { @@ -1219,6 +1269,11 @@ 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 +1296,55 @@ } #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. + MemoryAccess *AllSameValue = nullptr; + // See if all arguments are the same, ignoring unreachable arguments + for (unsigned i = 0, e = MP->getNumOperands(); i < e; ++i) { + BasicBlock *B = MP->getIncomingBlock(i); + if (!ReachableBlocks.count(B)) + continue; + MemoryAccess *Operand = + lookupMemoryAccessEquiv(cast(MP->getOperand(i))); + if (AllSameValue && AllSameValue != Operand) { + // Phi node does not have equal arguments, this phi node value numbers to + // itself. + AllSameValue = nullptr; + break; + } else if (!AllSameValue) { + AllSameValue = Operand; + } + } +#ifdef DEBUG + if (AllSameValue) + dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n"; + else + dbgs() << "Memory Phi value numbered to itself\n"; +#endif + + if (setMemoryAccessEquivTo(MP, AllSameValue)) + 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 +1408,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 +1434,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); - } else { - processOutgoingEdges(dyn_cast(I), CurrBlock); - } + if (MemoryPhi *MP = dyn_cast(V)) { + DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n"); + valueNumberMemoryPhi(MP); + continue; + } else if (Instruction *I = dyn_cast(V)) { + updateProcessedCount(I); + valueNumberInstruction(I); + } else + llvm_unreachable("Should have been a MemoryPhi or Instruction"); // Reset after processing (because we may mark ourselves as touched when // we propagate equalities). TouchedInstructions.reset(InstrNum);