[CodeMoverUtils] Move OrderedInstructions to CodeMoverUtils

[RithikSharma]

Summary

This patch moves OrderedInstructions to CodeMoverUtils as It was the only place where OrderedInstructions is required.

[nikic]

You don't need an actual OrderedInstructions class. You can simply make domTreeLevelBefore() a static function in CodeMoverUtils.cpp. Replace the localDominates() call with Instruction::comesBefore().

[RithikSharma]

In D80643#2057673, @nikic wrote:

You don't need an actual OrderedInstructions class. You can simply make domTreeLevelBefore() a static function in CodeMoverUtils.cpp. Replace the localDominates() call with Instruction::comesBefore().

Moving OrderedInstructions functions to CodeMoverUtils.cpp and making them static doesn't allow the unittest to pass! The unittest requires the call of "dominates" and the only way to fulfill is to define "dominates" into CodeMoverUtils.h which is not the preferred step!

[nikic]

In D80643#2074009, @RithikSharma wrote:

Moving OrderedInstructions functions to CodeMoverUtils.cpp and making them static doesn't allow the unittest to pass! The unittest requires the call of "dominates" and the only way to fulfill is to define "dominates" into CodeMoverUtils.h which is not the preferred step!

Not sure I follow. As far as I know, OrderedInstructions::dominates() is same as DominatorTree::dominates() at this point, so you can just use the DominatorTree method. I'm also not sure what the added DominanceTest is force. It doesn't seem related to CodeMoverUtils and only tests dominance queries, for which we already have dedicated domtree construction tests.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

103

No need, is not doing anything extra compare to DominatorTree::dominates defined in lib/IR/Dominators.cpp

116

As suggested by @nikic , change this call to comesBefore. And remove OrderedInstructions::localDominates.

119

Did you accidentally removed the line: return DA->getLevel() < DB->getLevel();?
Don't forget to build and test your change before updating your patch.

333

Please update the base of your diff. It is already calling domTreeLevelBefore before this patch.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

652

remove this test.

[RithikSharma]

This update removes the OrderedInstructions class from CodeMoverUtils and also removes it's exposure to other transformation passes, both localDominates and domTreeLevelBefore is made as static functions and are present in CodeMoverUtils.cpp. OrderedInstructions::dominates() has been removed from CodeMoverUtils.cpp due to it's existance in DominatorTree::dominates(), the dominance test moved from OrderedInstructionsTest.cpp to CodeMoverUtilsTest.cpp is also removed.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

96

Am I right that function localDominates is now dead? If so, can you remove it as well?

[RithikSharma]

This update removes localDominates which is not required, only one OrderedInstructions is required which is domTreeLevelBefore which is now a part of CodeMoverUtils.cpp

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

358

Why const is removed?

[RithikSharma]

This update fixes the existing errors in the patch.

[Whitney]

The patch LGTM. @nikic What do you think?

[Whitney]

@nikic ping

[nikic]

Sorry for the delay, this LGTM as well.

[Whitney]

https://reviews.llvm.org/rGe71c7b593a2d1b7d60dc8aaa4b8ede03de7bbd00

llvm/include/llvm/Analysis/OrderedInstructions.h

