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

[trentxintong]

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

[trentxintong]

Update test.

[davide]

This is a really nice cleanup and I think we can greatly benefit from it in other passes as well :)
Some comments inline.

lib/Transforms/Utils/OrderedInstructions.cpp

10 ↗

(On Diff #99677)

I'd say check dominance relation between two instructions rather than information (and I'd add efficiently, as we take shortcuts here :))

17–18 ↗

(On Diff #99677)

Do you need to define DEBUG_TYPE ?
This doesn't use any DEBUG() statements

19 ↗

(On Diff #99677)

I'd add a comment to this explaining what it does/how.

30–31 ↗

(On Diff #99677)

braces around this else, for consistency.

unittests/Transforms/Utils/OrderedInstructions.cpp

16 ↗

(On Diff #99677)

Do you need to include LegacyPassManager.h ?

30–31 ↗

(On Diff #99677)

Do you mind to add a textual representation of these tests for the reader? (it doesn't need to be perfect, just as guidance).

[trentxintong]

Address comments from @davide

[trentxintong]

Ping, appreciate it if this can get reviewed faster.

[• dberlin]

lib/Transforms/Utils/OrderedInstructions.cpp

22 ↗

(On Diff #99680)

Can you just take the DT in the constructor?
That way i can fill in the rest of the DT use cases as functions, and not have to take dominatortree anywhere.

[trentxintong]

Address comments.

[trentxintong]

Add a line of comment.

[• dberlin]

LGTM with one change to start. I'll add the other pieces of dominators functionality.

include/llvm/Transforms/Utils/OrderedInstructions.h

41 ↗

(On Diff #101446)

This should be const and the obbmap mutable

llvm/trunk/include/llvm/Transforms/Utils/OrderedInstructions.h

+//===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an efficient way to check for dominance relation between 2
+// instructions.
+//
+// This interface dispatches to appropriate dominance check given 2
+// instructions, i.e. in case the instructions are in the same basic block,
+// OrderedBasicBlock (with instruction numbering and caching) are used.
+// Otherwise, dominator tree is used.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H
+#define LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Operator.h"
+
+namespace llvm {
+
+class OrderedInstructions {
+  /// Used to check dominance for instructions in same basic block.
+  mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
+      OBBMap;
+
+  /// The dominator tree of the parent function.
+  DominatorTree *DT;
+
+public:
+  /// Constructor.
+  OrderedInstructions(DominatorTree *DT) : DT(DT) {}
+
+  /// Return true if first instruction dominates the second.
+  bool dominates(const Instruction *, const Instruction *) const;
+
+  /// Invalidate the OrderedBasicBlock cache when its basic block changes.
+  void invalidateBlock(BasicBlock *BB) { OBBMap.erase(BB); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H

llvm/trunk/lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LoopVersioning.cpp
   LowerInvoke.cpp
   LowerMemIntrinsics.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
+  OrderedInstructions.cpp
   PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   StripGCRelocates.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp

llvm/trunk/lib/Transforms/Utils/OrderedInstructions.cpp

+//===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines utility to check dominance relation of 2 instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
+using namespace llvm;
+
+/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
+/// if the instructions are in the same basic block, Otherwise, use dominator
+/// tree.
+bool OrderedInstructions::dominates(const Instruction *InstA,
+                                    const Instruction *InstB) const {
+  const BasicBlock *IBB = InstA->getParent();
+  // Use ordered basic block to do dominance check in case the 2 instructions
+  // are in the same basic block.
+  if (IBB == InstB->getParent()) {
+    auto OBB = OBBMap.find(IBB);
+    if (OBB == OBBMap.end())
+      OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
+    return OBB->second->dominates(InstA, InstB);
+  } else {
+    return DT->dominates(InstA->getParent(), InstB->getParent());
+  }
+}

llvm/trunk/unittests/Transforms/Utils/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   Support
   TransformUtils
   )
 
 add_llvm_unittest(UtilsTests
   ASanStackFrameLayoutTest.cpp
   Cloning.cpp
   FunctionComparator.cpp
   IntegerDivision.cpp
   Local.cpp
+  OrderedInstructions.cpp
   ValueMapperTest.cpp
   )

llvm/trunk/unittests/Transforms/Utils/OrderedInstructions.cpp

+//===- 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));
+}