unittests/Analysis/PhiValuesTest.cpp

   1 //===- PhiValuesTest.cpp - PhiValues unit tests ---------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/PhiValues.h"
  11 #include "llvm/IR/BasicBlock.h"
  12 #include "llvm/IR/Function.h"
  13 #include "llvm/IR/Instructions.h"
  14 #include "llvm/IR/Module.h"
  15 #include "llvm/IR/Type.h"
  16 #include "gtest/gtest.h"
  17
  18 using namespace llvm;
  19
  20 TEST(PhiValuesTest, SimplePhi) {
  21   LLVMContext C;
  22   Module M("PhiValuesTest", C);
  23
  24   Type *VoidTy = Type::getVoidTy(C);
  25   Type *I1Ty = Type::getInt1Ty(C);
  26   Type *I32Ty = Type::getInt32Ty(C);
  27   Type *I32PtrTy = Type::getInt32PtrTy(C);
  28
  29   // Create a function with phis that do not have other phis as incoming values
  30   Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
  31
  32   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
  33   BasicBlock *If = BasicBlock::Create(C, "if", F);
  34   BasicBlock *Else = BasicBlock::Create(C, "else", F);
  35   BasicBlock *Then = BasicBlock::Create(C, "then", F);
  36   BranchInst::Create(If, Else, UndefValue::get(I1Ty), Entry);
  37   BranchInst::Create(Then, If);
  38   BranchInst::Create(Then, Else);
  39
  40   Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
  41   Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
  42   Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
  43   Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
  44
  45   PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
  46   Phi1->addIncoming(Val1, If);
  47   Phi1->addIncoming(Val2, Else);
  48   PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
  49   Phi2->addIncoming(Val1, If);
  50   Phi2->addIncoming(Val3, Else);
  51
  52   PhiValues PV(*F);
  53   PhiValues::ValueSet Vals;
  54
  55   // Check that simple usage works
  56   Vals = PV.getValuesForPhi(Phi1);
  57   EXPECT_EQ(Vals.size(), 2u);
  58   EXPECT_TRUE(Vals.count(Val1));
  59   EXPECT_TRUE(Vals.count(Val2));
  60   Vals = PV.getValuesForPhi(Phi2);
  61   EXPECT_EQ(Vals.size(), 2u);
  62   EXPECT_TRUE(Vals.count(Val1));
  63   EXPECT_TRUE(Vals.count(Val3));
  64
  65   // Check that values are updated when one value is replaced with another
  66   Val1->replaceAllUsesWith(Val4);
  67   PV.invalidateValue(Val1);
  68   Vals = PV.getValuesForPhi(Phi1);
  69   EXPECT_EQ(Vals.size(), 2u);
  70   EXPECT_TRUE(Vals.count(Val4));
  71   EXPECT_TRUE(Vals.count(Val2));
  72   Vals = PV.getValuesForPhi(Phi2);
  73   EXPECT_EQ(Vals.size(), 2u);
  74   EXPECT_TRUE(Vals.count(Val4));
  75   EXPECT_TRUE(Vals.count(Val3));
  76
  77   // Check that setting in incoming value directly updates the values
  78   Phi1->setIncomingValue(0, Val1);
  79   PV.invalidateValue(Phi1);
  80   Vals = PV.getValuesForPhi(Phi1);
  81   EXPECT_EQ(Vals.size(), 2u);
  82   EXPECT_TRUE(Vals.count(Val1));
  83   EXPECT_TRUE(Vals.count(Val2));
  84 }
  85
  86 TEST(PhiValuesTest, DependentPhi) {
  87   LLVMContext C;
  88   Module M("PhiValuesTest", C);
  89
  90   Type *VoidTy = Type::getVoidTy(C);
  91   Type *I1Ty = Type::getInt1Ty(C);
  92   Type *I32Ty = Type::getInt32Ty(C);
  93   Type *I32PtrTy = Type::getInt32PtrTy(C);
  94
  95   // Create a function with a phi that has another phi as an incoming value
  96   Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
  97
  98   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
  99   BasicBlock *If1 = BasicBlock::Create(C, "if1", F);
 100   BasicBlock *Else1 = BasicBlock::Create(C, "else1", F);
 101   BasicBlock *Then = BasicBlock::Create(C, "then", F);
 102   BasicBlock *If2 = BasicBlock::Create(C, "if2", F);
 103   BasicBlock *Else2 = BasicBlock::Create(C, "else2", F);
 104   BasicBlock *End = BasicBlock::Create(C, "then", F);
 105   BranchInst::Create(If1, Else1, UndefValue::get(I1Ty), Entry);
 106   BranchInst::Create(Then, If1);
 107   BranchInst::Create(Then, Else1);
 108   BranchInst::Create(If2, Else2, UndefValue::get(I1Ty), Then);
 109   BranchInst::Create(End, If2);
 110   BranchInst::Create(End, Else2);
 111
 112   Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
 113   Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
 114   Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
 115   Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
 116
 117   PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
 118   Phi1->addIncoming(Val1, If1);
 119   Phi1->addIncoming(Val2, Else1);
 120   PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
 121   Phi2->addIncoming(Val2, If1);
 122   Phi2->addIncoming(Val3, Else1);
 123   PHINode *Phi3 = PHINode::Create(I32Ty, 2, "phi3", End);
 124   Phi3->addIncoming(Phi1, If2);
 125   Phi3->addIncoming(Val3, Else2);
 126
 127   PhiValues PV(*F);
 128   PhiValues::ValueSet Vals;
 129
 130   // Check that simple usage works
 131   Vals = PV.getValuesForPhi(Phi1);
 132   EXPECT_EQ(Vals.size(), 2u);
 133   EXPECT_TRUE(Vals.count(Val1));
 134   EXPECT_TRUE(Vals.count(Val2));
 135   Vals = PV.getValuesForPhi(Phi2);
 136   EXPECT_EQ(Vals.size(), 2u);
 137   EXPECT_TRUE(Vals.count(Val2));
 138   EXPECT_TRUE(Vals.count(Val3));
 139   Vals = PV.getValuesForPhi(Phi3);
 140   EXPECT_EQ(Vals.size(), 3u);
 141   EXPECT_TRUE(Vals.count(Val1));
 142   EXPECT_TRUE(Vals.count(Val2));
 143   EXPECT_TRUE(Vals.count(Val3));
 144
 145   // Check that changing an incoming value in the dependent phi changes the depending phi
 146   Phi1->setIncomingValue(0, Val4);
 147   PV.invalidateValue(Phi1);
 148   Vals = PV.getValuesForPhi(Phi1);
 149   EXPECT_EQ(Vals.size(), 2u);
 150   EXPECT_TRUE(Vals.count(Val4));
 151   EXPECT_TRUE(Vals.count(Val2));
 152   Vals = PV.getValuesForPhi(Phi2);
 153   EXPECT_EQ(Vals.size(), 2u);
 154   EXPECT_TRUE(Vals.count(Val2));
 155   EXPECT_TRUE(Vals.count(Val3));
 156   Vals = PV.getValuesForPhi(Phi3);
 157   EXPECT_EQ(Vals.size(), 3u);
 158   EXPECT_TRUE(Vals.count(Val4));
 159   EXPECT_TRUE(Vals.count(Val2));
 160   EXPECT_TRUE(Vals.count(Val3));
 161
 162   // Check that replacing an incoming phi with a value works
 163   Phi3->setIncomingValue(0, Val1);
 164   PV.invalidateValue(Phi3);
 165   Vals = PV.getValuesForPhi(Phi1);
 166   EXPECT_EQ(Vals.size(), 2u);
 167   EXPECT_TRUE(Vals.count(Val4));
 168   EXPECT_TRUE(Vals.count(Val2));
 169   Vals = PV.getValuesForPhi(Phi2);
 170   EXPECT_EQ(Vals.size(), 2u);
 171   EXPECT_TRUE(Vals.count(Val2));
 172   EXPECT_TRUE(Vals.count(Val3));
 173   Vals = PV.getValuesForPhi(Phi3);
 174   EXPECT_EQ(Vals.size(), 2u);
 175   EXPECT_TRUE(Vals.count(Val1));
 176   EXPECT_TRUE(Vals.count(Val3));
 177
 178   // Check that adding a phi as an incoming value works
 179   Phi3->setIncomingValue(1, Phi2);
 180   PV.invalidateValue(Phi3);
 181   Vals = PV.getValuesForPhi(Phi1);
 182   EXPECT_EQ(Vals.size(), 2u);
 183   EXPECT_TRUE(Vals.count(Val4));
 184   EXPECT_TRUE(Vals.count(Val2));
 185   Vals = PV.getValuesForPhi(Phi2);
 186   EXPECT_EQ(Vals.size(), 2u);
 187   EXPECT_TRUE(Vals.count(Val2));
 188   EXPECT_TRUE(Vals.count(Val3));
 189   Vals = PV.getValuesForPhi(Phi3);
 190   EXPECT_EQ(Vals.size(), 3u);
 191   EXPECT_TRUE(Vals.count(Val1));
 192   EXPECT_TRUE(Vals.count(Val2));
 193   EXPECT_TRUE(Vals.count(Val3));
 194
 195   // Check that replacing an incoming phi then deleting it works
 196   Phi3->setIncomingValue(1, Val2);
 197   PV.invalidateValue(Phi2);
 198   Phi2->eraseFromParent();
 199   PV.invalidateValue(Phi3);
 200   Vals = PV.getValuesForPhi(Phi1);
 201   EXPECT_EQ(Vals.size(), 2u);
 202   EXPECT_TRUE(Vals.count(Val4));
 203   EXPECT_TRUE(Vals.count(Val2));
 204   Vals = PV.getValuesForPhi(Phi3);
 205   EXPECT_EQ(Vals.size(), 2u);
 206   EXPECT_TRUE(Vals.count(Val1));
 207   EXPECT_TRUE(Vals.count(Val2));
 208 }