-//===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines an efficient way to check for dominance relation between 2
-// instructions.
-//
-// FIXME: This is really just a convenience wrapper to check dominance between
-// two arbitrary instructions in different basic blocks. We should fold it into
-// DominatorTree, which is the more widely used interface.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
-#define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Operator.h"
-
-namespace llvm {
-
-class OrderedInstructions {
-  /// The dominator tree of the parent function.
-  DominatorTree *DT;
-
-  /// Return true if the first instruction comes before the second in the
-  /// same basic block. It will create an ordered basic block, if it does
-  /// not yet exist in OBBMap.
-  bool localDominates(const Instruction *, const Instruction *) const;
-
-public:
-  /// Constructor.
-  OrderedInstructions(DominatorTree *DT) : DT(DT) {}
-
-  /// Return true if first instruction dominates the second.
-  bool dominates(const Instruction *, const Instruction *) const;
-
-  /// Return true if the first instruction comes before the second in the
-  /// dominator tree DFS traversal if they are in different basic blocks,
-  /// or if the first instruction comes before the second in the same basic
-  /// block.
-  bool dfsBefore(const Instruction *, const Instruction *) const;
-
-  // Return true if the first instruction comes before the second in the
-  // dominator tree BFS traversal based on the level number of nodes in
-  // dominator tree if they are in different basic blocks else if the first
-  // instruction comes before the second in the same basic block
-  bool bfsLevelBefore(const Instruction *, const Instruction *) const;
-};
-
-} // end namespace llvm
-
-#endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

 namespace llvm {
 
 class BasicBlock;
 class DependenceInfo;
 class DominatorTree;
 class Instruction;
 class PostDominatorTree;
 
+class OrderedInstructions {
+  DominatorTree *DT;
+  bool localDominates(const Instruction *, const Instruction *) const;
+
+public:
+  OrderedInstructions(DominatorTree *DT) : DT(DT) {}
+  bool dominates(const Instruction *, const Instruction *) const;
+  bool domTreeLevelBefore(const Instruction *, const Instruction *) const;
+};
+
 /// Return true if \p I0 and \p I1 are control flow equivalent.
 /// Two instructions are control flow equivalent if their basic blocks are
 /// control flow equivalent.
 bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p BB0 and \p BB1 are control flow equivalent.

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   MemorySSAUpdater.cpp
   ModuleDebugInfoPrinter.cpp
   ModuleSummaryAnalysis.cpp
   MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
-  OrderedInstructions.cpp
   PHITransAddr.cpp
   PhiValues.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp

llvm/lib/Analysis/OrderedInstructions.cpp

-//===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines utility to check dominance relation of 2 instructions.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/OrderedInstructions.h"
-using namespace llvm;
-
-bool OrderedInstructions::localDominates(const Instruction *InstA,
-                                         const Instruction *InstB) const {
-  assert(InstA->getParent() == InstB->getParent() &&
-         "Instructions must be in the same basic block");
-
-  return InstA->comesBefore(InstB);
-}
-
-/// Given 2 instructions, 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 {
-  // Use ordered basic block to do dominance check in case the 2 instructions
-  // are in the same basic block.
-  if (InstA->getParent() == InstB->getParent())
-    return localDominates(InstA, InstB);
-  return DT->dominates(InstA->getParent(), InstB->getParent());
-}
-
-bool OrderedInstructions::dfsBefore(const Instruction *InstA,
-                                    const Instruction *InstB) const {
-  // Use ordered basic block in case the 2 instructions are in the same basic
-  // block.
-  if (InstA->getParent() == InstB->getParent())
-    return localDominates(InstA, InstB);
-
-  DomTreeNode *DA = DT->getNode(InstA->getParent());
-  DomTreeNode *DB = DT->getNode(InstB->getParent());
-  return DA->getDFSNumIn() < DB->getDFSNumIn();
-}
-
-bool OrderedInstructions::bfsLevelBefore(const Instruction *InstA,
-                                         const Instruction *InstB) const {
-  // Use ordered basic block in case the 2 instructions are in the same basic
-  // block.
-  if (InstA->getParent() == InstB->getParent())
-    return localDominates(InstA, InstB);
-
-  DomTreeNode *DA = DT->getNode(InstA->getParent());
-  DomTreeNode *DB = DT->getNode(InstB->getParent());
-  return DA->getLevel() < DB->getLevel();
-}

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 // contained within a function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
-#include "llvm/Analysis/OrderedInstructions.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "codemover-utils"
 

 private:
   ControlConditions() = default;
 
   static bool isEquivalent(const Value &V1, const Value &V2);
   static bool isInverse(const Value &V1, const Value &V2);
 };
 } // namespace
 
