Fix most of PR10367.

This patch changes the design of GlobalAlias so that it doesn't take a
ConstantExpr anymore. It now points directly to a GlobalObject, but its type is
independent of the aliasee type.

To avoid changing all alias related tests in this patches, I kept the common
syntax

@foo = alias i32* @bar

to mean the same as now. The cases that used to use cast now use the more
general syntax

@foo = alias i16, i32* @bar.

Note that GlobalAlias now behaves a bit more like GlobalVariable. We
know that its type is always a pointer, so we omit the '*'.

For the bitcode, a nice surprise is that we were writing both identical types
already, so the format change is minimal. Auto upgrade is handled by looking
through the casts and no new fields are needed for now. New bitcode will
simply have different types for Alias and Aliasee.

One last interesting point in the patch is that replaceAllUsesWith becomes
smart enough to avoid putting a ConstantExpr in the aliasee. This seems better
than checking and updating every caller.

A followup patch will delete getAliasedGlobal now that it is redundant. Another
patch will add support for an explicit offset.

llvm-svn: 209007

11 files changed, 158 insertions, 87 deletions

diff --git a/llvm/lib/AsmParser/LLParser.cpp b/llvm/lib/AsmParser/LLParser.cpp
index e5813f0d210..b457672d777 100644
--- a/llvm/lib/AsmParser/LLParser.cpp
+++ b/llvm/lib/AsmParser/LLParser.cpp
@@ -630,10 +630,11 @@ static bool isValidVisibilityForLinkage(unsigned V, unsigned L) {
 /// ParseAlias:
 ///   ::= GlobalVar '=' OptionalVisibility OptionalDLLStorageClass 'alias'
 ///                     OptionalLinkage Aliasee
+///   ::= GlobalVar '=' OptionalVisibility OptionalDLLStorageClass 'alias'
+///                     OptionalLinkage OptionalAddrSpace Type, Aliasee
+///
 /// Aliasee
 ///   ::= TypeAndValue
-///   ::= 'bitcast' '(' TypeAndValue 'to' Type ')'
-///   ::= 'getelementptr' 'inbounds'? '(' ... ')'
 ///
 /// Everything through DLL storage class has already been parsed.
 ///
@@ -655,28 +656,49 @@ bool LLParser::ParseAlias(const std::string &Name, LocTy NameLoc,
     return Error(LinkageLoc,
                  "symbol with local linkage must have default visibility");
 
-  Constant *Aliasee;
-  LocTy AliaseeLoc = Lex.getLoc();
-  if (Lex.getKind() != lltok::kw_bitcast &&
-      Lex.getKind() != lltok::kw_getelementptr) {
-    if (ParseGlobalTypeAndValue(Aliasee)) return true;
+  bool HasAddrSpace = Lex.getKind() == lltok::kw_addrspace;
+  unsigned AddrSpace;
+  LocTy AddrSpaceLoc = Lex.getLoc();
+  if (ParseOptionalAddrSpace(AddrSpace))
+    return true;
+
+  LocTy TyLoc = Lex.getLoc();
+  Type *Ty = nullptr;
+  if (ParseType(Ty))
+    return true;
+
+  bool DifferentType = EatIfPresent(lltok::comma);
+  if (HasAddrSpace && !DifferentType)
+    return Error(AddrSpaceLoc, "A type is required if addrspace is given");
+
+  Type *AliaseeType = nullptr;
+  if (DifferentType) {
+    if (ParseType(AliaseeType))
+      return true;
   } else {
-    // The bitcast dest type is not present, it is implied by the dest type.
-    ValID ID;
-    if (ParseValID(ID)) return true;
-    if (ID.Kind != ValID::t_Constant)
-      return Error(AliaseeLoc, "invalid aliasee");
-    Aliasee = ID.ConstantVal;
+    AliaseeType = Ty;
+    auto *PTy = dyn_cast<PointerType>(Ty);
+    if (!PTy)
+      return Error(TyLoc, "An alias must have pointer type");
+    Ty = PTy->getElementType();
+    AddrSpace = PTy->getAddressSpace();
   }
 
-  if (!Aliasee->getType()->isPointerTy())
-    return Error(AliaseeLoc, "alias must have pointer type");
+  LocTy AliaseeLoc = Lex.getLoc();
+  Constant *C;
+  if (ParseGlobalValue(AliaseeType, C))
+    return true;
+
+  auto *Aliasee = dyn_cast<GlobalObject>(C);
+  if (!Aliasee)
+    return Error(AliaseeLoc, "Alias must point to function or variable");
+
+  assert(Aliasee->getType()->isPointerTy());
 
   // Okay, create the alias but do not insert it into the module yet.
-  PointerType *PTy = cast<PointerType>(Aliasee->getType());
   std::unique_ptr<GlobalAlias> GA(
-      new GlobalAlias(PTy->getElementType(), (GlobalValue::LinkageTypes)Linkage,
-                      Name, Aliasee, nullptr, PTy->getAddressSpace()));
+      new GlobalAlias(Ty, (GlobalValue::LinkageTypes)Linkage, Name, Aliasee,
+                      /*Parent*/ nullptr, AddrSpace));
   GA->setVisibility((GlobalValue::VisibilityTypes)Visibility);
   GA->setDLLStorageClass((GlobalValue::DLLStorageClassTypes)DLLStorageClass);
 
@@ -698,6 +720,11 @@ bool LLParser::ParseAlias(const std::string &Name, LocTy NameLoc,
 
     // If they agree, just RAUW the old value with the alias and remove the
     // forward ref info.
+    for (auto *User : Val->users()) {
+      if (auto *GA = dyn_cast<GlobalAlias>(User))
+        return Error(NameLoc, "Alias is pointed by alias " + GA->getName());
+    }
+
     Val->replaceAllUsesWith(GA.get());
     Val->eraseFromParent();
     ForwardRefVals.erase(I);
diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
index ea33578502b..14546c0fe4c 100644
--- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -1092,6 +1092,28 @@ uint64_t BitcodeReader::decodeSignRotatedValue(uint64_t V) {
   return 1ULL << 63;
 }
 
+// FIXME: Delete this in LLVM 4.0 and just assert that the aliasee is a
+// GlobalObject.
+static GlobalObject &
+getGlobalObjectInExpr(const DenseMap<GlobalAlias *, Constant *> &Map,
+                      Constant &C) {
+  auto *GO = dyn_cast<GlobalObject>(&C);
+  if (GO)
+    return *GO;
+
+  auto *GA = dyn_cast<GlobalAlias>(&C);
+  if (GA)
+    return getGlobalObjectInExpr(Map, *Map.find(GA)->second);
+
+  auto &CE = cast<ConstantExpr>(C);
+  assert(CE.getOpcode() == Instruction::BitCast ||
+         CE.getOpcode() == Instruction::GetElementPtr ||
+         CE.getOpcode() == Instruction::AddrSpaceCast);
+  if (CE.getOpcode() == Instruction::GetElementPtr)
+    assert(cast<GEPOperator>(CE).hasAllZeroIndices());
+  return getGlobalObjectInExpr(Map, *CE.getOperand(0));
+}
+
 /// ResolveGlobalAndAliasInits - Resolve all of the initializers for global
 /// values and aliases that we can.
 error_code BitcodeReader::ResolveGlobalAndAliasInits() {
@@ -1117,19 +1139,30 @@ error_code BitcodeReader::ResolveGlobalAndAliasInits() {
     GlobalInitWorklist.pop_back();
   }
 
+  // FIXME: Delete this in LLVM 4.0
+  // Older versions of llvm could write an alias pointing to another. We cannot
+  // construct those aliases, so we first collect an alias to aliasee expression
+  // and then compute the actual aliasee.
+  DenseMap<GlobalAlias *, Constant *> AliasInit;
+
   while (!AliasInitWorklist.empty()) {
     unsigned ValID = AliasInitWorklist.back().second;
     if (ValID >= ValueList.size()) {
       AliasInits.push_back(AliasInitWorklist.back());
     } else {
       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-        AliasInitWorklist.back().first->setAliasee(C);
+        AliasInit.insert(std::make_pair(AliasInitWorklist.back().first, C));
       else
         return Error(ExpectedConstant);
     }
     AliasInitWorklist.pop_back();
   }
 
+  for (auto &Pair : AliasInit) {
+    auto &GO = getGlobalObjectInExpr(AliasInit, *Pair.second);
+    Pair.first->setAliasee(&GO);
+  }
+
   while (!FunctionPrefixWorklist.empty()) {
     unsigned ValID = FunctionPrefixWorklist.back().second;
     if (ValID >= ValueList.size()) {
diff --git a/llvm/lib/IR/AsmWriter.cpp b/llvm/lib/IR/AsmWriter.cpp
index 3cbb1d10497..0fef0d0a188 100644
--- a/llvm/lib/IR/AsmWriter.cpp
+++ b/llvm/lib/IR/AsmWriter.cpp
@@ -1493,10 +1493,16 @@ void AssemblyWriter::printAlias(const GlobalAlias *GA) {
 
   PrintLinkage(GA->getLinkage(), Out);
 
+  PointerType *Ty = GA->getType();
   const Constant *Aliasee = GA->getAliasee();
+  if (!Aliasee || Ty != Aliasee->getType()) {
+    if (unsigned AddressSpace = Ty->getAddressSpace())
+      Out << "addrspace(" << AddressSpace << ") ";
+    TypePrinter.print(Ty->getElementType(), Out);
+    Out << ", ";
+  }
 
   if (!Aliasee) {
-    TypePrinter.print(GA->getType(), Out);
     Out << " <<NULL ALIASEE>>";
   } else {
     writeOperand(Aliasee, !isa<ConstantExpr>(Aliasee));
diff --git a/llvm/lib/IR/Core.cpp b/llvm/lib/IR/Core.cpp
index 40c1c70257e..100c9def185 100644
--- a/llvm/lib/IR/Core.cpp
+++ b/llvm/lib/IR/Core.cpp
@@ -1491,7 +1491,7 @@ LLVMValueRef LLVMAddAlias(LLVMModuleRef M, LLVMTypeRef Ty, LLVMValueRef Aliasee,
   auto *PTy = cast<PointerType>(unwrap(Ty));
   return wrap(new GlobalAlias(
       PTy->getElementType(), GlobalValue::ExternalLinkage, Name,
-      unwrap<Constant>(Aliasee), unwrap(M), PTy->getAddressSpace()));
+      unwrap<GlobalObject>(Aliasee), unwrap(M), PTy->getAddressSpace()));
 }
 
 /*--.. Operations on functions .............................................--*/
diff --git a/llvm/lib/IR/Globals.cpp b/llvm/lib/IR/Globals.cpp
index 8e7478496f0..d4fcf58e98b 100644
--- a/llvm/lib/IR/Globals.cpp
+++ b/llvm/lib/IR/Globals.cpp
@@ -214,15 +214,11 @@ void GlobalVariable::copyAttributesFrom(const GlobalValue *Src) {
 //===----------------------------------------------------------------------===//
 
 GlobalAlias::GlobalAlias(Type *Ty, LinkageTypes Link, const Twine &Name,
-                         Constant *Aliasee, Module *ParentModule,
+                         GlobalObject *Aliasee, Module *ParentModule,
                          unsigned AddressSpace)
     : GlobalValue(PointerType::get(Ty, AddressSpace), Value::GlobalAliasVal,
                   &Op<0>(), 1, Link, Name) {
   LeakDetector::addGarbageObject(this);
-
-  if (Aliasee)
-    assert(Aliasee->getType() == getType() &&
-           "Alias and aliasee types should match!");
   Op<0>() = Aliasee;
 
   if (ParentModule)
@@ -245,42 +241,4 @@ void GlobalAlias::eraseFromParent() {
   getParent()->getAliasList().erase(this);
 }
 
-void GlobalAlias::setAliasee(Constant *Aliasee) {
-  assert((!Aliasee || Aliasee->getType() == getType()) &&
-         "Alias and aliasee types should match!");
-
-  setOperand(0, Aliasee);
-}
-
-static GlobalValue *getAliaseeGV(GlobalAlias *GA) {
-  Constant *C = GA->getAliasee();
-  assert(C && "Must alias something");
-
-  if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
-    return GV;
-
-  ConstantExpr *CE = cast<ConstantExpr>(C);
-  assert((CE->getOpcode() == Instruction::BitCast ||
-          CE->getOpcode() == Instruction::AddrSpaceCast ||
-          CE->getOpcode() == Instruction::GetElementPtr) &&
-         "Unsupported aliasee");
-
-  return cast<GlobalValue>(CE->getOperand(0));
-}
-
-GlobalObject *GlobalAlias::getAliasedGlobal() {
-  SmallPtrSet<GlobalValue*, 3> Visited;
-
-  GlobalAlias *GA = this;
-
-  for (;;) {
-    GlobalValue *GV = getAliaseeGV(GA);
-    if (!Visited.insert(GV))
-      return nullptr;
-
-    // Iterate over aliasing chain.
-    GA = dyn_cast<GlobalAlias>(GV);
-    if (!GA)
-      return cast<GlobalObject>(GV);
-  }
-}
+void GlobalAlias::setAliasee(GlobalObject *Aliasee) { setOperand(0, Aliasee); }
diff --git a/llvm/lib/IR/Value.cpp b/llvm/lib/IR/Value.cpp
index 9a79e43359e..a3c02862007 100644
--- a/llvm/lib/IR/Value.cpp
+++ b/llvm/lib/IR/Value.cpp
@@ -301,6 +301,28 @@ void Value::takeName(Value *V) {
     ST->reinsertValue(this);
 }
 
+static GlobalObject &findReplacementForAliasUse(Value &C) {
+  if (auto *GO = dyn_cast<GlobalObject>(&C))
+    return *GO;
+  if (auto *GA = dyn_cast<GlobalAlias>(&C))
+    return *GA->getAliasee();
+  auto *CE = cast<ConstantExpr>(&C);
+  assert(CE->getOpcode() == Instruction::BitCast ||
+         CE->getOpcode() == Instruction::GetElementPtr ||
+         CE->getOpcode() == Instruction::AddrSpaceCast);
+  if (CE->getOpcode() == Instruction::GetElementPtr)
+    assert(cast<GEPOperator>(CE)->hasAllZeroIndices());
+  return findReplacementForAliasUse(*CE->getOperand(0));
+}
+
+static void replaceAliasUseWith(Use &U, Value *New) {
+  GlobalObject &Replacement = findReplacementForAliasUse(*New);
+  auto *Old = &cast<GlobalObject>(*U);
+  assert(Old != &Replacement &&
+         "replaceAliasUseWith cannot form an alias cycle");
+  U.set(&Replacement);
+}
+
 #ifndef NDEBUG
 static bool contains(SmallPtrSet<ConstantExpr *, 4> &Cache, ConstantExpr *Expr,
                      Constant *C) {
@@ -351,7 +373,11 @@ void Value::replaceAllUsesWith(Value *New) {
     Use &U = *UseList;
     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
     // constant because they are uniqued.
-    if (Constant *C = dyn_cast<Constant>(U.getUser())) {
+    if (auto *C = dyn_cast<Constant>(U.getUser())) {
+      if (isa<GlobalAlias>(C)) {
+        replaceAliasUseWith(U, New);
+        continue;
+      }
       if (!isa<GlobalValue>(C)) {
         C->replaceUsesOfWithOnConstant(this, New, &U);
         continue;
diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp
index ff9ca44f870..6ab5e58c4cc 100644
--- a/llvm/lib/IR/Verifier.cpp
+++ b/llvm/lib/IR/Verifier.cpp
@@ -473,8 +473,6 @@ void Verifier::visitGlobalAlias(const GlobalAlias &GA) {
           "Alias should have external or external weak linkage!", &GA);
   Assert1(GA.getAliasee(),
           "Aliasee cannot be NULL!", &GA);
-  Assert1(GA.getType() == GA.getAliasee()->getType(),
-          "Alias and aliasee types should match!", &GA);
   Assert1(!GA.hasUnnamedAddr(), "Alias cannot have unnamed_addr!", &GA);
 
   const Constant *Aliasee = GA.getAliasee();
@@ -506,10 +504,6 @@ void Verifier::visitGlobalAlias(const GlobalAlias &GA) {
             &GA);
   }
 
-  const GlobalValue *AG = GA.getAliasedGlobal();
-  Assert1(AG, "Aliasing chain should end with function or global variable",
-          &GA);
-
   visitGlobalValue(GA);
 }
 
diff --git a/llvm/lib/Linker/LinkModules.cpp b/llvm/lib/Linker/LinkModules.cpp
index 0507c5acc9c..cf49d3fd556 100644
--- a/llvm/lib/Linker/LinkModules.cpp
+++ b/llvm/lib/Linker/LinkModules.cpp
@@ -389,6 +389,8 @@ namespace {
     /// actually need, but this allows us to reuse the ValueMapper code.
     ValueToValueMapTy ValueMap;
 
+    std::vector<std::pair<GlobalValue *, GlobalAlias *>> ReplaceWithAlias;
+
     struct AppendingVarInfo {
       GlobalVariable *NewGV;  // New aggregate global in dest module.
       Constant *DstInit;      // Old initializer from dest module.
@@ -920,18 +922,15 @@ bool ModuleLinker::linkAliasProto(GlobalAlias *SGA) {
   // If there is no linkage to be performed or we're linking from the source,
   // bring over SGA.
   auto *PTy = cast<PointerType>(TypeMap.get(SGA->getType()));
-  GlobalAlias *NewDA =
+  auto *NewDA =
       new GlobalAlias(PTy->getElementType(), SGA->getLinkage(), SGA->getName(),
                       /*aliasee*/ nullptr, DstM, PTy->getAddressSpace());
   copyGVAttributes(NewDA, SGA);
   if (NewVisibility)
     NewDA->setVisibility(*NewVisibility);
 
-  if (DGV) {
-    // Any uses of DGV need to change to NewDA, with cast.
-    DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDA, DGV->getType()));
-    DGV->eraseFromParent();
-  }
+  if (DGV)
+    ReplaceWithAlias.push_back(std::make_pair(DGV, NewDA));
 
   ValueMap[SGA] = NewDA;
   return false;
@@ -1017,6 +1016,19 @@ void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
 
 }
 
+static GlobalObject &getGlobalObjectInExpr(Constant &C) {
+  auto *GO = dyn_cast<GlobalObject>(&C);
+  if (GO)
+    return *GO;
+  auto *GA = dyn_cast<GlobalAlias>(&C);
+  if (GA)
+    return *GA->getAliasee();
+  auto &CE = cast<ConstantExpr>(C);
+  assert(CE.getOpcode() == Instruction::BitCast ||
+         CE.getOpcode() == Instruction::AddrSpaceCast);
+  return getGlobalObjectInExpr(*CE.getOperand(0));
+}
+
 /// linkAliasBodies - Insert all of the aliases in Src into the Dest module.
 void ModuleLinker::linkAliasBodies() {
   for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end();
@@ -1025,10 +1037,27 @@ void ModuleLinker::linkAliasBodies() {
       continue;
     if (Constant *Aliasee = I->getAliasee()) {
       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
-      DA->setAliasee(MapValue(Aliasee, ValueMap, RF_None,
-                              &TypeMap, &ValMaterializer));
+      Constant *Val =
+          MapValue(Aliasee, ValueMap, RF_None, &TypeMap, &ValMaterializer);
+      DA->setAliasee(&getGlobalObjectInExpr(*Val));
     }
   }
+
+  // Any uses of DGV need to change to NewDA, with cast.
+  for (auto &Pair : ReplaceWithAlias) {
+    GlobalValue *DGV = Pair.first;
+    GlobalAlias *NewDA = Pair.second;
+
+    for (auto *User : DGV->users()) {
+      if (auto *GA = dyn_cast<GlobalAlias>(User)) {
+        if (GA == NewDA)
+          report_fatal_error("Linking these modules creates an alias cycle.");
+      }
+    }
+
+    DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDA, DGV->getType()));
+    DGV->eraseFromParent();
+  }
 }
 
 /// linkNamedMDNodes - Insert all of the named MDNodes in Src into the Dest
diff --git a/llvm/lib/Transforms/IPO/GlobalOpt.cpp b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
index a8471bacb49..ae80c437643 100644
--- a/llvm/lib/Transforms/IPO/GlobalOpt.cpp
+++ b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
@@ -2861,7 +2861,7 @@ bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
     if (!hasUsesToReplace(*J, Used, RenameTarget))
       continue;
 
-    J->replaceAllUsesWith(Aliasee);
+    J->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J->getType()));
     ++NumAliasesResolved;
     Changed = true;
 
diff --git a/llvm/lib/Transforms/IPO/MergeFunctions.cpp b/llvm/lib/Transforms/IPO/MergeFunctions.cpp
index a8106e0c32f..83d9a6f7497 100644
--- a/llvm/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/llvm/lib/Transforms/IPO/MergeFunctions.cpp
@@ -1327,11 +1327,9 @@ void MergeFunctions::writeThunk(Function *F, Function *G) {
 
 // Replace G with an alias to F and delete G.
 void MergeFunctions::writeAlias(Function *F, Function *G) {
-  Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
   PointerType *PTy = G->getType();
-  GlobalAlias *GA =
-      new GlobalAlias(PTy->getElementType(), G->getLinkage(), "", BitcastF,
-                      G->getParent(), PTy->getAddressSpace());
+  auto *GA = new GlobalAlias(PTy->getElementType(), G->getLinkage(), "", F,
+                             G->getParent(), PTy->getAddressSpace());
   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
   GA->takeName(G);
   GA->setVisibility(G->getVisibility());
diff --git a/llvm/lib/Transforms/Utils/CloneModule.cpp b/llvm/lib/Transforms/Utils/CloneModule.cpp
index 1a3641452d9..d4c4c1907aa 100644
--- a/llvm/lib/Transforms/Utils/CloneModule.cpp
+++ b/llvm/lib/Transforms/Utils/CloneModule.cpp
@@ -107,8 +107,8 @@ Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) {
   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
        I != E; ++I) {
     GlobalAlias *GA = cast<GlobalAlias>(VMap[I]);
-    if (const Constant *C = I->getAliasee())
-      GA->setAliasee(MapValue(C, VMap));
+    if (const GlobalObject *C = I->getAliasee())
+      GA->setAliasee(cast<GlobalObject>(MapValue(C, VMap)));
   }
 
   // And named metadata....