Add a dominanance check interface that uses caching for instructions within same basic block.

Summary:
This problem stems from the fact that instructions are allocated using new
in LLVM, i.e. there is no relationship that can be derived by just looking
at the pointer value.

This interface dispatches to appropriate dominance check given 2 instructions,
i.e. in case the instructions are in the same basic block, ordered basicblock
(with instruction numbering and caching) are used. Otherwise, dominator tree
is used.

This is a preparation patch for https://reviews.llvm.org/D32720

Reviewers: dberlin, hfinkel, davide

Subscribers: davide, mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D33380

llvm-svn: 304764

2 files changed, 66 insertions, 0 deletions

diff --git a/llvm/unittests/Transforms/Utils/CMakeLists.txt b/llvm/unittests/Transforms/Utils/CMakeLists.txt
index 0fc19ef09fb..475c365dddc 100644
--- a/llvm/unittests/Transforms/Utils/CMakeLists.txt
+++ b/llvm/unittests/Transforms/Utils/CMakeLists.txt
@@ -11,5 +11,6 @@ add_llvm_unittest(UtilsTests
   FunctionComparator.cpp
   IntegerDivision.cpp
   Local.cpp
+  OrderedInstructions.cpp
   ValueMapperTest.cpp
   )
diff --git a/llvm/unittests/Transforms/Utils/OrderedInstructions.cpp b/llvm/unittests/Transforms/Utils/OrderedInstructions.cpp
new file mode 100644
index 00000000000..1d6df172294
--- /dev/null
+++ b/llvm/unittests/Transforms/Utils/OrderedInstructions.cpp
@@ -0,0 +1,65 @@
+//===- OrderedInstructions.cpp - Unit tests for OrderedInstructions  ------===//
+//
+//                     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/OrderedInstructions.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+/// Check intra-basicblock and inter-basicblock dominance using
+/// OrderedInstruction.
+TEST(OrderedInstructionsTest, DominanceTest) {
+  LLVMContext Ctx;
+  Module M("test", Ctx);
+  IRBuilder<> B(Ctx);
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Ctx), {B.getInt8PtrTy()}, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+
+  // Create the function as follow and check for dominance relation.
+  //
+  // test():
+  //  bbx:
+  //    loadx;
+  //    loady;
+  //  bby:
+  //    loadz;
+  //    return;
+  //
+  // More specifically, check for loadx -> (dominates) loady,
+  // loady -> loadx and loady -> loadz.
+  //
+  // Create BBX with 2 loads.
+  BasicBlock *BBX = BasicBlock::Create(Ctx, "bbx", F);
+  B.SetInsertPoint(BBX);
+  Argument *PointerArg = &*F->arg_begin();
+  LoadInst *LoadInstX = B.CreateLoad(PointerArg);
+  LoadInst *LoadInstY = B.CreateLoad(PointerArg);
+
+  // Create BBY with 1 load.
+  BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F);
+  B.SetInsertPoint(BBY);
+  LoadInst *LoadInstZ = B.CreateLoad(PointerArg);
+  B.CreateRet(LoadInstZ);
+  std::unique_ptr<DominatorTree> DT(new DominatorTree(*F));
+  OrderedInstructions OI(&*DT);
+
+  // Intra-BB dominance test.
+  EXPECT_TRUE(OI.dominates(LoadInstX, LoadInstY));
+  EXPECT_FALSE(OI.dominates(LoadInstY, LoadInstX));
+
+  // Inter-BB dominance test.
+  EXPECT_TRUE(OI.dominates(LoadInstY, LoadInstZ));
+}