Add a PhiValuesAnalysis pass to calculate the underlying values of phis

This pass is being added in order to make the information available to BasicAA,
which can't do caching of this information itself, but possibly this information
may be useful for other passes.

Incorporates code based on Daniel Berlin's implementation of Tarjan's algorithm.

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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@335857 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 209 insertions, 0 deletions

diff --git a/unittests/Analysis/CMakeLists.txt b/unittests/Analysis/CMakeLists.txt
index 65f2aeda418..f6ff29064be 100644
--- a/unittests/Analysis/CMakeLists.txt
+++ b/unittests/Analysis/CMakeLists.txt
@@ -20,6 +20,7 @@ add_llvm_unittest(AnalysisTests
   MemoryBuiltinsTest.cpp
   MemorySSA.cpp
   OrderedBasicBlockTest.cpp
+  PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   SparsePropagation.cpp
diff --git a/unittests/Analysis/PhiValuesTest.cpp b/unittests/Analysis/PhiValuesTest.cpp
new file mode 100644
index 00000000000..9a1b5d7ec6c
--- /dev/null
+++ b/unittests/Analysis/PhiValuesTest.cpp
@@ -0,0 +1,208 @@
+//===- PhiValuesTest.cpp - PhiValues unit tests ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PhiValues.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(PhiValuesTest, SimplePhi) {
+  LLVMContext C;
+  Module M("PhiValuesTest", C);
+
+  Type *VoidTy = Type::getVoidTy(C);
+  Type *I1Ty = Type::getInt1Ty(C);
+  Type *I32Ty = Type::getInt32Ty(C);
+  Type *I32PtrTy = Type::getInt32PtrTy(C);
+
+  // Create a function with phis that do not have other phis as incoming values
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
+
+  BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
+  BasicBlock *If = BasicBlock::Create(C, "if", F);
+  BasicBlock *Else = BasicBlock::Create(C, "else", F);
+  BasicBlock *Then = BasicBlock::Create(C, "then", F);
+  BranchInst::Create(If, Else, UndefValue::get(I1Ty), Entry);
+  BranchInst::Create(Then, If);
+  BranchInst::Create(Then, Else);
+
+  Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
+  Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
+  Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
+  Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
+
+  PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
+  Phi1->addIncoming(Val1, If);
+  Phi1->addIncoming(Val2, Else);
+  PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
+  Phi2->addIncoming(Val1, If);
+  Phi2->addIncoming(Val3, Else);
+
+  PhiValues PV(*F);
+  PhiValues::ValueSet Vals;
+
+  // Check that simple usage works
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that values are updated when one value is replaced with another
+  Val1->replaceAllUsesWith(Val4);
+  PV.invalidateValue(Val1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that setting in incoming value directly updates the values
+  Phi1->setIncomingValue(0, Val1);
+  PV.invalidateValue(Phi1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+}
+
+TEST(PhiValuesTest, DependentPhi) {
+  LLVMContext C;
+  Module M("PhiValuesTest", C);
+
+  Type *VoidTy = Type::getVoidTy(C);
+  Type *I1Ty = Type::getInt1Ty(C);
+  Type *I32Ty = Type::getInt32Ty(C);
+  Type *I32PtrTy = Type::getInt32PtrTy(C);
+
+  // Create a function with a phi that has another phi as an incoming value
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
+
+  BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
+  BasicBlock *If1 = BasicBlock::Create(C, "if1", F);
+  BasicBlock *Else1 = BasicBlock::Create(C, "else1", F);
+  BasicBlock *Then = BasicBlock::Create(C, "then", F);
+  BasicBlock *If2 = BasicBlock::Create(C, "if2", F);
+  BasicBlock *Else2 = BasicBlock::Create(C, "else2", F);
+  BasicBlock *End = BasicBlock::Create(C, "then", F);
+  BranchInst::Create(If1, Else1, UndefValue::get(I1Ty), Entry);
+  BranchInst::Create(Then, If1);
+  BranchInst::Create(Then, Else1);
+  BranchInst::Create(If2, Else2, UndefValue::get(I1Ty), Then);
+  BranchInst::Create(End, If2);
+  BranchInst::Create(End, Else2);
+
+  Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
+  Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
+  Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
+  Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
+
+  PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
+  Phi1->addIncoming(Val1, If1);
+  Phi1->addIncoming(Val2, Else1);
+  PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
+  Phi2->addIncoming(Val2, If1);
+  Phi2->addIncoming(Val3, Else1);
+  PHINode *Phi3 = PHINode::Create(I32Ty, 2, "phi3", End);
+  Phi3->addIncoming(Phi1, If2);
+  Phi3->addIncoming(Val3, Else2);
+
+  PhiValues PV(*F);
+  PhiValues::ValueSet Vals;
+
+  // Check that simple usage works
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that changing an incoming value in the dependent phi changes the depending phi
+  Phi1->setIncomingValue(0, Val4);
+  PV.invalidateValue(Phi1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that replacing an incoming phi with a value works
+  Phi3->setIncomingValue(0, Val1);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that adding a phi as an incoming value works
+  Phi3->setIncomingValue(1, Phi2);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that replacing an incoming phi then deleting it works
+  Phi3->setIncomingValue(1, Val2);
+  Phi2->eraseFromParent();
+  PV.invalidateValue(Phi2);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+}