lib/Transforms/IPO/GlobalOpt.cpp

   1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass transforms simple global variables that never have their address
  11 // taken.  If obviously true, it marks read/write globals as constant, deletes
  12 // variables only stored to, etc.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/IPO.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Analysis/ConstantFolding.h"
  23 #include "llvm/Analysis/MemoryBuiltins.h"
  24 #include "llvm/IR/CallSite.h"
  25 #include "llvm/IR/CallingConv.h"
  26 #include "llvm/IR/Constants.h"
  27 #include "llvm/IR/DataLayout.h"
  28 #include "llvm/IR/DerivedTypes.h"
  29 #include "llvm/IR/GetElementPtrTypeIterator.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/IntrinsicInst.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/IR/Operator.h"
  34 #include "llvm/IR/ValueHandle.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/ErrorHandling.h"
  38 #include "llvm/Support/MathExtras.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include "llvm/Target/TargetLibraryInfo.h"
  41 #include "llvm/Transforms/Utils/GlobalStatus.h"
  42 #include "llvm/Transforms/Utils/ModuleUtils.h"
  43 #include <algorithm>
  44 using namespace llvm;
  45
  46 #define DEBUG_TYPE "globalopt"
  47
  48 STATISTIC(NumMarked    , "Number of globals marked constant");
  49 STATISTIC(NumUnnamed   , "Number of globals marked unnamed_addr");
  50 STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars");
  51 STATISTIC(NumHeapSRA   , "Number of heap objects SRA'd");
  52 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
  53 STATISTIC(NumDeleted   , "Number of globals deleted");
  54 STATISTIC(NumFnDeleted , "Number of functions deleted");
  55 STATISTIC(NumGlobUses  , "Number of global uses devirtualized");
  56 STATISTIC(NumLocalized , "Number of globals localized");
  57 STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans");
  58 STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc");
  59 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
  60 STATISTIC(NumNestRemoved   , "Number of nest attributes removed");
  61 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
  62 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
  63 STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
  64
  65 namespace {
  66   struct GlobalOpt : public ModulePass {
  67     void getAnalysisUsage(AnalysisUsage &AU) const override {
  68       AU.addRequired<TargetLibraryInfo>();
  69     }
  70     static char ID; // Pass identification, replacement for typeid
  71     GlobalOpt() : ModulePass(ID) {
  72       initializeGlobalOptPass(*PassRegistry::getPassRegistry());
  73     }
  74
  75     bool runOnModule(Module &M) override;
  76
  77   private:
  78     GlobalVariable *FindGlobalCtors(Module &M);
  79     bool OptimizeFunctions(Module &M);
  80     bool OptimizeGlobalVars(Module &M);
  81     bool OptimizeGlobalAliases(Module &M);
  82     bool OptimizeGlobalCtorsList(GlobalVariable *&GCL);
  83     bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
  84     bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI,
  85                                const GlobalStatus &GS);
  86     bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn);
  87
  88     const DataLayout *DL;
  89     TargetLibraryInfo *TLI;
  90   };
  91 }
  92
  93 char GlobalOpt::ID = 0;
  94 INITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt",
  95                 "Global Variable Optimizer", false, false)
  96 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
  97 INITIALIZE_PASS_END(GlobalOpt, "globalopt",
  98                 "Global Variable Optimizer", false, false)
  99
 100 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
 101
 102 /// isLeakCheckerRoot - Is this global variable possibly used by a leak checker
 103 /// as a root?  If so, we might not really want to eliminate the stores to it.
 104 static bool isLeakCheckerRoot(GlobalVariable *GV) {
 105   // A global variable is a root if it is a pointer, or could plausibly contain
 106   // a pointer.  There are two challenges; one is that we could have a struct
 107   // the has an inner member which is a pointer.  We recurse through the type to
 108   // detect these (up to a point).  The other is that we may actually be a union
 109   // of a pointer and another type, and so our LLVM type is an integer which
 110   // gets converted into a pointer, or our type is an [i8 x #] with a pointer
 111   // potentially contained here.
 112
 113   if (GV->hasPrivateLinkage())
 114     return false;
 115
 116   SmallVector<Type *, 4> Types;
 117   Types.push_back(cast<PointerType>(GV->getType())->getElementType());
 118
 119   unsigned Limit = 20;
 120   do {
 121     Type *Ty = Types.pop_back_val();
 122     switch (Ty->getTypeID()) {
 123       default: break;
 124       case Type::PointerTyID: return true;
 125       case Type::ArrayTyID:
 126       case Type::VectorTyID: {
 127         SequentialType *STy = cast<SequentialType>(Ty);
 128         Types.push_back(STy->getElementType());
 129         break;
 130       }
 131       case Type::StructTyID: {
 132         StructType *STy = cast<StructType>(Ty);
 133         if (STy->isOpaque()) return true;
 134         for (StructType::element_iterator I = STy->element_begin(),
 135                  E = STy->element_end(); I != E; ++I) {
 136           Type *InnerTy = *I;
 137           if (isa<PointerType>(InnerTy)) return true;
 138           if (isa<CompositeType>(InnerTy))
 139             Types.push_back(InnerTy);
 140         }
 141         break;
 142       }
 143     }
 144     if (--Limit == 0) return true;
 145   } while (!Types.empty());
 146   return false;
 147 }
 148
 149 /// Given a value that is stored to a global but never read, determine whether
 150 /// it's safe to remove the store and the chain of computation that feeds the
 151 /// store.
 152 static bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) {
 153   do {
 154     if (isa<Constant>(V))
 155       return true;
 156     if (!V->hasOneUse())
 157       return false;
 158     if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
 159         isa<GlobalValue>(V))
 160       return false;
 161     if (isAllocationFn(V, TLI))
 162       return true;
 163
 164     Instruction *I = cast<Instruction>(V);
 165     if (I->mayHaveSideEffects())
 166       return false;
 167     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
 168       if (!GEP->hasAllConstantIndices())
 169         return false;
 170     } else if (I->getNumOperands() != 1) {
 171       return false;
 172     }
 173
 174     V = I->getOperand(0);
 175   } while (1);
 176 }
 177
 178 /// CleanupPointerRootUsers - This GV is a pointer root.  Loop over all users
 179 /// of the global and clean up any that obviously don't assign the global a
 180 /// value that isn't dynamically allocated.
 181 ///
 182 static bool CleanupPointerRootUsers(GlobalVariable *GV,
 183                                     const TargetLibraryInfo *TLI) {
 184   // A brief explanation of leak checkers.  The goal is to find bugs where
 185   // pointers are forgotten, causing an accumulating growth in memory
 186   // usage over time.  The common strategy for leak checkers is to whitelist the
 187   // memory pointed to by globals at exit.  This is popular because it also
 188   // solves another problem where the main thread of a C++ program may shut down
 189   // before other threads that are still expecting to use those globals.  To
 190   // handle that case, we expect the program may create a singleton and never
 191   // destroy it.
 192
 193   bool Changed = false;
 194
 195   // If Dead[n].first is the only use of a malloc result, we can delete its
 196   // chain of computation and the store to the global in Dead[n].second.
 197   SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;
 198
 199   // Constants can't be pointers to dynamically allocated memory.
 200   for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
 201        UI != E;) {
 202     User *U = *UI++;
 203     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 204       Value *V = SI->getValueOperand();
 205       if (isa<Constant>(V)) {
 206         Changed = true;
 207         SI->eraseFromParent();
 208       } else if (Instruction *I = dyn_cast<Instruction>(V)) {
 209         if (I->hasOneUse())
 210           Dead.push_back(std::make_pair(I, SI));
 211       }
 212     } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
 213       if (isa<Constant>(MSI->getValue())) {
 214         Changed = true;
 215         MSI->eraseFromParent();
 216       } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
 217         if (I->hasOneUse())
 218           Dead.push_back(std::make_pair(I, MSI));
 219       }
 220     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
 221       GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
 222       if (MemSrc && MemSrc->isConstant()) {
 223         Changed = true;
 224         MTI->eraseFromParent();
 225       } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
 226         if (I->hasOneUse())
 227           Dead.push_back(std::make_pair(I, MTI));
 228       }
 229     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 230       if (CE->use_empty()) {
 231         CE->destroyConstant();
 232         Changed = true;
 233       }
 234     } else if (Constant *C = dyn_cast<Constant>(U)) {
 235       if (isSafeToDestroyConstant(C)) {
 236         C->destroyConstant();
 237         // This could have invalidated UI, start over from scratch.
 238         Dead.clear();
 239         CleanupPointerRootUsers(GV, TLI);
 240         return true;
 241       }
 242     }
 243   }
 244
 245   for (int i = 0, e = Dead.size(); i != e; ++i) {
 246     if (IsSafeComputationToRemove(Dead[i].first, TLI)) {
 247       Dead[i].second->eraseFromParent();
 248       Instruction *I = Dead[i].first;
 249       do {
 250         if (isAllocationFn(I, TLI))
 251           break;
 252         Instruction *J = dyn_cast<Instruction>(I->getOperand(0));
 253         if (!J)
 254           break;
 255         I->eraseFromParent();
 256         I = J;
 257       } while (1);
 258       I->eraseFromParent();
 259     }
 260   }
 261
 262   return Changed;
 263 }
 264
 265 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 266 /// users of the global, cleaning up the obvious ones.  This is largely just a
 267 /// quick scan over the use list to clean up the easy and obvious cruft.  This
 268 /// returns true if it made a change.
 269 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init,
 270                                        const DataLayout *DL,
 271                                        TargetLibraryInfo *TLI) {
 272   bool Changed = false;
 273   // Note that we need to use a weak value handle for the worklist items. When
 274   // we delete a constant array, we may also be holding pointer to one of its
 275   // elements (or an element of one of its elements if we're dealing with an
 276   // array of arrays) in the worklist.
 277   SmallVector<WeakVH, 8> WorkList(V->user_begin(), V->user_end());
 278   while (!WorkList.empty()) {
 279     Value *UV = WorkList.pop_back_val();
 280     if (!UV)
 281       continue;
 282
 283     User *U = cast<User>(UV);
 284
 285     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 286       if (Init) {
 287         // Replace the load with the initializer.
 288         LI->replaceAllUsesWith(Init);
 289         LI->eraseFromParent();
 290         Changed = true;
 291       }
 292     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 293       // Store must be unreachable or storing Init into the global.
 294       SI->eraseFromParent();
 295       Changed = true;
 296     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 297       if (CE->getOpcode() == Instruction::GetElementPtr) {
 298         Constant *SubInit = nullptr;
 299         if (Init)
 300           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 301         Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, TLI);
 302       } else if ((CE->getOpcode() == Instruction::BitCast &&
 303                   CE->getType()->isPointerTy()) ||
 304                  CE->getOpcode() == Instruction::AddrSpaceCast) {
 305         // Pointer cast, delete any stores and memsets to the global.
 306         Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, TLI);
 307       }
 308
 309       if (CE->use_empty()) {
 310         CE->destroyConstant();
 311         Changed = true;
 312       }
 313     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 314       // Do not transform "gepinst (gep constexpr (GV))" here, because forming
 315       // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
 316       // and will invalidate our notion of what Init is.
 317       Constant *SubInit = nullptr;
 318       if (!isa<ConstantExpr>(GEP->getOperand(0))) {
 319         ConstantExpr *CE =
 320           dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, DL, TLI));
 321         if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
 322           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 323
 324         // If the initializer is an all-null value and we have an inbounds GEP,
 325         // we already know what the result of any load from that GEP is.
 326         // TODO: Handle splats.
 327         if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
 328           SubInit = Constant::getNullValue(GEP->getType()->getElementType());
 329       }
 330       Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, TLI);
 331
 332       if (GEP->use_empty()) {
 333         GEP->eraseFromParent();
 334         Changed = true;
 335       }
 336     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
 337       if (MI->getRawDest() == V) {
 338         MI->eraseFromParent();
 339         Changed = true;
 340       }
 341
 342     } else if (Constant *C = dyn_cast<Constant>(U)) {
 343       // If we have a chain of dead constantexprs or other things dangling from
 344       // us, and if they are all dead, nuke them without remorse.
 345       if (isSafeToDestroyConstant(C)) {
 346         C->destroyConstant();
 347         CleanupConstantGlobalUsers(V, Init, DL, TLI);
 348         return true;
 349       }
 350     }
 351   }
 352   return Changed;
 353 }
 354
 355 /// isSafeSROAElementUse - Return true if the specified instruction is a safe
 356 /// user of a derived expression from a global that we want to SROA.
 357 static bool isSafeSROAElementUse(Value *V) {
 358   // We might have a dead and dangling constant hanging off of here.
 359   if (Constant *C = dyn_cast<Constant>(V))
 360     return isSafeToDestroyConstant(C);
 361
 362   Instruction *I = dyn_cast<Instruction>(V);
 363   if (!I) return false;
 364
 365   // Loads are ok.
 366   if (isa<LoadInst>(I)) return true;
 367
 368   // Stores *to* the pointer are ok.
 369   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 370     return SI->getOperand(0) != V;
 371
 372   // Otherwise, it must be a GEP.
 373   GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I);
 374   if (!GEPI) return false;
 375
 376   if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) ||
 377       !cast<Constant>(GEPI->getOperand(1))->isNullValue())
 378     return false;
 379
 380   for (User *U : GEPI->users())
 381     if (!isSafeSROAElementUse(U))
 382       return false;
 383   return true;
 384 }
 385
 386
 387 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
 388 /// Look at it and its uses and decide whether it is safe to SROA this global.
 389 ///
 390 static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) {
 391   // The user of the global must be a GEP Inst or a ConstantExpr GEP.
 392   if (!isa<GetElementPtrInst>(U) &&
 393       (!isa<ConstantExpr>(U) ||
 394        cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
 395     return false;
 396
 397   // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 398   // don't like < 3 operand CE's, and we don't like non-constant integer
 399   // indices.  This enforces that all uses are 'gep GV, 0, C, ...' for some
 400   // value of C.
 401   if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
 402       !cast<Constant>(U->getOperand(1))->isNullValue() ||
 403       !isa<ConstantInt>(U->getOperand(2)))
 404     return false;
 405
 406   gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
 407   ++GEPI;  // Skip over the pointer index.
 408
 409   // If this is a use of an array allocation, do a bit more checking for sanity.
 410   if (ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) {
 411     uint64_t NumElements = AT->getNumElements();
 412     ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2));
 413
 414     // Check to make sure that index falls within the array.  If not,
 415     // something funny is going on, so we won't do the optimization.
 416     //
 417     if (Idx->getZExtValue() >= NumElements)
 418       return false;
 419
 420     // We cannot scalar repl this level of the array unless any array
 421     // sub-indices are in-range constants.  In particular, consider:
 422     // A[0][i].  We cannot know that the user isn't doing invalid things like
 423     // allowing i to index an out-of-range subscript that accesses A[1].
 424     //
 425     // Scalar replacing *just* the outer index of the array is probably not
 426     // going to be a win anyway, so just give up.
 427     for (++GEPI; // Skip array index.
 428          GEPI != E;
 429          ++GEPI) {
 430       uint64_t NumElements;
 431       if (ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI))
 432         NumElements = SubArrayTy->getNumElements();
 433       else if (VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI))
 434         NumElements = SubVectorTy->getNumElements();
 435       else {
 436         assert((*GEPI)->isStructTy() &&
 437                "Indexed GEP type is not array, vector, or struct!");
 438         continue;
 439       }
 440
 441       ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
 442       if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
 443         return false;
 444     }
 445   }
 446
 447   for (User *UU : U->users())
 448     if (!isSafeSROAElementUse(UU))
 449       return false;
 450
 451   return true;
 452 }
 453
 454 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
 455 /// is safe for us to perform this transformation.
 456 ///
 457 static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
 458   for (User *U : GV->users())
 459     if (!IsUserOfGlobalSafeForSRA(U, GV))
 460       return false;
 461
 462   return true;
 463 }
 464
 465
 466 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 467 /// variable.  This opens the door for other optimizations by exposing the
 468 /// behavior of the program in a more fine-grained way.  We have determined that
 469 /// this transformation is safe already.  We return the first global variable we
 470 /// insert so that the caller can reprocess it.
 471 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
 472   // Make sure this global only has simple uses that we can SRA.
 473   if (!GlobalUsersSafeToSRA(GV))
 474     return nullptr;
 475
 476   assert(GV->hasLocalLinkage() && !GV->isConstant());
 477   Constant *Init = GV->getInitializer();
 478   Type *Ty = Init->getType();
 479
 480   std::vector<GlobalVariable*> NewGlobals;
 481   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 482
 483   // Get the alignment of the global, either explicit or target-specific.
 484   unsigned StartAlignment = GV->getAlignment();
 485   if (StartAlignment == 0)
 486     StartAlignment = DL.getABITypeAlignment(GV->getType());
 487
 488   if (StructType *STy = dyn_cast<StructType>(Ty)) {
 489     NewGlobals.reserve(STy->getNumElements());
 490     const StructLayout &Layout = *DL.getStructLayout(STy);
 491     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 492       Constant *In = Init->getAggregateElement(i);
 493       assert(In && "Couldn't get element of initializer?");
 494       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 495                                                GlobalVariable::InternalLinkage,
 496                                                In, GV->getName()+"."+Twine(i),
 497                                                GV->getThreadLocalMode(),
 498                                               GV->getType()->getAddressSpace());
 499       Globals.insert(GV, NGV);
 500       NewGlobals.push_back(NGV);
 501
 502       // Calculate the known alignment of the field.  If the original aggregate
 503       // had 256 byte alignment for example, something might depend on that:
 504       // propagate info to each field.
 505       uint64_t FieldOffset = Layout.getElementOffset(i);
 506       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset);
 507       if (NewAlign > DL.getABITypeAlignment(STy->getElementType(i)))
 508         NGV->setAlignment(NewAlign);
 509     }
 510   } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 511     unsigned NumElements = 0;
 512     if (ArrayType *ATy = dyn_cast<ArrayType>(STy))
 513       NumElements = ATy->getNumElements();
 514     else
 515       NumElements = cast<VectorType>(STy)->getNumElements();
 516
 517     if (NumElements > 16 && GV->hasNUsesOrMore(16))
 518       return nullptr; // It's not worth it.
 519     NewGlobals.reserve(NumElements);
 520
 521     uint64_t EltSize = DL.getTypeAllocSize(STy->getElementType());
 522     unsigned EltAlign = DL.getABITypeAlignment(STy->getElementType());
 523     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 524       Constant *In = Init->getAggregateElement(i);
 525       assert(In && "Couldn't get element of initializer?");
 526
 527       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 528                                                GlobalVariable::InternalLinkage,
 529                                                In, GV->getName()+"."+Twine(i),
 530                                                GV->getThreadLocalMode(),
 531                                               GV->getType()->getAddressSpace());
 532       Globals.insert(GV, NGV);
 533       NewGlobals.push_back(NGV);
 534
 535       // Calculate the known alignment of the field.  If the original aggregate
 536       // had 256 byte alignment for example, something might depend on that:
 537       // propagate info to each field.
 538       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i);
 539       if (NewAlign > EltAlign)
 540         NGV->setAlignment(NewAlign);
 541     }
 542   }
 543
 544   if (NewGlobals.empty())
 545     return nullptr;
 546
 547   DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV);
 548
 549   Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
 550
 551   // Loop over all of the uses of the global, replacing the constantexpr geps,
 552   // with smaller constantexpr geps or direct references.
 553   while (!GV->use_empty()) {
 554     User *GEP = GV->user_back();
 555     assert(((isa<ConstantExpr>(GEP) &&
 556              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
 557             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
 558
 559     // Ignore the 1th operand, which has to be zero or else the program is quite
 560     // broken (undefined).  Get the 2nd operand, which is the structure or array
 561     // index.
 562     unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
 563     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 564
 565     Value *NewPtr = NewGlobals[Val];
 566
 567     // Form a shorter GEP if needed.
 568     if (GEP->getNumOperands() > 3) {
 569       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
 570         SmallVector<Constant*, 8> Idxs;
 571         Idxs.push_back(NullInt);
 572         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 573           Idxs.push_back(CE->getOperand(i));
 574         NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs);
 575       } else {
 576         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
 577         SmallVector<Value*, 8> Idxs;
 578         Idxs.push_back(NullInt);
 579         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
 580           Idxs.push_back(GEPI->getOperand(i));
 581         NewPtr = GetElementPtrInst::Create(NewPtr, Idxs,
 582                                            GEPI->getName()+"."+Twine(Val),GEPI);
 583       }
 584     }
 585     GEP->replaceAllUsesWith(NewPtr);
 586
 587     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
 588       GEPI->eraseFromParent();
 589     else
 590       cast<ConstantExpr>(GEP)->destroyConstant();
 591   }
 592
 593   // Delete the old global, now that it is dead.
 594   Globals.erase(GV);
 595   ++NumSRA;
 596
 597   // Loop over the new globals array deleting any globals that are obviously
 598   // dead.  This can arise due to scalarization of a structure or an array that
 599   // has elements that are dead.
 600   unsigned FirstGlobal = 0;
 601   for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
 602     if (NewGlobals[i]->use_empty()) {
 603       Globals.erase(NewGlobals[i]);
 604       if (FirstGlobal == i) ++FirstGlobal;
 605     }
 606
 607   return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr;
 608 }
 609
 610 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
 611 /// value will trap if the value is dynamically null.  PHIs keeps track of any
 612 /// phi nodes we've seen to avoid reprocessing them.
 613 static bool AllUsesOfValueWillTrapIfNull(const Value *V,
 614                                          SmallPtrSet<const PHINode*, 8> &PHIs) {
 615   for (const User *U : V->users())
 616     if (isa<LoadInst>(U)) {
 617       // Will trap.
 618     } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
 619       if (SI->getOperand(0) == V) {
 620         //cerr << "NONTRAPPING USE: " << *U;
 621         return false;  // Storing the value.
 622       }
 623     } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
 624       if (CI->getCalledValue() != V) {
 625         //cerr << "NONTRAPPING USE: " << *U;
 626         return false;  // Not calling the ptr
 627       }
 628     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
 629       if (II->getCalledValue() != V) {
 630         //cerr << "NONTRAPPING USE: " << *U;
 631         return false;  // Not calling the ptr
 632       }
 633     } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
 634       if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
 635     } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
 636       if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
 637     } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
 638       // If we've already seen this phi node, ignore it, it has already been
 639       // checked.
 640       if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
 641         return false;
 642     } else if (isa<ICmpInst>(U) &&
 643                isa<ConstantPointerNull>(U->getOperand(1))) {
 644       // Ignore icmp X, null
 645     } else {
 646       //cerr << "NONTRAPPING USE: " << *U;
 647       return false;
 648     }
 649
 650   return true;
 651 }
 652
 653 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
 654 /// from GV will trap if the loaded value is null.  Note that this also permits
 655 /// comparisons of the loaded value against null, as a special case.
 656 static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
 657   for (const User *U : GV->users())
 658     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
 659       SmallPtrSet<const PHINode*, 8> PHIs;
 660       if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
 661         return false;
 662     } else if (isa<StoreInst>(U)) {
 663       // Ignore stores to the global.
 664     } else {
 665       // We don't know or understand this user, bail out.
 666       //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
 667       return false;
 668     }
 669   return true;
 670 }
 671
 672 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
 673   bool Changed = false;
 674   for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
 675     Instruction *I = cast<Instruction>(*UI++);
 676     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 677       LI->setOperand(0, NewV);
 678       Changed = true;
 679     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 680       if (SI->getOperand(1) == V) {
 681         SI->setOperand(1, NewV);
 682         Changed = true;
 683       }
 684     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 685       CallSite CS(I);
 686       if (CS.getCalledValue() == V) {
 687         // Calling through the pointer!  Turn into a direct call, but be careful
 688         // that the pointer is not also being passed as an argument.
 689         CS.setCalledFunction(NewV);
 690         Changed = true;
 691         bool PassedAsArg = false;
 692         for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
 693           if (CS.getArgument(i) == V) {
 694             PassedAsArg = true;
 695             CS.setArgument(i, NewV);
 696           }
 697
 698         if (PassedAsArg) {
 699           // Being passed as an argument also.  Be careful to not invalidate UI!
 700           UI = V->user_begin();
 701         }
 702       }
 703     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 704       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
 705                                 ConstantExpr::getCast(CI->getOpcode(),
 706                                                       NewV, CI->getType()));
 707       if (CI->use_empty()) {
 708         Changed = true;
 709         CI->eraseFromParent();
 710       }
 711     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
 712       // Should handle GEP here.
 713       SmallVector<Constant*, 8> Idxs;
 714       Idxs.reserve(GEPI->getNumOperands()-1);
 715       for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
 716            i != e; ++i)
 717         if (Constant *C = dyn_cast<Constant>(*i))
 718           Idxs.push_back(C);
 719         else
 720           break;
 721       if (Idxs.size() == GEPI->getNumOperands()-1)
 722         Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
 723                           ConstantExpr::getGetElementPtr(NewV, Idxs));
 724       if (GEPI->use_empty()) {
 725         Changed = true;
 726         GEPI->eraseFromParent();
 727       }
 728     }
 729   }
 730
 731   return Changed;
 732 }
 733
 734
 735 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
 736 /// value stored into it.  If there are uses of the loaded value that would trap
 737 /// if the loaded value is dynamically null, then we know that they cannot be
 738 /// reachable with a null optimize away the load.
 739 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV,
 740                                             const DataLayout *DL,
 741                                             TargetLibraryInfo *TLI) {
 742   bool Changed = false;
 743
 744   // Keep track of whether we are able to remove all the uses of the global
 745   // other than the store that defines it.
 746   bool AllNonStoreUsesGone = true;
 747
 748   // Replace all uses of loads with uses of uses of the stored value.
 749   for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
 750     User *GlobalUser = *GUI++;
 751     if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
 752       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
 753       // If we were able to delete all uses of the loads
 754       if (LI->use_empty()) {
 755         LI->eraseFromParent();
 756         Changed = true;
 757       } else {
 758         AllNonStoreUsesGone = false;
 759       }
 760     } else if (isa<StoreInst>(GlobalUser)) {
 761       // Ignore the store that stores "LV" to the global.
 762       assert(GlobalUser->getOperand(1) == GV &&
 763              "Must be storing *to* the global");
 764     } else {
 765       AllNonStoreUsesGone = false;
 766
 767       // If we get here we could have other crazy uses that are transitively
 768       // loaded.
 769       assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
 770               isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||
 771               isa<BitCastInst>(GlobalUser) ||
 772               isa<GetElementPtrInst>(GlobalUser)) &&
 773              "Only expect load and stores!");
 774     }
 775   }
 776
 777   if (Changed) {
 778     DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV);
 779     ++NumGlobUses;
 780   }
 781
 782   // If we nuked all of the loads, then none of the stores are needed either,
 783   // nor is the global.
 784   if (AllNonStoreUsesGone) {
 785     if (isLeakCheckerRoot(GV)) {
 786       Changed |= CleanupPointerRootUsers(GV, TLI);
 787     } else {
 788       Changed = true;
 789       CleanupConstantGlobalUsers(GV, nullptr, DL, TLI);
 790     }
 791     if (GV->use_empty()) {
 792       DEBUG(dbgs() << "  *** GLOBAL NOW DEAD!\n");
 793       Changed = true;
 794       GV->eraseFromParent();
 795       ++NumDeleted;
 796     }
 797   }
 798   return Changed;
 799 }
 800
 801 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
 802 /// instructions that are foldable.
 803 static void ConstantPropUsersOf(Value *V, const DataLayout *DL,
 804                                 TargetLibraryInfo *TLI) {
 805   for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
 806     if (Instruction *I = dyn_cast<Instruction>(*UI++))
 807       if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
 808         I->replaceAllUsesWith(NewC);
 809
 810         // Advance UI to the next non-I use to avoid invalidating it!
 811         // Instructions could multiply use V.
 812         while (UI != E && *UI == I)
 813           ++UI;
 814         I->eraseFromParent();
 815       }
 816 }
 817
 818 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
 819 /// variable, and transforms the program as if it always contained the result of
 820 /// the specified malloc.  Because it is always the result of the specified
 821 /// malloc, there is no reason to actually DO the malloc.  Instead, turn the
 822 /// malloc into a global, and any loads of GV as uses of the new global.
 823 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV,
 824                                                      CallInst *CI,
 825                                                      Type *AllocTy,
 826                                                      ConstantInt *NElements,
 827                                                      const DataLayout *DL,
 828                                                      TargetLibraryInfo *TLI) {
 829   DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CI << '\n');
 830
 831   Type *GlobalType;
 832   if (NElements->getZExtValue() == 1)
 833     GlobalType = AllocTy;
 834   else
 835     // If we have an array allocation, the global variable is of an array.
 836     GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
 837
 838   // Create the new global variable.  The contents of the malloc'd memory is
 839   // undefined, so initialize with an undef value.
 840   GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(),
 841                                              GlobalType, false,
 842                                              GlobalValue::InternalLinkage,
 843                                              UndefValue::get(GlobalType),
 844                                              GV->getName()+".body",
 845                                              GV,
 846                                              GV->getThreadLocalMode());
 847
 848   // If there are bitcast users of the malloc (which is typical, usually we have
 849   // a malloc + bitcast) then replace them with uses of the new global.  Update
 850   // other users to use the global as well.
 851   BitCastInst *TheBC = nullptr;
 852   while (!CI->use_empty()) {
 853     Instruction *User = cast<Instruction>(CI->user_back());
 854     if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
 855       if (BCI->getType() == NewGV->getType()) {
 856         BCI->replaceAllUsesWith(NewGV);
 857         BCI->eraseFromParent();
 858       } else {
 859         BCI->setOperand(0, NewGV);
 860       }
 861     } else {
 862       if (!TheBC)
 863         TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
 864       User->replaceUsesOfWith(CI, TheBC);
 865     }
 866   }
 867
 868   Constant *RepValue = NewGV;
 869   if (NewGV->getType() != GV->getType()->getElementType())
 870     RepValue = ConstantExpr::getBitCast(RepValue,
 871                                         GV->getType()->getElementType());
 872
 873   // If there is a comparison against null, we will insert a global bool to
 874   // keep track of whether the global was initialized yet or not.
 875   GlobalVariable *InitBool =
 876     new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
 877                        GlobalValue::InternalLinkage,
 878                        ConstantInt::getFalse(GV->getContext()),
 879                        GV->getName()+".init", GV->getThreadLocalMode());
 880   bool InitBoolUsed = false;
 881
 882   // Loop over all uses of GV, processing them in turn.
 883   while (!GV->use_empty()) {
 884     if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
 885       // The global is initialized when the store to it occurs.
 886       new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0,
 887                     SI->getOrdering(), SI->getSynchScope(), SI);
 888       SI->eraseFromParent();
 889       continue;
 890     }
 891
 892     LoadInst *LI = cast<LoadInst>(GV->user_back());
 893     while (!LI->use_empty()) {
 894       Use &LoadUse = *LI->use_begin();
 895       ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
 896       if (!ICI) {
 897         LoadUse = RepValue;
 898         continue;
 899       }
 900
 901       // Replace the cmp X, 0 with a use of the bool value.
 902       // Sink the load to where the compare was, if atomic rules allow us to.
 903       Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0,
 904                                LI->getOrdering(), LI->getSynchScope(),
 905                                LI->isUnordered() ? (Instruction*)ICI : LI);
 906       InitBoolUsed = true;
 907       switch (ICI->getPredicate()) {
 908       default: llvm_unreachable("Unknown ICmp Predicate!");
 909       case ICmpInst::ICMP_ULT:
 910       case ICmpInst::ICMP_SLT:   // X < null -> always false
 911         LV = ConstantInt::getFalse(GV->getContext());
 912         break;
 913       case ICmpInst::ICMP_ULE:
 914       case ICmpInst::ICMP_SLE:
 915       case ICmpInst::ICMP_EQ:
 916         LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
 917         break;
 918       case ICmpInst::ICMP_NE:
 919       case ICmpInst::ICMP_UGE:
 920       case ICmpInst::ICMP_SGE:
 921       case ICmpInst::ICMP_UGT:
 922       case ICmpInst::ICMP_SGT:
 923         break;  // no change.
 924       }
 925       ICI->replaceAllUsesWith(LV);
 926       ICI->eraseFromParent();
 927     }
 928     LI->eraseFromParent();
 929   }
 930
 931   // If the initialization boolean was used, insert it, otherwise delete it.
 932   if (!InitBoolUsed) {
 933     while (!InitBool->use_empty())  // Delete initializations
 934       cast<StoreInst>(InitBool->user_back())->eraseFromParent();
 935     delete InitBool;
 936   } else
 937     GV->getParent()->getGlobalList().insert(GV, InitBool);
 938
 939   // Now the GV is dead, nuke it and the malloc..
 940   GV->eraseFromParent();
 941   CI->eraseFromParent();
 942
 943   // To further other optimizations, loop over all users of NewGV and try to
 944   // constant prop them.  This will promote GEP instructions with constant
 945   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
 946   ConstantPropUsersOf(NewGV, DL, TLI);
 947   if (RepValue != NewGV)
 948     ConstantPropUsersOf(RepValue, DL, TLI);
 949
 950   return NewGV;
 951 }
 952
 953 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
 954 /// to make sure that there are no complex uses of V.  We permit simple things
 955 /// like dereferencing the pointer, but not storing through the address, unless
 956 /// it is to the specified global.
 957 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V,
 958                                                       const GlobalVariable *GV,
 959                                          SmallPtrSet<const PHINode*, 8> &PHIs) {
 960   for (const User *U : V->users()) {
 961     const Instruction *Inst = cast<Instruction>(U);
 962
 963     if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
 964       continue; // Fine, ignore.
 965     }
 966
 967     if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 968       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
 969         return false;  // Storing the pointer itself... bad.
 970       continue; // Otherwise, storing through it, or storing into GV... fine.
 971     }
 972
 973     // Must index into the array and into the struct.
 974     if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) {
 975       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
 976         return false;
 977       continue;
 978     }
 979
 980     if (const PHINode *PN = dyn_cast<PHINode>(Inst)) {
 981       // PHIs are ok if all uses are ok.  Don't infinitely recurse through PHI
 982       // cycles.
 983       if (PHIs.insert(PN))
 984         if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs))
 985           return false;
 986       continue;
 987     }
 988
 989     if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
 990       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs))
 991         return false;
 992       continue;
 993     }
 994
 995     return false;
 996   }
 997   return true;
 998 }
 999