+bool OrderedInstructions::localDominates(const Instruction *InstA,
+                                         const Instruction *InstB) const {
+  assert(InstA->getParent() == InstB->getParent() &&
+         "Instructions must be in the same basic block");
+
+  return InstA->comesBefore(InstB);
+}
+bool OrderedInstructions::dominates(const Instruction *InstA,
+                                    const Instruction *InstB) const {
+  // Use ordered basic block to do dominance check in case the 2 instructions
+  // are in the same basic block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+  return DT->dominates(InstA->getParent(), InstB->getParent());
+}
+bool OrderedInstructions::domTreeLevelBefore(const Instruction *InstA,
+                                             const Instruction *InstB) const {
+  // Use ordered basic block in case the 2 instructions are in the same basic
+  // block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+
+  DomTreeNode *DA = DT->getNode(InstA->getParent());
+  DomTreeNode *DB = DT->getNode(InstB->getParent());
+}
+
 const Optional<ControlConditions> ControlConditions::collectControlConditions(
     const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
     const PostDominatorTree &PDT, unsigned MaxLookup) {
   assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
 
   ControlConditions Conditions;
   unsigned NumConditions = 0;
 
bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
   if (!DT.dominates(&I, &InsertPoint))
     for (const Value *Op : I.operands())
       if (auto *OpInst = dyn_cast<Instruction>(Op))
         if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
           return false;
 
   OrderedInstructions OI(&DT);
   DT.updateDFSNumbers();
-  const bool MoveForward = OI.bfsLevelBefore(&I, &InsertPoint);
+  const bool MoveForward = OI.domTreeLevelBefore(&I, &InsertPoint);
   Instruction &StartInst = (MoveForward ? I : InsertPoint);
   Instruction &EndInst = (MoveForward ? InsertPoint : I);
   SmallPtrSet<Instruction *, 10> InstsToCheck;
   collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
   if (!MoveForward)
     InstsToCheck.insert(&InsertPoint);
 
   // Check if there exists instructions which may throw, may synchonize, or may

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   GlobalsModRefTest.cpp
   IVDescriptorsTest.cpp
   LazyCallGraphTest.cpp
   LoadsTest.cpp
   LoopInfoTest.cpp
   LoopNestTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp
-  OrderedInstructionsTest.cpp
   PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   VectorFunctionABITest.cpp
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzerTest.cpp
   ValueLatticeTest.cpp
   ValueTrackingTest.cpp
   VectorUtilsTest.cpp
   )

llvm/unittests/Analysis/OrderedInstructionsTest.cpp

-//===- OrderedInstructions.cpp - Unit tests for OrderedInstructions  ------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/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 = Function::Create(FTy, Function::ExternalLinkage, "f", M);
-
-  // 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(B.getInt8Ty(), PointerArg);
-  LoadInst *LoadInstY = B.CreateLoad(B.getInt8Ty(), PointerArg);
-
-  // Create BBY with 1 load.
-  BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F);
-  B.SetInsertPoint(BBY);
-  LoadInst *LoadInstZ = B.CreateLoad(B.getInt8Ty(), 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));
-}

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

run(*M, "foo",
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
         EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
         EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI));
       });
 }
+TEST(CodeMoverUtils, DominanceTest) {
+  LLVMContext Ctx;
+  Module M("test", Ctx);
+  IRBuilder<> B(Ctx);
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Ctx), {B.getInt8PtrTy()}, false);
+  Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
+
+  // 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(B.getInt8Ty(), PointerArg);
+  LoadInst *LoadInstY = B.CreateLoad(B.getInt8Ty(), PointerArg);
+
+  // Create BBY with 1 load.
+  BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F);
+  B.SetInsertPoint(BBY);
+  LoadInst *LoadInstZ = B.CreateLoad(B.getInt8Ty(), 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));
+}

llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn

sources = [
     "MemorySSAUpdater.cpp",
     "ModuleDebugInfoPrinter.cpp",
     "ModuleSummaryAnalysis.cpp",
     "MustExecute.cpp",
     "ObjCARCAliasAnalysis.cpp",
     "ObjCARCAnalysisUtils.cpp",
     "ObjCARCInstKind.cpp",
     "OptimizationRemarkEmitter.cpp",
-    "OrderedInstructions.cpp",
     "PHITransAddr.cpp",
     "PhiValues.cpp",
     "PostDominators.cpp",
     "ProfileSummaryInfo.cpp",
     "PtrUseVisitor.cpp",
     "RegionInfo.cpp",
     "RegionPass.cpp",
     "RegionPrinter.cpp",

llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn

sources = [
     "GlobalsModRefTest.cpp",
     "IVDescriptorsTest.cpp",
     "LazyCallGraphTest.cpp",
     "LoadsTest.cpp",
     "LoopInfoTest.cpp",
     "LoopNestTest.cpp",
     "MemoryBuiltinsTest.cpp",
     "MemorySSATest.cpp",
-    "OrderedInstructionsTest.cpp",
     "PhiValuesTest.cpp",
     "ProfileSummaryInfoTest.cpp",
     "ScalarEvolutionTest.cpp",
     "SparsePropagation.cpp",
     "TBAATest.cpp",
     "TargetLibraryInfoTest.cpp",
     "UnrollAnalyzerTest.cpp",
     "ValueLatticeTest.cpp",
     "ValueTrackingTest.cpp",
     "VectorFunctionABITest.cpp",
     "VectorUtilsTest.cpp",
   ]
 }