Index: lib/Transforms/IPO/GlobalOpt.cpp =================================================================== --- lib/Transforms/IPO/GlobalOpt.cpp +++ lib/Transforms/IPO/GlobalOpt.cpp @@ -1963,6 +1963,109 @@ return Changed; } +namespace { + +// Sort stores to globals from most significant to least signifcant. The key to +// the map is either the global variable itself (value clobbers the entire +// initializer), or a GEP expression (value merges into initializer). +struct MutatedComparator { + bool operator()(Constant *a, Constant *b) const { + ConstantExpr *CEA = dyn_cast(a); + ConstantExpr *CEB = dyn_cast(b); + + if (!CEA && !CEB) { + // Both clobber, let CEB overwrite. + return false; + } + + if (!CEA) { + // CEA clobbers, it's more significant. + return true; + } + + // Sort indexes from smallest to largest. + int NumOpA = CEA->getNumOperands(); + int NumOpB = CEB->getNumOperands(); + + for (int i = 2; i < NumOpA && i < NumOpB; i++) { + ConstantInt *IndexA = cast(CEA->getOperand(i)); + ConstantInt *IndexB = cast(CEB->getOperand(i)); + + if (IndexA->getZExtValue() < IndexB->getZExtValue()) { + return true; + } + } + + // Less indexes is more significant. + return NumOpA < NumOpB; + } +}; + +typedef std::map MutatedMap; + +struct MutatedGlobal { + GlobalVariable *GV; + MutatedMap Stores; +}; + +class MutatedGlobals { + DenseMap Globals; + typedef DenseMap::const_iterator const_iterator; + + GlobalVariable *GetGlobalForAddr(Constant *Addr) { + GlobalVariable *GV = dyn_cast(Addr); + if (!GV) { + ConstantExpr *CE = dyn_cast(Addr); + if (CE) { + GV = cast(CE->getOperand(0)); + } + } + return GV; + } + +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 *Addr, Constant *Value) { + GlobalVariable *GV = GetGlobalForAddr(Addr); + assert(GV); + + auto I = Globals.find(GV); + if (I == Globals.end()) { + auto R = Globals.insert(std::make_pair(GV, MutatedGlobal { GV, {} })); + assert(R.second); + I = R.first; + } + + MutatedGlobal &MG = I->second; + MG.Stores[Addr] = Value; + } + + Constant *lookupStore(Constant *Addr) { + GlobalVariable *GV = GetGlobalForAddr(Addr); + if (!GV) { + return nullptr; + } + + auto I = Globals.find(GV); + if (I == Globals.end()) { + return nullptr; + } + + MutatedGlobal &MG = I->second; + auto SI = MG.Stores.find(Addr); + if (SI == MG.Stores.end()) { + return nullptr; + } + + return SI->second; + } +}; + +} + static inline bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl &SimpleConstants, @@ -2095,67 +2198,96 @@ 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; +/// MergeStoresInto - Merge stores to a global variable into its initializer. +Constant *MergeStoresInto(Constant *Init, MutatedMap::const_iterator &It, + const MutatedMap::const_iterator &End, + uint64_t CurrentIdx, unsigned OpNum) { + if (It == End) { + // Nothing left to merge. + return Init; } - 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); + const ConstantExpr *Addr = dyn_cast(It->first); + + // If the address isn't a GEP expression, completely clobber the initializer. + if (!Addr) { + Constant *Val = It->second; + It++; + return MergeStoresInto(Val, It, End, CurrentIdx, OpNum); } - ConstantInt *CI = cast(Addr->getOperand(OpNo)); - SequentialType *InitTy = cast(Init->getType()); + // If the GEP expression has been traversed completely, terminate. + if (OpNum >= Addr->getNumOperands()) { + Constant *Val = It->second; + It++; + return Val; + } - uint64_t NumElts; - if (ArrayType *ATy = dyn_cast(InitTy)) + // A GEP expression is being traversed which means the initializer must be an + // aggregate type. Start off by cloning 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 - NumElts = InitTy->getVectorNumElements(); + } else if (STy) { + NumElts = STy->getNumElements(); + } else if (VTy) { + NumElts = VTy->getNumElements(); + } else { + assert(false && "Unexpected initializer type"); + } - // Break up the array into elements. - for (uint64_t i = 0, e = NumElts; i != e; ++i) + SmallVector Elts; + for (unsigned i = 0; i < NumElts; ++i) { Elts.push_back(Init->getAggregateElement(i)); + } - assert(CI->getZExtValue() < NumElts); - Elts[CI->getZExtValue()] = - EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); + // Iterate over the sorted stores, merging all stores for the current GEP + // index. + while (It != End) { + Addr = cast(It->first); - if (Init->getType()->isArrayTy()) - return ConstantArray::get(cast(InitTy), Elts); - return ConstantVector::get(Elts); -} + // If the store doesn't belong to the current index, we're done. + ConstantInt *CI = cast(Addr->getOperand(OpNum - 1)); + uint64_t Idx = CI->getZExtValue(); + if (Idx != CurrentIdx) { + break; + } -/// 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; + // Recurse into the next GEP index. + CI = cast(Addr->getOperand(OpNum)); + Idx = CI->getZExtValue(); + Elts[Idx] = MergeStoresInto(Elts[Idx], It, End, 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 { + assert(false && "Unexpected initializer type"); } - ConstantExpr *CE = cast(Addr); - GlobalVariable *GV = cast(CE->getOperand(0)); - GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2)); + return nullptr; +}; + +/// CommitMutatedGlobal - We have decided that stores to the global (which +/// satisfy the predicate isSimpleEnoughPointerToCommit) should be committed. +static void CommitMutatedGlobal(const MutatedGlobal &MG) { + MutatedMap::const_iterator Start = MG.Stores.begin(); + MutatedMap::const_iterator End = MG.Stores.end(); + + // Globals are always pointers, skip first GEP index assuming it's 0. + Constant *Init = MergeStoresInto(MG.GV->getInitializer(), Start, End, 0, 2); + assert(Start == End); + MG.GV->setInitializer(Init); } namespace { @@ -2202,8 +2334,8 @@ ValueStack.back()[V] = C; } - const DenseMap &getMutatedMemory() const { - return MutatedMemory; + const MutatedGlobals &getMutated() const { + return Mutated; } const SmallPtrSetImpl &getInvariants() const { @@ -2223,10 +2355,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 +2385,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 +2490,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 +2826,12 @@ // 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"); + + for (auto I : Eval.getMutated()) + CommitMutatedGlobal(I.second); + for (GlobalVariable *GV : Eval.getInvariants()) GV->setConstant(true); }