[IR] Add GraphTraits specializations for Value def-use graphs

[eush]

Summary

This adds GraphTraits specializations for Value type that provide
GraphTraits interface to operands (forward direction) or uses (inverse
direction) of a given Value. This allows applying graph algorithms to
use-def graphs.

Note that walking this graph in the forward direction inherently
requires dynamically casting each node to User, due to the underlying
representation of the edges.

The specializations are put in IR/User.h to avoid introducing a
cyclical dependency between IR/Value.h and IR/User.h.

include/llvm/IR/User.h

 //  * Instructions are the largest class of Users.
 //  * Constants may be users of other constants (think arrays and stuff)
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_USER_H
 #define LLVM_IR_USER_H
 
+#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>

 template<> struct simplify_type<User::const_op_iterator> {
   using SimpleType = /*const*/ Value*;
 
   static SimpleType getSimplifiedValue(User::const_op_iterator &Val) {
     return Val->get();
   }
 };
 
+//===--------------------------------------------------------------------===//
+// GraphTraits specializations for def-use graphs
+//===--------------------------------------------------------------------===//
+
+template <> struct GraphTraits<Value *> {
+  using NodeRef = Value *;
+  using ChildIteratorType = User::op_iterator;
+
+  static NodeRef getEntryNode(Value *V) { return V; }
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    if (auto *U = dyn_cast<User>(N))
+      return U->op_begin();
+    else
+      return {};
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    if (auto *U = dyn_cast<User>(N))
+      return U->op_end();
+    else
+      return {};
+  }
+};
+
+template <> struct GraphTraits<const Value *> {
+  using NodeRef = const Value *;
+  using ChildIteratorType = User::const_op_iterator;
+
+  static NodeRef getEntryNode(const Value *V) { return V; }
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    if (auto *U = dyn_cast<User>(N))
+      return U->op_begin();
+    else
+      return {};
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    if (auto *U = dyn_cast<User>(N))
+      return U->op_end();
+    else
+      return {};
+  }
+};
+
+template <> struct GraphTraits<Inverse<Value *>> {
+  using NodeRef = Value *;
+  using ChildIteratorType = Value::user_iterator;
+
+  static NodeRef getEntryNode(Inverse<Value *> G) { return G.Graph; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
+};
+
+template <> struct GraphTraits<Inverse<const Value *>> {
+  using NodeRef = const Value *;
+  using ChildIteratorType = Value::const_user_iterator;
+
+  static NodeRef getEntryNode(Inverse<const Value *> G) { return G.Graph; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_IR_USER_H

unittests/IR/UserTest.cpp

 //===- llvm/unittest/IR/UserTest.cpp - User unit tests --------------------===//
 //
 // 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/IR/User.h"
+#include "llvm/ADT/GraphTraits.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/Value.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 using namespace llvm;
 
 namespace {
 
 TEST(UserTest, ValueOpIteration) {
   LLVMContext C;
TEST(UserTest, PersonalityUser) {
 
   // Reset the personality function
   TestF->setPersonalityFn(nullptr);
 
   // No users should remain
   EXPECT_TRUE(TestF->user_empty());
 }
 
+TEST(UserTest, GraphTraits) {
+  LLVMContext C;
+  const char *ModuleString = "define void @f(i32 %x) {\n"
+                             "entry:\n"
+                             "  %0 = icmp eq i32 %x, 1\n"
+                             "  br i1 %0, label %1, label %1\n"
+                             "\n"
+                             "  ret void\n"
+                             "}\n";
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(ModuleString, Err, C);
+
+  Function *F = M->getFunction("f");
+
+  Value *Arg = F->arg_begin();
+  EXPECT_EQ(std::next(inverse_children<Value *>(Arg).begin()),
+            inverse_children<Value *>(Arg).end());
+
+  auto *ICmp = dyn_cast<Instruction>(*inverse_children<Value *>(Arg).begin());
+  EXPECT_TRUE(ICmp);
+  EXPECT_EQ(ICmp->getOpcode(), Instruction::ICmp);
+  EXPECT_EQ(std::next(children<Value *>(ICmp).begin(), 2),
+            children<Value *>(ICmp).end());
+  EXPECT_EQ(*children<Value *>(ICmp).begin(), Arg);
+  EXPECT_EQ(std::next(inverse_children<Value *>(ICmp).begin()),
+            inverse_children<Value *>(ICmp).end());
+
+  auto *One =
+      dyn_cast<ConstantInt>(*std::next(children<Value *>(ICmp).begin()));
+  EXPECT_TRUE(One);
+  EXPECT_EQ(One->getSExtValue(), 1);
+
+  auto *Br = dyn_cast<BranchInst>(*inverse_children<Value *>(ICmp).begin());
+  EXPECT_TRUE(Br);
+  EXPECT_EQ(std::next(children<Value *>(Br).begin(), 3),
+            children<Value *>(Br).end());
+  EXPECT_EQ(*children<Value *>(Br).begin(), ICmp);
+  EXPECT_EQ(*std::next(children<Value *>(Br).begin()),
+            *std::next(children<Value *>(Br).begin(), 2));
+  EXPECT_EQ(inverse_children<Value *>(Br).begin(),
+            inverse_children<Value *>(Br).end());
+
+  auto *BB = dyn_cast<BasicBlock>(*std::next(children<Value *>(Br).begin()));
+  EXPECT_TRUE(BB);
+  EXPECT_EQ(children<Value *>(BB).begin(), children<Value *>(BB).end());
+  EXPECT_EQ(std::next(inverse_children<Value *>(BB).begin(), 2),
+            inverse_children<Value *>(BB).end());
+  EXPECT_EQ(*inverse_children<Value *>(BB).begin(), Br);
+  EXPECT_EQ(*std::next(inverse_children<Value *>(BB).begin()), Br);
+}
+
 } // end anonymous namespace