unittests/Analysis/PhiValuesTest.cpp

   1 //===- PhiValuesTest.cpp - PhiValues unit tests ---------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Analysis/PhiValues.h"
  10 #include "llvm/IR/BasicBlock.h"
  11 #include "llvm/IR/Function.h"
  12 #include "llvm/IR/Instructions.h"
  13 #include "llvm/IR/Module.h"
  14 #include "llvm/IR/Type.h"
  15 #include "gtest/gtest.h"
  16
  17 using namespace llvm;
  18
  19 TEST(PhiValuesTest, SimplePhi) {
  20   LLVMContext C;
  21   Module M("PhiValuesTest", C);
  22
  23   Type *VoidTy = Type::getVoidTy(C);
  24   Type *I1Ty = Type::getInt1Ty(C);
  25   Type *I32Ty = Type::getInt32Ty(C);
  26   Type *I32PtrTy = Type::getInt32PtrTy(C);
  27
  28   // Create a function with phis that do not have other phis as incoming values
  29   Function *F = Function::Create(FunctionType::get(VoidTy, false),
  30                                  Function::ExternalLinkage, "f", M);
  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(I32Ty, UndefValue::get(I32PtrTy), "val1", Entry);
  41   Value *Val2 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val2", Entry);
  42   Value *Val3 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val3", Entry);
  43   Value *Val4 = new LoadInst(I32Ty, 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 = Function::Create(FunctionType::get(VoidTy, false),
  97                                  Function::ExternalLinkage, "f", M);
  98
  99   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
 100   BasicBlock *If1 = BasicBlock::Create(C, "if1", F);
 101   BasicBlock *Else1 = BasicBlock::Create(C, "else1", F);
 102   BasicBlock *Then = BasicBlock::Create(C, "then", F);
 103   BasicBlock *If2 = BasicBlock::Create(C, "if2", F);
 104   BasicBlock *Else2 = BasicBlock::Create(C, "else2", F);
 105   BasicBlock *End = BasicBlock::Create(C, "then", F);
 106   BranchInst::Create(If1, Else1, UndefValue::get(I1Ty), Entry);
 107   BranchInst::Create(Then, If1);
 108   BranchInst::Create(Then, Else1);
 109   BranchInst::Create(If2, Else2, UndefValue::get(I1Ty), Then);
 110   BranchInst::Create(End, If2);
 111   BranchInst::Create(End, Else2);
 112
 113   Value *Val1 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val1", Entry);
 114   Value *Val2 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val2", Entry);
 115   Value *Val3 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val3", Entry);
 116   Value *Val4 = new LoadInst(I32Ty, UndefValue::get(I32PtrTy), "val4", Entry);
 117
 118   PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
 119   Phi1->addIncoming(Val1, If1);
 120   Phi1->addIncoming(Val2, Else1);
 121   PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
 122   Phi2->addIncoming(Val2, If1);
 123   Phi2->addIncoming(Val3, Else1);
 124   PHINode *Phi3 = PHINode::Create(I32Ty, 2, "phi3", End);
 125   Phi3->addIncoming(Phi1, If2);
 126   Phi3->addIncoming(Val3, Else2);
 127
 128   PhiValues PV(*F);
 129   PhiValues::ValueSet Vals;
 130
 131   // Check that simple usage works
 132   Vals = PV.getValuesForPhi(Phi1);
 133   EXPECT_EQ(Vals.size(), 2u);
 134   EXPECT_TRUE(Vals.count(Val1));
 135   EXPECT_TRUE(Vals.count(Val2));
 136   Vals = PV.getValuesForPhi(Phi2);
 137   EXPECT_EQ(Vals.size(), 2u);
 138   EXPECT_TRUE(Vals.count(Val2));
 139   EXPECT_TRUE(Vals.count(Val3));
 140   Vals = PV.getValuesForPhi(Phi3);
 141   EXPECT_EQ(Vals.size(), 3u);
 142   EXPECT_TRUE(Vals.count(Val1));
 143   EXPECT_TRUE(Vals.count(Val2));
 144   EXPECT_TRUE(Vals.count(Val3));
 145
 146   // Check that changing an incoming value in the dependent phi changes the depending phi
 147   Phi1->setIncomingValue(0, Val4);
 148   PV.invalidateValue(Phi1);
 149   Vals = PV.getValuesForPhi(Phi1);
 150   EXPECT_EQ(Vals.size(), 2u);
 151   EXPECT_TRUE(Vals.count(Val4));
 152   EXPECT_TRUE(Vals.count(Val2));
 153   Vals = PV.getValuesForPhi(Phi2);
 154   EXPECT_EQ(Vals.size(), 2u);
 155   EXPECT_TRUE(Vals.count(Val2));
 156   EXPECT_TRUE(Vals.count(Val3));
 157   Vals = PV.getValuesForPhi(Phi3);
 158   EXPECT_EQ(Vals.size(), 3u);
 159   EXPECT_TRUE(Vals.count(Val4));
 160   EXPECT_TRUE(Vals.count(Val2));
 161   EXPECT_TRUE(Vals.count(Val3));
 162
 163   // Check that replacing an incoming phi with a value works
 164   Phi3->setIncomingValue(0, Val1);
 165   PV.invalidateValue(Phi3);
 166   Vals = PV.getValuesForPhi(Phi1);
 167   EXPECT_EQ(Vals.size(), 2u);
 168   EXPECT_TRUE(Vals.count(Val4));
 169   EXPECT_TRUE(Vals.count(Val2));
 170   Vals = PV.getValuesForPhi(Phi2);
 171   EXPECT_EQ(Vals.size(), 2u);
 172   EXPECT_TRUE(Vals.count(Val2));
 173   EXPECT_TRUE(Vals.count(Val3));
 174   Vals = PV.getValuesForPhi(Phi3);
 175   EXPECT_EQ(Vals.size(), 2u);
 176   EXPECT_TRUE(Vals.count(Val1));
 177   EXPECT_TRUE(Vals.count(Val3));
 178
 179   // Check that adding a phi as an incoming value works
 180   Phi3->setIncomingValue(1, Phi2);
 181   PV.invalidateValue(Phi3);
 182   Vals = PV.getValuesForPhi(Phi1);
 183   EXPECT_EQ(Vals.size(), 2u);
 184   EXPECT_TRUE(Vals.count(Val4));
 185   EXPECT_TRUE(Vals.count(Val2));
 186   Vals = PV.getValuesForPhi(Phi2);
 187   EXPECT_EQ(Vals.size(), 2u);
 188   EXPECT_TRUE(Vals.count(Val2));
 189   EXPECT_TRUE(Vals.count(Val3));
 190   Vals = PV.getValuesForPhi(Phi3);
 191   EXPECT_EQ(Vals.size(), 3u);
 192   EXPECT_TRUE(Vals.count(Val1));
 193   EXPECT_TRUE(Vals.count(Val2));
 194   EXPECT_TRUE(Vals.count(Val3));
 195
 196   // Check that replacing an incoming phi then deleting it works
 197   Phi3->setIncomingValue(1, Val2);
 198   PV.invalidateValue(Phi2);
 199   Phi2->eraseFromParent();
 200   PV.invalidateValue(Phi3);
 201   Vals = PV.getValuesForPhi(Phi1);
 202   EXPECT_EQ(Vals.size(), 2u);
 203   EXPECT_TRUE(Vals.count(Val4));
 204   EXPECT_TRUE(Vals.count(Val2));
 205   Vals = PV.getValuesForPhi(Phi3);
 206   EXPECT_EQ(Vals.size(), 2u);
 207   EXPECT_TRUE(Vals.count(Val1));
 208   EXPECT_TRUE(Vals.count(Val2));
 209 }