1000 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
1001 /// somewhere.  Transform all uses of the allocation into loads from the
1002 /// global and uses of the resultant pointer.  Further, delete the store into
1003 /// GV.  This assumes that these value pass the
1004 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
1005 static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
1006                                           GlobalVariable *GV) {
1007   while (!Alloc->use_empty()) {
1008     Instruction *U = cast<Instruction>(*Alloc->user_begin());
1009     Instruction *InsertPt = U;
1010     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1011       // If this is the store of the allocation into the global, remove it.
1012       if (SI->getOperand(1) == GV) {
1013         SI->eraseFromParent();
1014         continue;
1015       }
1016     } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
1017       // Insert the load in the corresponding predecessor, not right before the
1018       // PHI.
1019       InsertPt = PN->getIncomingBlock(*Alloc->use_begin())->getTerminator();
1020     } else if (isa<BitCastInst>(U)) {
1021       // Must be bitcast between the malloc and store to initialize the global.
1022       ReplaceUsesOfMallocWithGlobal(U, GV);
1023       U->eraseFromParent();
1024       continue;
1025     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1026       // If this is a "GEP bitcast" and the user is a store to the global, then
1027       // just process it as a bitcast.
1028       if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse())
1029         if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->user_back()))
1030           if (SI->getOperand(1) == GV) {
1031             // Must be bitcast GEP between the malloc and store to initialize
1032             // the global.
1033             ReplaceUsesOfMallocWithGlobal(GEPI, GV);
1034             GEPI->eraseFromParent();
1035             continue;
1036           }
1037     }
1038
1039     // Insert a load from the global, and use it instead of the malloc.
1040     Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt);
1041     U->replaceUsesOfWith(Alloc, NL);
1042   }
1043 }
1044
1045 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
1046 /// of a load) are simple enough to perform heap SRA on.  This permits GEP's
1047 /// that index through the array and struct field, icmps of null, and PHIs.
1048 static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V,
1049                         SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs,
1050                         SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) {
1051   // We permit two users of the load: setcc comparing against the null
1052   // pointer, and a getelementptr of a specific form.
1053   for (const User *U : V->users()) {
1054     const Instruction *UI = cast<Instruction>(U);
1055
1056     // Comparison against null is ok.
1057     if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UI)) {
1058       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
1059         return false;
1060       continue;
1061     }
1062
1063     // getelementptr is also ok, but only a simple form.
1064     if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) {
1065       // Must index into the array and into the struct.
1066       if (GEPI->getNumOperands() < 3)
1067         return false;
1068
1069       // Otherwise the GEP is ok.
1070       continue;
1071     }
1072
1073     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1074       if (!LoadUsingPHIsPerLoad.insert(PN))
1075         // This means some phi nodes are dependent on each other.
1076         // Avoid infinite looping!
1077         return false;
1078       if (!LoadUsingPHIs.insert(PN))
1079         // If we have already analyzed this PHI, then it is safe.
1080         continue;
1081
1082       // Make sure all uses of the PHI are simple enough to transform.
1083       if (!LoadUsesSimpleEnoughForHeapSRA(PN,
1084                                           LoadUsingPHIs, LoadUsingPHIsPerLoad))
1085         return false;
1086
1087       continue;
1088     }
1089
1090     // Otherwise we don't know what this is, not ok.
1091     return false;
1092   }
1093
1094   return true;
1095 }
1096
1097
1098 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
1099 /// GV are simple enough to perform HeapSRA, return true.
1100 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV,
1101                                                     Instruction *StoredVal) {
1102   SmallPtrSet<const PHINode*, 32> LoadUsingPHIs;
1103   SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad;
1104   for (const User *U : GV->users())
1105     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
1106       if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
1107                                           LoadUsingPHIsPerLoad))
1108         return false;
1109       LoadUsingPHIsPerLoad.clear();
1110     }
1111
1112   // If we reach here, we know that all uses of the loads and transitive uses
1113   // (through PHI nodes) are simple enough to transform.  However, we don't know
1114   // that all inputs the to the PHI nodes are in the same equivalence sets.
1115   // Check to verify that all operands of the PHIs are either PHIS that can be
1116   // transformed, loads from GV, or MI itself.
1117   for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin()
1118        , E = LoadUsingPHIs.end(); I != E; ++I) {
1119     const PHINode *PN = *I;
1120     for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
1121       Value *InVal = PN->getIncomingValue(op);
1122
1123       // PHI of the stored value itself is ok.
1124       if (InVal == StoredVal) continue;
1125
1126       if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) {
1127         // One of the PHIs in our set is (optimistically) ok.
1128         if (LoadUsingPHIs.count(InPN))
1129           continue;
1130         return false;
1131       }
1132
1133       // Load from GV is ok.
1134       if (const LoadInst *LI = dyn_cast<LoadInst>(InVal))
1135         if (LI->getOperand(0) == GV)
1136           continue;
1137
1138       // UNDEF? NULL?
1139
1140       // Anything else is rejected.
1141       return false;
1142     }
1143   }
1144
1145   return true;
1146 }
1147
1148 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo,
1149                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1150                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1151   std::vector<Value*> &FieldVals = InsertedScalarizedValues[V];
1152
1153   if (FieldNo >= FieldVals.size())
1154     FieldVals.resize(FieldNo+1);
1155
1156   // If we already have this value, just reuse the previously scalarized
1157   // version.
1158   if (Value *FieldVal = FieldVals[FieldNo])
1159     return FieldVal;
1160
1161   // Depending on what instruction this is, we have several cases.
1162   Value *Result;
1163   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
1164     // This is a scalarized version of the load from the global.  Just create
1165     // a new Load of the scalarized global.
1166     Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo,
1167                                            InsertedScalarizedValues,
1168                                            PHIsToRewrite),
1169                           LI->getName()+".f"+Twine(FieldNo), LI);
1170   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
1171     // PN's type is pointer to struct.  Make a new PHI of pointer to struct
1172     // field.
1173
1174     PointerType *PTy = cast<PointerType>(PN->getType());
1175     StructType *ST = cast<StructType>(PTy->getElementType());
1176
1177     unsigned AS = PTy->getAddressSpace();
1178     PHINode *NewPN =
1179       PHINode::Create(PointerType::get(ST->getElementType(FieldNo), AS),
1180                      PN->getNumIncomingValues(),
1181                      PN->getName()+".f"+Twine(FieldNo), PN);
1182     Result = NewPN;
1183     PHIsToRewrite.push_back(std::make_pair(PN, FieldNo));
1184   } else {
1185     llvm_unreachable("Unknown usable value");
1186   }
1187
1188   return FieldVals[FieldNo] = Result;
1189 }
1190
1191 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from
1192 /// the load, rewrite the derived value to use the HeapSRoA'd load.
1193 static void RewriteHeapSROALoadUser(Instruction *LoadUser,
1194              DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1195                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1196   // If this is a comparison against null, handle it.
1197   if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) {
1198     assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
1199     // If we have a setcc of the loaded pointer, we can use a setcc of any
1200     // field.
1201     Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0,
1202                                    InsertedScalarizedValues, PHIsToRewrite);
1203
1204     Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr,
1205                               Constant::getNullValue(NPtr->getType()),
1206                               SCI->getName());
1207     SCI->replaceAllUsesWith(New);
1208     SCI->eraseFromParent();
1209     return;
1210   }
1211
1212   // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...'
1213   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) {
1214     assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
1215            && "Unexpected GEPI!");
1216
1217     // Load the pointer for this field.
1218     unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
1219     Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo,
1220                                      InsertedScalarizedValues, PHIsToRewrite);
1221
1222     // Create the new GEP idx vector.
1223     SmallVector<Value*, 8> GEPIdx;
1224     GEPIdx.push_back(GEPI->getOperand(1));
1225     GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end());
1226
1227     Value *NGEPI = GetElementPtrInst::Create(NewPtr, GEPIdx,
1228                                              GEPI->getName(), GEPI);
1229     GEPI->replaceAllUsesWith(NGEPI);
1230     GEPI->eraseFromParent();
1231     return;
1232   }
1233
1234   // Recursively transform the users of PHI nodes.  This will lazily create the
1235   // PHIs that are needed for individual elements.  Keep track of what PHIs we
1236   // see in InsertedScalarizedValues so that we don't get infinite loops (very
1237   // antisocial).  If the PHI is already in InsertedScalarizedValues, it has
1238   // already been seen first by another load, so its uses have already been
1239   // processed.
1240   PHINode *PN = cast<PHINode>(LoadUser);
1241   if (!InsertedScalarizedValues.insert(std::make_pair(PN,
1242                                               std::vector<Value*>())).second)
1243     return;
1244
1245   // If this is the first time we've seen this PHI, recursively process all
1246   // users.
1247   for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
1248     Instruction *User = cast<Instruction>(*UI++);
1249     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1250   }
1251 }
1252
1253 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global.  Ptr
1254 /// is a value loaded from the global.  Eliminate all uses of Ptr, making them
1255 /// use FieldGlobals instead.  All uses of loaded values satisfy
1256 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA.
1257 static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load,
1258                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1259                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1260   for (auto UI = Load->user_begin(), E = Load->user_end(); UI != E;) {
1261     Instruction *User = cast<Instruction>(*UI++);
1262     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1263   }
1264
1265   if (Load->use_empty()) {
1266     Load->eraseFromParent();
1267     InsertedScalarizedValues.erase(Load);
1268   }
1269 }
1270
1271 /// PerformHeapAllocSRoA - CI is an allocation of an array of structures.  Break
1272 /// it up into multiple allocations of arrays of the fields.
1273 static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI,
1274                                             Value *NElems, const DataLayout *DL,
1275                                             const TargetLibraryInfo *TLI) {
1276   DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << "  MALLOC = " << *CI << '\n');
1277   Type *MAT = getMallocAllocatedType(CI, TLI);
1278   StructType *STy = cast<StructType>(MAT);
1279
1280   // There is guaranteed to be at least one use of the malloc (storing
1281   // it into GV).  If there are other uses, change them to be uses of
1282   // the global to simplify later code.  This also deletes the store
1283   // into GV.
1284   ReplaceUsesOfMallocWithGlobal(CI, GV);
1285
1286   // Okay, at this point, there are no users of the malloc.  Insert N
1287   // new mallocs at the same place as CI, and N globals.
1288   std::vector<Value*> FieldGlobals;
1289   std::vector<Value*> FieldMallocs;
1290
1291   unsigned AS = GV->getType()->getPointerAddressSpace();
1292   for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
1293     Type *FieldTy = STy->getElementType(FieldNo);
1294     PointerType *PFieldTy = PointerType::get(FieldTy, AS);
1295
1296     GlobalVariable *NGV =
1297       new GlobalVariable(*GV->getParent(),
1298                          PFieldTy, false, GlobalValue::InternalLinkage,
1299                          Constant::getNullValue(PFieldTy),
1300                          GV->getName() + ".f" + Twine(FieldNo), GV,
1301                          GV->getThreadLocalMode());
1302     FieldGlobals.push_back(NGV);
1303
1304     unsigned TypeSize = DL->getTypeAllocSize(FieldTy);
1305     if (StructType *ST = dyn_cast<StructType>(FieldTy))
1306       TypeSize = DL->getStructLayout(ST)->getSizeInBytes();
1307     Type *IntPtrTy = DL->getIntPtrType(CI->getType());
1308     Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy,
1309                                         ConstantInt::get(IntPtrTy, TypeSize),
1310                                         NElems, nullptr,
1311                                         CI->getName() + ".f" + Twine(FieldNo));
1312     FieldMallocs.push_back(NMI);
1313     new StoreInst(NMI, NGV, CI);
1314   }
1315
1316   // The tricky aspect of this transformation is handling the case when malloc
1317   // fails.  In the original code, malloc failing would set the result pointer
1318   // of malloc to null.  In this case, some mallocs could succeed and others
1319   // could fail.  As such, we emit code that looks like this:
1320   //    F0 = malloc(field0)
1321   //    F1 = malloc(field1)
1322   //    F2 = malloc(field2)
1323   //    if (F0 == 0 || F1 == 0 || F2 == 0) {
1324   //      if (F0) { free(F0); F0 = 0; }
1325   //      if (F1) { free(F1); F1 = 0; }
1326   //      if (F2) { free(F2); F2 = 0; }
1327   //    }
1328   // The malloc can also fail if its argument is too large.
1329   Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0);
1330   Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0),
1331                                   ConstantZero, "isneg");
1332   for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
1333     Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i],
1334                              Constant::getNullValue(FieldMallocs[i]->getType()),
1335                                "isnull");
1336     RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI);
1337   }
1338
1339   // Split the basic block at the old malloc.
1340   BasicBlock *OrigBB = CI->getParent();
1341   BasicBlock *ContBB = OrigBB->splitBasicBlock(CI, "malloc_cont");
1342
1343   // Create the block to check the first condition.  Put all these blocks at the
1344   // end of the function as they are unlikely to be executed.
1345   BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(),
1346                                                 "malloc_ret_null",
1347                                                 OrigBB->getParent());
1348
1349   // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
1350   // branch on RunningOr.
1351   OrigBB->getTerminator()->eraseFromParent();
1352   BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB);
1353
1354   // Within the NullPtrBlock, we need to emit a comparison and branch for each
1355   // pointer, because some may be null while others are not.
1356   for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1357     Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
1358     Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal,
1359                               Constant::getNullValue(GVVal->getType()));
1360     BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it",
1361                                                OrigBB->getParent());
1362     BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next",
1363                                                OrigBB->getParent());
1364     Instruction *BI = BranchInst::Create(FreeBlock, NextBlock,
1365                                          Cmp, NullPtrBlock);
1366
1367     // Fill in FreeBlock.
1368     CallInst::CreateFree(GVVal, BI);
1369     new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
1370                   FreeBlock);
1371     BranchInst::Create(NextBlock, FreeBlock);
1372
1373     NullPtrBlock = NextBlock;
1374   }
1375
1376   BranchInst::Create(ContBB, NullPtrBlock);
1377
1378   // CI is no longer needed, remove it.
1379   CI->eraseFromParent();
1380
1381   /// InsertedScalarizedLoads - As we process loads, if we can't immediately
1382   /// update all uses of the load, keep track of what scalarized loads are
1383   /// inserted for a given load.
1384   DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues;
1385   InsertedScalarizedValues[GV] = FieldGlobals;
1386
1387   std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite;
1388
1389   // Okay, the malloc site is completely handled.  All of the uses of GV are now
1390   // loads, and all uses of those loads are simple.  Rewrite them to use loads
1391   // of the per-field globals instead.
1392   for (auto UI = GV->user_begin(), E = GV->user_end(); UI != E;) {
1393     Instruction *User = cast<Instruction>(*UI++);
1394
1395     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1396       RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite);
1397       continue;
1398     }
1399
1400     // Must be a store of null.
1401     StoreInst *SI = cast<StoreInst>(User);
1402     assert(isa<ConstantPointerNull>(SI->getOperand(0)) &&
1403            "Unexpected heap-sra user!");
1404
1405     // Insert a store of null into each global.
1406     for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1407       PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType());
1408       Constant *Null = Constant::getNullValue(PT->getElementType());
1409       new StoreInst(Null, FieldGlobals[i], SI);
1410     }
1411     // Erase the original store.
1412     SI->eraseFromParent();
1413   }
1414
1415   // While we have PHIs that are interesting to rewrite, do it.
1416   while (!PHIsToRewrite.empty()) {
1417     PHINode *PN = PHIsToRewrite.back().first;
1418     unsigned FieldNo = PHIsToRewrite.back().second;
1419     PHIsToRewrite.pop_back();
1420     PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]);
1421     assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi");
1422
1423     // Add all the incoming values.  This can materialize more phis.
1424     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1425       Value *InVal = PN->getIncomingValue(i);
1426       InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues,
1427                                PHIsToRewrite);
1428       FieldPN->addIncoming(InVal, PN->getIncomingBlock(i));
1429     }
1430   }
1431
1432   // Drop all inter-phi links and any loads that made it this far.
1433   for (DenseMap<Value*, std::vector<Value*> >::iterator
1434        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1435        I != E; ++I) {
1436     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1437       PN->dropAllReferences();
1438     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1439       LI->dropAllReferences();
1440   }
1441
1442   // Delete all the phis and loads now that inter-references are dead.
1443   for (DenseMap<Value*, std::vector<Value*> >::iterator
1444        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1445        I != E; ++I) {
1446     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1447       PN->eraseFromParent();
1448     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1449       LI->eraseFromParent();
1450   }
1451
1452   // The old global is now dead, remove it.
1453   GV->eraseFromParent();
1454
1455   ++NumHeapSRA;
1456   return cast<GlobalVariable>(FieldGlobals[0]);
1457 }
1458
1459 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a
1460 /// pointer global variable with a single value stored it that is a malloc or
1461 /// cast of malloc.
1462 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV,
1463                                                CallInst *CI,
1464                                                Type *AllocTy,
1465                                                AtomicOrdering Ordering,
1466                                                Module::global_iterator &GVI,
1467                                                const DataLayout *DL,
1468                                                TargetLibraryInfo *TLI) {
1469   if (!DL)
1470     return false;
1471
1472   // If this is a malloc of an abstract type, don't touch it.
1473   if (!AllocTy->isSized())
1474     return false;
1475
1476   // We can't optimize this global unless all uses of it are *known* to be
1477   // of the malloc value, not of the null initializer value (consider a use
1478   // that compares the global's value against zero to see if the malloc has
1479   // been reached).  To do this, we check to see if all uses of the global
1480   // would trap if the global were null: this proves that they must all
1481   // happen after the malloc.
1482   if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
1483     return false;
1484
1485   // We can't optimize this if the malloc itself is used in a complex way,
1486   // for example, being stored into multiple globals.  This allows the
1487   // malloc to be stored into the specified global, loaded icmp'd, and
1488   // GEP'd.  These are all things we could transform to using the global
1489   // for.
1490   SmallPtrSet<const PHINode*, 8> PHIs;
1491   if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs))
1492     return false;
1493
1494   // If we have a global that is only initialized with a fixed size malloc,
1495   // transform the program to use global memory instead of malloc'd memory.
1496   // This eliminates dynamic allocation, avoids an indirection accessing the
1497   // data, and exposes the resultant global to further GlobalOpt.
1498   // We cannot optimize the malloc if we cannot determine malloc array size.
1499   Value *NElems = getMallocArraySize(CI, DL, TLI, true);
1500   if (!NElems)
1501     return false;
1502
1503   if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
1504     // Restrict this transformation to only working on small allocations
1505     // (2048 bytes currently), as we don't want to introduce a 16M global or
1506     // something.
1507     if (NElements->getZExtValue() * DL->getTypeAllocSize(AllocTy) < 2048) {
1508       GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
1509       return true;
1510     }
1511
1512   // If the allocation is an array of structures, consider transforming this
1513   // into multiple malloc'd arrays, one for each field.  This is basically
1514   // SRoA for malloc'd memory.
1515
1516   if (Ordering != NotAtomic)
1517     return false;
1518
1519   // If this is an allocation of a fixed size array of structs, analyze as a
1520   // variable size array.  malloc [100 x struct],1 -> malloc struct, 100
1521   if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1))
1522     if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy))
1523       AllocTy = AT->getElementType();
1524
1525   StructType *AllocSTy = dyn_cast<StructType>(AllocTy);
1526   if (!AllocSTy)
1527     return false;
1528
1529   // This the structure has an unreasonable number of fields, leave it
1530   // alone.
1531   if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 &&
1532       AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) {
1533
1534     // If this is a fixed size array, transform the Malloc to be an alloc of
1535     // structs.  malloc [100 x struct],1 -> malloc struct, 100
1536     if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) {
1537       Type *IntPtrTy = DL->getIntPtrType(CI->getType());
1538       unsigned TypeSize = DL->getStructLayout(AllocSTy)->getSizeInBytes();
1539       Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize);
1540       Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements());
1541       Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy,
1542                                                    AllocSize, NumElements,
1543                                                    nullptr, CI->getName());
1544       Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI);
1545       CI->replaceAllUsesWith(Cast);
1546       CI->eraseFromParent();
1547       if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc))
1548         CI = cast<CallInst>(BCI->getOperand(0));
1549       else
1550         CI = cast<CallInst>(Malloc);
1551     }
1552
1553     GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, DL, TLI, true),
1554                                DL, TLI);
1555     return true;
1556   }
1557
1558   return false;
1559 }
1560
1561 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
1562 // that only one value (besides its initializer) is ever stored to the global.
1563 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
1564                                      AtomicOrdering Ordering,
1565                                      Module::global_iterator &GVI,
1566                                      const DataLayout *DL,
1567                                      TargetLibraryInfo *TLI) {
1568   // Ignore no-op GEPs and bitcasts.
1569   StoredOnceVal = StoredOnceVal->stripPointerCasts();
1570
1571   // If we are dealing with a pointer global that is initialized to null and
1572   // only has one (non-null) value stored into it, then we can optimize any
1573   // users of the loaded value (often calls and loads) that would trap if the
1574   // value was null.
1575   if (GV->getInitializer()->getType()->isPointerTy() &&
1576       GV->getInitializer()->isNullValue()) {
1577     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1578       if (GV->getInitializer()->getType() != SOVC->getType())
1579         SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
1580
1581       // Optimize away any trapping uses of the loaded value.
1582       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, TLI))
1583         return true;
1584     } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) {
1585       Type *MallocType = getMallocAllocatedType(CI, TLI);
1586       if (MallocType &&
1587           TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI,
1588                                              DL, TLI))
1589         return true;
1590     }
1591   }
1592
1593   return false;
1594 }
1595
1596 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
1597 /// two values ever stored into GV are its initializer and OtherVal.  See if we
1598 /// can shrink the global into a boolean and select between the two values
1599 /// whenever it is used.  This exposes the values to other scalar optimizations.
1600 static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
1601   Type *GVElType = GV->getType()->getElementType();
1602
1603   // If GVElType is already i1, it is already shrunk.  If the type of the GV is
1604   // an FP value, pointer or vector, don't do this optimization because a select
1605   // between them is very expensive and unlikely to lead to later
1606   // simplification.  In these cases, we typically end up with "cond ? v1 : v2"
1607   // where v1 and v2 both require constant pool loads, a big loss.
1608   if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1609       GVElType->isFloatingPointTy() ||
1610       GVElType->isPointerTy() || GVElType->isVectorTy())
1611     return false;
1612
1613   // Walk the use list of the global seeing if all the uses are load or store.
1614   // If there is anything else, bail out.
1615   for (User *U : GV->users())
1616     if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
1617       return false;
1618
1619   DEBUG(dbgs() << "   *** SHRINKING TO BOOL: " << *GV);
1620
1621   // Create the new global, initializing it to false.
1622   GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
1623                                              false,
1624                                              GlobalValue::InternalLinkage,
1625                                         ConstantInt::getFalse(GV->getContext()),
1626                                              GV->getName()+".b",
1627                                              GV->getThreadLocalMode(),
1628                                              GV->getType()->getAddressSpace());
1629   GV->getParent()->getGlobalList().insert(GV, NewGV);
1630
1631   Constant *InitVal = GV->getInitializer();
1632   assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
1633          "No reason to shrink to bool!");
1634
1635   // If initialized to zero and storing one into the global, we can use a cast
1636   // instead of a select to synthesize the desired value.
1637   bool IsOneZero = false;
1638   if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
1639     IsOneZero = InitVal->isNullValue() && CI->isOne();
1640
1641   while (!GV->use_empty()) {
1642     Instruction *UI = cast<Instruction>(GV->user_back());
1643     if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1644       // Change the store into a boolean store.
1645       bool StoringOther = SI->getOperand(0) == OtherVal;
1646       // Only do this if we weren't storing a loaded value.
1647       Value *StoreVal;
1648       if (StoringOther || SI->getOperand(0) == InitVal) {
1649         StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
1650                                     StoringOther);
1651       } else {
1652         // Otherwise, we are storing a previously loaded copy.  To do this,
1653         // change the copy from copying the original value to just copying the
1654         // bool.
1655         Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1656
1657         // If we've already replaced the input, StoredVal will be a cast or
1658         // select instruction.  If not, it will be a load of the original
1659         // global.
1660         if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1661           assert(LI->getOperand(0) == GV && "Not a copy!");
1662           // Insert a new load, to preserve the saved value.
1663           StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1664                                   LI->getOrdering(), LI->getSynchScope(), LI);
1665         } else {
1666           assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1667                  "This is not a form that we understand!");
1668           StoreVal = StoredVal->getOperand(0);
1669           assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1670         }
1671       }
1672       new StoreInst(StoreVal, NewGV, false, 0,
1673                     SI->getOrdering(), SI->getSynchScope(), SI);
1674     } else {
1675       // Change the load into a load of bool then a select.
1676       LoadInst *LI = cast<LoadInst>(UI);
1677       LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1678                                    LI->getOrdering(), LI->getSynchScope(), LI);
1679       Value *NSI;
1680       if (IsOneZero)
1681         NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1682       else
1683         NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1684       NSI->takeName(LI);
1685       LI->replaceAllUsesWith(NSI);
1686     }
1687     UI->eraseFromParent();
1688   }
1689
1690   // Retain the name of the old global variable. People who are debugging their
1691   // programs may expect these variables to be named the same.
1692   NewGV->takeName(GV);
1693   GV->eraseFromParent();
1694   return true;
1695 }
1696
1697
1698 /// ProcessGlobal - Analyze the specified global variable and optimize it if
1699 /// possible.  If we make a change, return true.
1700 bool GlobalOpt::ProcessGlobal(GlobalVariable *GV,
1701                               Module::global_iterator &GVI) {
1702   if (!GV->isDiscardableIfUnused())
1703     return false;
1704
1705   // Do more involved optimizations if the global is internal.
1706   GV->removeDeadConstantUsers();
1707
1708   if (GV->use_empty()) {
1709     DEBUG(dbgs() << "GLOBAL DEAD: " << *GV);
1710     GV->eraseFromParent();
1711     ++NumDeleted;
1712     return true;
1713   }
1714
1715   if (!GV->hasLocalLinkage())
1716     return false;
1717
1718   GlobalStatus GS;
1719
1720   if (GlobalStatus::analyzeGlobal(GV, GS))
1721     return false;
1722
1723   if (!GS.IsCompared && !GV->hasUnnamedAddr()) {
1724     GV->setUnnamedAddr(true);
1725     NumUnnamed++;
1726   }
1727
1728   if (GV->isConstant() || !GV->hasInitializer())
1729     return false;
1730
1731   return ProcessInternalGlobal(GV, GVI, GS);
1732 }
1733
1734 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
1735 /// it if possible.  If we make a change, return true.
1736 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
1737                                       Module::global_iterator &GVI,
1738                                       const GlobalStatus &GS) {
1739   // If this is a first class global and has only one accessing function
1740   // and this function is main (which we know is not recursive), we replace
1741   // the global with a local alloca in this function.
1742   //
1743   // NOTE: It doesn't make sense to promote non-single-value types since we
1744   // are just replacing static memory to stack memory.
1745   //
1746   // If the global is in different address space, don't bring it to stack.
1747   if (!GS.HasMultipleAccessingFunctions &&
1748       GS.AccessingFunction && !GS.HasNonInstructionUser &&
1749       GV->getType()->getElementType()->isSingleValueType() &&
1750       GS.AccessingFunction->getName() == "main" &&
1751       GS.AccessingFunction->hasExternalLinkage() &&
1752       GV->getType()->getAddressSpace() == 0) {
1753     DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV);
1754     Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1755                                                    ->getEntryBlock().begin());
1756     Type *ElemTy = GV->getType()->getElementType();
1757     // FIXME: Pass Global's alignment when globals have alignment
1758     AllocaInst *Alloca = new AllocaInst(ElemTy, nullptr,
1759                                         GV->getName(), &FirstI);
1760     if (!isa<UndefValue>(GV->getInitializer()))
1761       new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1762
1763     GV->replaceAllUsesWith(Alloca);
1764     GV->eraseFromParent();
1765     ++NumLocalized;
1766     return true;
1767   }
1768
1769   // If the global is never loaded (but may be stored to), it is dead.
1770   // Delete it now.
1771   if (!GS.IsLoaded) {
1772     DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV);
1773
1774     bool Changed;
1775     if (isLeakCheckerRoot(GV)) {
1776       // Delete any constant stores to the global.
1777       Changed = CleanupPointerRootUsers(GV, TLI);
1778     } else {
1779       // Delete any stores we can find to the global.  We may not be able to
1780       // make it completely dead though.
1781       Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1782     }
1783
1784     // If the global is dead now, delete it.
1785     if (GV->use_empty()) {
1786       GV->eraseFromParent();
1787       ++NumDeleted;
1788       Changed = true;
1789     }
1790     return Changed;
1791
1792   } else if (GS.StoredType <= GlobalStatus::InitializerStored) {
1793     DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
1794     GV->setConstant(true);
1795
1796     // Clean up any obviously simplifiable users now.
1797     CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1798
1799     // If the global is dead now, just nuke it.
1800     if (GV->use_empty()) {
1801       DEBUG(dbgs() << "   *** Marking constant allowed us to simplify "
1802             << "all users and delete global!\n");
1803       GV->eraseFromParent();
1804       ++NumDeleted;
1805     }
1806
1807     ++NumMarked;
1808     return true;
1809   } else if (!GV->getInitializer()->getType()->isSingleValueType()) {
1810     if (DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>()) {
1811       const DataLayout &DL = DLP->getDataLayout();
1812       if (GlobalVariable *FirstNewGV = SRAGlobal(GV, DL)) {
1813         GVI = FirstNewGV;  // Don't skip the newly produced globals!
1814         return true;
1815       }
1816     }
1817   } else if (GS.StoredType == GlobalStatus::StoredOnce) {
1818     // If the initial value for the global was an undef value, and if only
1819     // one other value was stored into it, we can just change the
1820     // initializer to be the stored value, then delete all stores to the
1821     // global.  This allows us to mark it constant.
1822     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1823       if (isa<UndefValue>(GV->getInitializer())) {
1824         // Change the initial value here.
1825         GV->setInitializer(SOVConstant);
1826
1827         // Clean up any obviously simplifiable users now.
1828         CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1829
1830         if (GV->use_empty()) {
1831           DEBUG(dbgs() << "   *** Substituting initializer allowed us to "
1832                        << "simplify all users and delete global!\n");
1833           GV->eraseFromParent();
1834           ++NumDeleted;
1835         } else {
1836           GVI = GV;
1837         }
1838         ++NumSubstitute;
1839         return true;
1840       }
1841
1842     // Try to optimize globals based on the knowledge that only one value
1843     // (besides its initializer) is ever stored to the global.
1844     if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI,
1845                                  DL, TLI))
1846       return true;
1847
1848     // Otherwise, if the global was not a boolean, we can shrink it to be a
1849     // boolean.
1850     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
1851       if (GS.Ordering == NotAtomic) {
1852         if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
1853           ++NumShrunkToBool;
1854           return true;
1855         }
1856       }
1857     }
1858   }
1859
1860   return false;
1861 }
1862
1863 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
1864 /// function, changing them to FastCC.
1865 static void ChangeCalleesToFastCall(Function *F) {
1866   for (User *U : F->users()) {
1867     if (isa<BlockAddress>(U))
1868       continue;
1869     CallSite CS(cast<Instruction>(U));
1870     CS.setCallingConv(CallingConv::Fast);
1871   }
1872 }
1873
1874 static AttributeSet StripNest(LLVMContext &C, const AttributeSet &Attrs) {
1875   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
1876     unsigned Index = Attrs.getSlotIndex(i);
1877     if (!Attrs.getSlotAttributes(i).hasAttribute(Index, Attribute::Nest))
1878       continue;
1879
1880     // There can be only one.
1881     return Attrs.removeAttribute(C, Index, Attribute::Nest);
1882   }
1883
1884   return Attrs;
1885 }
1886
1887 static void RemoveNestAttribute(Function *F) {
1888   F->setAttributes(StripNest(F->getContext(), F->getAttributes()));
1889   for (User *U : F->users()) {
1890     if (isa<BlockAddress>(U))
1891       continue;
1892     CallSite CS(cast<Instruction>(U));
1893     CS.setAttributes(StripNest(F->getContext(), CS.getAttributes()));
1894   }
1895 }
1896
1897 /// Return true if this is a calling convention that we'd like to change.  The
1898 /// idea here is that we don't want to mess with the convention if the user
1899 /// explicitly requested something with performance implications like coldcc,
1900 /// GHC, or anyregcc.
1901 static bool isProfitableToMakeFastCC(Function *F) {
1902   CallingConv::ID CC = F->getCallingConv();
1903   // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
1904   return CC == CallingConv::C || CC == CallingConv::X86_ThisCall;
1905 }
1906
1907 bool GlobalOpt::OptimizeFunctions(Module &M) {
1908   bool Changed = false;
1909   // Optimize functions.
1910   for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
1911     Function *F = FI++;
1912     // Functions without names cannot be referenced outside this module.
1913     if (!F->hasName() && !F->isDeclaration())
1914       F->setLinkage(GlobalValue::InternalLinkage);
1915     F->removeDeadConstantUsers();
1916     if (F->isDefTriviallyDead()) {
1917       F->eraseFromParent();
1918       Changed = true;
1919       ++NumFnDeleted;
1920     } else if (F->hasLocalLinkage()) {
1921       if (isProfitableToMakeFastCC(F) && !F->isVarArg() &&
1922           !F->hasAddressTaken()) {
1923         // If this function has a calling convention worth changing, is not a
1924         // varargs function, and is only called directly, promote it to use the
1925         // Fast calling convention.
1926         F->setCallingConv(CallingConv::Fast);
1927         ChangeCalleesToFastCall(F);
1928         ++NumFastCallFns;
1929         Changed = true;
1930       }
1931
1932       if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
1933           !F->hasAddressTaken()) {
1934         // The function is not used by a trampoline intrinsic, so it is safe
1935         // to remove the 'nest' attribute.
1936         RemoveNestAttribute(F);
1937         ++NumNestRemoved;
1938         Changed = true;
1939       }
1940     }
1941   }
1942   return Changed;
1943 }
1944
1945 bool GlobalOpt::OptimizeGlobalVars(Module &M) {
1946   bool Changed = false;
1947   for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
1948        GVI != E; ) {
1949     GlobalVariable *GV = GVI++;
1950     // Global variables without names cannot be referenced outside this module.
1951     if (!GV->hasName() && !GV->isDeclaration())
1952       GV->setLinkage(GlobalValue::InternalLinkage);
1953     // Simplify the initializer.
1954     if (GV->hasInitializer())
1955       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) {
1956         Constant *New = ConstantFoldConstantExpression(CE, DL, TLI);
1957         if (New && New != CE)
1958           GV->setInitializer(New);
1959       }
1960
1961     Changed |= ProcessGlobal(GV, GVI);
1962   }
1963   return Changed;
1964 }
1965
1966 /// FindGlobalCtors - Find the llvm.global_ctors list, verifying that all
1967 /// initializers have an init priority of 65535.
1968 GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) {
1969   GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors");
1970   if (!GV) return nullptr;
1971
1972   // Verify that the initializer is simple enough for us to handle. We are
1973   // only allowed to optimize the initializer if it is unique.
1974   if (!GV->hasUniqueInitializer()) return nullptr;
1975
1976   if (isa<ConstantAggregateZero>(GV->getInitializer()))
1977     return GV;
1978   ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
1979
1980   for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) {
1981     if (isa<ConstantAggregateZero>(*i))
1982       continue;
1983     ConstantStruct *CS = cast<ConstantStruct>(*i);
1984     if (isa<ConstantPointerNull>(CS->getOperand(1)))
1985       continue;
1986
1987     // Must have a function or null ptr.
1988     if (!isa<Function>(CS->getOperand(1)))
1989       return nullptr;
1990
1991     // Init priority must be standard.
1992     ConstantInt *CI = cast<ConstantInt>(CS->getOperand(0));
1993     if (CI->getZExtValue() != 65535)
1994       return nullptr;
1995   }
1996
1997   return GV;
1998 }
1999
2000 /// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand,
2001 /// return a list of the functions and null terminator as a vector.
2002 static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) {
2003   if (GV->getInitializer()->isNullValue())
2004     return std::vector<Function*>();
2005   ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
2006   std::vector<Function*> Result;
2007   Result.reserve(CA->getNumOperands());
2008   for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) {
2009     ConstantStruct *CS = cast<ConstantStruct>(*i);
2010     Result.push_back(dyn_cast<Function>(CS->getOperand(1)));
2011   }
2012   return Result;
2013 }
2014
2015 /// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the
2016 /// specified array, returning the new global to use.
2017 static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL,
2018                                           const std::vector<Function*> &Ctors) {
2019   // If we made a change, reassemble the initializer list.
2020   Constant *CSVals[2];
2021   CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 65535);
2022   CSVals[1] = nullptr;
2023
2024   StructType *StructTy =
2025     cast<StructType>(GCL->getType()->getElementType()->getArrayElementType());
2026
2027   // Create the new init list.
2028   std::vector<Constant*> CAList;
2029   for (unsigned i = 0, e = Ctors.size(); i != e; ++i) {
2030     if (Ctors[i]) {
2031       CSVals[1] = Ctors[i];
2032     } else {
2033       Type *FTy = FunctionType::get(Type::getVoidTy(GCL->getContext()),
2034                                           false);
2035       PointerType *PFTy = PointerType::getUnqual(FTy);
2036       CSVals[1] = Constant::getNullValue(PFTy);
2037       CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()),
2038                                    0x7fffffff);
2039     }
2040     CAList.push_back(ConstantStruct::get(StructTy, CSVals));
2041   }
2042
2043   // Create the array initializer.
2044   Constant *CA = ConstantArray::get(ArrayType::get(StructTy,
2045                                                    CAList.size()), CAList);
2046
2047   // If we didn't change the number of elements, don't create a new GV.
2048   if (CA->getType() == GCL->getInitializer()->getType()) {
2049     GCL->setInitializer(CA);
2050     return GCL;
2051   }
2052
2053   // Create the new global and insert it next to the existing list.
2054   GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(),
2055                                            GCL->getLinkage(), CA, "",
2056                                            GCL->getThreadLocalMode());
2057   GCL->getParent()->getGlobalList().insert(GCL, NGV);
2058   NGV->takeName(GCL);
2059
2060   // Nuke the old list, replacing any uses with the new one.
2061   if (!GCL->use_empty()) {
2062     Constant *V = NGV;
2063     if (V->getType() != GCL->getType())
2064       V = ConstantExpr::getBitCast(V, GCL->getType());
2065     GCL->replaceAllUsesWith(V);
2066   }
2067   GCL->eraseFromParent();
2068
2069   if (Ctors.size())
2070     return NGV;
2071   else
2072     return nullptr;
2073 }
2074
2075
2076 static inline bool
2077 isSimpleEnoughValueToCommit(Constant *C,
2078                             SmallPtrSet<Constant*, 8> &SimpleConstants,
2079                             const DataLayout *DL);
2080
2081
2082 /// isSimpleEnoughValueToCommit - Return true if the specified constant can be
2083 /// handled by the code generator.  We don't want to generate something like:
2084 ///   void *X = &X/42;
2085 /// because the code generator doesn't have a relocation that can handle that.
2086 ///
2087 /// This function should be called if C was not found (but just got inserted)
2088 /// in SimpleConstants to avoid having to rescan the same constants all the
2089 /// time.
2090 static bool isSimpleEnoughValueToCommitHelper(Constant *C,
2091                                    SmallPtrSet<Constant*, 8> &SimpleConstants,
2092                                    const DataLayout *DL) {
2093   // Simple integer, undef, constant aggregate zero, global addresses, etc are
2094   // all supported.
2095   if (C->getNumOperands() == 0 || isa<BlockAddress>(C) ||
2096       isa<GlobalValue>(C))
2097     return true;
2098
2099   // Aggregate values are safe if all their elements are.
2100   if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) ||
2101       isa<ConstantVector>(C)) {
2102     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
2103       Constant *Op = cast<Constant>(C->getOperand(i));
2104       if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, DL))
2105         return false;
2106     }
2107     return true;
2108   }
2109
2110   // We don't know exactly what relocations are allowed in constant expressions,
2111   // so we allow &global+constantoffset, which is safe and uniformly supported
2112   // across targets.
2113   ConstantExpr *CE = cast<ConstantExpr>(C);
2114   switch (CE->getOpcode()) {
2115   case Instruction::BitCast:
2116     // Bitcast is fine if the casted value is fine.
2117     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2118
2119   case Instruction::IntToPtr:
2120   case Instruction::PtrToInt:
2121     // int <=> ptr is fine if the int type is the same size as the
2122     // pointer type.
2123     if (!DL || DL->getTypeSizeInBits(CE->getType()) !=
2124                DL->getTypeSizeInBits(CE->getOperand(0)->getType()))
2125       return false;
2126     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2127
2128   // GEP is fine if it is simple + constant offset.
2129   case Instruction::GetElementPtr:
2130     for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
2131       if (!isa<ConstantInt>(CE->getOperand(i)))
2132         return false;
2133     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2134
2135   case Instruction::Add:
2136     // We allow simple+cst.
2137     if (!isa<ConstantInt>(CE->getOperand(1)))
2138       return false;
2139     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2140   }
2141   return false;
2142 }
2143
2144 static inline bool
2145 isSimpleEnoughValueToCommit(Constant *C,
2146                             SmallPtrSet<Constant*, 8> &SimpleConstants,
2147                             const DataLayout *DL) {
2148   // If we already checked this constant, we win.
2149   if (!SimpleConstants.insert(C)) return true;
2150   // Check the constant.
2151   return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
2152 }
2153
2154
2155 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple
2156 /// enough for us to understand.  In particular, if it is a cast to anything
2157 /// other than from one pointer type to another pointer type, we punt.
2158 /// We basically just support direct accesses to globals and GEP's of
2159 /// globals.  This should be kept up to date with CommitValueTo.
2160 static bool isSimpleEnoughPointerToCommit(Constant *C) {
2161   // Conservatively, avoid aggregate types. This is because we don't
2162   // want to worry about them partially overlapping other stores.
2163   if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
2164     return false;
2165
2166   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
2167     // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2168     // external globals.
2169     return GV->hasUniqueInitializer();
2170
2171   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
2172     // Handle a constantexpr gep.
2173     if (CE->getOpcode() == Instruction::GetElementPtr &&
2174         isa<GlobalVariable>(CE->getOperand(0)) &&
2175         cast<GEPOperator>(CE)->isInBounds()) {
2176       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2177       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2178       // external globals.
2179       if (!GV->hasUniqueInitializer())
2180         return false;
2181
2182       // The first index must be zero.
2183       ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
2184       if (!CI || !CI->isZero()) return false;
2185
2186       // The remaining indices must be compile-time known integers within the
2187       // notional bounds of the corresponding static array types.
2188       if (!CE->isGEPWithNoNotionalOverIndexing())
2189         return false;
2190
2191       return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2192
2193     // A constantexpr bitcast from a pointer to another pointer is a no-op,
2194     // and we know how to evaluate it by moving the bitcast from the pointer
2195     // operand to the value operand.
2196     } else if (CE->getOpcode() == Instruction::BitCast &&
2197                isa<GlobalVariable>(CE->getOperand(0))) {
2198       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2199       // external globals.
2200       return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
2201     }
2202   }
2203
2204   return false;
2205 }
2206
2207 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
2208 /// initializer.  This returns 'Init' modified to reflect 'Val' stored into it.
2209 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
2210 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
2211                                    ConstantExpr *Addr, unsigned OpNo) {
2212   // Base case of the recursion.
2213   if (OpNo == Addr->getNumOperands()) {
2214     assert(Val->getType() == Init->getType() && "Type mismatch!");
2215     return Val;
2216   }
2217
2218   SmallVector<Constant*, 32> Elts;
2219   if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
2220     // Break up the constant into its elements.
2221     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2222       Elts.push_back(Init->getAggregateElement(i));
2223
2224     // Replace the element that we are supposed to.
2225     ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2226     unsigned Idx = CU->getZExtValue();
2227     assert(Idx < STy->getNumElements() && "Struct index out of range!");
2228     Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2229
2230     // Return the modified struct.
2231     return ConstantStruct::get(STy, Elts);
2232   }
2233
2234   ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2235   SequentialType *InitTy = cast<SequentialType>(Init->getType());
2236
2237   uint64_t NumElts;
2238   if (ArrayType *ATy = dyn_cast<ArrayType>(InitTy))
2239     NumElts = ATy->getNumElements();
2240   else
2241     NumElts = InitTy->getVectorNumElements();
2242
2243   // Break up the array into elements.
2244   for (uint64_t i = 0, e = NumElts; i != e; ++i)
2245     Elts.push_back(Init->getAggregateElement(i));
2246
2247   assert(CI->getZExtValue() < NumElts);
2248   Elts[CI->getZExtValue()] =
2249     EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2250
2251   if (Init->getType()->isArrayTy())
2252     return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
2253   return ConstantVector::get(Elts);
2254 }
2255
2256 /// CommitValueTo - We have decided that Addr (which satisfies the predicate
2257 /// isSimpleEnoughPointerToCommit) should get Val as its value.  Make it happen.
2258 static void CommitValueTo(Constant *Val, Constant *Addr) {
2259   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2260     assert(GV->hasInitializer());
2261     GV->setInitializer(Val);
2262     return;
2263   }
2264
2265   ConstantExpr *CE = cast<ConstantExpr>(Addr);
2266   GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2267   GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2268 }
2269
2270 namespace {
2271
2272 /// Evaluator - This class evaluates LLVM IR, producing the Constant
2273 /// representing each SSA instruction.  Changes to global variables are stored
2274 /// in a mapping that can be iterated over after the evaluation is complete.
2275 /// Once an evaluation call fails, the evaluation object should not be reused.
2276 class Evaluator {
2277 public:
2278   Evaluator(const DataLayout *DL, const TargetLibraryInfo *TLI)
2279     : DL(DL), TLI(TLI) {
2280     ValueStack.push_back(make_unique<DenseMap<Value*, Constant*>>());
2281   }
2282
2283   ~Evaluator() {
2284     for (auto &Tmp : AllocaTmps)
2285       // If there are still users of the alloca, the program is doing something
2286       // silly, e.g. storing the address of the alloca somewhere and using it
2287       // later.  Since this is undefined, we'll just make it be null.
2288       if (!Tmp->use_empty())
2289         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
2290   }
2291
2292   /// EvaluateFunction - Evaluate a call to function F, returning true if
2293   /// successful, false if we can't evaluate it.  ActualArgs contains the formal
2294   /// arguments for the function.
2295   bool EvaluateFunction(Function *F, Constant *&RetVal,
2296                         const SmallVectorImpl<Constant*> &ActualArgs);
2297
2298   /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2299   /// successful, false if we can't evaluate it.  NewBB returns the next BB that
2300   /// control flows into, or null upon return.
2301   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
2302
2303   Constant *getVal(Value *V) {
2304     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
2305     Constant *R = ValueStack.back()->lookup(V);
2306     assert(R && "Reference to an uncomputed value!");
2307     return R;
2308   }
2309
2310   void setVal(Value *V, Constant *C) {
2311     (*ValueStack.back())[V] = C;
2312   }
2313
2314   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
2315     return MutatedMemory;
2316   }
2317
2318   const SmallPtrSet<GlobalVariable*, 8> &getInvariants() const {
2319     return Invariants;
2320   }
2321
2322 private:
2323   Constant *ComputeLoadResult(Constant *P);
2324
2325   /// ValueStack - As we compute SSA register values, we store their contents
2326   /// here. The back of the vector contains the current function and the stack
2327   /// contains the values in the calling frames.
2328   SmallVector<std::unique_ptr<DenseMap<Value*, Constant*>>, 4> ValueStack;
2329
2330   /// CallStack - This is used to detect recursion.  In pathological situations
2331   /// we could hit exponential behavior, but at least there is nothing
2332   /// unbounded.
2333   SmallVector<Function*, 4> CallStack;
2334
2335   /// MutatedMemory - For each store we execute, we update this map.  Loads
2336   /// check this to get the most up-to-date value.  If evaluation is successful,
2337   /// this state is committed to the process.
2338   DenseMap<Constant*, Constant*> MutatedMemory;
2339
2340   /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
2341   /// to represent its body.  This vector is needed so we can delete the
2342   /// temporary globals when we are done.
2343   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
2344
2345   /// Invariants - These global variables have been marked invariant by the
2346   /// static constructor.
2347   SmallPtrSet<GlobalVariable*, 8> Invariants;
2348
2349   /// SimpleConstants - These are constants we have checked and know to be
2350   /// simple enough to live in a static initializer of a global.
2351   SmallPtrSet<Constant*, 8> SimpleConstants;
2352
2353   const DataLayout *DL;
2354   const TargetLibraryInfo *TLI;
2355 };
2356
2357 }  // anonymous namespace
2358
2359 /// ComputeLoadResult - Return the value that would be computed by a load from
2360 /// P after the stores reflected by 'memory' have been performed.  If we can't
2361 /// decide, return null.
2362 Constant *Evaluator::ComputeLoadResult(Constant *P) {
2363   // If this memory location has been recently stored, use the stored value: it
2364   // is the most up-to-date.
2365   DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
2366   if (I != MutatedMemory.end()) return I->second;
2367
2368   // Access it.
2369   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
2370     if (GV->hasDefinitiveInitializer())
2371       return GV->getInitializer();
2372     return nullptr;
2373   }
2374
2375   // Handle a constantexpr getelementptr.
2376   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
2377     if (CE->getOpcode() == Instruction::GetElementPtr &&
2378         isa<GlobalVariable>(CE->getOperand(0))) {
2379       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2380       if (GV->hasDefinitiveInitializer())
2381         return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2382     }
2383
2384   return nullptr;  // don't know how to evaluate.
2385 }
2386
2387 /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2388 /// successful, false if we can't evaluate it.  NewBB returns the next BB that
2389 /// control flows into, or null upon return.
2390 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
2391                               BasicBlock *&NextBB) {
2392   // This is the main evaluation loop.
2393   while (1) {
2394     Constant *InstResult = nullptr;
2395
2396     DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
2397
2398     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
2399       if (!SI->isSimple()) {
2400         DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
2401         return false;  // no volatile/atomic accesses.
2402       }
2403       Constant *Ptr = getVal(SI->getOperand(1));
2404       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2405         DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
2406         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2407         DEBUG(dbgs() << "; To: " << *Ptr << "\n");
2408       }
2409       if (!isSimpleEnoughPointerToCommit(Ptr)) {
2410         // If this is too complex for us to commit, reject it.
2411         DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
2412         return false;
2413       }
2414
2415       Constant *Val = getVal(SI->getOperand(0));
2416
2417       // If this might be too difficult for the backend to handle (e.g. the addr
2418       // of one global variable divided by another) then we can't commit it.
2419       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
2420         DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
2421               << "\n");
2422         return false;
2423       }
2424
2425       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2426         if (CE->getOpcode() == Instruction::BitCast) {
2427           DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
2428           // If we're evaluating a store through a bitcast, then we need
2429           // to pull the bitcast off the pointer type and push it onto the
2430           // stored value.
2431           Ptr = CE->getOperand(0);
2432
2433           Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
2434
2435           // In order to push the bitcast onto the stored value, a bitcast
2436           // from NewTy to Val's type must be legal.  If it's not, we can try
2437           // introspecting NewTy to find a legal conversion.
2438           while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) {
2439             // If NewTy is a struct, we can convert the pointer to the struct
2440             // into a pointer to its first member.
2441             // FIXME: This could be extended to support arrays as well.
2442             if (StructType *STy = dyn_cast<StructType>(NewTy)) {
2443               NewTy = STy->getTypeAtIndex(0U);
2444
2445               IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
2446               Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
2447               Constant * const IdxList[] = {IdxZero, IdxZero};
2448
2449               Ptr = ConstantExpr::getGetElementPtr(Ptr, IdxList);
2450               if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
2451                 Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2452
2453             // If we can't improve the situation by introspecting NewTy,
2454             // we have to give up.
2455             } else {
2456               DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
2457                     "evaluate.\n");
2458               return false;
2459             }
2460           }
2461
2462           // If we found compatible types, go ahead and push the bitcast
2463           // onto the stored value.
2464           Val = ConstantExpr::getBitCast(Val, NewTy);
2465
2466           DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
2467         }
2468       }
2469
2470       MutatedMemory[Ptr] = Val;
2471     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
2472       InstResult = ConstantExpr::get(BO->getOpcode(),
2473                                      getVal(BO->getOperand(0)),
2474                                      getVal(BO->getOperand(1)));
2475       DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
2476             << "\n");
2477     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
2478       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
2479                                             getVal(CI->getOperand(0)),
2480                                             getVal(CI->getOperand(1)));
2481       DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
2482             << "\n");
2483     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
2484       InstResult = ConstantExpr::getCast(CI->getOpcode(),
2485                                          getVal(CI->getOperand(0)),
2486                                          CI->getType());
2487       DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
2488             << "\n");
2489     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
2490       InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
2491                                            getVal(SI->getOperand(1)),
2492                                            getVal(SI->getOperand(2)));
2493       DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
2494             << "\n");
2495     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
2496       Constant *P = getVal(GEP->getOperand(0));
2497       SmallVector<Constant*, 8> GEPOps;
2498       for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
2499            i != e; ++i)
2500         GEPOps.push_back(getVal(*i));
2501       InstResult =
2502         ConstantExpr::getGetElementPtr(P, GEPOps,
2503                                        cast<GEPOperator>(GEP)->isInBounds());
2504       DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
2505             << "\n");
2506     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
2507
2508       if (!LI->isSimple()) {
2509         DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
2510         return false;  // no volatile/atomic accesses.
2511       }
2512
2513       Constant *Ptr = getVal(LI->getOperand(0));
2514       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2515         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2516         DEBUG(dbgs() << "Found a constant pointer expression, constant "
2517               "folding: " << *Ptr << "\n");
2518       }
2519       InstResult = ComputeLoadResult(Ptr);
2520       if (!InstResult) {
2521         DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
2522               "\n");
2523         return false; // Could not evaluate load.
2524       }
2525
2526       DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
2527     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
2528       if (AI->isArrayAllocation()) {
2529         DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
2530         return false;  // Cannot handle array allocs.
2531       }
2532       Type *Ty = AI->getType()->getElementType();
2533       AllocaTmps.push_back(
2534           make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage,
2535                                       UndefValue::get(Ty), AI->getName()));
2536       InstResult = AllocaTmps.back().get();
2537       DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
2538     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
2539       CallSite CS(CurInst);
2540
2541       // Debug info can safely be ignored here.
2542       if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
2543         DEBUG(dbgs() << "Ignoring debug info.\n");
2544         ++CurInst;
2545         continue;
2546       }
2547
2548       // Cannot handle inline asm.
2549       if (isa<InlineAsm>(CS.getCalledValue())) {
2550         DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
2551         return false;
2552       }
2553
2554       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
2555         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
2556           if (MSI->isVolatile()) {
2557             DEBUG(dbgs() << "Can not optimize a volatile memset " <<
2558                   "intrinsic.\n");
2559             return false;
2560           }
2561           Constant *Ptr = getVal(MSI->getDest());
2562           Constant *Val = getVal(MSI->getValue());
2563           Constant *DestVal = ComputeLoadResult(getVal(Ptr));
2564           if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
2565             // This memset is a no-op.
2566             DEBUG(dbgs() << "Ignoring no-op memset.\n");
2567             ++CurInst;
2568             continue;
2569           }
2570         }
2571
2572         if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
2573             II->getIntrinsicID() == Intrinsic::lifetime_end) {
2574           DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
2575           ++CurInst;
2576           continue;
2577         }
2578
2579         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2580           // We don't insert an entry into Values, as it doesn't have a
2581           // meaningful return value.
2582           if (!II->use_empty()) {
2583             DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
2584             return false;
2585           }
2586           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
2587           Value *PtrArg = getVal(II->getArgOperand(1));
2588           Value *Ptr = PtrArg->stripPointerCasts();
2589           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
2590             Type *ElemTy = cast<PointerType>(GV->getType())->getElementType();
2591             if (DL && !Size->isAllOnesValue() &&
2592                 Size->getValue().getLimitedValue() >=
2593                 DL->getTypeStoreSize(ElemTy)) {
2594               Invariants.insert(GV);
2595               DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
2596                     << "\n");
2597             } else {
2598               DEBUG(dbgs() << "Found a global var, but can not treat it as an "
2599                     "invariant.\n");
2600             }
2601           }
2602           // Continue even if we do nothing.
2603           ++CurInst;
2604           continue;
2605         }
2606
2607         DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
2608         return false;
2609       }
2610
2611       // Resolve function pointers.
2612       Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
2613       if (!Callee || Callee->mayBeOverridden()) {
2614         DEBUG(dbgs() << "Can not resolve function pointer.\n");
2615         return false;  // Cannot resolve.
2616       }
2617
2618       SmallVector<Constant*, 8> Formals;
2619       for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i)
2620         Formals.push_back(getVal(*i));
2621
2622       if (Callee->isDeclaration()) {
2623         // If this is a function we can constant fold, do it.
2624         if (Constant *C = ConstantFoldCall(Callee, Formals, TLI)) {
2625           InstResult = C;
2626           DEBUG(dbgs() << "Constant folded function call. Result: " <<
2627                 *InstResult << "\n");
2628         } else {
2629           DEBUG(dbgs() << "Can not constant fold function call.\n");
2630           return false;
2631         }
2632       } else {
2633         if (Callee->getFunctionType()->isVarArg()) {
2634           DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
2635           return false;
2636         }
2637
2638         Constant *RetVal = nullptr;
2639         // Execute the call, if successful, use the return value.
2640         ValueStack.push_back(make_unique<DenseMap<Value *, Constant *>>());
2641         if (!EvaluateFunction(Callee, RetVal, Formals)) {
2642           DEBUG(dbgs() << "Failed to evaluate function.\n");
2643           return false;
2644         }
2645         ValueStack.pop_back();
2646         InstResult = RetVal;
2647
2648         if (InstResult) {
2649           DEBUG(dbgs() << "Successfully evaluated function. Result: " <<
2650                 InstResult << "\n\n");
2651         } else {
2652           DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
2653         }
2654       }
2655     } else if (isa<TerminatorInst>(CurInst)) {
2656       DEBUG(dbgs() << "Found a terminator instruction.\n");
2657
2658       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
2659         if (BI->isUnconditional()) {
2660           NextBB = BI->getSuccessor(0);
2661         } else {
2662           ConstantInt *Cond =
2663             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
2664           if (!Cond) return false;  // Cannot determine.
2665
2666           NextBB = BI->getSuccessor(!Cond->getZExtValue());
2667         }
2668       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
2669         ConstantInt *Val =
2670           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
2671         if (!Val) return false;  // Cannot determine.
2672         NextBB = SI->findCaseValue(Val).getCaseSuccessor();
2673       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
2674         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
2675         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
2676           NextBB = BA->getBasicBlock();
2677         else
2678           return false;  // Cannot determine.
2679       } else if (isa<ReturnInst>(CurInst)) {
2680         NextBB = nullptr;
2681       } else {
2682         // invoke, unwind, resume, unreachable.
2683         DEBUG(dbgs() << "Can not handle terminator.");
2684         return false;  // Cannot handle this terminator.
2685       }
2686
2687       // We succeeded at evaluating this block!
2688       DEBUG(dbgs() << "Successfully evaluated block.\n");
2689       return true;
2690     } else {
2691       // Did not know how to evaluate this!
2692       DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
2693             "\n");
2694       return false;
2695     }
2696
2697     if (!CurInst->use_empty()) {
2698       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult))
2699         InstResult = ConstantFoldConstantExpression(CE, DL, TLI);
2700
2701       setVal(CurInst, InstResult);
2702     }
2703
2704     // If we just processed an invoke, we finished evaluating the block.
2705     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
2706       NextBB = II->getNormalDest();
2707       DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
2708       return true;
2709     }
2710
2711     // Advance program counter.
2712     ++CurInst;
2713   }
2714 }
2715
2716 /// EvaluateFunction - Evaluate a call to function F, returning true if
2717 /// successful, false if we can't evaluate it.  ActualArgs contains the formal
2718 /// arguments for the function.
2719 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
2720                                  const SmallVectorImpl<Constant*> &ActualArgs) {
2721   // Check to see if this function is already executing (recursion).  If so,
2722   // bail out.  TODO: we might want to accept limited recursion.
2723   if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
2724     return false;
2725
2726   CallStack.push_back(F);
2727
2728   // Initialize arguments to the incoming values specified.
2729   unsigned ArgNo = 0;
2730   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2731        ++AI, ++ArgNo)
2732     setVal(AI, ActualArgs[ArgNo]);
2733
2734   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
2735   // we can only evaluate any one basic block at most once.  This set keeps
2736   // track of what we have executed so we can detect recursive cases etc.
2737   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
2738
2739   // CurBB - The current basic block we're evaluating.
2740   BasicBlock *CurBB = F->begin();
2741
2742   BasicBlock::iterator CurInst = CurBB->begin();
2743
2744   while (1) {
2745     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
2746     DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
2747
2748     if (!EvaluateBlock(CurInst, NextBB))
2749       return false;
2750
2751     if (!NextBB) {
2752       // Successfully running until there's no next block means that we found
2753       // the return.  Fill it the return value and pop the call stack.
2754       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
2755       if (RI->getNumOperands())
2756         RetVal = getVal(RI->getOperand(0));
2757       CallStack.pop_back();
2758       return true;
2759     }
2760
2761     // Okay, we succeeded in evaluating this control flow.  See if we have
2762     // executed the new block before.  If so, we have a looping function,
2763     // which we cannot evaluate in reasonable time.
2764     if (!ExecutedBlocks.insert(NextBB))
2765       return false;  // looped!
2766
2767     // Okay, we have never been in this block before.  Check to see if there
2768     // are any PHI nodes.  If so, evaluate them with information about where
2769     // we came from.
2770     PHINode *PN = nullptr;
2771     for (CurInst = NextBB->begin();
2772          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
2773       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
2774
2775     // Advance to the next block.
2776     CurBB = NextBB;
2777   }
2778 }
2779
2780 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if
2781 /// we can.  Return true if we can, false otherwise.
2782 static bool EvaluateStaticConstructor(Function *F, const DataLayout *DL,
2783                                       const TargetLibraryInfo *TLI) {
2784   // Call the function.
2785   Evaluator Eval(DL, TLI);
2786   Constant *RetValDummy;
2787   bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2788                                            SmallVector<Constant*, 0>());
2789
2790   if (EvalSuccess) {
2791     // We succeeded at evaluation: commit the result.
2792     DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2793           << F->getName() << "' to " << Eval.getMutatedMemory().size()
2794           << " stores.\n");
2795     for (DenseMap<Constant*, Constant*>::const_iterator I =
2796            Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end();
2797          I != E; ++I)
2798       CommitValueTo(I->second, I->first);
2799     for (SmallPtrSet<GlobalVariable*, 8>::const_iterator I =
2800            Eval.getInvariants().begin(), E = Eval.getInvariants().end();
2801          I != E; ++I)
2802       (*I)->setConstant(true);
2803   }
2804
2805   return EvalSuccess;
2806 }
2807
2808 /// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible.
2809 /// Return true if anything changed.
2810 bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) {
2811   std::vector<Function*> Ctors = ParseGlobalCtors(GCL);
2812   bool MadeChange = false;
2813   if (Ctors.empty()) return false;
2814
2815   // Loop over global ctors, optimizing them when we can.
2816   for (unsigned i = 0; i != Ctors.size(); ++i) {
2817     Function *F = Ctors[i];
2818     // Found a null terminator in the middle of the list, prune off the rest of
2819     // the list.
2820     if (!F) {
2821       if (i != Ctors.size()-1) {
2822         Ctors.resize(i+1);
2823         MadeChange = true;
2824       }
2825       break;
2826     }
2827     DEBUG(dbgs() << "Optimizing Global Constructor: " << *F << "\n");
2828
2829     // We cannot simplify external ctor functions.
2830     if (F->empty()) continue;
2831
2832     // If we can evaluate the ctor at compile time, do.
2833     if (EvaluateStaticConstructor(F, DL, TLI)) {
2834       Ctors.erase(Ctors.begin()+i);
2835       MadeChange = true;
2836       --i;
2837       ++NumCtorsEvaluated;
2838       continue;
2839     }
2840   }
2841
2842   if (!MadeChange) return false;
2843
2844   GCL = InstallGlobalCtors(GCL, Ctors);
2845   return true;
2846 }
2847
2848 static int compareNames(Constant *const *A, Constant *const *B) {
2849   return (*A)->getName().compare((*B)->getName());
2850 }
2851
2852 static void setUsedInitializer(GlobalVariable &V,
2853                                SmallPtrSet<GlobalValue *, 8> Init) {
2854   if (Init.empty()) {
2855     V.eraseFromParent();
2856     return;
2857   }
2858
2859   // Type of pointer to the array of pointers.
2860   PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
2861
2862   SmallVector<llvm::Constant *, 8> UsedArray;
2863   for (SmallPtrSet<GlobalValue *, 8>::iterator I = Init.begin(), E = Init.end();
2864        I != E; ++I) {
2865     Constant *Cast
2866       = ConstantExpr::getPointerBitCastOrAddrSpaceCast(*I, Int8PtrTy);
2867     UsedArray.push_back(Cast);
2868   }
2869   // Sort to get deterministic order.
2870   array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2871   ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
2872
2873   Module *M = V.getParent();
2874   V.removeFromParent();
2875   GlobalVariable *NV =
2876       new GlobalVariable(*M, ATy, false, llvm::GlobalValue::AppendingLinkage,
2877                          llvm::ConstantArray::get(ATy, UsedArray), "");
2878   NV->takeName(&V);
2879   NV->setSection("llvm.metadata");
2880   delete &V;
2881 }
2882
2883 namespace {
2884 /// \brief An easy to access representation of llvm.used and llvm.compiler.used.
2885 class LLVMUsed {
2886   SmallPtrSet<GlobalValue *, 8> Used;
2887   SmallPtrSet<GlobalValue *, 8> CompilerUsed;
2888   GlobalVariable *UsedV;
2889   GlobalVariable *CompilerUsedV;
2890
2891 public:
2892   LLVMUsed(Module &M) {
2893     UsedV = collectUsedGlobalVariables(M, Used, false);
2894     CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true);
2895   }
2896   typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator;
2897   iterator usedBegin() { return Used.begin(); }
2898   iterator usedEnd() { return Used.end(); }
2899   iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2900   iterator compilerUsedEnd() { return CompilerUsed.end(); }
2901   bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2902   bool compilerUsedCount(GlobalValue *GV) const {
2903     return CompilerUsed.count(GV);
2904   }
2905   bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2906   bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2907   bool usedInsert(GlobalValue *GV) { return Used.insert(GV); }
2908   bool compilerUsedInsert(GlobalValue *GV) { return CompilerUsed.insert(GV); }
2909
2910   void syncVariablesAndSets() {
2911     if (UsedV)
2912       setUsedInitializer(*UsedV, Used);
2913     if (CompilerUsedV)
2914       setUsedInitializer(*CompilerUsedV, CompilerUsed);
2915   }
2916 };
2917 }
2918
2919 static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2920   if (GA.use_empty()) // No use at all.
2921     return false;
2922
2923   assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
2924          "We should have removed the duplicated "
2925          "element from llvm.compiler.used");
2926   if (!GA.hasOneUse())
2927     // Strictly more than one use. So at least one is not in llvm.used and
2928     // llvm.compiler.used.
2929     return true;
2930
2931   // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2932   return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2933 }
2934
2935 static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
2936                                                const LLVMUsed &U) {
2937   unsigned N = 2;
2938   assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
2939          "We should have removed the duplicated "
2940          "element from llvm.compiler.used");
2941   if (U.usedCount(&V) || U.compilerUsedCount(&V))
2942     ++N;
2943   return V.hasNUsesOrMore(N);
2944 }
2945
2946 static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
2947   if (!GA.hasLocalLinkage())
2948     return true;
2949
2950   return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2951 }
2952
2953 static bool hasUsesToReplace(GlobalAlias &GA, LLVMUsed &U, bool &RenameTarget) {
2954   RenameTarget = false;
2955   bool Ret = false;
2956   if (hasUseOtherThanLLVMUsed(GA, U))
2957     Ret = true;
2958
2959   // If the alias is externally visible, we may still be able to simplify it.
2960   if (!mayHaveOtherReferences(GA, U))
2961     return Ret;
2962
2963   // If the aliasee has internal linkage, give it the name and linkage
2964   // of the alias, and delete the alias.  This turns:
2965   //   define internal ... @f(...)
2966   //   @a = alias ... @f
2967   // into:
2968   //   define ... @a(...)
2969   Constant *Aliasee = GA.getAliasee();
2970   GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2971   if (!Target->hasLocalLinkage())
2972     return Ret;
2973
2974   // Do not perform the transform if multiple aliases potentially target the
2975   // aliasee. This check also ensures that it is safe to replace the section
2976   // and other attributes of the aliasee with those of the alias.
2977   if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
2978     return Ret;
2979
2980   RenameTarget = true;
2981   return true;
2982 }
2983
2984 bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
2985   bool Changed = false;
2986   LLVMUsed Used(M);
2987
2988   for (SmallPtrSet<GlobalValue *, 8>::iterator I = Used.usedBegin(),
2989                                                E = Used.usedEnd();
2990        I != E; ++I)
2991     Used.compilerUsedErase(*I);
2992
2993   for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
2994        I != E;) {
2995     Module::alias_iterator J = I++;
2996     // Aliases without names cannot be referenced outside this module.
2997     if (!J->hasName() && !J->isDeclaration())
2998       J->setLinkage(GlobalValue::InternalLinkage);
2999     // If the aliasee may change at link time, nothing can be done - bail out.
3000     if (J->mayBeOverridden())
3001       continue;
3002
3003     Constant *Aliasee = J->getAliasee();
3004     GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
3005     Target->removeDeadConstantUsers();
3006
3007     // Make all users of the alias use the aliasee instead.
3008     bool RenameTarget;
3009     if (!hasUsesToReplace(*J, Used, RenameTarget))
3010       continue;
3011
3012     J->replaceAllUsesWith(Aliasee);
3013     ++NumAliasesResolved;
3014     Changed = true;
3015
3016     if (RenameTarget) {
3017       // Give the aliasee the name, linkage and other attributes of the alias.
3018       Target->takeName(J);
3019       Target->setLinkage(J->getLinkage());
3020       Target->setVisibility(J->getVisibility());
3021       Target->setDLLStorageClass(J->getDLLStorageClass());
3022
3023       if (Used.usedErase(J))
3024         Used.usedInsert(Target);
3025
3026       if (Used.compilerUsedErase(J))
3027         Used.compilerUsedInsert(Target);
3028     } else if (mayHaveOtherReferences(*J, Used))
3029       continue;
3030
3031     // Delete the alias.
3032     M.getAliasList().erase(J);
3033     ++NumAliasesRemoved;
3034     Changed = true;
3035   }
3036
3037   Used.syncVariablesAndSets();
3038
3039   return Changed;
3040 }
3041
3042 static Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) {
3043   if (!TLI->has(LibFunc::cxa_atexit))
3044     return nullptr;
3045
3046   Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit));
3047
3048   if (!Fn)
3049     return nullptr;
3050
3051   FunctionType *FTy = Fn->getFunctionType();
3052
3053   // Checking that the function has the right return type, the right number of
3054   // parameters and that they all have pointer types should be enough.
3055   if (!FTy->getReturnType()->isIntegerTy() ||
3056       FTy->getNumParams() != 3 ||
3057       !FTy->getParamType(0)->isPointerTy() ||
3058       !FTy->getParamType(1)->isPointerTy() ||
3059       !FTy->getParamType(2)->isPointerTy())
3060     return nullptr;
3061
3062   return Fn;
3063 }
3064
3065 /// cxxDtorIsEmpty - Returns whether the given function is an empty C++
3066 /// destructor and can therefore be eliminated.
3067 /// Note that we assume that other optimization passes have already simplified
3068 /// the code so we only look for a function with a single basic block, where
3069 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
3070 /// other side-effect free instructions.
3071 static bool cxxDtorIsEmpty(const Function &Fn,
3072                            SmallPtrSet<const Function *, 8> &CalledFunctions) {
3073   // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
3074   // nounwind, but that doesn't seem worth doing.
3075   if (Fn.isDeclaration())
3076     return false;
3077
3078   if (++Fn.begin() != Fn.end())
3079     return false;
3080
3081   const BasicBlock &EntryBlock = Fn.getEntryBlock();
3082   for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
3083        I != E; ++I) {
3084     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
3085       // Ignore debug intrinsics.
3086       if (isa<DbgInfoIntrinsic>(CI))
3087         continue;
3088
3089       const Function *CalledFn = CI->getCalledFunction();
3090
3091       if (!CalledFn)
3092         return false;
3093
3094       SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
3095
3096       // Don't treat recursive functions as empty.
3097       if (!NewCalledFunctions.insert(CalledFn))
3098         return false;
3099
3100       if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
3101         return false;
3102     } else if (isa<ReturnInst>(*I))
3103       return true; // We're done.
3104     else if (I->mayHaveSideEffects())
3105       return false; // Destructor with side effects, bail.
3106   }
3107
3108   return false;
3109 }
3110
3111 bool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
3112   /// Itanium C++ ABI p3.3.5:
3113   ///
3114   ///   After constructing a global (or local static) object, that will require
3115   ///   destruction on exit, a termination function is registered as follows:
3116   ///
3117   ///   extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
3118   ///
3119   ///   This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
3120   ///   call f(p) when DSO d is unloaded, before all such termination calls
3121   ///   registered before this one. It returns zero if registration is
3122   ///   successful, nonzero on failure.
3123
3124   // This pass will look for calls to __cxa_atexit where the function is trivial
3125   // and remove them.
3126   bool Changed = false;
3127
3128   for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
3129        I != E;) {
3130     // We're only interested in calls. Theoretically, we could handle invoke
3131     // instructions as well, but neither llvm-gcc nor clang generate invokes
3132     // to __cxa_atexit.
3133     CallInst *CI = dyn_cast<CallInst>(*I++);
3134     if (!CI)
3135       continue;
3136
3137     Function *DtorFn =
3138       dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
3139     if (!DtorFn)
3140       continue;
3141
3142     SmallPtrSet<const Function *, 8> CalledFunctions;
3143     if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions))
3144       continue;
3145
3146     // Just remove the call.
3147     CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
3148     CI->eraseFromParent();
3149
3150     ++NumCXXDtorsRemoved;
3151
3152     Changed |= true;
3153   }
3154
3155   return Changed;
3156 }
3157
3158 bool GlobalOpt::runOnModule(Module &M) {
3159   bool Changed = false;
3160
3161   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
3162   DL = DLP ? &DLP->getDataLayout() : nullptr;
3163   TLI = &getAnalysis<TargetLibraryInfo>();
3164
3165   // Try to find the llvm.globalctors list.
3166   GlobalVariable *GlobalCtors = FindGlobalCtors(M);
3167
3168   bool LocalChange = true;
3169   while (LocalChange) {
3170     LocalChange = false;
3171
3172     // Delete functions that are trivially dead, ccc -> fastcc
3173     LocalChange |= OptimizeFunctions(M);
3174
3175     // Optimize global_ctors list.
3176     if (GlobalCtors)
3177       LocalChange |= OptimizeGlobalCtorsList(GlobalCtors);
3178
3179     // Optimize non-address-taken globals.
3180     LocalChange |= OptimizeGlobalVars(M);
3181
3182     // Resolve aliases, when possible.
3183     LocalChange |= OptimizeGlobalAliases(M);
3184
3185     // Try to remove trivial global destructors if they are not removed
3186     // already.
3187     Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
3188     if (CXAAtExitFn)
3189       LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
3190
3191     Changed |= LocalChange;
3192   }
3193
3194   // TODO: Move all global ctors functions to the end of the module for code
3195   // layout.
3196
3197   return Changed;
3198 }