Index: lib/Transforms/IPO/GlobalOpt.cpp =================================================================== --- lib/Transforms/IPO/GlobalOpt.cpp +++ lib/Transforms/IPO/GlobalOpt.cpp @@ -1963,6 +1963,232 @@ 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(); + + 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 onto 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, @@ -2043,7 +2269,6 @@ return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL); } - /// isSimpleEnoughPointerToCommit - Return true if this constant is simple /// enough for us to understand. In particular, if it is a cast to anything /// other than from one pointer type to another pointer type, we punt. @@ -2095,69 +2320,6 @@ 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 @@ -2202,8 +2364,8 @@ ValueStack.back()[V] = C; } - const DenseMap &getMutatedMemory() const { - return MutatedMemory; + MutatedGlobals &getMutated() { + return Mutated; } const SmallPtrSetImpl &getInvariants() const { @@ -2223,10 +2385,10 @@ /// unbounded. SmallVector CallStack; - /// 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, + /// 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, /// this state is committed to the process. - DenseMap MutatedMemory; + MutatedGlobals Mutated; /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable /// to represent its body. This vector is needed so we can delete the @@ -2253,8 +2415,8 @@ Constant *Evaluator::ComputeLoadResult(Constant *P) { // If this memory location has been recently stored, use the stored value: it // is the most up-to-date. - DenseMap::const_iterator I = MutatedMemory.find(P); - if (I != MutatedMemory.end()) return I->second; + Constant *Val = Mutated.LookupStore(P); + if (Val) return Val; // Access it. if (GlobalVariable *GV = dyn_cast(P)) { @@ -2358,7 +2520,7 @@ } } - MutatedMemory[Ptr] = Val; + Mutated.AddStore(Ptr, Val); } else if (BinaryOperator *BO = dyn_cast(CurInst)) { InstResult = ConstantExpr::get(BO->getOpcode(), getVal(BO->getOperand(0)), @@ -2694,12 +2856,13 @@ // We succeeded at evaluation: commit the result. DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" - << 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); + << F->getName() << "' to " << Eval.getMutated().size() + << " mutated globals.\n"); + + MutatedGlobals &Mutated = Eval.getMutated(); + for (auto I : Mutated) + Mutated.Commit(I.second); + for (GlobalVariable *GV : Eval.getInvariants()) GV->setConstant(true); }