Index: llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp +++ llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp @@ -341,6 +341,7 @@ void cleanupTables(); std::pair assignDFSNumbers(BasicBlock *, unsigned); void updateProcessedCount(Value *V); + void verifyMemoryCongruency(); }; char NewGVN::ID = 0; @@ -703,6 +704,8 @@ const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I, const BasicBlock *B) { + // Unlike loads, we never try to eliminate stores, so we do not check if they + // are simple and avoid value numbering them. auto *SI = cast(I); // If this store's memorydef stores the same value as the last store, the // memory accesses are equivalent. @@ -712,13 +715,14 @@ 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; + // current store. FIXME: Right now, we only do this for simple stores. + if (SI->isSimple()) { + CongruenceClass *CC = ExpressionToClass.lookup(OldStore); + if (CC && CC->DefiningExpr && isa(CC->DefiningExpr) && + CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B)) + return createStoreExpression(SI, StoreRHS, B); } + return createStoreExpression(SI, StoreAccess, B); } @@ -727,7 +731,7 @@ auto *LI = cast(I); // We can eliminate in favor of non-simple loads, but we won't be able to - // eliminate them. + // eliminate the loads themselves. if (!LI->isSimple()) return nullptr; @@ -769,24 +773,30 @@ // 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}); + DEBUG(dbgs() << "Setting " << *From << " equivalent to "); + if (!To) + DEBUG(dbgs() << "itself"); + else + DEBUG(dbgs() << *To); + DEBUG(dbgs() << "\n"); + auto LookupResult = MemoryAccessEquiv.find(From); bool Changed = false; // If it's already in the table, see if the value changed. - if (LookupResult.second) { - if (To && LookupResult.first->second != To) { + if (LookupResult != MemoryAccessEquiv.end()) { + if (To && LookupResult->second != To) { // It wasn't equivalent before, and now it is. - LookupResult.first->second = To; + LookupResult->second = To; Changed = true; } else if (!To) { // It used to be equivalent to something, and now it's not. - MemoryAccessEquiv.erase(LookupResult.first); + MemoryAccessEquiv.erase(LookupResult); Changed = true; } - } else if (To) { - // It wasn't in the table, but is equivalent to something. - LookupResult.first->second = To; - Changed = true; + } else { + assert(!To && + "Memory equivalence should never change from nothing to something"); } + return Changed; } // Evaluate PHI nodes symbolically, and create an expression result. @@ -1043,10 +1053,15 @@ EClass = NewClass; DEBUG(dbgs() << "Created new congruence class for " << *V << " using expression " << *E << " at " << NewClass->ID - << "\n"); + << " and leader " << *(NewClass->RepLeader) << "\n"); DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n"); } else { EClass = lookupResult.first->second; + if (isa(E)) + assert(isa(EClass->RepLeader) && + "Any class with a constant expression should have a " + "constant leader"); + assert(EClass && "Somehow don't have an eclass"); assert(!EClass->Dead && "We accidentally looked up a dead class"); @@ -1082,10 +1097,32 @@ } } } + markUsersTouched(V); - if (auto *I = dyn_cast(V)) - if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) + if (auto *I = dyn_cast(V)) { + if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) { + // If this is a MemoryDef, we need to update the equivalence table. If + // we + // determined the expression is congruent to a different memory state, + // use that different memory state. If we determined it didn't, we + // update + // that as well. Note that currently, we do not guarantee the + // "different" memory state dominates us. The goal is to make things + // that are congruent look congruent, not ensure we can eliminate one in + // favor of the other. + // Right now, the only way they can be equivalent is for store + // expresions. + if (!isa(MA)) { + if (E && isa(E) && EClass->Members.size() != 1) { + auto *DefAccess = cast(E)->getDefiningAccess(); + setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr); + } else { + setMemoryAccessEquivTo(MA, nullptr); + } + } markMemoryUsersTouched(MA); + } + } } } @@ -1108,6 +1145,9 @@ // impact predicates. Otherwise, only mark the phi nodes as touched, as // they are the only thing that depend on new edges. Anything using their // values will get propagated to if necessary. + if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To)) + TouchedInstructions.set(InstrDFS[MemPhi]); + auto BI = To->begin(); while (isa(BI)) { TouchedInstructions.set(InstrDFS[&*BI]); @@ -1198,6 +1238,11 @@ BasicBlock *TargetBlock = TI->getSuccessor(i); updateReachableEdge(B, TargetBlock); } + + // This also may be a memory defining terminator, in which case, set it + // equivalent to nothing. + if (MemoryAccess *MA = MSSA->getMemoryAccess(TI)) + setMemoryAccessEquivTo(MA, nullptr); } } @@ -1211,11 +1256,25 @@ // Initialize all other instructions to be in INITIAL class. CongruenceClass::MemberSet InitialValues; InitialClass = createCongruenceClass(nullptr, nullptr); - for (auto &B : F) + for (auto &B : F) { + if (auto *MP = MSSA->getMemoryAccess(&B)) + MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()}); + for (auto &I : B) { InitialValues.insert(&I); ValueToClass[&I] = InitialClass; + // All memory accesses are equivalent to live on entry to start. They must + // be initialized to something so that initial changes are noticed. For + // the maximal answer, we initialize them all to be the same as + // liveOnEntry. Note that to save time, we only initialize the + // MemoryDef's for stores and all MemoryPhis to be equal. Right now, no + // other expression can generate a memory equivalence. If we start + // handling memcpy/etc, we can expand this. + if (isa(&I)) + MemoryAccessEquiv.insert( + {MSSA->getMemoryAccess(&I), MSSA->getLiveOnEntryDef()}); } + } InitialClass->Members.swap(InitialValues); // Initialize arguments to be in their own unique congruence classes @@ -1340,6 +1399,67 @@ } } +// Verify the that the memory equivalence table makes sense relative to the +// congruence classes. +void NewGVN::verifyMemoryCongruency() { + // Anything equivalent in the memory access table should be in the same + // congruence class. + + // Filter out the unreachable and trivially dead entries, because they may + // never have been updated if the instructions were not processed. + auto ReachableAccessPred = + [&](const std::pair Pair) { + bool Result = ReachableBlocks.count(Pair.first->getBlock()); + if (!Result) + return false; + if (auto *MemDef = dyn_cast(Pair.first)) + return !isInstructionTriviallyDead(MemDef->getMemoryInst()); + return true; + }; + + auto Filtered = make_filter_range(MemoryAccessEquiv, ReachableAccessPred); + for (auto KV : Filtered) { + assert(KV.first != KV.second && + "We added a useless equivalence to the memory equivalence table"); + // Unreachable instructions may not have changed because we never process + // them. + if (!ReachableBlocks.count(KV.first->getBlock())) + continue; + if (auto *FirstMUD = dyn_cast(KV.first)) { + auto *SecondMUD = dyn_cast(KV.second); + if (FirstMUD && SecondMUD) { + auto *FirstInst = FirstMUD->getMemoryInst(); + auto *SecondInst = SecondMUD->getMemoryInst(); + assert( + ValueToClass.lookup(FirstInst) == ValueToClass.lookup(SecondInst) && + "The instructions for these memory operations should have been in " + "the same congruence class"); + } + } else if (auto *FirstMP = dyn_cast(KV.first)) { + + // We can only sanely verify that MemoryDefs in the operand list all have + // the same class. + auto ReachableOperandPred = [&](const Use &U) { + return ReachableBlocks.count(FirstMP->getIncomingBlock(U)) && + isa(U); + + }; + // All arguments should in the same class, ignoring unreachable arguments + auto FilteredPhiArgs = + make_filter_range(FirstMP->operands(), ReachableOperandPred); + SmallVector PhiOpClasses; + std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(), + std::back_inserter(PhiOpClasses), [&](const Use &U) { + const MemoryDef *MD = cast(U); + return ValueToClass.lookup(MD->getMemoryInst()); + }); + assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), + PhiOpClasses.begin()) && + "All MemoryPhi arguments should be in the same class"); + } + } +} + // This is the main transformation entry point. bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC, TargetLibraryInfo *_TLI, AliasAnalysis *_AA, @@ -1468,6 +1588,10 @@ } } +// FIXME: Move this to expensive checks when we are satisfied with NewGVN +#ifndef NDEBUG + verifyMemoryCongruency(); +#endif Changed |= eliminateInstructions(F); // Delete all instructions marked for deletion.