Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -682,8 +682,11 @@ #ifndef NDEBUG static const Function *getParent(const Value *V) { - if (const Instruction *inst = dyn_cast(V)) + if (const Instruction *inst = dyn_cast(V)) { + if (!inst->getParent()) + return nullptr; return inst->getParent()->getParent(); + } if (const Argument *arg = dyn_cast(V)) return arg->getParent(); Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -30,9 +30,19 @@ /// tracks what operations have a given value number (IE it also tracks the /// reverse mapping from value number -> operations with that value number), so /// that it only needs to reprocess the instructions that are affected when -/// something's value number changes. The rest of the algorithm is devoted to -/// performing symbolic evaluation, forward propagation, and simplification of -/// operations based on the value numbers deduced so far. +/// something's value number changes. The vast majority of complexity and code +/// in this file is devoted to tracking what value numbers could change for what +/// instructions when various things happen. The rest of the algorithm is +/// devoted to performing symbolic evaluation, forward propagation, and +/// simplification of operations based on the value numbers deduced so far +/// +/// In order to make the GVN mostly-complete, we use a technique derived from +/// "Detection of Redundant Expressions: A Complete and Polynomial-time +/// Algorithm in SSA" by R.R. Pai. The source of incompleteness in most SSA +/// based GVN algorithms is related to their inability to detect equivalence +/// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)). +/// We resolve this issue by generating the equivalent "phi of ops" form for +/// each op of phis we see, in a way that only takes polynomial time to resolve. /// /// We also do not perform elimination by using any published algorithm. All /// published algorithms are O(Instructions). Instead, we use a technique that @@ -104,12 +114,14 @@ STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes"); STATISTIC(NumGVNAvoidedSortedLeaderChanges, "Number of avoided sorted leader changes"); -STATISTIC(NumGVNNotMostDominatingLeader, - "Number of times a member dominated it's new classes' leader"); STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated"); +STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created"); +STATISTIC(NumGVNPHIOfOpsEliminations, + "Number of things eliminated using PHI of ops"); DEBUG_COUNTER(VNCounter, "newgvn-vn", "Controls which instructions are value numbered") - +DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi", + "Controls which instructions we create phi of ops for") // Currently store defining access refinement is too slow due to basicaa being // egregiously slow. This flag lets us keep it working while we work on this // issue. @@ -172,10 +184,9 @@ } } // See if we really were the root of a component, by seeing if we still have - // our DFSNumber. - // If we do, we are the root of the component, and we have completed a - // component. If we do not, - // we are not the root of a component, and belong on the component stack. + // our DFSNumber. If we do, we are the root of the component, and we have + // completed a component. If we do not, we are not the root of a component, + // and belong on the component stack. if (Root.lookup(I) == OurDFS) { unsigned ComponentID = Components.size(); Components.resize(Components.size() + 1); @@ -365,6 +376,7 @@ int StoreCount = 0; }; +struct HashedExpression; namespace llvm { template <> struct DenseMapInfo { static const Expression *getEmptyKey() { @@ -377,9 +389,11 @@ Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return reinterpret_cast(Val); } - static unsigned getHashValue(const Expression *V) { - return static_cast(V->getHashValue()); + static unsigned getHashValue(const Expression *E) { + return static_cast(E->getHashValue()); } + static unsigned getHashValue(const HashedExpression &HE); + static bool isEqual(const HashedExpression &LHS, const Expression *RHS); static bool isEqual(const Expression *LHS, const Expression *RHS) { if (LHS == RHS) return true; @@ -391,6 +405,26 @@ }; } // end namespace llvm +// This is just a wrapper around Expression that computes the hash value once at +// creation time. Hash values for an Expression can't change once they are +// inserted into the DenseMap (it breaks DenseMap), so they must be immutable at +// that point anyway. +struct HashedExpression { + const Expression *E; + unsigned HashVal; + HashedExpression(const Expression *E) + : E(E), HashVal(DenseMapInfo::getHashValue(E)) {} +}; + +unsigned +DenseMapInfo::getHashValue(const HashedExpression &HE) { + return HE.HashVal; +} +bool DenseMapInfo::isEqual(const HashedExpression &LHS, + const Expression *RHS) { + return isEqual(LHS.E, RHS); +} + namespace { class NewGVN { Function &F; @@ -425,6 +459,36 @@ // Value Mappings. DenseMap ValueToClass; DenseMap ValueToExpression; + // Value PHI handling, used to make equivalence between phi(op, op) and + // op(phi, phi). + // These mappings just store various data that would normally be part of the + // IR. + + DenseSet PHINodeUses; + // Map a temporary instruction we created to a parent block. + DenseMap TempToBlock; + // Map between the temporary phis we created and the real instructions they + // are known equivalent to. + DenseMap RealToTemp; + DenseMap TempToReal; + // In order to know when we shoudl re-process instructions that have + // phi-of-ops, we track the set of expressions that they needed as + // leaders. When we disover new leaders for those expressions, we process the + // associated phi-of-op instructions again in case they have changed. The + // other way they may change is if they had leaders, and those leaders + // disappear. However, at the point they have leaders, there are uses of the + // relevant operands in the created phi node, and so they will get reprocessed + // through the normal user marking we perform. + DenseMap> AdditionalUsers; + DenseMap> + ExpressionToPhiOfOps; + + // Map from basic block to the temporary operations we created + DenseMap> PHIOfOpsPHIs; + // Map from temporary operation to MemoryAccess. + DenseMap TempToMemory; + // Set of all temporary instructions we created. + DenseSet AllTempInstructions; // Mapping from predicate info we used to the instructions we used it with. // In order to correctly ensure propagation, we must keep track of what @@ -456,8 +520,8 @@ enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique }; DenseMap MemoryPhiState; - enum PhiCycleState { PCS_Unknown, PCS_CycleFree, PCS_Cycle }; - DenseMap PhiCycleState; + enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle }; + DenseMap InstCycleState; // Expression to class mapping. using ExpressionClassMap = DenseMap; ExpressionClassMap ExpressionToClass; @@ -514,7 +578,7 @@ const Expression *createExpression(Instruction *); const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *); PHIExpression *createPHIExpression(Instruction *, bool &HasBackedge, - bool &AllConstant); + bool &OriginalOpsConstant); const VariableExpression *createVariableExpression(Value *); const ConstantExpression *createConstantExpression(Constant *); const Expression *createVariableOrConstant(Value *V); @@ -553,6 +617,9 @@ return CClass; } void initializeCongruenceClasses(Function &F); + const Expression *makePossiblePhiOfOps(Instruction *, bool, + SmallPtrSetImpl &); + void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue); // Value number an Instruction or MemoryPhi. void valueNumberMemoryPhi(MemoryPhi *); @@ -561,7 +628,8 @@ // Symbolic evaluation. const Expression *checkSimplificationResults(Expression *, Instruction *, Value *); - const Expression *performSymbolicEvaluation(Value *); + const Expression *performSymbolicEvaluation(Value *, + SmallPtrSetImpl &); const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *, Instruction *, MemoryAccess *); const Expression *performSymbolicLoadEvaluation(Instruction *); @@ -585,7 +653,7 @@ bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To); CongruenceClass *getMemoryClass(const MemoryAccess *MA) const; const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const; - bool isMemoryAccessTop(const MemoryAccess *) const; + bool isMemoryAccessTOP(const MemoryAccess *) const; // Ranking unsigned int getRank(const Value *) const; @@ -609,6 +677,7 @@ void replaceInstruction(Instruction *, Value *); void markInstructionForDeletion(Instruction *); void deleteInstructionsInBlock(BasicBlock *); + Value *findPhiOfOpsLeader(const Expression *E, const BasicBlock *BB) const; // New instruction creation. void handleNewInstruction(Instruction *){}; @@ -620,8 +689,10 @@ void markPredicateUsersTouched(Instruction *); void markValueLeaderChangeTouched(CongruenceClass *CC); void markMemoryLeaderChangeTouched(CongruenceClass *CC); + void markPhiOfOpsChanged(const HashedExpression &HE); void addPredicateUsers(const PredicateBase *, Instruction *); void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U); + void addAdditionalUsers(Value *To, Value *User); // Main loop of value numbering void iterateTouchedInstructions(); @@ -629,12 +700,16 @@ // Utilities. void cleanupTables(); std::pair assignDFSNumbers(BasicBlock *, unsigned); - void updateProcessedCount(Value *V); + void updateProcessedCount(const Value *V); void verifyMemoryCongruency() const; void verifyIterationSettled(Function &F); bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const; BasicBlock *getBlockForValue(Value *V) const; void deleteExpression(const Expression *E); + MemoryUseOrDef *getMemoryAccess(const Instruction *) const; + MemoryAccess *getDefiningAccess(const MemoryAccess *) const; + MemoryPhi *getMemoryAccess(const BasicBlock *) const; + template T *getMinDFSOfRange(const Range &) const; unsigned InstrToDFSNum(const Value *V) const { assert(isa(V) && "This should not be used for MemoryAccesses"); return InstrDFS.lookup(V); @@ -654,8 +729,8 @@ ? InstrToDFSNum(cast(MA)->getMemoryInst()) : InstrDFS.lookup(MA); } - bool isCycleFree(const PHINode *PN); - template T *getMinDFSOfRange(const Range &) const; + bool isCycleFree(const Instruction *); + bool isBackedge(BasicBlock *From, BasicBlock *To) const; // Debug counter info. When verifying, we have to reset the value numbering // debug counter to the same state it started in to get the same results. std::pair StartingVNCounter; @@ -683,20 +758,46 @@ return true; } +// Determine if the edge From->To is a backedge +bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const { + if (From == To) + return true; + auto *FromDTN = DT->getNode(From); + auto *ToDTN = DT->getNode(To); + return RPOOrdering.lookup(FromDTN) >= RPOOrdering.lookup(ToDTN); +} + #ifndef NDEBUG static std::string getBlockName(const BasicBlock *B) { return DOTGraphTraits::getSimpleNodeLabel(B, nullptr); } #endif +// Get a MemoryAccess for an instruction, fake or real. +MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const { + auto *Result = MSSA->getMemoryAccess(I); + return Result ? Result : TempToMemory.lookup(I); +} + +// Get a MemoryPhi for a basic block. These are all real. +MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const { + return MSSA->getMemoryAccess(BB); +} + // Get the basic block from an instruction/memory value. BasicBlock *NewGVN::getBlockForValue(Value *V) const { - if (auto *I = dyn_cast(V)) - return I->getParent(); - else if (auto *MP = dyn_cast(V)) - return MP->getBlock(); - llvm_unreachable("Should have been able to figure out a block for our value"); - return nullptr; + if (auto *I = dyn_cast(V)) { + auto *Parent = I->getParent(); + if (Parent) + return Parent; + Parent = TempToBlock.lookup(V); + assert(Parent && "Every fake instruction should have a block"); + return Parent; + } + + auto *MP = dyn_cast(V); + assert(MP && "Should have been an instruction or a MemoryPhi"); + return MP->getBlock(); } // Delete a definitely dead expression, so it can be reused by the expression @@ -708,10 +809,9 @@ const_cast(BE)->deallocateOperands(ArgRecycler); ExpressionAllocator.Deallocate(E); } - PHIExpression *NewGVN::createPHIExpression(Instruction *I, bool &HasBackedge, - bool &AllConstant) { - BasicBlock *PHIBlock = I->getParent(); + bool &OriginalOpsConstant) { + BasicBlock *PHIBlock = getBlockForValue(I); auto *PN = cast(I); auto *E = new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock); @@ -720,24 +820,22 @@ E->setType(I->getType()); E->setOpcode(I->getOpcode()); - unsigned PHIRPO = RPOOrdering.lookup(DT->getNode(PHIBlock)); - // Filter out unreachable phi operands. auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) { return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock}); }); - std::transform(Filtered.begin(), Filtered.end(), op_inserter(E), [&](const Use &U) -> Value * { auto *BB = PN->getIncomingBlock(U); - auto *DTN = DT->getNode(BB); - if (RPOOrdering.lookup(DTN) >= PHIRPO) - HasBackedge = true; - AllConstant &= isa(U) || isa(U); + HasBackedge = HasBackedge || isBackedge(BB, PHIBlock); + OriginalOpsConstant = + OriginalOpsConstant && isa(U); // Don't try to transform self-defined phis. - if (U == PN) + if (U == PN) { return PN; + } + return lookupOperandLeader(U); }); return E; @@ -758,7 +856,7 @@ // whether all members are constant. std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) { auto Operand = lookupOperandLeader(O); - AllConstant &= isa(Operand); + AllConstant = AllConstant && isa(Operand); return Operand; }); @@ -1026,7 +1124,7 @@ // Return true if the MemoryAccess is really equivalent to everything. This is // equivalent to the lattice value "TOP" in most lattices. This is the initial // state of all MemoryAccesses. -bool NewGVN::isMemoryAccessTop(const MemoryAccess *MA) const { +bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const { return getMemoryClass(MA) == TOPClass; } @@ -1072,7 +1170,7 @@ // 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); - auto *StoreAccess = MSSA->getMemoryAccess(SI); + auto *StoreAccess = getMemoryAccess(SI); // Get the expression, if any, for the RHS of the MemoryDef. const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess(); if (EnableStoreRefinement) @@ -1109,7 +1207,7 @@ dyn_cast(lookupOperandLeader(SI->getValueOperand()))) { if ((lookupOperandLeader(LI->getPointerOperand()) == lookupOperandLeader(SI->getPointerOperand())) && - (lookupMemoryLeader(MSSA->getMemoryAccess(LI)->getDefiningAccess()) == + (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) == StoreRHS)) return createVariableExpression(LI); } @@ -1213,8 +1311,9 @@ // Load of undef is undef. if (isa(LoadAddressLeader)) return createConstantExpression(UndefValue::get(LI->getType())); - - MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I); + MemoryAccess *OriginalAccess = getMemoryAccess(I); + MemoryAccess *DefiningAccess = + MSSAWalker->getClobberingMemoryAccess(OriginalAccess); if (!MSSA->isLiveOnEntryDef(DefiningAccess)) { if (auto *MD = dyn_cast(DefiningAccess)) { @@ -1303,6 +1402,7 @@ // operands are equal, because assumes must always be true. if (CmpInst::isTrueWhenEqual(Predicate)) { addPredicateUsers(PI, I); + addAdditionalUsers(Cmp->getOperand(0), I); return createVariableOrConstant(FirstOp); } } @@ -1315,6 +1415,7 @@ if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) || (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) { addPredicateUsers(PI, I); + addAdditionalUsers(Cmp->getOperand(0), I); return createVariableOrConstant(FirstOp); } // Handle the special case of floating point. @@ -1322,6 +1423,7 @@ (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && isa(FirstOp) && !cast(FirstOp)->isZero()) { addPredicateUsers(PI, I); + addAdditionalUsers(Cmp->getOperand(0), I); return createConstantExpression(cast(FirstOp)); } } @@ -1403,34 +1505,37 @@ return Changed; } -// Determine if a phi is cycle-free. That means the values in the phi don't -// depend on any expressions that can change value as a result of the phi. -// For example, a non-cycle free phi would be v = phi(0, v+1). -bool NewGVN::isCycleFree(const PHINode *PN) { - // In order to compute cycle-freeness, we do SCC finding on the phi, and see +// Determine if a instruction is cycle-free. That means the values in the +// instruction don't +// depend on any expressions that can change value as a result of the +// instruction. +// For example, a non-cycle free instruction would be v = phi(0, v+1). +bool NewGVN::isCycleFree(const Instruction *I) { + // In order to compute cycle-freeness, we do SCC finding on the instruction, + // and see // what kind of SCC it ends up in. If it is a singleton, it is cycle-free. // If it is not in a singleton, it is only cycle free if the other members are // all phi nodes (as they do not compute anything, they are copies). TODO: // There are likely a few other intrinsics or expressions that could be // included here, but this happens so infrequently already that it is not // likely to be worth it. - auto PCS = PhiCycleState.lookup(PN); - if (PCS == PCS_Unknown) { - SCCFinder.Start(PN); - auto &SCC = SCCFinder.getComponentFor(PN); + auto ICS = InstCycleState.lookup(I); + if (ICS == ICS_Unknown) { + SCCFinder.Start(I); + auto &SCC = SCCFinder.getComponentFor(I); // It's cycle free if it's size 1 or or the SCC is *only* phi nodes. if (SCC.size() == 1) - PhiCycleState.insert({PN, PCS_CycleFree}); + InstCycleState.insert({I, ICS_CycleFree}); else { bool AllPhis = llvm::all_of(SCC, [](const Value *V) { return isa(V); }); - PCS = AllPhis ? PCS_CycleFree : PCS_Cycle; + ICS = AllPhis ? ICS_CycleFree : ICS_Cycle; for (auto *Member : SCC) if (auto *MemberPhi = dyn_cast(Member)) - PhiCycleState.insert({MemberPhi, PCS}); + InstCycleState.insert({MemberPhi, ICS}); } } - if (PCS == PCS_Cycle) + if (ICS == ICS_Cycle) return false; return true; } @@ -1492,7 +1597,7 @@ // constants, or all operands are ignored but the undef, it also must be // cycle free. if (!AllConstant && HasBackedge && NumOps > 0 && - !isa(AllSameValue) && !isCycleFree(cast(I))) + !isa(AllSameValue) && !isCycleFree(I)) return E; // Only have to check for instructions @@ -1662,8 +1767,17 @@ return createExpression(I); } +// Return true if V is a value that will always be available (IE can +// be placed anywhere) in the function. We don't do globals here +// because they are often worse to put in place. +// TODO: Separate cost from availability +static bool alwaysAvailable(Value *V) { + return isa(V) || isa(V); +} + // Substitute and symbolize the value before value numbering. -const Expression *NewGVN::performSymbolicEvaluation(Value *V) { +const Expression * +NewGVN::performSymbolicEvaluation(Value *V, SmallPtrSetImpl &Visited) { const Expression *E = nullptr; if (auto *C = dyn_cast(V)) E = createConstantExpression(C); @@ -1737,16 +1851,34 @@ default: return nullptr; } + + if (E && !isa(E) && !isa(E) && + PHINodeUses.count(I)) { + // FIXME: Backedge argument + auto *PHIE = makePossiblePhiOfOps(I, false, Visited); + if (PHIE) + return PHIE; + } } return E; } +void NewGVN::addAdditionalUsers(Value *To, Value *User) { + AdditionalUsers[To].insert(User); +} + void NewGVN::markUsersTouched(Value *V) { // Now mark the users as touched. for (auto *User : V->users()) { assert(isa(User) && "Use of value not within an instruction?"); TouchedInstructions.set(InstrToDFSNum(User)); } + const auto Result = AdditionalUsers.find(V); + if (Result != AdditionalUsers.end()) { + for (auto *User : Result->second) + TouchedInstructions.set(InstrToDFSNum(User)); + AdditionalUsers.erase(Result); + } } void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) { @@ -1773,6 +1905,10 @@ // Add I to the set of users of a given predicate. void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) { + // Don't add temporary instructions to the user lists. + if (AllTempInstructions.count(I)) + return; + if (auto *PBranch = dyn_cast(PB)) PredicateToUsers[PBranch->Condition].insert(I); else if (auto *PAssume = dyn_cast(PB)) @@ -1829,11 +1965,11 @@ "Can't get next leader if there is none"); if (CC->getStoreCount() > 0) { if (auto *NL = dyn_cast_or_null(CC->getNextLeader().first)) - return MSSA->getMemoryAccess(NL); + return getMemoryAccess(NL); // Find the store with the minimum DFS number. auto *V = getMinDFSOfRange(make_filter_range( *CC, [&](const Value *V) { return isa(V); })); - return MSSA->getMemoryAccess(cast(V)); + return getMemoryAccess(cast(V)); } assert(CC->getStoreCount() == 0); @@ -1917,32 +2053,11 @@ CongruenceClass *NewClass) { if (I == OldClass->getNextLeader().first) OldClass->resetNextLeader(); - - // It's possible, though unlikely, for us to discover equivalences such - // that the current leader does not dominate the old one. - // This statistic tracks how often this happens. - // We assert on phi nodes when this happens, currently, for debugging, because - // we want to make sure we name phi node cycles properly. - if (isa(NewClass->getLeader()) && NewClass->getLeader() && - I != NewClass->getLeader()) { - auto *IBB = I->getParent(); - auto *NCBB = cast(NewClass->getLeader())->getParent(); - bool Dominated = - IBB == NCBB && InstrToDFSNum(I) < InstrToDFSNum(NewClass->getLeader()); - Dominated = Dominated || DT->properlyDominates(IBB, NCBB); - if (Dominated) { - ++NumGVNNotMostDominatingLeader; - assert( - !isa(I) && - "New class for instruction should not be dominated by instruction"); - } - } - + OldClass->erase(I); + NewClass->insert(I); if (NewClass->getLeader() != I) NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)}); - OldClass->erase(I); - NewClass->insert(I); // Handle our special casing of stores. if (auto *SI = dyn_cast(I)) { OldClass->decStoreCount(); @@ -1977,7 +2092,7 @@ // instructions before. // If it's not a memory use, set the MemoryAccess equivalence - auto *InstMA = dyn_cast_or_null(MSSA->getMemoryAccess(I)); + auto *InstMA = dyn_cast_or_null(getMemoryAccess(I)); bool InstWasMemoryLeader = InstMA && OldClass->getMemoryLeader() == InstMA; if (InstMA) moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass); @@ -2035,22 +2150,36 @@ } } +// For a given expression, mark the phi of ops instructions that could have +// changed as a result. +void NewGVN::markPhiOfOpsChanged(const HashedExpression &HE) { + auto PhiOfOpsSet = ExpressionToPhiOfOps.find_as(HE); + if (PhiOfOpsSet != ExpressionToPhiOfOps.end()) { + for (auto I : PhiOfOpsSet->second) + TouchedInstructions.set(InstrToDFSNum(I)); + ExpressionToPhiOfOps.erase(PhiOfOpsSet); + } +} + // Perform congruence finding on a given value numbering expression. void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) { ValueToExpression[I] = E; + + assert(!TempToReal.lookup(I) && + "Should not congruence find fake instructions"); // This is guaranteed to return something, since it will at least find // TOP. - CongruenceClass *IClass = ValueToClass[I]; assert(IClass && "Should have found a IClass"); // Dead classes should have been eliminated from the mapping. assert(!IClass->isDead() && "Found a dead class"); - CongruenceClass *EClass; + CongruenceClass *EClass = nullptr; + HashedExpression HE(E); if (const auto *VE = dyn_cast(E)) { - EClass = ValueToClass[VE->getVariableValue()]; + EClass = ValueToClass.lookup(VE->getVariableValue()); } else { - auto lookupResult = ExpressionToClass.insert({E, nullptr}); + auto lookupResult = ExpressionToClass.insert_as({E, nullptr}, HE); // If it's not in the value table, create a new congruence class. if (lookupResult.second) { @@ -2099,10 +2228,13 @@ if (ClassChanged || LeaderChanged) { DEBUG(dbgs() << "New class " << EClass->getID() << " for expression " << *E << "\n"); - if (ClassChanged) + if (ClassChanged) { moveValueToNewCongruenceClass(I, E, IClass, EClass); + markPhiOfOpsChanged(HE); + } + markUsersTouched(I); - if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) + if (MemoryAccess *MA = getMemoryAccess(I)) markMemoryUsersTouched(MA); if (auto *CI = dyn_cast(I)) markPredicateUsersTouched(CI); @@ -2128,7 +2260,7 @@ // 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)) + if (MemoryAccess *MemPhi = getMemoryAccess(To)) TouchedInstructions.set(InstrToDFSNum(MemPhi)); auto BI = To->begin(); @@ -2136,6 +2268,12 @@ TouchedInstructions.set(InstrToDFSNum(&*BI)); ++BI; } + const auto PHIResult = PHIOfOpsPHIs.find(To); + if (PHIResult != PHIOfOpsPHIs.end()) { + const auto &PHIs = PHIResult->second; + for (auto I : PHIs) + TouchedInstructions.set(InstrToDFSNum(I)); + } } } } @@ -2225,7 +2363,7 @@ // This also may be a memory defining terminator, in which case, set it // equivalent only to itself. // - auto *MA = MSSA->getMemoryAccess(TI); + auto *MA = getMemoryAccess(TI); if (MA && !isa(MA)) { auto *CC = ensureLeaderOfMemoryClass(MA); if (setMemoryClass(MA, CC)) @@ -2234,6 +2372,160 @@ } } +void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB, + Instruction *ExistingValue) { + InstrDFS[Op] = InstrToDFSNum(ExistingValue); + AllTempInstructions.insert(Op); + PHIOfOpsPHIs[BB].push_back(Op); + TempToBlock[Op] = BB; + if (ExistingValue) { + RealToTemp[ExistingValue] = Op; + TempToReal[Op] = ExistingValue; + } +} + +static bool okayForPHIOfOps(const Instruction *I) { + return isa(I) || isa(I) || isa(I) || + isa(I); +} + +// When we see an instruction that is an op of phis, generate the equivalent phi +// of ops form. +const Expression * +NewGVN::makePossiblePhiOfOps(Instruction *I, bool HasBackedge, + SmallPtrSetImpl &Visited) { + if (!okayForPHIOfOps(I)) + return nullptr; + + if (!Visited.insert(I).second) + return nullptr; + // For now, we require the instruction be cycle free because we don't + // *always* create a phi of ops for instructions that could be done as phi + // of ops, we only do it if we think it is useful. If we did do it all the + // time, we could remove the cycle free check. + if (!isCycleFree(I)) + return nullptr; + + unsigned IDFSNum = InstrToDFSNum(I); + // Pretty much all of the instructions we can convert to phi of ops over a + // backedge that are adds, are really induction variables, and those are + // pretty much pointless to convert. This is very coarse-grained for a + // test, so if we do find some value, we can change it later. + // But otherwise, what can happen is we convert the induction variable from + // + // i = phi (0, tmp) + // tmp = i + 1 + // + // to + // i = phi (0, tmpphi) + // tmpphi = phi(1, tmpphi+1) + // + // Which we don't want to happen. We could just avoid this for all non-cycle + // free phis, and we made go that route. + if (HasBackedge && I->getOpcode() == Instruction::Add) + return nullptr; + + SmallPtrSet ProcessedPHIs; + // TODO: We don't do phi translation on memory accesses because it's + // complicated. For a load, we'd need to be able to simulate a new memoryuse, + // which we don't have a good way of doing ATM. + auto *MemAccess = getMemoryAccess(I); + // If the memory operation is defined by a memory operation this block that + // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi + // can't help, as it would still be killed by that memory operation. + if (MemAccess && !isa(MemAccess->getDefiningAccess()) && + MemAccess->getDefiningAccess()->getBlock() == I->getParent()) + return nullptr; + + // Convert op of phis to phi of ops + for (auto &Op : I->operands()) { + if (!isa(Op)) + continue; + auto *OpPHI = cast(Op); + // No point in doing this for one-operand phis. + if (OpPHI->getNumOperands() == 1) + continue; + if (!DebugCounter::shouldExecute(PHIOfOpsCounter)) + return nullptr; + SmallVector, 4> Ops; + auto *PHIBlock = getBlockForValue(OpPHI); + for (auto PredBB : OpPHI->blocks()) { + Value *FoundVal = nullptr; + // We could just skip unreachable edges entirely but it's tricky to do + // with rewriting existing phi nodes. + if (ReachableEdges.count({PredBB, PHIBlock})) { + // Clone the instruction, create an expression from it, and see if we + // have a leader. + Instruction *ValueOp = I->clone(); + auto Iter = TempToMemory.end(); + if (MemAccess) + Iter = TempToMemory.insert({ValueOp, MemAccess}).first; + + for (auto &Op : ValueOp->operands()) { + Op = Op->DoPHITranslation(PHIBlock, PredBB); + // When this operand changes, it could change whether there is a + // leader for us or not. + addAdditionalUsers(Op, I); + } + // Make sure it's marked as a temporary instruction. + AllTempInstructions.insert(ValueOp); + // and make sure anything that tries to add it's DFS number is + // redirected to the instruction we are making a phi of ops + // for. + InstrDFS.insert({ValueOp, IDFSNum}); + const Expression *E = performSymbolicEvaluation(ValueOp, Visited); + InstrDFS.erase(ValueOp); + AllTempInstructions.erase(ValueOp); + delete ValueOp; + if (MemAccess) + TempToMemory.erase(Iter); + if (!E) + return nullptr; + FoundVal = findPhiOfOpsLeader(E, PredBB); + if (!FoundVal) { + ExpressionToPhiOfOps[E].insert(I); + return nullptr; + } + if (auto *SI = dyn_cast(FoundVal)) + FoundVal = SI->getValueOperand(); + } else { + DEBUG(dbgs() << "Skipping phi of ops operand for incoming block " + << getBlockName(PredBB) + << " because the block is unreachable\n"); + FoundVal = UndefValue::get(I->getType()); + } + + Ops.push_back({FoundVal, PredBB}); + DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in " + << getBlockName(PredBB) << "\n"); + } + auto *ValuePHI = RealToTemp.lookup(I); + bool NewPHI = false; + if (!ValuePHI) { + ValuePHI = PHINode::Create(I->getType(), OpPHI->getNumOperands()); + addPhiOfOps(ValuePHI, PHIBlock, I); + NewPHI = true; + NumGVNPHIOfOpsCreated++; + } + if (NewPHI) { + for (auto PHIOp : Ops) + ValuePHI->addIncoming(PHIOp.first, PHIOp.second); + } else { + unsigned int i = 0; + for (auto PHIOp : Ops) { + ValuePHI->setIncomingValue(i, PHIOp.first); + ValuePHI->setIncomingBlock(i, PHIOp.second); + ++i; + } + } + + DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I + << "\n"); + return performSymbolicEvaluation(ValuePHI, Visited); + } + return nullptr; +} + // The algorithm initially places the values of the routine in the TOP // congruence class. The leader of TOP is the undetermined value `undef`. // When the algorithm has finished, values still in TOP are unreachable. @@ -2276,6 +2568,12 @@ TOPClass->incStoreCount(); } for (auto &I : *BB) { + // TODO: Move to helper + if (isa(&I)) + for (auto *U : I.users()) + if (auto *UInst = dyn_cast(U)) + if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst)) + PHINodeUses.insert(UInst); // Don't insert void terminators into the class. We don't value number // them, and they just end up sitting in TOP. if (isa(I) && I.getType()->isVoidTy()) @@ -2300,12 +2598,36 @@ CongruenceClasses[i] = nullptr; } + // Destroy the value expressions + SmallVector TempInst(AllTempInstructions.begin(), + AllTempInstructions.end()); + AllTempInstructions.clear(); + + // We have to drop all references for everything first, so there are no uses + // left as we delete them. + for (auto *I : TempInst) { + I->dropAllReferences(); + } + + while (!TempInst.empty()) { + auto *I = TempInst.back(); + TempInst.pop_back(); + delete I; + } + ValueToClass.clear(); ArgRecycler.clear(ExpressionAllocator); ExpressionAllocator.Reset(); CongruenceClasses.clear(); ExpressionToClass.clear(); ValueToExpression.clear(); + RealToTemp.clear(); + TempToReal.clear(); + AdditionalUsers.clear(); + ExpressionToPhiOfOps.clear(); + TempToBlock.clear(); + TempToMemory.clear(); + PHIOfOpsPHIs.clear(); ReachableBlocks.clear(); ReachableEdges.clear(); #ifndef NDEBUG @@ -2321,14 +2643,17 @@ MemoryToUsers.clear(); } +// Assign local DFS number mapping to instructions, and leave space for Value +// PHI's. std::pair NewGVN::assignDFSNumbers(BasicBlock *B, unsigned Start) { unsigned End = Start; - if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) { + if (MemoryAccess *MemPhi = getMemoryAccess(B)) { InstrDFS[MemPhi] = End++; DFSToInstr.emplace_back(MemPhi); } + // Then the real block goes next. for (auto &I : *B) { // There's no need to call isInstructionTriviallyDead more than once on // an instruction. Therefore, once we know that an instruction is dead @@ -2339,7 +2664,6 @@ markInstructionForDeletion(&I); continue; } - InstrDFS[&I] = End++; DFSToInstr.emplace_back(&I); } @@ -2350,7 +2674,7 @@ return std::make_pair(Start, End); } -void NewGVN::updateProcessedCount(Value *V) { +void NewGVN::updateProcessedCount(const Value *V) { #ifndef NDEBUG if (ProcessedCount.count(V) == 0) { ProcessedCount.insert({V, 1}); @@ -2369,7 +2693,7 @@ const BasicBlock *PHIBlock = MP->getBlock(); auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) { return lookupMemoryLeader(cast(U)) != MP && - !isMemoryAccessTop(cast(U)) && + !isMemoryAccessTOP(cast(U)) && ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock}); }); // If all that is left is nothing, our memoryphi is undef. We keep it as @@ -2422,18 +2746,17 @@ DEBUG(dbgs() << "Processing instruction " << *I << "\n"); if (!I->isTerminator()) { const Expression *Symbolized = nullptr; + SmallPtrSet Visited; if (DebugCounter::shouldExecute(VNCounter)) { - Symbolized = performSymbolicEvaluation(I); + Symbolized = performSymbolicEvaluation(I, Visited); } else { // Mark the instruction as unused so we don't value number it again. InstrDFS[I] = 0; } // If we couldn't come up with a symbolic expression, use the unknown // expression - if (Symbolized == nullptr) { + if (Symbolized == nullptr) Symbolized = createUnknownExpression(I); - } - performCongruenceFinding(I, Symbolized); } else { // Handle terminators that return values. All of them produce values we @@ -2523,13 +2846,15 @@ return false; if (auto *MemDef = dyn_cast(Pair.first)) return !isInstructionTriviallyDead(MemDef->getMemoryInst()); + if (auto *MemPhi = dyn_cast(Pair.first)) + return all_of(MemPhi->operands(), [&](const Value *V) { + return isMemoryAccessTOP(cast(V)); + }); return true; }; auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred); for (auto KV : Filtered) { - assert(KV.second != TOPClass && - "Memory not unreachable but ended up in TOP"); if (auto *FirstMUD = dyn_cast(KV.first)) { auto *SecondMUD = dyn_cast(KV.second->getMemoryLeader()); if (FirstMUD && SecondMUD) @@ -2623,7 +2948,7 @@ // Nothing set, nothing to iterate, just return. if (FirstInstr == -1) return; - BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr)); + const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr)); while (TouchedInstructions.any()) { ++Iterations; // Walk through all the instructions in all the blocks in RPO. @@ -2641,7 +2966,7 @@ } Value *V = InstrFromDFSNum(InstrNum); - BasicBlock *CurrBlock = getBlockForValue(V); + const BasicBlock *CurrBlock = getBlockForValue(V); // If we hit a new block, do reachability processing. if (CurrBlock != LastBlock) { @@ -2722,6 +3047,7 @@ BlockInstRange.insert({B, BlockRange}); ICount += BlockRange.second - BlockRange.first; } + initializeCongruenceClasses(F); TouchedInstructions.resize(ICount); // Ensure we don't end up resizing the expressionToClass map, as @@ -2732,9 +3058,10 @@ // Initialize the touched instructions to include the entry block. const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock()); TouchedInstructions.set(InstRange.first, InstRange.second); + DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock()) + << " marked reachable\n"); ReachableBlocks.insert(&F.getEntryBlock()); - initializeCongruenceClasses(F); iterateTouchedInstructions(); verifyMemoryCongruency(); verifyIterationSettled(F); @@ -2746,7 +3073,8 @@ if (!ToErase->use_empty()) ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType())); - ToErase->eraseFromParent(); + if (ToErase->getParent()) + ToErase->eraseFromParent(); } // Delete all unreachable blocks. @@ -2765,14 +3093,6 @@ return Changed; } -// Return true if V is a value that will always be available (IE can -// be placed anywhere) in the function. We don't do globals here -// because they are often worse to put in place. -// TODO: Separate cost from availability -static bool alwaysAvailable(Value *V) { - return isa(V) || isa(V); -} - struct NewGVN::ValueDFS { int DFSIn = 0; int DFSOut = 0; @@ -2862,9 +3182,21 @@ } assert(isa(D) && "The dense set member should always be an instruction"); - VDDef.LocalNum = InstrToDFSNum(D); - DFSOrderedSet.emplace_back(VDDef); Instruction *Def = cast(D); + VDDef.LocalNum = InstrToDFSNum(D); + DFSOrderedSet.push_back(VDDef); + // If there is a phi node equivalent, add it + if (auto *PN = RealToTemp.lookup(Def)) { + auto *PHIE = + dyn_cast_or_null(ValueToExpression.lookup(Def)); + if (PHIE) { + VDDef.Def.setInt(false); + VDDef.Def.setPointer(PN); + VDDef.LocalNum = 0; + DFSOrderedSet.push_back(VDDef); + } + } + unsigned int UseCount = 0; // Now add the uses. for (auto &U : Def->uses()) { @@ -2881,7 +3213,7 @@ // they are from. VDUse.LocalNum = InstrDFS.size() + 1; } else { - IBlock = I->getParent(); + IBlock = getBlockForValue(I); VDUse.LocalNum = InstrToDFSNum(I); } @@ -3051,6 +3383,37 @@ }; } +// Given a value and a basic block we are trying to see if it is available in, +// see if the value has a leader available in that block. +Value *NewGVN::findPhiOfOpsLeader(const Expression *E, + const BasicBlock *BB) const { + // It would already be constant if we could make it constant + if (auto *CE = dyn_cast(E)) + return CE->getConstantValue(); + if (auto *VE = dyn_cast(E)) + return VE->getVariableValue(); + + auto *CC = ExpressionToClass.lookup(E); + if (!CC) + return nullptr; + if (alwaysAvailable(CC->getLeader())) + return CC->getLeader(); + + for (auto Member : *CC) { + auto *MemberInst = dyn_cast(Member); + // Anything that isn't an instruction is always available. + if (!MemberInst) + return Member; + // If we are looking for something in the same block as the member, it must + // be a leader because this function is looking for operands for a phi node. + if (MemberInst->getParent() == BB || + DT->dominates(MemberInst->getParent(), BB)) { + return Member; + } + } + return nullptr; +} + bool NewGVN::eliminateInstructions(Function &F) { // This is a non-standard eliminator. The normal way to eliminate is // to walk the dominator tree in order, keeping track of available @@ -3080,26 +3443,45 @@ // Since we are going to walk the domtree anyway, and we can't guarantee the // DFS numbers are updated, we compute some ourselves. DT->updateDFSNumbers(); - - for (auto &B : F) { - if (!ReachableBlocks.count(&B)) { - for (const auto S : successors(&B)) { - for (auto II = S->begin(); isa(II); ++II) { - auto &Phi = cast(*II); - DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block " - << getBlockName(&B) - << " with undef due to it being unreachable\n"); - for (auto &Operand : Phi.incoming_values()) - if (Phi.getIncomingBlock(Operand) == &B) - Operand.set(UndefValue::get(Phi.getType())); + auto ReplaceUnreachablePHIArgs = [&](PHINode &PHI, BasicBlock *BB) { + for (auto &Operand : PHI.incoming_values()) + if (!ReachableEdges.count({PHI.getIncomingBlock(Operand), BB})) { + DEBUG(dbgs() << "Replacing incoming value of " << PHI << " for block " + << getBlockName(PHI.getIncomingBlock(Operand)) + << " with undef due to it being unreachable\n"); + Operand.set(UndefValue::get(PHI.getType())); + } + }; + SmallPtrSet BlocksWithPhis; + for (auto &B : F) + if ((!B.empty() && isa(*B.begin())) || + (PHIOfOpsPHIs.find(&B) != PHIOfOpsPHIs.end())) + BlocksWithPhis.insert(&B); + DenseMap ReachablePredCount; + for (auto KV : ReachableEdges) + ReachablePredCount[KV.getEnd()]++; + for (auto *BB : BlocksWithPhis) + // TODO: It would be faster to use getNumIncomingBlocks() on a phi node in + // the block and subtract the pred count, but it's more complicated. + if (ReachablePredCount.lookup(BB) != + std::distance(pred_begin(BB), pred_end(BB))) { + for (auto II = BB->begin(); isa(II); ++II) { + auto &PHI = cast(*II); + ReplaceUnreachablePHIArgs(PHI, BB); + } + auto PHIResult = PHIOfOpsPHIs.find(BB); + if (PHIResult != PHIOfOpsPHIs.end()) { + auto &PHIs = PHIResult->second; + for (auto I : PHIs) { + auto *PHI = dyn_cast(I); + ReplaceUnreachablePHIArgs(*PHI, BB); } } } - } // Map to store the use counts DenseMap UseCounts; - for (CongruenceClass *CC : reverse(CongruenceClasses)) { + for (auto *CC : reverse(CongruenceClasses)) { // Track the equivalent store info so we can decide whether to try // dead store elimination. SmallVector PossibleDeadStores; @@ -3147,7 +3529,7 @@ DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID() << "\n"); // If this is a singleton, we can skip it. - if (CC->size() != 1) { + if (CC->size() != 1 || RealToTemp.lookup(Leader)) { // This is a stack because equality replacement/etc may place // constants in the middle of the member list, and we want to use // those constant values in preference to the current leader, over @@ -3169,6 +3551,22 @@ // We ignore void things because we can't get a value from them. if (Def && Def->getType()->isVoidTy()) continue; + auto *DefInst = dyn_cast_or_null(Def); + if (DefInst && AllTempInstructions.count(DefInst)) { + auto *PN = cast(DefInst); + + // If this is a value phi and that's the expression we used, insert + // it into the program + // remove from temp instruction list. + AllTempInstructions.erase(PN); + auto *DefBlock = getBlockForValue(Def); + DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def + << " into block " + << getBlockName(getBlockForValue(Def)) << "\n"); + PN->insertBefore(&DefBlock->front()); + Def = PN; + NumGVNPHIOfOpsEliminations++; + } if (EliminationStack.empty()) { DEBUG(dbgs() << "Elimination Stack is empty\n"); @@ -3327,7 +3725,6 @@ } } } - return AnythingReplaced; } @@ -3337,19 +3734,23 @@ // we will simplify an operation with all constants so that it doesn't matter // what order they appear in. unsigned int NewGVN::getRank(const Value *V) const { - // Prefer undef to anything else + // Prefer constants to undef to anything else + // Undef is a constant, have to check it first. + // Prefer smaller constants to constantexprs + if (isa(V)) + return 2; if (isa(V)) - return 0; - if (isa(V)) return 1; + if (isa(V)) + return 0; else if (auto *A = dyn_cast(V)) - return 2 + A->getArgNo(); + return 3 + A->getArgNo(); // Need to shift the instruction DFS by number of arguments + 3 to account for // the constant and argument ranking above. unsigned Result = InstrToDFSNum(V); if (Result > 0) - return 3 + NumFuncArgs + Result; + return 4 + NumFuncArgs + Result; // Unreachable or something else, just return a really large number. return ~0; } Index: test/Transforms/NewGVN/completeness.ll =================================================================== --- /dev/null +++ test/Transforms/NewGVN/completeness.ll @@ -0,0 +1,415 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" + +define i32 @test1(i32, i8**) { +; CHECK-LABEL: @test1( +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i32 [[TMP0:%.*]], 0 +; CHECK-NEXT: br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]] +; CHECK: br label [[TMP6:%.*]] +; CHECK: br label [[TMP6]] +; CHECK: [[TMP7:%.*]] = phi i32 [ 75, [[TMP4]] ], [ 105, [[TMP5]] ] +; CHECK-NEXT: [[DOT0:%.*]] = phi i32 [ 5, [[TMP4]] ], [ 7, [[TMP5]] ] +; CHECK-NEXT: ret i32 [[TMP7]] +; + %3 = icmp ne i32 %0, 0 + br i1 %3, label %4, label %5 + +;