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
TEST(PhiValuesTest,SimplePhi)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
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 = 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 }
209