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 
TEST(PhiValuesTest,SimplePhi)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 
TEST(PhiValuesTest,DependentPhi)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 }
210