Use the space freed up by sparc and zaurus to import LLVM.

ok hackroom@

7 files changed, 999 insertions, 0 deletions

diff --git a/gnu/llvm/unittests/Transforms/Utils/ASanStackFrameLayoutTest.cpp b/gnu/llvm/unittests/Transforms/Utils/ASanStackFrameLayoutTest.cpp
new file mode 100644
index 00000000000..0d3a239da34
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/ASanStackFrameLayoutTest.cpp
@@ -0,0 +1,102 @@
+//===- ASanStackFrameLayoutTest.cpp - Tests for ComputeASanStackFrameLayout===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/Transforms/Utils/ASanStackFrameLayout.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "gtest/gtest.h"
+#include <sstream>
+
+using namespace llvm;
+
+static std::string
+ShadowBytesToString(ArrayRef<uint8_t> ShadowBytes) {
+  std::ostringstream os;
+  for (size_t i = 0, n = ShadowBytes.size(); i < n; i++) {
+    switch (ShadowBytes[i]) {
+      case kAsanStackLeftRedzoneMagic:    os << "L"; break;
+      case kAsanStackRightRedzoneMagic:   os << "R"; break;
+      case kAsanStackMidRedzoneMagic:     os << "M"; break;
+      default:                            os << (unsigned)ShadowBytes[i];
+    }
+  }
+  return os.str();
+}
+
+static void TestLayout(SmallVector<ASanStackVariableDescription, 10> Vars,
+                       size_t Granularity, size_t MinHeaderSize,
+                       const std::string &ExpectedDescr,
+                       const std::string &ExpectedShadow) {
+  ASanStackFrameLayout L;
+  ComputeASanStackFrameLayout(Vars, Granularity, MinHeaderSize, &L);
+  EXPECT_EQ(ExpectedDescr, L.DescriptionString);
+  EXPECT_EQ(ExpectedShadow, ShadowBytesToString(L.ShadowBytes));
+}
+
+TEST(ASanStackFrameLayout, Test) {
+#define VEC1(a) SmallVector<ASanStackVariableDescription, 10>(1, a)
+#define VEC(a)                                                                 \
+  SmallVector<ASanStackVariableDescription, 10>(a, a + sizeof(a) / sizeof(a[0]))
+
+#define VAR(name, size, alignment)                                             \
+  ASanStackVariableDescription name##size##_##alignment = {                    \
+    #name #size "_" #alignment,                                                \
+    size,                                                                      \
+    alignment,                                                                 \
+    0,                                                                         \
+    0                                                                          \
+  }
+
+  VAR(a, 1, 1);
+  VAR(p, 1, 32);
+  VAR(p, 1, 256);
+  VAR(a, 2, 1);
+  VAR(a, 3, 1);
+  VAR(a, 4, 1);
+  VAR(a, 7, 1);
+  VAR(a, 8, 1);
+  VAR(a, 9, 1);
+  VAR(a, 16, 1);
+  VAR(a, 41, 1);
+  VAR(a, 105, 1);
+
+  TestLayout(VEC1(a1_1), 8, 16, "1 16 1 4 a1_1", "LL1R");
+  TestLayout(VEC1(a1_1), 64, 64, "1 64 1 4 a1_1", "L1");
+  TestLayout(VEC1(p1_32), 8, 32, "1 32 1 5 p1_32", "LLLL1RRR");
+  TestLayout(VEC1(p1_32), 8, 64, "1 64 1 5 p1_32", "LLLLLLLL1RRRRRRR");
+
+  TestLayout(VEC1(a1_1), 8, 32, "1 32 1 4 a1_1", "LLLL1RRR");
+  TestLayout(VEC1(a2_1), 8, 32, "1 32 2 4 a2_1", "LLLL2RRR");
+  TestLayout(VEC1(a3_1), 8, 32, "1 32 3 4 a3_1", "LLLL3RRR");
+  TestLayout(VEC1(a4_1), 8, 32, "1 32 4 4 a4_1", "LLLL4RRR");
+  TestLayout(VEC1(a7_1), 8, 32, "1 32 7 4 a7_1", "LLLL7RRR");
+  TestLayout(VEC1(a8_1), 8, 32, "1 32 8 4 a8_1", "LLLL0RRR");
+  TestLayout(VEC1(a9_1), 8, 32, "1 32 9 4 a9_1", "LLLL01RR");
+  TestLayout(VEC1(a16_1), 8, 32, "1 32 16 5 a16_1", "LLLL00RR");
+  TestLayout(VEC1(p1_256), 8, 32, "1 256 1 6 p1_256",
+             "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL1RRR");
+  TestLayout(VEC1(a41_1), 8, 32, "1 32 41 5 a41_1", "LLLL000001RRRRRR");
+  TestLayout(VEC1(a105_1), 8, 32, "1 32 105 6 a105_1",
+             "LLLL00000000000001RRRRRR");
+
+  {
+    ASanStackVariableDescription t[] = {a1_1, p1_256};
+    TestLayout(VEC(t), 8, 32,
+               "2 256 1 6 p1_256 272 1 4 a1_1",
+               "LLLLLLLL" "LLLLLLLL" "LLLLLLLL" "LLLLLLLL" "1M1R");
+  }
+
+  {
+    ASanStackVariableDescription t[] = {a1_1, a16_1, a41_1};
+    TestLayout(VEC(t), 8, 32,
+               "3 32 1 4 a1_1 48 16 5 a16_1 80 41 5 a41_1",
+               "LLLL" "1M00" "MM00" "0001" "RRRR");
+  }
+#undef VEC1
+#undef VEC
+#undef VAR
+}
diff --git a/gnu/llvm/unittests/Transforms/Utils/CMakeLists.txt b/gnu/llvm/unittests/Transforms/Utils/CMakeLists.txt
new file mode 100644
index 00000000000..517ff99ea46
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/CMakeLists.txt
@@ -0,0 +1,13 @@
+set(LLVM_LINK_COMPONENTS
+  Core
+  Support
+  TransformUtils
+  )
+
+add_llvm_unittest(UtilsTests
+  ASanStackFrameLayoutTest.cpp
+  Cloning.cpp
+  IntegerDivision.cpp
+  Local.cpp
+  ValueMapperTest.cpp
+  )
diff --git a/gnu/llvm/unittests/Transforms/Utils/Cloning.cpp b/gnu/llvm/unittests/Transforms/Utils/Cloning.cpp
new file mode 100644
index 00000000000..25e322ee5a8
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/Cloning.cpp
@@ -0,0 +1,450 @@
+//===- Cloning.cpp - Unit tests for the Cloner ----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/IR/Argument.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+class CloneInstruction : public ::testing::Test {
+protected:
+  void SetUp() override { V = nullptr; }
+
+  template <typename T>
+  T *clone(T *V1) {
+    Value *V2 = V1->clone();
+    Orig.insert(V1);
+    Clones.insert(V2);
+    return cast<T>(V2);
+  }
+
+  void eraseClones() {
+    DeleteContainerPointers(Clones);
+  }
+
+  void TearDown() override {
+    eraseClones();
+    DeleteContainerPointers(Orig);
+    delete V;
+  }
+
+  SmallPtrSet<Value *, 4> Orig;   // Erase on exit
+  SmallPtrSet<Value *, 4> Clones; // Erase in eraseClones
+
+  LLVMContext context;
+  Value *V;
+};
+
+TEST_F(CloneInstruction, OverflowBits) {
+  V = new Argument(Type::getInt32Ty(context));
+
+  BinaryOperator *Add = BinaryOperator::Create(Instruction::Add, V, V);
+  BinaryOperator *Sub = BinaryOperator::Create(Instruction::Sub, V, V);
+  BinaryOperator *Mul = BinaryOperator::Create(Instruction::Mul, V, V);
+
+  BinaryOperator *AddClone = this->clone(Add);
+  BinaryOperator *SubClone = this->clone(Sub);
+  BinaryOperator *MulClone = this->clone(Mul);
+
+  EXPECT_FALSE(AddClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(AddClone->hasNoSignedWrap());
+  EXPECT_FALSE(SubClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(SubClone->hasNoSignedWrap());
+  EXPECT_FALSE(MulClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(MulClone->hasNoSignedWrap());
+
+  eraseClones();
+
+  Add->setHasNoUnsignedWrap();
+  Sub->setHasNoUnsignedWrap();
+  Mul->setHasNoUnsignedWrap();
+
+  AddClone = this->clone(Add);
+  SubClone = this->clone(Sub);
+  MulClone = this->clone(Mul);
+
+  EXPECT_TRUE(AddClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(AddClone->hasNoSignedWrap());
+  EXPECT_TRUE(SubClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(SubClone->hasNoSignedWrap());
+  EXPECT_TRUE(MulClone->hasNoUnsignedWrap());
+  EXPECT_FALSE(MulClone->hasNoSignedWrap());
+
+  eraseClones();
+
+  Add->setHasNoSignedWrap();
+  Sub->setHasNoSignedWrap();
+  Mul->setHasNoSignedWrap();
+
+  AddClone = this->clone(Add);
+  SubClone = this->clone(Sub);
+  MulClone = this->clone(Mul);
+
+  EXPECT_TRUE(AddClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(AddClone->hasNoSignedWrap());
+  EXPECT_TRUE(SubClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(SubClone->hasNoSignedWrap());
+  EXPECT_TRUE(MulClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(MulClone->hasNoSignedWrap());
+
+  eraseClones();
+
+  Add->setHasNoUnsignedWrap(false);
+  Sub->setHasNoUnsignedWrap(false);
+  Mul->setHasNoUnsignedWrap(false);
+
+  AddClone = this->clone(Add);
+  SubClone = this->clone(Sub);
+  MulClone = this->clone(Mul);
+
+  EXPECT_FALSE(AddClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(AddClone->hasNoSignedWrap());
+  EXPECT_FALSE(SubClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(SubClone->hasNoSignedWrap());
+  EXPECT_FALSE(MulClone->hasNoUnsignedWrap());
+  EXPECT_TRUE(MulClone->hasNoSignedWrap());
+}
+
+TEST_F(CloneInstruction, Inbounds) {
+  V = new Argument(Type::getInt32PtrTy(context));
+
+  Constant *Z = Constant::getNullValue(Type::getInt32Ty(context));
+  std::vector<Value *> ops;
+  ops.push_back(Z);
+  GetElementPtrInst *GEP =
+      GetElementPtrInst::Create(Type::getInt32Ty(context), V, ops);
+  EXPECT_FALSE(this->clone(GEP)->isInBounds());
+
+  GEP->setIsInBounds();
+  EXPECT_TRUE(this->clone(GEP)->isInBounds());
+}
+
+TEST_F(CloneInstruction, Exact) {
+  V = new Argument(Type::getInt32Ty(context));
+
+  BinaryOperator *SDiv = BinaryOperator::Create(Instruction::SDiv, V, V);
+  EXPECT_FALSE(this->clone(SDiv)->isExact());
+
+  SDiv->setIsExact(true);
+  EXPECT_TRUE(this->clone(SDiv)->isExact());
+}
+
+TEST_F(CloneInstruction, Attributes) {
+  Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
+  FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
+
+  Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
+  BasicBlock *BB = BasicBlock::Create(context, "", F1);
+  IRBuilder<> Builder(BB);
+  Builder.CreateRetVoid();
+
+  Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
+
+  Attribute::AttrKind AK[] = { Attribute::NoCapture };
+  AttributeSet AS = AttributeSet::get(context, 0, AK);
+  Argument *A = &*F1->arg_begin();
+  A->addAttr(AS);
+
+  SmallVector<ReturnInst*, 4> Returns;
+  ValueToValueMapTy VMap;
+  VMap[A] = UndefValue::get(A->getType());
+
+  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr());
+
+  delete F1;
+  delete F2;
+}
+
+TEST_F(CloneInstruction, CallingConvention) {
+  Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
+  FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
+
+  Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
+  F1->setCallingConv(CallingConv::Cold);
+  BasicBlock *BB = BasicBlock::Create(context, "", F1);
+  IRBuilder<> Builder(BB);
+  Builder.CreateRetVoid();
+
+  Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
+
+  SmallVector<ReturnInst*, 4> Returns;
+  ValueToValueMapTy VMap;
+  VMap[&*F1->arg_begin()] = &*F2->arg_begin();
+
+  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  EXPECT_EQ(CallingConv::Cold, F2->getCallingConv());
+
+  delete F1;
+  delete F2;
+}
+
+class CloneFunc : public ::testing::Test {
+protected:
+  void SetUp() override {
+    SetupModule();
+    CreateOldFunc();
+    CreateNewFunc();
+    SetupFinder();
+  }
+
+  void TearDown() override { delete Finder; }
+
+  void SetupModule() {
+    M = new Module("", C);
+  }
+
+  void CreateOldFunc() {
+    FunctionType* FuncType = FunctionType::get(Type::getVoidTy(C), false);
+    OldFunc = Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", M);
+    CreateOldFunctionBodyAndDI();
+  }
+
+  void CreateOldFunctionBodyAndDI() {
+    DIBuilder DBuilder(*M);
+    IRBuilder<> IBuilder(C);
+
+    // Function DI
+    auto *File = DBuilder.createFile("filename.c", "/file/dir/");
+    DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None);
+    DISubroutineType *FuncType =
+        DBuilder.createSubroutineType(ParamTypes);
+    auto *CU =
+        DBuilder.createCompileUnit(dwarf::DW_LANG_C99, "filename.c",
+                                   "/file/dir", "CloneFunc", false, "", 0);
+
+    auto *Subprogram = DBuilder.createFunction(
+        CU, "f", "f", File, 4, FuncType, true, true, 3, 0, false);
+    OldFunc->setSubprogram(Subprogram);
+
+    // Function body
+    BasicBlock* Entry = BasicBlock::Create(C, "", OldFunc);
+    IBuilder.SetInsertPoint(Entry);
+    DebugLoc Loc = DebugLoc::get(3, 2, Subprogram);
+    IBuilder.SetCurrentDebugLocation(Loc);
+    AllocaInst* Alloca = IBuilder.CreateAlloca(IntegerType::getInt32Ty(C));
+    IBuilder.SetCurrentDebugLocation(DebugLoc::get(4, 2, Subprogram));
+    Value* AllocaContent = IBuilder.getInt32(1);
+    Instruction* Store = IBuilder.CreateStore(AllocaContent, Alloca);
+    IBuilder.SetCurrentDebugLocation(DebugLoc::get(5, 2, Subprogram));
+    Instruction* Terminator = IBuilder.CreateRetVoid();
+
+    // Create a local variable around the alloca
+    auto *IntType =
+        DBuilder.createBasicType("int", 32, 0, dwarf::DW_ATE_signed);
+    auto *E = DBuilder.createExpression();
+    auto *Variable =
+        DBuilder.createAutoVariable(Subprogram, "x", File, 5, IntType, true);
+    auto *DL = DILocation::get(Subprogram->getContext(), 5, 0, Subprogram);
+    DBuilder.insertDeclare(Alloca, Variable, E, DL, Store);
+    DBuilder.insertDbgValueIntrinsic(AllocaContent, 0, Variable, E, DL,
+                                     Terminator);
+    // Finalize the debug info
+    DBuilder.finalize();
+
+
+    // Create another, empty, compile unit
+    DIBuilder DBuilder2(*M);
+    DBuilder2.createCompileUnit(dwarf::DW_LANG_C99,
+        "extra.c", "/file/dir", "CloneFunc", false, "", 0);
+    DBuilder2.finalize();
+  }
+
+  void CreateNewFunc() {
+    ValueToValueMapTy VMap;
+    NewFunc = CloneFunction(OldFunc, VMap, true, nullptr);
+    M->getFunctionList().push_back(NewFunc);
+  }
+
+  void SetupFinder() {
+    Finder = new DebugInfoFinder();
+    Finder->processModule(*M);
+  }
+
+  LLVMContext C;
+  Function* OldFunc;
+  Function* NewFunc;
+  Module* M;
+  DebugInfoFinder* Finder;
+};
+
+// Test that a new, distinct function was created.
+TEST_F(CloneFunc, NewFunctionCreated) {
+  EXPECT_NE(OldFunc, NewFunc);
+}
+
+// Test that a new subprogram entry was added and is pointing to the new
+// function, while the original subprogram still points to the old one.
+TEST_F(CloneFunc, Subprogram) {
+  EXPECT_FALSE(verifyModule(*M));
+
+  unsigned SubprogramCount = Finder->subprogram_count();
+  EXPECT_EQ(2U, SubprogramCount);
+
+  auto Iter = Finder->subprograms().begin();
+  auto *Sub1 = cast<DISubprogram>(*Iter);
+  Iter++;
+  auto *Sub2 = cast<DISubprogram>(*Iter);
+
+  EXPECT_TRUE(
+      (Sub1 == OldFunc->getSubprogram() && Sub2 == NewFunc->getSubprogram()) ||
+      (Sub1 == NewFunc->getSubprogram() && Sub2 == OldFunc->getSubprogram()));
+}
+
+// Test that the new subprogram entry was not added to the CU which doesn't
+// contain the old subprogram entry.
+TEST_F(CloneFunc, SubprogramInRightCU) {
+  EXPECT_FALSE(verifyModule(*M));
+
+  EXPECT_EQ(2U, Finder->compile_unit_count());
+
+  auto Iter = Finder->compile_units().begin();
+  auto *CU1 = cast<DICompileUnit>(*Iter);
+  Iter++;
+  auto *CU2 = cast<DICompileUnit>(*Iter);
+  EXPECT_TRUE(CU1->getSubprograms().size() == 0 ||
+              CU2->getSubprograms().size() == 0);
+}
+
+// Test that instructions in the old function still belong to it in the
+// metadata, while instruction in the new function belong to the new one.
+TEST_F(CloneFunc, InstructionOwnership) {
+  EXPECT_FALSE(verifyModule(*M));
+
+  inst_iterator OldIter = inst_begin(OldFunc);
+  inst_iterator OldEnd = inst_end(OldFunc);
+  inst_iterator NewIter = inst_begin(NewFunc);
+  inst_iterator NewEnd = inst_end(NewFunc);
+  while (OldIter != OldEnd && NewIter != NewEnd) {
+    Instruction& OldI = *OldIter;
+    Instruction& NewI = *NewIter;
+    EXPECT_NE(&OldI, &NewI);
+
+    EXPECT_EQ(OldI.hasMetadata(), NewI.hasMetadata());
+    if (OldI.hasMetadata()) {
+      const DebugLoc& OldDL = OldI.getDebugLoc();
+      const DebugLoc& NewDL = NewI.getDebugLoc();
+
+      // Verify that the debug location data is the same
+      EXPECT_EQ(OldDL.getLine(), NewDL.getLine());
+      EXPECT_EQ(OldDL.getCol(), NewDL.getCol());
+
+      // But that they belong to different functions
+      auto *OldSubprogram = cast<DISubprogram>(OldDL.getScope());
+      auto *NewSubprogram = cast<DISubprogram>(NewDL.getScope());
+      EXPECT_EQ(OldFunc->getSubprogram(), OldSubprogram);
+      EXPECT_EQ(NewFunc->getSubprogram(), NewSubprogram);
+    }
+
+    ++OldIter;
+    ++NewIter;
+  }
+  EXPECT_EQ(OldEnd, OldIter);
+  EXPECT_EQ(NewEnd, NewIter);
+}
+
+// Test that the arguments for debug intrinsics in the new function were
+// properly cloned
+TEST_F(CloneFunc, DebugIntrinsics) {
+  EXPECT_FALSE(verifyModule(*M));
+
+  inst_iterator OldIter = inst_begin(OldFunc);
+  inst_iterator OldEnd = inst_end(OldFunc);
+  inst_iterator NewIter = inst_begin(NewFunc);
+  inst_iterator NewEnd = inst_end(NewFunc);
+  while (OldIter != OldEnd && NewIter != NewEnd) {
+    Instruction& OldI = *OldIter;
+    Instruction& NewI = *NewIter;
+    if (DbgDeclareInst* OldIntrin = dyn_cast<DbgDeclareInst>(&OldI)) {
+      DbgDeclareInst* NewIntrin = dyn_cast<DbgDeclareInst>(&NewI);
+      EXPECT_TRUE(NewIntrin);
+
+      // Old address must belong to the old function
+      EXPECT_EQ(OldFunc, cast<AllocaInst>(OldIntrin->getAddress())->
+                         getParent()->getParent());
+      // New address must belong to the new function
+      EXPECT_EQ(NewFunc, cast<AllocaInst>(NewIntrin->getAddress())->
+                         getParent()->getParent());
+
+      // Old variable must belong to the old function
+      EXPECT_EQ(OldFunc->getSubprogram(),
+                cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
+      // New variable must belong to the New function
+      EXPECT_EQ(NewFunc->getSubprogram(),
+                cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
+    } else if (DbgValueInst* OldIntrin = dyn_cast<DbgValueInst>(&OldI)) {
+      DbgValueInst* NewIntrin = dyn_cast<DbgValueInst>(&NewI);
+      EXPECT_TRUE(NewIntrin);
+
+      // Old variable must belong to the old function
+      EXPECT_EQ(OldFunc->getSubprogram(),
+                cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
+      // New variable must belong to the New function
+      EXPECT_EQ(NewFunc->getSubprogram(),
+                cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
+    }
+
+    ++OldIter;
+    ++NewIter;
+  }
+}
+
+class CloneModule : public ::testing::Test {
+protected:
+  void SetUp() override {
+    SetupModule();
+    CreateOldModule();
+    CreateNewModule();
+  }
+
+  void SetupModule() { OldM = new Module("", C); }
+
+  void CreateOldModule() {
+    IRBuilder<> IBuilder(C);
+
+    auto *FuncType = FunctionType::get(Type::getVoidTy(C), false);
+    auto *PersFn = Function::Create(FuncType, GlobalValue::ExternalLinkage,
+                                    "persfn", OldM);
+    auto *F =
+        Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", OldM);
+    F->setPersonalityFn(PersFn);
+    auto *Entry = BasicBlock::Create(C, "", F);
+    IBuilder.SetInsertPoint(Entry);
+    IBuilder.CreateRetVoid();
+  }
+
+  void CreateNewModule() { NewM = llvm::CloneModule(OldM).release(); }
+
+  LLVMContext C;
+  Module *OldM;
+  Module *NewM;
+};
+
+TEST_F(CloneModule, Verify) {
+  EXPECT_FALSE(verifyModule(*NewM));
+}
+
+}
diff --git a/gnu/llvm/unittests/Transforms/Utils/IntegerDivision.cpp b/gnu/llvm/unittests/Transforms/Utils/IntegerDivision.cpp
new file mode 100644
index 00000000000..4cda2b4e589
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/IntegerDivision.cpp
@@ -0,0 +1,264 @@
+//===- IntegerDivision.cpp - Unit tests for the integer division code -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/IntegerDivision.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Module.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+
+TEST(IntegerDivision, SDiv) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test division", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Div = Builder.CreateSDiv(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv);
+
+  Value *Ret = Builder.CreateRet(Div);
+
+  expandDivision(cast<BinaryOperator>(Div));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
+
+  Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub);
+}
+
+TEST(IntegerDivision, UDiv) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test division", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Div = Builder.CreateUDiv(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv);
+
+  Value *Ret = Builder.CreateRet(Div);
+
+  expandDivision(cast<BinaryOperator>(Div));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
+
+  Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI);
+}
+
+TEST(IntegerDivision, SRem) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test remainder", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Rem = Builder.CreateSRem(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem);
+
+  Value *Ret = Builder.CreateRet(Rem);
+
+  expandRemainder(cast<BinaryOperator>(Rem));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
+
+  Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
+}
+
+TEST(IntegerDivision, URem) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test remainder", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Rem = Builder.CreateURem(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem);
+
+  Value *Ret = Builder.CreateRet(Rem);
+
+  expandRemainder(cast<BinaryOperator>(Rem));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
+
+  Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
+}
+
+
+TEST(IntegerDivision, SDiv64) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test division", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Div = Builder.CreateSDiv(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv);
+
+  Value *Ret = Builder.CreateRet(Div);
+
+  expandDivision(cast<BinaryOperator>(Div));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
+
+  Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub);
+}
+
+TEST(IntegerDivision, UDiv64) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test division", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Div = Builder.CreateUDiv(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv);
+
+  Value *Ret = Builder.CreateRet(Div);
+
+  expandDivision(cast<BinaryOperator>(Div));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
+
+  Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI);
+}
+
+TEST(IntegerDivision, SRem64) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test remainder", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Rem = Builder.CreateSRem(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem);
+
+  Value *Ret = Builder.CreateRet(Rem);
+
+  expandRemainder(cast<BinaryOperator>(Rem));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
+
+  Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
+}
+
+TEST(IntegerDivision, URem64) {
+  LLVMContext &C(getGlobalContext());
+  Module M("test remainder", C);
+  IRBuilder<> Builder(C);
+
+  SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
+  Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                                   ArgTys, false),
+                                 GlobalValue::ExternalLinkage, "F", &M);
+  assert(F->getArgumentList().size() == 2);
+
+  BasicBlock *BB = BasicBlock::Create(C, "", F);
+  Builder.SetInsertPoint(BB);
+
+  Function::arg_iterator AI = F->arg_begin();
+  Value *A = &*AI++;
+  Value *B = &*AI++;
+
+  Value *Rem = Builder.CreateURem(A, B);
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem);
+
+  Value *Ret = Builder.CreateRet(Rem);
+
+  expandRemainder(cast<BinaryOperator>(Rem));
+  EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
+
+  Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
+  EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
+}
+
+}
diff --git a/gnu/llvm/unittests/Transforms/Utils/Local.cpp b/gnu/llvm/unittests/Transforms/Utils/Local.cpp
new file mode 100644
index 00000000000..2ff56047555
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/Local.cpp
@@ -0,0 +1,97 @@
+//===- Local.cpp - Unit tests for Local -----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(Local, RecursivelyDeleteDeadPHINodes) {
+  LLVMContext &C(getGlobalContext());
+
+  IRBuilder<> builder(C);
+
+  // Make blocks
+  BasicBlock *bb0 = BasicBlock::Create(C);
+  BasicBlock *bb1 = BasicBlock::Create(C);
+
+  builder.SetInsertPoint(bb0);
+  PHINode    *phi = builder.CreatePHI(Type::getInt32Ty(C), 2);
+  BranchInst *br0 = builder.CreateCondBr(builder.getTrue(), bb0, bb1);
+
+  builder.SetInsertPoint(bb1);
+  BranchInst *br1 = builder.CreateBr(bb0);
+
+  phi->addIncoming(phi, bb0);
+  phi->addIncoming(phi, bb1);
+
+  // The PHI will be removed
+  EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
+
+  // Make sure the blocks only contain the branches
+  EXPECT_EQ(&bb0->front(), br0);
+  EXPECT_EQ(&bb1->front(), br1);
+
+  builder.SetInsertPoint(bb0);
+  phi = builder.CreatePHI(Type::getInt32Ty(C), 0);
+
+  EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
+
+  builder.SetInsertPoint(bb0);
+  phi = builder.CreatePHI(Type::getInt32Ty(C), 0);
+  builder.CreateAdd(phi, phi);
+
+  EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
+
+  bb0->dropAllReferences();
+  bb1->dropAllReferences();
+  delete bb0;
+  delete bb1;
+}
+
+TEST(Local, RemoveDuplicatePHINodes) {
+  LLVMContext &C(getGlobalContext());
+  IRBuilder<> B(C);
+
+  std::unique_ptr<Function> F(
+      Function::Create(FunctionType::get(B.getVoidTy(), false),
+                       GlobalValue::ExternalLinkage, "F"));
+  BasicBlock *Entry(BasicBlock::Create(C, "", F.get()));
+  BasicBlock *BB(BasicBlock::Create(C, "", F.get()));
+  BranchInst::Create(BB, Entry);
+
+  B.SetInsertPoint(BB);
+
+  AssertingVH<PHINode> P1 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P1->addIncoming(B.getInt32(42), Entry);
+
+  PHINode *P2 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P2->addIncoming(B.getInt32(42), Entry);
+
+  AssertingVH<PHINode> P3 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P3->addIncoming(B.getInt32(42), Entry);
+  P3->addIncoming(B.getInt32(23), BB);
+
+  PHINode *P4 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P4->addIncoming(B.getInt32(42), Entry);
+  P4->addIncoming(B.getInt32(23), BB);
+
+  P1->addIncoming(P3, BB);
+  P2->addIncoming(P4, BB);
+  BranchInst::Create(BB, BB);
+
+  // Verify that we can eliminate PHIs that become duplicates after chaning PHIs
+  // downstream.
+  EXPECT_TRUE(EliminateDuplicatePHINodes(BB));
+  EXPECT_EQ(3U, BB->size());
+}
diff --git a/gnu/llvm/unittests/Transforms/Utils/Makefile b/gnu/llvm/unittests/Transforms/Utils/Makefile
new file mode 100644
index 00000000000..e6c2a2c133a
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/Makefile
@@ -0,0 +1,15 @@
+##===- unittests/Transforms/Utils/Makefile -----------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../../..
+TESTNAME = Utils
+LINK_COMPONENTS := TransformUtils
+
+include $(LEVEL)/Makefile.config
+include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest
diff --git a/gnu/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp b/gnu/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp
new file mode 100644
index 00000000000..9dbe4dbc56d
--- /dev/null
+++ b/gnu/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp
@@ -0,0 +1,58 @@
+//===- ValueMapper.cpp - Unit tests for ValueMapper -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(ValueMapperTest, MapMetadataUnresolved) {
+  LLVMContext Context;
+  TempMDTuple T = MDTuple::getTemporary(Context, None);
+
+  ValueToValueMapTy VM;
+  EXPECT_EQ(T.get(), MapMetadata(T.get(), VM, RF_NoModuleLevelChanges));
+}
+
+TEST(ValueMapperTest, MapMetadataDistinct) {
+  LLVMContext Context;
+  auto *D = MDTuple::getDistinct(Context, None);
+
+  {
+    // The node should be cloned.
+    ValueToValueMapTy VM;
+    EXPECT_NE(D, MapMetadata(D, VM, RF_None));
+  }
+  {
+    // The node should be moved.
+    ValueToValueMapTy VM;
+    EXPECT_EQ(D, MapMetadata(D, VM, RF_MoveDistinctMDs));
+  }
+}
+
+TEST(ValueMapperTest, MapMetadataDistinctOperands) {
+  LLVMContext Context;
+  Metadata *Old = MDTuple::getDistinct(Context, None);
+  auto *D = MDTuple::getDistinct(Context, Old);
+  ASSERT_EQ(Old, D->getOperand(0));
+
+  Metadata *New = MDTuple::getDistinct(Context, None);
+  ValueToValueMapTy VM;
+  VM.MD()[Old].reset(New);
+
+  // Make sure operands are updated.
+  EXPECT_EQ(D, MapMetadata(D, VM, RF_MoveDistinctMDs));
+  EXPECT_EQ(New, D->getOperand(0));
+}
+
+}