diff options
Diffstat (limited to 'lib/Transforms/Scalar/NewGVN.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/NewGVN.cpp | 803 |
1 files changed, 556 insertions, 247 deletions
diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp index 8ac10348eb77..9ebf2d769356 100644 --- a/lib/Transforms/Scalar/NewGVN.cpp +++ b/lib/Transforms/Scalar/NewGVN.cpp @@ -1,4 +1,4 @@ -//===---- NewGVN.cpp - Global Value Numbering Pass --------------*- C++ -*-===// +//===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===// // // The LLVM Compiler Infrastructure // @@ -6,6 +6,7 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This file implements the new LLVM's Global Value Numbering pass. /// GVN partitions values computed by a function into congruence classes. @@ -48,59 +49,81 @@ /// published algorithms are O(Instructions). Instead, we use a technique that /// is O(number of operations with the same value number), enabling us to skip /// trying to eliminate things that have unique value numbers. +// //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/NewGVN.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/Hashing.h" -#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SparseBitVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CFGPrinter.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Argument.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" #include "llvm/IR/Dominators.h" -#include "llvm/IR/GlobalVariable.h" -#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Metadata.h" -#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/ArrayRecycler.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/DebugCounter.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/PointerLikeTypeTraits.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Scalar/GVNExpression.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/PredicateInfo.h" #include "llvm/Transforms/Utils/VNCoercion.h" -#include <numeric> -#include <unordered_map> +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <map> +#include <memory> +#include <set> +#include <string> +#include <tuple> #include <utility> #include <vector> + using namespace llvm; -using namespace PatternMatch; using namespace llvm::GVNExpression; using namespace llvm::VNCoercion; + #define DEBUG_TYPE "newgvn" STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted"); @@ -118,15 +141,19 @@ 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") + "Controls which instructions are value numbered"); DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi", - "Controls which instructions we create phi of ops for") + "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. static cl::opt<bool> EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden); +/// Currently, the generation "phi of ops" can result in correctness issues. +static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true), + cl::Hidden); + //===----------------------------------------------------------------------===// // GVN Pass //===----------------------------------------------------------------------===// @@ -134,6 +161,7 @@ static cl::opt<bool> EnableStoreRefinement("enable-store-refinement", // Anchor methods. namespace llvm { namespace GVNExpression { + Expression::~Expression() = default; BasicExpression::~BasicExpression() = default; CallExpression::~CallExpression() = default; @@ -141,8 +169,11 @@ LoadExpression::~LoadExpression() = default; StoreExpression::~StoreExpression() = default; AggregateValueExpression::~AggregateValueExpression() = default; PHIExpression::~PHIExpression() = default; -} -} + +} // end namespace GVNExpression +} // end namespace llvm + +namespace { // Tarjan's SCC finding algorithm with Nuutila's improvements // SCCIterator is actually fairly complex for the simple thing we want. @@ -153,7 +184,6 @@ PHIExpression::~PHIExpression() = default; // instructions, // not generic values (arguments, etc). struct TarjanSCC { - TarjanSCC() : Components(1) {} void Start(const Instruction *Start) { @@ -208,15 +238,19 @@ private: Stack.push_back(I); } } + unsigned int DFSNum = 1; SmallPtrSet<const Value *, 8> InComponent; DenseMap<const Value *, unsigned int> Root; SmallVector<const Value *, 8> Stack; + // Store the components as vector of ptr sets, because we need the topo order // of SCC's, but not individual member order SmallVector<SmallPtrSet<const Value *, 8>, 8> Components; + DenseMap<const Value *, unsigned> ValueToComponent; }; + // Congruence classes represent the set of expressions/instructions // that are all the same *during some scope in the function*. // That is, because of the way we perform equality propagation, and @@ -265,7 +299,9 @@ public: explicit CongruenceClass(unsigned ID) : ID(ID) {} CongruenceClass(unsigned ID, Value *Leader, const Expression *E) : ID(ID), RepLeader(Leader), DefiningExpr(E) {} + unsigned getID() const { return ID; } + // True if this class has no members left. This is mainly used for assertion // purposes, and for skipping empty classes. bool isDead() const { @@ -273,6 +309,7 @@ public: // perspective, it's really dead. return empty() && memory_empty(); } + // Leader functions Value *getLeader() const { return RepLeader; } void setLeader(Value *Leader) { RepLeader = Leader; } @@ -280,7 +317,6 @@ public: return NextLeader; } void resetNextLeader() { NextLeader = {nullptr, ~0}; } - void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) { if (LeaderPair.second < NextLeader.second) NextLeader = LeaderPair; @@ -315,6 +351,7 @@ public: iterator_range<MemoryMemberSet::const_iterator> memory() const { return make_range(memory_begin(), memory_end()); } + void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); } void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); } @@ -354,34 +391,48 @@ public: private: unsigned ID; + // Representative leader. Value *RepLeader = nullptr; + // The most dominating leader after our current leader, because the member set // is not sorted and is expensive to keep sorted all the time. std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U}; + // If this is represented by a store, the value of the store. Value *RepStoredValue = nullptr; + // If this class contains MemoryDefs or MemoryPhis, this is the leading memory // access. const MemoryAccess *RepMemoryAccess = nullptr; + // Defining Expression. const Expression *DefiningExpr = nullptr; + // Actual members of this class. MemberSet Members; + // This is the set of MemoryPhis that exist in the class. MemoryDefs and // MemoryUses have real instructions representing them, so we only need to // track MemoryPhis here. MemoryMemberSet MemoryMembers; + // Number of stores in this congruence class. // This is used so we can detect store equivalence changes properly. int StoreCount = 0; }; +} // end anonymous namespace + namespace llvm { + struct ExactEqualsExpression { const Expression &E; + explicit ExactEqualsExpression(const Expression &E) : E(E) {} + hash_code getComputedHash() const { return E.getComputedHash(); } + bool operator==(const Expression &Other) const { return E.exactlyEquals(Other); } @@ -393,17 +444,21 @@ template <> struct DenseMapInfo<const Expression *> { Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; return reinterpret_cast<const Expression *>(Val); } + static const Expression *getTombstoneKey() { auto Val = static_cast<uintptr_t>(~1U); Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; return reinterpret_cast<const Expression *>(Val); } + static unsigned getHashValue(const Expression *E) { return E->getComputedHash(); } + static unsigned getHashValue(const ExactEqualsExpression &E) { return E.getComputedHash(); } + static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) { if (RHS == getTombstoneKey() || RHS == getEmptyKey()) return false; @@ -425,9 +480,11 @@ template <> struct DenseMapInfo<const Expression *> { return *LHS == *RHS; } }; + } // end namespace llvm namespace { + class NewGVN { Function &F; DominatorTree *DT; @@ -464,16 +521,22 @@ class NewGVN { // Value Mappings. DenseMap<Value *, CongruenceClass *> ValueToClass; DenseMap<Value *, const Expression *> 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<const Instruction *> PHINodeUses; + SmallPtrSet<const Instruction *, 8> PHINodeUses; + + DenseMap<const Value *, bool> OpSafeForPHIOfOps; + // Map a temporary instruction we created to a parent block. DenseMap<const Value *, BasicBlock *> TempToBlock; - // Map between the temporary phis we created and the real instructions they - // are known equivalent to. + + // Map between the already in-program instructions and the temporary phis we + // created that they are known equivalent to. DenseMap<const Value *, PHINode *> RealToTemp; + // In order to know when we should re-process instructions that have // phi-of-ops, we track the set of expressions that they needed as // leaders. When we discover new leaders for those expressions, we process the @@ -485,19 +548,32 @@ class NewGVN { mutable DenseMap<const Value *, SmallPtrSet<Value *, 2>> AdditionalUsers; DenseMap<const Expression *, SmallPtrSet<Instruction *, 2>> ExpressionToPhiOfOps; - // Map from basic block to the temporary operations we created - DenseMap<const BasicBlock *, SmallVector<PHINode *, 8>> PHIOfOpsPHIs; + // Map from temporary operation to MemoryAccess. DenseMap<const Instruction *, MemoryUseOrDef *> TempToMemory; + // Set of all temporary instructions we created. + // Note: This will include instructions that were just created during value + // numbering. The way to test if something is using them is to check + // RealToTemp. DenseSet<Instruction *> AllTempInstructions; + // This is the set of instructions to revisit on a reachability change. At + // the end of the main iteration loop it will contain at least all the phi of + // ops instructions that will be changed to phis, as well as regular phis. + // During the iteration loop, it may contain other things, such as phi of ops + // instructions that used edge reachability to reach a result, and so need to + // be revisited when the edge changes, independent of whether the phi they + // depended on changes. + DenseMap<BasicBlock *, SparseBitVector<>> RevisitOnReachabilityChange; + // 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 // comparisons we used, so that when the values of the comparisons change, we // propagate the information to the places we used the comparison. mutable DenseMap<const Value *, SmallPtrSet<Instruction *, 2>> PredicateToUsers; + // the same reasoning as PredicateToUsers. When we skip MemoryAccesses for // stores, we no longer can rely solely on the def-use chains of MemorySSA. mutable DenseMap<const MemoryAccess *, SmallPtrSet<MemoryAccess *, 2>> @@ -525,6 +601,7 @@ class NewGVN { enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle }; mutable DenseMap<const Instruction *, InstCycleState> InstCycleState; + // Expression to class mapping. using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>; ExpressionClassMap ExpressionToClass; @@ -581,6 +658,7 @@ public: : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), DL(DL), PredInfo(make_unique<PredicateInfo>(F, *DT, *AC)), SQ(DL, TLI, DT, AC) { } + bool runGVN(); private: @@ -588,7 +666,13 @@ private: const Expression *createExpression(Instruction *) const; const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *, Instruction *) const; - PHIExpression *createPHIExpression(Instruction *, bool &HasBackEdge, + + // Our canonical form for phi arguments is a pair of incoming value, incoming + // basic block. + using ValPair = std::pair<Value *, BasicBlock *>; + + PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *, + BasicBlock *, bool &HasBackEdge, bool &OriginalOpsConstant) const; const DeadExpression *createDeadExpression() const; const VariableExpression *createVariableExpression(Value *) const; @@ -617,6 +701,7 @@ private: CC->setMemoryLeader(MA); return CC; } + CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) { auto *CC = getMemoryClass(MA); if (CC->getMemoryLeader() != MA) @@ -630,10 +715,21 @@ private: ValueToClass[Member] = CClass; return CClass; } + void initializeCongruenceClasses(Function &F); - const Expression *makePossiblePhiOfOps(Instruction *, + const Expression *makePossiblePHIOfOps(Instruction *, SmallPtrSetImpl<Value *> &); + Value *findLeaderForInst(Instruction *ValueOp, + SmallPtrSetImpl<Value *> &Visited, + MemoryAccess *MemAccess, Instruction *OrigInst, + BasicBlock *PredBB); + bool OpIsSafeForPHIOfOpsHelper(Value *V, const BasicBlock *PHIBlock, + SmallPtrSetImpl<const Value *> &Visited, + SmallVectorImpl<Instruction *> &Worklist); + bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock, + SmallPtrSetImpl<const Value *> &); void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue); + void removePhiOfOps(Instruction *I, PHINode *PHITemp); // Value number an Instruction or MemoryPhi. void valueNumberMemoryPhi(MemoryPhi *); @@ -650,7 +746,10 @@ private: const Expression *performSymbolicLoadEvaluation(Instruction *) const; const Expression *performSymbolicStoreEvaluation(Instruction *) const; const Expression *performSymbolicCallEvaluation(Instruction *) const; - const Expression *performSymbolicPHIEvaluation(Instruction *) const; + void sortPHIOps(MutableArrayRef<ValPair> Ops) const; + const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>, + Instruction *I, + BasicBlock *PHIBlock) const; const Expression *performSymbolicAggrValueEvaluation(Instruction *) const; const Expression *performSymbolicCmpEvaluation(Instruction *) const; const Expression *performSymbolicPredicateInfoEvaluation(Instruction *) const; @@ -658,6 +757,7 @@ private: // Congruence finding. bool someEquivalentDominates(const Instruction *, const Instruction *) const; Value *lookupOperandLeader(Value *) const; + CongruenceClass *getClassForExpression(const Expression *E) const; void performCongruenceFinding(Instruction *, const Expression *); void moveValueToNewCongruenceClass(Instruction *, const Expression *, CongruenceClass *, CongruenceClass *); @@ -692,10 +792,11 @@ private: void replaceInstruction(Instruction *, Value *); void markInstructionForDeletion(Instruction *); void deleteInstructionsInBlock(BasicBlock *); - Value *findPhiOfOpsLeader(const Expression *E, const BasicBlock *BB) const; + Value *findPHIOfOpsLeader(const Expression *, const Instruction *, + const BasicBlock *) const; // New instruction creation. - void handleNewInstruction(Instruction *){}; + void handleNewInstruction(Instruction *) {} // Various instruction touch utilities template <typename Map, typename KeyType, typename Func> @@ -731,6 +832,7 @@ private: MemoryAccess *getDefiningAccess(const MemoryAccess *) const; MemoryPhi *getMemoryAccess(const BasicBlock *) const; template <class T, class Range> T *getMinDFSOfRange(const Range &) const; + unsigned InstrToDFSNum(const Value *V) const { assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses"); return InstrDFS.lookup(V); @@ -739,7 +841,9 @@ private: unsigned InstrToDFSNum(const MemoryAccess *MA) const { return MemoryToDFSNum(MA); } + Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; } + // Given a MemoryAccess, return the relevant instruction DFS number. Note: // This deliberately takes a value so it can be used with Use's, which will // auto-convert to Value's but not to MemoryAccess's. @@ -750,12 +854,15 @@ private: ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst()) : InstrDFS.lookup(MA); } + bool isCycleFree(const Instruction *) const; 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<int, int> StartingVNCounter; }; + } // end anonymous namespace template <typename T> @@ -781,11 +888,9 @@ bool StoreExpression::equals(const Expression &Other) const { // 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); + return From == To || + RPOOrdering.lookup(DT->getNode(From)) >= + RPOOrdering.lookup(DT->getNode(To)); } #ifndef NDEBUG @@ -830,51 +935,77 @@ void NewGVN::deleteExpression(const Expression *E) const { const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler); ExpressionAllocator.Deallocate(E); } -PHIExpression *NewGVN::createPHIExpression(Instruction *I, bool &HasBackedge, + +// If V is a predicateinfo copy, get the thing it is a copy of. +static Value *getCopyOf(const Value *V) { + if (auto *II = dyn_cast<IntrinsicInst>(V)) + if (II->getIntrinsicID() == Intrinsic::ssa_copy) + return II->getOperand(0); + return nullptr; +} + +// Return true if V is really PN, even accounting for predicateinfo copies. +static bool isCopyOfPHI(const Value *V, const PHINode *PN) { + return V == PN || getCopyOf(V) == PN; +} + +static bool isCopyOfAPHI(const Value *V) { + auto *CO = getCopyOf(V); + return CO && isa<PHINode>(CO); +} + +// Sort PHI Operands into a canonical order. What we use here is an RPO +// order. The BlockInstRange numbers are generated in an RPO walk of the basic +// blocks. +void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const { + std::sort(Ops.begin(), Ops.end(), [&](const ValPair &P1, const ValPair &P2) { + return BlockInstRange.lookup(P1.second).first < + BlockInstRange.lookup(P2.second).first; + }); +} + +// 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. +static bool alwaysAvailable(Value *V) { + return isa<Constant>(V) || isa<Argument>(V); +} + +// Create a PHIExpression from an array of {incoming edge, value} pairs. I is +// the original instruction we are creating a PHIExpression for (but may not be +// a phi node). We require, as an invariant, that all the PHIOperands in the +// same block are sorted the same way. sortPHIOps will sort them into a +// canonical order. +PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands, + const Instruction *I, + BasicBlock *PHIBlock, + bool &HasBackedge, bool &OriginalOpsConstant) const { - BasicBlock *PHIBlock = getBlockForValue(I); - auto *PN = cast<PHINode>(I); - auto *E = - new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock); + unsigned NumOps = PHIOperands.size(); + auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock); E->allocateOperands(ArgRecycler, ExpressionAllocator); - E->setType(I->getType()); - E->setOpcode(I->getOpcode()); - - // NewGVN assumes the operands of a PHI node are in a consistent order across - // PHIs. LLVM doesn't seem to always guarantee this. While we need to fix - // this in LLVM at some point we don't want GVN to find wrong congruences. - // Therefore, here we sort uses in predecessor order. - // We're sorting the values by pointer. In theory this might be cause of - // non-determinism, but here we don't rely on the ordering for anything - // significant, e.g. we don't create new instructions based on it so we're - // fine. - SmallVector<const Use *, 4> PHIOperands; - for (const Use &U : PN->operands()) - PHIOperands.push_back(&U); - std::sort(PHIOperands.begin(), PHIOperands.end(), - [&](const Use *U1, const Use *U2) { - return PN->getIncomingBlock(*U1) < PN->getIncomingBlock(*U2); - }); + E->setType(PHIOperands.begin()->first->getType()); + E->setOpcode(Instruction::PHI); // Filter out unreachable phi operands. - auto Filtered = make_filter_range(PHIOperands, [&](const Use *U) { - if (*U == PN) - return false; - if (!ReachableEdges.count({PN->getIncomingBlock(*U), PHIBlock})) + auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) { + auto *BB = P.second; + if (auto *PHIOp = dyn_cast<PHINode>(I)) + if (isCopyOfPHI(P.first, PHIOp)) + return false; + if (!ReachableEdges.count({BB, PHIBlock})) return false; // Things in TOPClass are equivalent to everything. - if (ValueToClass.lookup(*U) == TOPClass) + if (ValueToClass.lookup(P.first) == TOPClass) return false; - return lookupOperandLeader(*U) != PN; + OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first); + HasBackedge = HasBackedge || isBackedge(BB, PHIBlock); + return lookupOperandLeader(P.first) != I; }); std::transform(Filtered.begin(), Filtered.end(), op_inserter(E), - [&](const Use *U) -> Value * { - auto *BB = PN->getIncomingBlock(*U); - HasBackedge = HasBackedge || isBackedge(BB, PHIBlock); - OriginalOpsConstant = - OriginalOpsConstant && isa<Constant>(*U); - return lookupOperandLeader(*U); + [&](const ValPair &P) -> Value * { + return lookupOperandLeader(P.first); }); return E; } @@ -929,8 +1060,6 @@ const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T, // Take a Value returned by simplification of Expression E/Instruction // I, and see if it resulted in a simpler expression. If so, return // that expression. -// TODO: Once finished, this should not take an Instruction, we only -// use it for printing. const Expression *NewGVN::checkSimplificationResults(Expression *E, Instruction *I, Value *V) const { @@ -954,25 +1083,37 @@ const Expression *NewGVN::checkSimplificationResults(Expression *E, } CongruenceClass *CC = ValueToClass.lookup(V); - if (CC && CC->getDefiningExpr()) { - // If we simplified to something else, we need to communicate - // that we're users of the value we simplified to. - if (I != V) { + if (CC) { + if (CC->getLeader() && CC->getLeader() != I) { // Don't add temporary instructions to the user lists. if (!AllTempInstructions.count(I)) addAdditionalUsers(V, I); + return createVariableOrConstant(CC->getLeader()); } + if (CC->getDefiningExpr()) { + // If we simplified to something else, we need to communicate + // that we're users of the value we simplified to. + if (I != V) { + // Don't add temporary instructions to the user lists. + if (!AllTempInstructions.count(I)) + addAdditionalUsers(V, I); + } - if (I) - DEBUG(dbgs() << "Simplified " << *I << " to " - << " expression " << *CC->getDefiningExpr() << "\n"); - NumGVNOpsSimplified++; - deleteExpression(E); - return CC->getDefiningExpr(); + if (I) + DEBUG(dbgs() << "Simplified " << *I << " to " + << " expression " << *CC->getDefiningExpr() << "\n"); + NumGVNOpsSimplified++; + deleteExpression(E); + return CC->getDefiningExpr(); + } } + return nullptr; } +// Create a value expression from the instruction I, replacing operands with +// their leaders. + const Expression *NewGVN::createExpression(Instruction *I) const { auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands()); @@ -987,15 +1128,7 @@ const Expression *NewGVN::createExpression(Instruction *I) const { if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) E->swapOperands(0, 1); } - - // Perform simplificaiton - // TODO: Right now we only check to see if we get a constant result. - // We may get a less than constant, but still better, result for - // some operations. - // IE - // add 0, x -> x - // and x, x -> x - // We should handle this by simply rewriting the expression. + // Perform simplification. if (auto *CI = dyn_cast<CmpInst>(I)) { // Sort the operand value numbers so x<y and y>x get the same value // number. @@ -1016,7 +1149,7 @@ const Expression *NewGVN::createExpression(Instruction *I) const { return SimplifiedE; } else if (isa<SelectInst>(I)) { if (isa<Constant>(E->getOperand(0)) || - E->getOperand(0) == E->getOperand(1)) { + E->getOperand(1) == E->getOperand(2)) { assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() && E->getOperand(2)->getType() == I->getOperand(2)->getType()); Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1), @@ -1121,7 +1254,7 @@ NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const { bool NewGVN::someEquivalentDominates(const Instruction *Inst, const Instruction *U) const { auto *CC = ValueToClass.lookup(Inst); - // This must be an instruction because we are only called from phi nodes + // This must be an instruction because we are only called from phi nodes // in the case that the value it needs to check against is an instruction. // The most likely candiates for dominance are the leader and the next leader. @@ -1139,6 +1272,8 @@ bool NewGVN::someEquivalentDominates(const Instruction *Inst, // any of these siblings. if (!CC) return false; + if (alwaysAvailable(CC->getLeader())) + return true; if (DT->dominates(cast<Instruction>(CC->getLeader()), U)) return true; if (CC->getNextLeader().first && @@ -1229,9 +1364,9 @@ const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const { if (EnableStoreRefinement) StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess); // If we bypassed the use-def chains, make sure we add a use. + StoreRHS = lookupMemoryLeader(StoreRHS); if (StoreRHS != StoreAccess->getDefiningAccess()) addMemoryUsers(StoreRHS, StoreAccess); - StoreRHS = lookupMemoryLeader(StoreRHS); // If we are defined by ourselves, use the live on entry def. if (StoreRHS == StoreAccess) StoreRHS = MSSA->getLiveOnEntryDef(); @@ -1278,7 +1413,7 @@ NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr, if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) { // Can't forward from non-atomic to atomic without violating memory model. // Also don't need to coerce if they are the same type, we will just - // propogate.. + // propagate. if (LI->isAtomic() > DepSI->isAtomic() || LoadType == DepSI->getValueOperand()->getType()) return nullptr; @@ -1292,14 +1427,13 @@ NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr, getConstantStoreValueForLoad(C, Offset, LoadType, DL)); } } - - } else if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { + } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) { // Can't forward from non-atomic to atomic without violating memory model. if (LI->isAtomic() > DepLI->isAtomic()) return nullptr; int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL); if (Offset >= 0) { - // We can coerce a constant load into a load + // We can coerce a constant load into a load. if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI))) if (auto *PossibleConstant = getConstantLoadValueForLoad(C, Offset, LoadType, DL)) { @@ -1308,8 +1442,7 @@ NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr, return createConstantExpression(PossibleConstant); } } - - } else if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) { + } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) { int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL); if (Offset >= 0) { if (auto *PossibleConstant = @@ -1381,9 +1514,13 @@ const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const { } } - const Expression *E = createLoadExpression(LI->getType(), LoadAddressLeader, - LI, DefiningAccess); - return E; + const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI, + DefiningAccess); + // If our MemoryLeader is not our defining access, add a use to the + // MemoryLeader, so that we get reprocessed when it changes. + if (LE->getMemoryLeader() != DefiningAccess) + addMemoryUsers(LE->getMemoryLeader(), OriginalAccess); + return LE; } const Expression * @@ -1402,7 +1539,7 @@ NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { auto *Cond = PWC->Condition; // If this a copy of the condition, it must be either true or false depending - // on the predicate info type and edge + // on the predicate info type and edge. if (CopyOf == Cond) { // We should not need to add predicate users because the predicate info is // already a use of this operand. @@ -1438,7 +1575,7 @@ NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0)); Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1)); bool SwappedOps = false; - // Sort the ops + // Sort the ops. if (shouldSwapOperands(FirstOp, SecondOp)) { std::swap(FirstOp, SecondOp); SwappedOps = true; @@ -1464,7 +1601,8 @@ NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) || (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) { addPredicateUsers(PI, I); - addAdditionalUsers(Cmp->getOperand(0), I); + addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0), + I); return createVariableOrConstant(FirstOp); } // Handle the special case of floating point. @@ -1472,7 +1610,8 @@ NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && isa<ConstantFP>(FirstOp) && !cast<ConstantFP>(FirstOp)->isZero()) { addPredicateUsers(PI, I); - addAdditionalUsers(Cmp->getOperand(0), I); + addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0), + I); return createConstantExpression(cast<Constant>(FirstOp)); } } @@ -1502,7 +1641,6 @@ const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) const { // Retrieve the memory class for a given MemoryAccess. CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const { - auto *Result = MemoryAccessToClass.lookup(MA); assert(Result && "Should have found memory class"); return Result; @@ -1571,8 +1709,9 @@ bool NewGVN::isCycleFree(const Instruction *I) const { if (SCC.size() == 1) InstCycleState.insert({I, ICS_CycleFree}); else { - bool AllPhis = - llvm::all_of(SCC, [](const Value *V) { return isa<PHINode>(V); }); + bool AllPhis = llvm::all_of(SCC, [](const Value *V) { + return isa<PHINode>(V) || isCopyOfAPHI(V); + }); ICS = AllPhis ? ICS_CycleFree : ICS_Cycle; for (auto *Member : SCC) if (auto *MemberPhi = dyn_cast<PHINode>(Member)) @@ -1584,17 +1723,20 @@ bool NewGVN::isCycleFree(const Instruction *I) const { return true; } -// Evaluate PHI nodes symbolically, and create an expression result. -const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) const { +// Evaluate PHI nodes symbolically and create an expression result. +const Expression * +NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps, + Instruction *I, + BasicBlock *PHIBlock) const { // True if one of the incoming phi edges is a backedge. bool HasBackedge = false; // All constant tracks the state of whether all the *original* phi operands // This is really shorthand for "this phi cannot cycle due to forward // change in value of the phi is guaranteed not to later change the value of // the phi. IE it can't be v = phi(undef, v+1) - bool AllConstant = true; - auto *E = - cast<PHIExpression>(createPHIExpression(I, HasBackedge, AllConstant)); + bool OriginalOpsConstant = true; + auto *E = cast<PHIExpression>(createPHIExpression( + PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant)); // We match the semantics of SimplifyPhiNode from InstructionSimplify here. // See if all arguments are the same. // We track if any were undef because they need special handling. @@ -1620,14 +1762,10 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) const { deleteExpression(E); return createDeadExpression(); } - unsigned NumOps = 0; Value *AllSameValue = *(Filtered.begin()); ++Filtered.begin(); // Can't use std::equal here, sadly, because filter.begin moves. - if (llvm::all_of(Filtered, [&](Value *Arg) { - ++NumOps; - return Arg == AllSameValue; - })) { + if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) { // In LLVM's non-standard representation of phi nodes, it's possible to have // phi nodes with cycles (IE dependent on other phis that are .... dependent // on the original phi node), especially in weird CFG's where some arguments @@ -1642,9 +1780,8 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) const { // multivalued phi, and we need to know if it's cycle free in order to // evaluate whether we can ignore the undef. The other parts of this are // just shortcuts. If there is no backedge, or all operands are - // constants, or all operands are ignored but the undef, it also must be - // cycle free. - if (!AllConstant && HasBackedge && NumOps > 0 && + // constants, it also must be cycle free. + if (HasBackedge && !OriginalOpsConstant && !isa<UndefValue>(AllSameValue) && !isCycleFree(I)) return E; @@ -1708,8 +1845,11 @@ NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const { return createAggregateValueExpression(I); } + const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { - auto *CI = dyn_cast<CmpInst>(I); + assert(isa<CmpInst>(I) && "Expected a cmp instruction."); + + auto *CI = cast<CmpInst>(I); // See if our operands are equal to those of a previous predicate, and if so, // if it implies true or false. auto Op0 = lookupOperandLeader(CI->getOperand(0)); @@ -1720,7 +1860,7 @@ const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { OurPredicate = CI->getSwappedPredicate(); } - // Avoid processing the same info twice + // Avoid processing the same info twice. const PredicateBase *LastPredInfo = nullptr; // See if we know something about the comparison itself, like it is the target // of an assume. @@ -1754,7 +1894,7 @@ const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { // %operands are considered users of the icmp. // *Currently* we only check one level of comparisons back, and only mark one - // level back as touched when changes appen . If you modify this code to look + // level back as touched when changes happen. If you modify this code to look // back farther through comparisons, you *must* mark the appropriate // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if // we know something just from the operands themselves @@ -1767,10 +1907,15 @@ const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { if (PI == LastPredInfo) continue; LastPredInfo = PI; - - // TODO: Along the false edge, we may know more things too, like icmp of + // In phi of ops cases, we may have predicate info that we are evaluating + // in a different context. + if (!DT->dominates(PBranch->To, getBlockForValue(I))) + continue; + // TODO: Along the false edge, we may know more things too, like + // icmp of // same operands is false. - // TODO: We only handle actual comparison conditions below, not and/or. + // TODO: We only handle actual comparison conditions below, not + // and/or. auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition); if (!BranchCond) continue; @@ -1798,7 +1943,6 @@ const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { return createConstantExpression( ConstantInt::getFalse(CI->getType())); } - } else { // Just handle the ne and eq cases, where if we have the same // operands, we may know something. @@ -1822,14 +1966,6 @@ const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { 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<Constant>(V) || isa<Argument>(V); -} - // Substitute and symbolize the value before value numbering. const Expression * NewGVN::performSymbolicEvaluation(Value *V, @@ -1849,9 +1985,15 @@ NewGVN::performSymbolicEvaluation(Value *V, case Instruction::InsertValue: E = performSymbolicAggrValueEvaluation(I); break; - case Instruction::PHI: - E = performSymbolicPHIEvaluation(I); - break; + case Instruction::PHI: { + SmallVector<ValPair, 3> Ops; + auto *PN = cast<PHINode>(I); + for (unsigned i = 0; i < PN->getNumOperands(); ++i) + Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)}); + // Sort to ensure the invariant createPHIExpression requires is met. + sortPHIOps(Ops); + E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I)); + } break; case Instruction::Call: E = performSymbolicCallEvaluation(I); break; @@ -1861,13 +2003,13 @@ NewGVN::performSymbolicEvaluation(Value *V, case Instruction::Load: E = performSymbolicLoadEvaluation(I); break; - case Instruction::BitCast: { + case Instruction::BitCast: E = createExpression(I); - } break; + break; case Instruction::ICmp: - case Instruction::FCmp: { + case Instruction::FCmp: E = performSymbolicCmpEvaluation(I); - } break; + break; case Instruction::Add: case Instruction::FAdd: case Instruction::Sub: @@ -2017,7 +2159,7 @@ T *NewGVN::getMinDFSOfRange(const Range &R) const { const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const { // TODO: If this ends up to slow, we can maintain a next memory leader like we // do for regular leaders. - // Make sure there will be a leader to find + // Make sure there will be a leader to find. assert(!CC->definesNoMemory() && "Can't get next leader if there is none"); if (CC->getStoreCount() > 0) { if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first)) @@ -2194,7 +2336,7 @@ void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E, // For a given expression, mark the phi of ops instructions that could have // changed as a result. void NewGVN::markPhiOfOpsChanged(const Expression *E) { - touchAndErase(ExpressionToPhiOfOps, ExactEqualsExpression(*E)); + touchAndErase(ExpressionToPhiOfOps, E); } // Perform congruence finding on a given value numbering expression. @@ -2315,14 +2457,11 @@ void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { if (MemoryAccess *MemPhi = getMemoryAccess(To)) TouchedInstructions.set(InstrToDFSNum(MemPhi)); - auto BI = To->begin(); - while (isa<PHINode>(BI)) { - TouchedInstructions.set(InstrToDFSNum(&*BI)); - ++BI; - } - for_each_found(PHIOfOpsPHIs, To, [&](const PHINode *I) { - TouchedInstructions.set(InstrToDFSNum(I)); - }); + // FIXME: We should just add a union op on a Bitvector and + // SparseBitVector. We can do it word by word faster than we are doing it + // here. + for (auto InstNum : RevisitOnReachabilityChange[To]) + TouchedInstructions.set(InstNum); } } } @@ -2419,24 +2558,146 @@ void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) { } } +// Remove the PHI of Ops PHI for I +void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) { + InstrDFS.erase(PHITemp); + // It's still a temp instruction. We keep it in the array so it gets erased. + // However, it's no longer used by I, or in the block + TempToBlock.erase(PHITemp); + RealToTemp.erase(I); + // We don't remove the users from the phi node uses. This wastes a little + // time, but such is life. We could use two sets to track which were there + // are the start of NewGVN, and which were added, but right nowt he cost of + // tracking is more than the cost of checking for more phi of ops. +} + +// Add PHI Op in BB as a PHI of operations version of ExistingValue. void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue) { InstrDFS[Op] = InstrToDFSNum(ExistingValue); AllTempInstructions.insert(Op); - PHIOfOpsPHIs[BB].push_back(Op); TempToBlock[Op] = BB; RealToTemp[ExistingValue] = Op; + // Add all users to phi node use, as they are now uses of the phi of ops phis + // and may themselves be phi of ops. + for (auto *U : ExistingValue->users()) + if (auto *UI = dyn_cast<Instruction>(U)) + PHINodeUses.insert(UI); } static bool okayForPHIOfOps(const Instruction *I) { + if (!EnablePhiOfOps) + return false; return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) || isa<LoadInst>(I); } +bool NewGVN::OpIsSafeForPHIOfOpsHelper( + Value *V, const BasicBlock *PHIBlock, + SmallPtrSetImpl<const Value *> &Visited, + SmallVectorImpl<Instruction *> &Worklist) { + + if (!isa<Instruction>(V)) + return true; + auto OISIt = OpSafeForPHIOfOps.find(V); + if (OISIt != OpSafeForPHIOfOps.end()) + return OISIt->second; + + // Keep walking until we either dominate the phi block, or hit a phi, or run + // out of things to check. + if (DT->properlyDominates(getBlockForValue(V), PHIBlock)) { + OpSafeForPHIOfOps.insert({V, true}); + return true; + } + // PHI in the same block. + if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) { + OpSafeForPHIOfOps.insert({V, false}); + return false; + } + + auto *OrigI = cast<Instruction>(V); + for (auto *Op : OrigI->operand_values()) { + if (!isa<Instruction>(Op)) + continue; + // Stop now if we find an unsafe operand. + auto OISIt = OpSafeForPHIOfOps.find(OrigI); + if (OISIt != OpSafeForPHIOfOps.end()) { + if (!OISIt->second) { + OpSafeForPHIOfOps.insert({V, false}); + return false; + } + continue; + } + if (!Visited.insert(Op).second) + continue; + Worklist.push_back(cast<Instruction>(Op)); + } + return true; +} + +// Return true if this operand will be safe to use for phi of ops. +// +// The reason some operands are unsafe is that we are not trying to recursively +// translate everything back through phi nodes. We actually expect some lookups +// of expressions to fail. In particular, a lookup where the expression cannot +// exist in the predecessor. This is true even if the expression, as shown, can +// be determined to be constant. +bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock, + SmallPtrSetImpl<const Value *> &Visited) { + SmallVector<Instruction *, 4> Worklist; + if (!OpIsSafeForPHIOfOpsHelper(V, PHIBlock, Visited, Worklist)) + return false; + while (!Worklist.empty()) { + auto *I = Worklist.pop_back_val(); + if (!OpIsSafeForPHIOfOpsHelper(I, PHIBlock, Visited, Worklist)) + return false; + } + OpSafeForPHIOfOps.insert({V, true}); + return true; +} + +// Try to find a leader for instruction TransInst, which is a phi translated +// version of something in our original program. Visited is used to ensure we +// don't infinite loop during translations of cycles. OrigInst is the +// instruction in the original program, and PredBB is the predecessor we +// translated it through. +Value *NewGVN::findLeaderForInst(Instruction *TransInst, + SmallPtrSetImpl<Value *> &Visited, + MemoryAccess *MemAccess, Instruction *OrigInst, + BasicBlock *PredBB) { + unsigned IDFSNum = InstrToDFSNum(OrigInst); + // Make sure it's marked as a temporary instruction. + AllTempInstructions.insert(TransInst); + // 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. + TempToBlock.insert({TransInst, PredBB}); + InstrDFS.insert({TransInst, IDFSNum}); + + const Expression *E = performSymbolicEvaluation(TransInst, Visited); + InstrDFS.erase(TransInst); + AllTempInstructions.erase(TransInst); + TempToBlock.erase(TransInst); + if (MemAccess) + TempToMemory.erase(TransInst); + if (!E) + return nullptr; + auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB); + if (!FoundVal) { + ExpressionToPhiOfOps[E].insert(OrigInst); + DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst + << " in block " << getBlockName(PredBB) << "\n"); + return nullptr; + } + if (auto *SI = dyn_cast<StoreInst>(FoundVal)) + FoundVal = SI->getValueOperand(); + return FoundVal; +} + // When we see an instruction that is an op of phis, generate the equivalent phi // of ops form. const Expression * -NewGVN::makePossiblePhiOfOps(Instruction *I, +NewGVN::makePossiblePHIOfOps(Instruction *I, SmallPtrSetImpl<Value *> &Visited) { if (!okayForPHIOfOps(I)) return nullptr; @@ -2450,7 +2711,6 @@ NewGVN::makePossiblePhiOfOps(Instruction *I, if (!isCycleFree(I)) return nullptr; - unsigned IDFSNum = InstrToDFSNum(I); SmallPtrSet<const Value *, 8> 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, @@ -2463,81 +2723,94 @@ NewGVN::makePossiblePhiOfOps(Instruction *I, MemAccess->getDefiningAccess()->getBlock() == I->getParent()) return nullptr; + SmallPtrSet<const Value *, 10> VisitedOps; // Convert op of phis to phi of ops - for (auto &Op : I->operands()) { - // TODO: We can't handle expressions that must be recursively translated - // IE - // a = phi (b, c) - // f = use a - // g = f + phi of something - // To properly make a phi of ops for g, we'd have to properly translate and - // use the instruction for f. We should add this by splitting out the - // instruction creation we do below. - if (isa<Instruction>(Op) && PHINodeUses.count(cast<Instruction>(Op))) - return nullptr; - if (!isa<PHINode>(Op)) - continue; + for (auto *Op : I->operand_values()) { + if (!isa<PHINode>(Op)) { + auto *ValuePHI = RealToTemp.lookup(Op); + if (!ValuePHI) + continue; + DEBUG(dbgs() << "Found possible dependent phi of ops\n"); + Op = ValuePHI; + } auto *OpPHI = cast<PHINode>(Op); // No point in doing this for one-operand phis. if (OpPHI->getNumOperands() == 1) continue; if (!DebugCounter::shouldExecute(PHIOfOpsCounter)) return nullptr; - SmallVector<std::pair<Value *, BasicBlock *>, 4> Ops; + SmallVector<ValPair, 4> Ops; + SmallPtrSet<Value *, 4> Deps; auto *PHIBlock = getBlockForValue(OpPHI); - for (auto PredBB : OpPHI->blocks()) { + RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I)); + for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) { + auto *PredBB = OpPHI->getIncomingBlock(PredNum); 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. + // Clone the instruction, create an expression from it that is + // translated back into the predecessor, and see if we have a leader. Instruction *ValueOp = I->clone(); if (MemAccess) TempToMemory.insert({ValueOp, MemAccess}); - + bool SafeForPHIOfOps = true; + VisitedOps.clear(); 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); + auto *OrigOp = &*Op; + // When these operand changes, it could change whether there is a + // leader for us or not, so we have to add additional users. + if (isa<PHINode>(Op)) { + Op = Op->DoPHITranslation(PHIBlock, PredBB); + if (Op != OrigOp && Op != I) + Deps.insert(Op); + } else if (auto *ValuePHI = RealToTemp.lookup(Op)) { + if (getBlockForValue(ValuePHI) == PHIBlock) + Op = ValuePHI->getIncomingValueForBlock(PredBB); + } + // If we phi-translated the op, it must be safe. + SafeForPHIOfOps = + SafeForPHIOfOps && + (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps)); } - // 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); + // FIXME: For those things that are not safe we could generate + // expressions all the way down, and see if this comes out to a + // constant. For anything where that is true, and unsafe, we should + // have made a phi-of-ops (or value numbered it equivalent to something) + // for the pieces already. + FoundVal = !SafeForPHIOfOps ? nullptr + : findLeaderForInst(ValueOp, Visited, + MemAccess, I, PredBB); ValueOp->deleteValue(); - if (MemAccess) - TempToMemory.erase(ValueOp); - if (!E) + if (!FoundVal) return nullptr; - FoundVal = findPhiOfOpsLeader(E, PredBB); - if (!FoundVal) { - ExpressionToPhiOfOps[E].insert(I); - return nullptr; - } - if (auto *SI = dyn_cast<StoreInst>(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()); + RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); } Ops.push_back({FoundVal, PredBB}); DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in " << getBlockName(PredBB) << "\n"); } + for (auto Dep : Deps) + addAdditionalUsers(Dep, I); + sortPHIOps(Ops); + auto *E = performSymbolicPHIEvaluation(Ops, I, PHIBlock); + if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) { + DEBUG(dbgs() + << "Not creating real PHI of ops because it simplified to existing " + "value or constant\n"); + return E; + } auto *ValuePHI = RealToTemp.lookup(I); bool NewPHI = false; if (!ValuePHI) { - ValuePHI = PHINode::Create(I->getType(), OpPHI->getNumOperands()); + ValuePHI = + PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops"); addPhiOfOps(ValuePHI, PHIBlock, I); NewPHI = true; NumGVNPHIOfOpsCreated++; @@ -2553,10 +2826,11 @@ NewGVN::makePossiblePhiOfOps(Instruction *I, ++i; } } - + RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I << "\n"); - return performSymbolicEvaluation(ValuePHI, Visited); + + return E; } return nullptr; } @@ -2602,8 +2876,11 @@ void NewGVN::initializeCongruenceClasses(Function &F) { if (MD && isa<StoreInst>(MD->getMemoryInst())) TOPClass->incStoreCount(); } + + // FIXME: This is trying to discover which instructions are uses of phi + // nodes. We should move this into one of the myriad of places that walk + // all the operands already. for (auto &I : *BB) { - // TODO: Move to helper if (isa<PHINode>(&I)) for (auto *U : I.users()) if (auto *UInst = dyn_cast<Instruction>(U)) @@ -2661,7 +2938,8 @@ void NewGVN::cleanupTables() { ExpressionToPhiOfOps.clear(); TempToBlock.clear(); TempToMemory.clear(); - PHIOfOpsPHIs.clear(); + PHINodeUses.clear(); + OpSafeForPHIOfOps.clear(); ReachableBlocks.clear(); ReachableEdges.clear(); #ifndef NDEBUG @@ -2675,6 +2953,7 @@ void NewGVN::cleanupTables() { MemoryAccessToClass.clear(); PredicateToUsers.clear(); MemoryToUsers.clear(); + RevisitOnReachabilityChange.clear(); } // Assign local DFS number mapping to instructions, and leave space for Value @@ -2698,6 +2977,8 @@ std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B, markInstructionForDeletion(&I); continue; } + if (isa<PHINode>(&I)) + RevisitOnReachabilityChange[B].set(End); InstrDFS[&I] = End++; DFSToInstr.emplace_back(&I); } @@ -2719,6 +3000,7 @@ void NewGVN::updateProcessedCount(const Value *V) { } #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 @@ -2787,11 +3069,15 @@ void NewGVN::valueNumberInstruction(Instruction *I) { // Make a phi of ops if necessary if (Symbolized && !isa<ConstantExpression>(Symbolized) && !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) { - auto *PHIE = makePossiblePhiOfOps(I, Visited); - if (PHIE) + auto *PHIE = makePossiblePHIOfOps(I, Visited); + // If we created a phi of ops, use it. + // If we couldn't create one, make sure we don't leave one lying around + if (PHIE) { Symbolized = PHIE; + } else if (auto *Op = RealToTemp.lookup(I)) { + removePhiOfOps(I, Op); + } } - } else { // Mark the instruction as unused so we don't value number it again. InstrDFS[I] = 0; @@ -2905,7 +3191,7 @@ void NewGVN::verifyMemoryCongruency() const { // so we don't process them. if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) { for (auto &U : MemPHI->incoming_values()) { - if (Instruction *I = dyn_cast<Instruction>(U.get())) { + if (auto *I = dyn_cast<Instruction>(&*U)) { if (!isInstructionTriviallyDead(I)) return true; } @@ -3200,11 +3486,13 @@ struct NewGVN::ValueDFS { int DFSIn = 0; int DFSOut = 0; int LocalNum = 0; + // Only one of Def and U will be set. // The bool in the Def tells us whether the Def is the stored value of a // store. PointerIntPair<Value *, 1, bool> Def; Use *U = nullptr; + bool operator<(const ValueDFS &Other) const { // It's not enough that any given field be less than - we have sets // of fields that need to be evaluated together to give a proper ordering. @@ -3439,7 +3727,6 @@ void NewGVN::markInstructionForDeletion(Instruction *I) { } void NewGVN::replaceInstruction(Instruction *I, Value *V) { - DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n"); patchAndReplaceAllUsesWith(I, V); // We save the actual erasing to avoid invalidating memory @@ -3460,7 +3747,9 @@ public: ValueStack.emplace_back(V); DFSStack.emplace_back(DFSIn, DFSOut); } + bool empty() const { return DFSStack.empty(); } + bool isInScope(int DFSIn, int DFSOut) const { if (empty()) return false; @@ -3484,19 +3773,33 @@ private: SmallVector<Value *, 8> ValueStack; SmallVector<std::pair<int, int>, 8> DFSStack; }; + +} // end anonymous namespace + +// Given an expression, get the congruence class for it. +CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const { + if (auto *VE = dyn_cast<VariableExpression>(E)) + return ValueToClass.lookup(VE->getVariableValue()); + else if (isa<DeadExpression>(E)) + return TOPClass; + return ExpressionToClass.lookup(E); } // 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, +Value *NewGVN::findPHIOfOpsLeader(const Expression *E, + const Instruction *OrigInst, const BasicBlock *BB) const { // It would already be constant if we could make it constant if (auto *CE = dyn_cast<ConstantExpression>(E)) return CE->getConstantValue(); - if (auto *VE = dyn_cast<VariableExpression>(E)) - return VE->getVariableValue(); + if (auto *VE = dyn_cast<VariableExpression>(E)) { + auto *V = VE->getVariableValue(); + if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB)) + return VE->getVariableValue(); + } - auto *CC = ExpressionToClass.lookup(E); + auto *CC = getClassForExpression(E); if (!CC) return nullptr; if (alwaysAvailable(CC->getLeader())) @@ -3504,15 +3807,13 @@ Value *NewGVN::findPhiOfOpsLeader(const Expression *E, for (auto Member : *CC) { auto *MemberInst = dyn_cast<Instruction>(Member); + if (MemberInst == OrigInst) + continue; // 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)) { + if (DT->dominates(getBlockForValue(MemberInst), BB)) return Member; - } } return nullptr; } @@ -3549,36 +3850,39 @@ bool NewGVN::eliminateInstructions(Function &F) { // Go through all of our phi nodes, and kill the arguments associated with // unreachable edges. - auto ReplaceUnreachablePHIArgs = [&](PHINode &PHI, BasicBlock *BB) { - for (auto &Operand : PHI.incoming_values()) - if (!ReachableEdges.count({PHI.getIncomingBlock(Operand), BB})) { + 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)) + << getBlockName(PHI->getIncomingBlock(Operand)) << " with undef due to it being unreachable\n"); - Operand.set(UndefValue::get(PHI.getType())); + Operand.set(UndefValue::get(PHI->getType())); } }; - SmallPtrSet<BasicBlock *, 8> BlocksWithPhis; - for (auto &B : F) - if ((!B.empty() && isa<PHINode>(*B.begin())) || - (PHIOfOpsPHIs.find(&B) != PHIOfOpsPHIs.end())) - BlocksWithPhis.insert(&B); + // Replace unreachable phi arguments. + // At this point, RevisitOnReachabilityChange only contains: + // + // 1. PHIs + // 2. Temporaries that will convert to PHIs + // 3. Operations that are affected by an unreachable edge but do not fit into + // 1 or 2 (rare). + // So it is a slight overshoot of what we want. We could make it exact by + // using two SparseBitVectors per block. DenseMap<const BasicBlock *, unsigned> ReachablePredCount; - for (auto KV : ReachableEdges) + 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) != - unsigned(std::distance(pred_begin(BB), pred_end(BB)))) { - for (auto II = BB->begin(); isa<PHINode>(II); ++II) { - auto &PHI = cast<PHINode>(*II); + for (auto &BBPair : RevisitOnReachabilityChange) { + for (auto InstNum : BBPair.second) { + auto *Inst = InstrFromDFSNum(InstNum); + auto *PHI = dyn_cast<PHINode>(Inst); + PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst)); + if (!PHI) + continue; + auto *BB = BBPair.first; + if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues()) ReplaceUnreachablePHIArgs(PHI, BB); - } - for_each_found(PHIOfOpsPHIs, BB, [&](PHINode *PHI) { - ReplaceUnreachablePHIArgs(*PHI, BB); - }); } + } // Map to store the use counts DenseMap<const Value *, unsigned int> UseCounts; @@ -3631,7 +3935,7 @@ bool NewGVN::eliminateInstructions(Function &F) { CC->swap(MembersLeft); } else { // If this is a singleton, we can skip it. - if (CC->size() != 1 || RealToTemp.lookup(Leader)) { + if (CC->size() != 1 || RealToTemp.count(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 @@ -3873,12 +4177,16 @@ bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const { } namespace { + class NewGVNLegacyPass : public FunctionPass { public: - static char ID; // Pass identification, replacement for typeid. + // Pass identification, replacement for typeid. + static char ID; + NewGVNLegacyPass() : FunctionPass(ID) { initializeNewGVNLegacyPassPass(*PassRegistry::getPassRegistry()); } + bool runOnFunction(Function &F) override; private: @@ -3892,7 +4200,8 @@ private: AU.addPreserved<GlobalsAAWrapperPass>(); } }; -} // namespace + +} // end anonymous namespace bool NewGVNLegacyPass::runOnFunction(Function &F) { if (skipFunction(F)) @@ -3906,6 +4215,8 @@ bool NewGVNLegacyPass::runOnFunction(Function &F) { .runGVN(); } +char NewGVNLegacyPass::ID = 0; + INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) @@ -3917,8 +4228,6 @@ INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false, false) -char NewGVNLegacyPass::ID = 0; - // createGVNPass - The public interface to this file. FunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); } |