From 186b8ca6dcd6af79eb2a74dc6b25cf5e01e65be6 Mon Sep 17 00:00:00 2001 From: Anthony Pesch Date: Wed, 22 Jul 2015 22:26:54 +0000 Subject: [PATCH] Revert "Improve merging of stores from static constructors in GlobalOpt" This reverts commit 0a9dee959a30b81b9e7df64c9a58ff9898c24024. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@242954 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/GlobalOpt.cpp | 326 ++++++++----------------------- 1 file changed, 77 insertions(+), 249 deletions(-) diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index 27be1b40a32..af19e7d3b4e 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -1963,240 +1963,6 @@ bool GlobalOpt::OptimizeGlobalVars(Module &M) { return Changed; } -namespace { - -/// Sorts GEP expressions in ascending order by their indexes. -struct GEPComparator { - bool operator()(GEPOperator *A, GEPOperator *B) const { - int NumOpA = A->getNumOperands(); - int NumOpB = B->getNumOperands(); - - // Globals are always pointers, the first index should be 0. - assert(cast(A->getOperand(1))->isZero() && - "GEP A steps over object"); - assert(cast(B->getOperand(1))->isZero() && - "GEP B steps over object"); - - for (int i = 2; i < NumOpA && i < NumOpB; i++) { - ConstantInt *IndexA = cast(A->getOperand(i)); - ConstantInt *IndexB = cast(B->getOperand(i)); - - if (IndexA->getZExtValue() < IndexB->getZExtValue()) { - return true; - } - } - - return NumOpA < NumOpB; - } -}; - -typedef std::map StoreMap; - -/// MutatedGlobal - Holds mutations for a global. If a store overwrites the -/// the entire global, Initializer is updated with the new value. If a store -/// writes to a GEP of a global, the store is instead added to the Pending -/// map to be merged later during MergePendingStores. -struct MutatedGlobal { - GlobalVariable *GV; - Constant *Initializer; - StoreMap Pending; -}; - -/// MutatedGlobals - This class tracks and commits stores to globals as basic -/// blocks are evaluated. -class MutatedGlobals { - DenseMap Globals; - typedef DenseMap::const_iterator - const_iterator; - - GlobalVariable *GetGlobalForPointer(Constant *Ptr) { - if (GlobalVariable *GV = dyn_cast(Ptr)) { - return GV; - } - - if (ConstantExpr *CE = dyn_cast(Ptr)) { - if (CE->getOpcode() == Instruction::GetElementPtr) { - return cast(CE->getOperand(0)); - } - } - - return nullptr; - } - - Constant *MergePendingStores(Constant *Init, StoreMap &Pending, - uint64_t CurrentIdx, unsigned OpNum); - -public: - const_iterator begin() const { return Globals.begin(); } - const_iterator end() const { return Globals.end(); } - size_t size() const { return Globals.size(); } - - void AddStore(Constant *Ptr, Constant *Value); - Constant *LookupStore(Constant *Ptr); - - void Commit(MutatedGlobal &MG); -}; -} - -/// AddStore - Add store for the global variable referenced by Ptr. -/// Currently, it's assumed that the incoming pointer is either the global -/// variable itself, or a GEP expression referencing the global. -void MutatedGlobals::AddStore(Constant *Ptr, Constant *Value) { - GlobalVariable *GV = GetGlobalForPointer(Ptr); - assert(GV && "Failed to resolve global for pointer"); - - auto I = Globals.find(GV); - if (I == Globals.end()) { - auto R = Globals.insert(std::make_pair(GV, MutatedGlobal{GV, nullptr, {}})); - assert(R.second && "Global value already in the map?"); - I = R.first; - } - - MutatedGlobal &MG = I->second; - - if (Ptr == GV) { - MG.Initializer = Value; - // Pending stores are no longer valid. - MG.Pending.clear(); - } else if (GEPOperator *GEPOp = dyn_cast(Ptr)) { - MG.Pending[GEPOp] = Value; - } else { - llvm_unreachable("Unexpected address type"); - } -} - -Constant *MutatedGlobals::LookupStore(Constant *Ptr) { - GlobalVariable *GV = GetGlobalForPointer(Ptr); - if (!GV) { - return nullptr; - } - - auto I = Globals.find(GV); - if (I == Globals.end()) { - return nullptr; - } - - MutatedGlobal &MG = I->second; - - if (Ptr == MG.GV) { - if (MG.Initializer) { - // If there are any pending stores, Initializer isn't valid, it would - // need them merged in first. This situation currently doesn't occur - // due to isSimpleEnoughPointerToCommit / isSimpleEnoughValueToCommit - // not letting stores for aggregate types pass through. If this needs - // to be supported, calling Commit() at this point should do the trick. - assert(MG.Pending.empty() && - "Can't use pending initializer without merging pending stores."); - return MG.Initializer; - } - } else if (GEPOperator *GEPOp = dyn_cast(Ptr)) { - auto SI = MG.Pending.find(GEPOp); - if (SI != MG.Pending.end()) { - return SI->second; - } - } - - return nullptr; -} - -/// MergePendingStores - Recursively merge stores to a global variable into its -/// initializer. Merging any number of stores into the initializer requires -/// cloning the entire initializer, so stores are batched up during evaluation -/// and processed all at once. -Constant *MutatedGlobals::MergePendingStores(Constant *Init, StoreMap &Pending, - uint64_t CurrentIdx, - unsigned OpNum) { - if (Pending.empty()) { - // Nothing left to merge. - return Init; - } - - // If the GEP expression has been traversed completely, terminate. - auto It = Pending.begin(); - GEPOperator *GEP = It->first; - - if (OpNum >= GEP->getNumOperands()) { - Constant *Val = It->second; - assert(Val->getType() == Init->getType() && "Type mismatch!"); - - // Move on to the next expression. - Pending.erase(It++); - - return Val; - } - - // Clone the existing initializer so it can be merged into. - Type *InitTy = Init->getType(); - ArrayType *ATy = dyn_cast(InitTy); - StructType *STy = dyn_cast(InitTy); - VectorType *VTy = dyn_cast(InitTy); - - unsigned NumElts; - if (ATy) { - NumElts = ATy->getNumElements(); - } else if (STy) { - NumElts = STy->getNumElements(); - } else if (VTy) { - NumElts = VTy->getNumElements(); - } else { - llvm_unreachable("Unexpected initializer type"); - } - - SmallVector Elts; - for (unsigned i = 0; i < NumElts; ++i) { - Elts.push_back(Init->getAggregateElement(i)); - } - - // Iterate over the sorted stores, merging all stores for the current GEP - // index. - while (!Pending.empty()) { - It = Pending.begin(); - GEP = It->first; - - // If the store doesn't belong to the current index, we're done. - ConstantInt *CI = cast(GEP->getOperand(OpNum - 1)); - uint64_t Idx = CI->getZExtValue(); - if (Idx != CurrentIdx) { - break; - } - - // Recurse into the next index. - CI = cast(GEP->getOperand(OpNum)); - Idx = CI->getZExtValue(); - assert(Idx < NumElts && "GEP index out of range!"); - Elts[Idx] = MergePendingStores(Elts[Idx], Pending, Idx, OpNum + 1); - } - - if (ATy) { - return ConstantArray::get(ATy, Elts); - } else if (STy) { - return ConstantStruct::get(STy, Elts); - } else if (VTy) { - return ConstantVector::get(Elts); - } else { - llvm_unreachable("Unexpected initializer type"); - } - - return nullptr; -}; - -/// Commit - We have decided that stores to the global (which satisfy the -/// predicate isSimpleEnoughPointerToCommit) should be committed. -void MutatedGlobals::Commit(MutatedGlobal &MG) { - Constant *Init = MG.Initializer ? MG.Initializer : MG.GV->getInitializer(); - - // Globals are always pointers, skip first GEP index assuming it's 0. - Init = MergePendingStores(Init, MG.Pending, 0, 2); - - // Reset pending state. - MG.Initializer = nullptr; - assert(MG.Pending.empty() && - "Expected pending stores to be empty after merging"); - - MG.GV->setInitializer(Init); -} - - static inline bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl &SimpleConstants, @@ -2329,6 +2095,69 @@ static bool isSimpleEnoughPointerToCommit(Constant *C) { return false; } +/// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global +/// initializer. This returns 'Init' modified to reflect 'Val' stored into it. +/// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. +static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, + ConstantExpr *Addr, unsigned OpNo) { + // Base case of the recursion. + if (OpNo == Addr->getNumOperands()) { + assert(Val->getType() == Init->getType() && "Type mismatch!"); + return Val; + } + + SmallVector Elts; + if (StructType *STy = dyn_cast(Init->getType())) { + // Break up the constant into its elements. + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + Elts.push_back(Init->getAggregateElement(i)); + + // Replace the element that we are supposed to. + ConstantInt *CU = cast(Addr->getOperand(OpNo)); + unsigned Idx = CU->getZExtValue(); + assert(Idx < STy->getNumElements() && "Struct index out of range!"); + Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); + + // Return the modified struct. + return ConstantStruct::get(STy, Elts); + } + + ConstantInt *CI = cast(Addr->getOperand(OpNo)); + SequentialType *InitTy = cast(Init->getType()); + + uint64_t NumElts; + if (ArrayType *ATy = dyn_cast(InitTy)) + NumElts = ATy->getNumElements(); + else + NumElts = InitTy->getVectorNumElements(); + + // Break up the array into elements. + for (uint64_t i = 0, e = NumElts; i != e; ++i) + Elts.push_back(Init->getAggregateElement(i)); + + assert(CI->getZExtValue() < NumElts); + Elts[CI->getZExtValue()] = + EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); + + if (Init->getType()->isArrayTy()) + return ConstantArray::get(cast(InitTy), Elts); + return ConstantVector::get(Elts); +} + +/// CommitValueTo - We have decided that Addr (which satisfies the predicate +/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. +static void CommitValueTo(Constant *Val, Constant *Addr) { + if (GlobalVariable *GV = dyn_cast(Addr)) { + assert(GV->hasInitializer()); + GV->setInitializer(Val); + return; + } + + ConstantExpr *CE = cast(Addr); + GlobalVariable *GV = cast(CE->getOperand(0)); + GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2)); +} + namespace { /// Evaluator - This class evaluates LLVM IR, producing the Constant @@ -2373,8 +2202,8 @@ public: ValueStack.back()[V] = C; } - MutatedGlobals &getMutated() { - return Mutated; + const DenseMap &getMutatedMemory() const { + return MutatedMemory; } const SmallPtrSetImpl &getInvariants() const { @@ -2394,10 +2223,10 @@ private: /// unbounded. SmallVector CallStack; - /// Mutated - For each store we execute, we update this map. Loads check - /// this to get the most up-to-date value. If evaluation is successful, + /// MutatedMemory - For each store we execute, we update this map. Loads + /// check this to get the most up-to-date value. If evaluation is successful, /// this state is committed to the process. - MutatedGlobals Mutated; + DenseMap MutatedMemory; /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable /// to represent its body. This vector is needed so we can delete the @@ -2424,8 +2253,8 @@ private: Constant *Evaluator::ComputeLoadResult(Constant *P) { // If this memory location has been recently stored, use the stored value: it // is the most up-to-date. - Constant *Val = Mutated.LookupStore(P); - if (Val) return Val; + DenseMap::const_iterator I = MutatedMemory.find(P); + if (I != MutatedMemory.end()) return I->second; // Access it. if (GlobalVariable *GV = dyn_cast(P)) { @@ -2529,7 +2358,7 @@ bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, } } - Mutated.AddStore(Ptr, Val); + MutatedMemory[Ptr] = Val; } else if (BinaryOperator *BO = dyn_cast(CurInst)) { InstResult = ConstantExpr::get(BO->getOpcode(), getVal(BO->getOperand(0)), @@ -2865,13 +2694,12 @@ static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL, // We succeeded at evaluation: commit the result. DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" - << F->getName() << "' to " << Eval.getMutated().size() - << " mutated globals.\n"); - - MutatedGlobals &Mutated = Eval.getMutated(); - for (auto I : Mutated) - Mutated.Commit(I.second); - + << F->getName() << "' to " << Eval.getMutatedMemory().size() + << " stores.\n"); + for (DenseMap::const_iterator I = + Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end(); + I != E; ++I) + CommitValueTo(I->second, I->first); for (GlobalVariable *GV : Eval.getInvariants()) GV->setConstant(true); } -- 2.34.1