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/Constants.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 *PtrTy = PointerType::get(C, AddressSpace: 0); |
28 | |
29 | // Create a function with phis that do not have other phis as incoming values |
30 | Function *F = Function::Create(Ty: FunctionType::get(Result: VoidTy, isVarArg: false), |
31 | Linkage: Function::ExternalLinkage, N: "f" , M); |
32 | |
33 | BasicBlock *Entry = BasicBlock::Create(Context&: C, Name: "entry" , Parent: F); |
34 | BasicBlock *If = BasicBlock::Create(Context&: C, Name: "if" , Parent: F); |
35 | BasicBlock *Else = BasicBlock::Create(Context&: C, Name: "else" , Parent: F); |
36 | BasicBlock *Then = BasicBlock::Create(Context&: C, Name: "then" , Parent: F); |
37 | BranchInst::Create(IfTrue: If, IfFalse: Else, Cond: UndefValue::get(T: I1Ty), InsertAtEnd: Entry); |
38 | BranchInst::Create(IfTrue: Then, InsertAtEnd: If); |
39 | BranchInst::Create(IfTrue: Then, InsertAtEnd: Else); |
40 | |
41 | Value *Val1 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val1" , Entry); |
42 | Value *Val2 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val2" , Entry); |
43 | Value *Val3 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val3" , Entry); |
44 | Value *Val4 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val4" , Entry); |
45 | |
46 | PHINode *Phi1 = PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: "phi1" , InsertAtEnd: Then); |
47 | Phi1->addIncoming(V: Val1, BB: If); |
48 | Phi1->addIncoming(V: Val2, BB: Else); |
49 | PHINode *Phi2 = PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: "phi2" , InsertAtEnd: Then); |
50 | Phi2->addIncoming(V: Val1, BB: If); |
51 | Phi2->addIncoming(V: Val3, BB: Else); |
52 | |
53 | PhiValues PV(*F); |
54 | PhiValues::ValueSet Vals; |
55 | |
56 | // Check that simple usage works |
57 | Vals = PV.getValuesForPhi(PN: Phi1); |
58 | EXPECT_EQ(Vals.size(), 2u); |
59 | EXPECT_TRUE(Vals.count(Val1)); |
60 | EXPECT_TRUE(Vals.count(Val2)); |
61 | Vals = PV.getValuesForPhi(PN: Phi2); |
62 | EXPECT_EQ(Vals.size(), 2u); |
63 | EXPECT_TRUE(Vals.count(Val1)); |
64 | EXPECT_TRUE(Vals.count(Val3)); |
65 | |
66 | // Check that values are updated when one value is replaced with another |
67 | Val1->replaceAllUsesWith(V: Val4); |
68 | PV.invalidateValue(V: Val1); |
69 | Vals = PV.getValuesForPhi(PN: Phi1); |
70 | EXPECT_EQ(Vals.size(), 2u); |
71 | EXPECT_TRUE(Vals.count(Val4)); |
72 | EXPECT_TRUE(Vals.count(Val2)); |
73 | Vals = PV.getValuesForPhi(PN: Phi2); |
74 | EXPECT_EQ(Vals.size(), 2u); |
75 | EXPECT_TRUE(Vals.count(Val4)); |
76 | EXPECT_TRUE(Vals.count(Val3)); |
77 | |
78 | // Check that setting in incoming value directly updates the values |
79 | Phi1->setIncomingValue(i: 0, V: Val1); |
80 | PV.invalidateValue(V: Phi1); |
81 | Vals = PV.getValuesForPhi(PN: Phi1); |
82 | EXPECT_EQ(Vals.size(), 2u); |
83 | EXPECT_TRUE(Vals.count(Val1)); |
84 | EXPECT_TRUE(Vals.count(Val2)); |
85 | } |
86 | |
87 | TEST(PhiValuesTest, DependentPhi) { |
88 | LLVMContext C; |
89 | Module M("PhiValuesTest" , C); |
90 | |
91 | Type *VoidTy = Type::getVoidTy(C); |
92 | Type *I1Ty = Type::getInt1Ty(C); |
93 | Type *I32Ty = Type::getInt32Ty(C); |
94 | Type *PtrTy = PointerType::get(C, AddressSpace: 0); |
95 | |
96 | // Create a function with a phi that has another phi as an incoming value |
97 | Function *F = Function::Create(Ty: FunctionType::get(Result: VoidTy, isVarArg: false), |
98 | Linkage: Function::ExternalLinkage, N: "f" , M); |
99 | |
100 | BasicBlock *Entry = BasicBlock::Create(Context&: C, Name: "entry" , Parent: F); |
101 | BasicBlock *If1 = BasicBlock::Create(Context&: C, Name: "if1" , Parent: F); |
102 | BasicBlock *Else1 = BasicBlock::Create(Context&: C, Name: "else1" , Parent: F); |
103 | BasicBlock *Then = BasicBlock::Create(Context&: C, Name: "then" , Parent: F); |
104 | BasicBlock *If2 = BasicBlock::Create(Context&: C, Name: "if2" , Parent: F); |
105 | BasicBlock *Else2 = BasicBlock::Create(Context&: C, Name: "else2" , Parent: F); |
106 | BasicBlock *End = BasicBlock::Create(Context&: C, Name: "then" , Parent: F); |
107 | BranchInst::Create(IfTrue: If1, IfFalse: Else1, Cond: UndefValue::get(T: I1Ty), InsertAtEnd: Entry); |
108 | BranchInst::Create(IfTrue: Then, InsertAtEnd: If1); |
109 | BranchInst::Create(IfTrue: Then, InsertAtEnd: Else1); |
110 | BranchInst::Create(IfTrue: If2, IfFalse: Else2, Cond: UndefValue::get(T: I1Ty), InsertAtEnd: Then); |
111 | BranchInst::Create(IfTrue: End, InsertAtEnd: If2); |
112 | BranchInst::Create(IfTrue: End, InsertAtEnd: Else2); |
113 | |
114 | Value *Val1 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val1" , Entry); |
115 | Value *Val2 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val2" , Entry); |
116 | Value *Val3 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val3" , Entry); |
117 | Value *Val4 = new LoadInst(I32Ty, UndefValue::get(T: PtrTy), "val4" , Entry); |
118 | |
119 | PHINode *Phi1 = PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: "phi1" , InsertAtEnd: Then); |
120 | Phi1->addIncoming(V: Val1, BB: If1); |
121 | Phi1->addIncoming(V: Val2, BB: Else1); |
122 | PHINode *Phi2 = PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: "phi2" , InsertAtEnd: Then); |
123 | Phi2->addIncoming(V: Val2, BB: If1); |
124 | Phi2->addIncoming(V: Val3, BB: Else1); |
125 | PHINode *Phi3 = PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: "phi3" , InsertAtEnd: End); |
126 | Phi3->addIncoming(V: Phi1, BB: If2); |
127 | Phi3->addIncoming(V: Val3, BB: Else2); |
128 | |
129 | PhiValues PV(*F); |
130 | PhiValues::ValueSet Vals; |
131 | |
132 | // Check that simple usage works |
133 | Vals = PV.getValuesForPhi(PN: Phi1); |
134 | EXPECT_EQ(Vals.size(), 2u); |
135 | EXPECT_TRUE(Vals.count(Val1)); |
136 | EXPECT_TRUE(Vals.count(Val2)); |
137 | Vals = PV.getValuesForPhi(PN: Phi2); |
138 | EXPECT_EQ(Vals.size(), 2u); |
139 | EXPECT_TRUE(Vals.count(Val2)); |
140 | EXPECT_TRUE(Vals.count(Val3)); |
141 | Vals = PV.getValuesForPhi(PN: Phi3); |
142 | EXPECT_EQ(Vals.size(), 3u); |
143 | EXPECT_TRUE(Vals.count(Val1)); |
144 | EXPECT_TRUE(Vals.count(Val2)); |
145 | EXPECT_TRUE(Vals.count(Val3)); |
146 | |
147 | // Check that changing an incoming value in the dependent phi changes the depending phi |
148 | Phi1->setIncomingValue(i: 0, V: Val4); |
149 | PV.invalidateValue(V: Phi1); |
150 | Vals = PV.getValuesForPhi(PN: Phi1); |
151 | EXPECT_EQ(Vals.size(), 2u); |
152 | EXPECT_TRUE(Vals.count(Val4)); |
153 | EXPECT_TRUE(Vals.count(Val2)); |
154 | Vals = PV.getValuesForPhi(PN: Phi2); |
155 | EXPECT_EQ(Vals.size(), 2u); |
156 | EXPECT_TRUE(Vals.count(Val2)); |
157 | EXPECT_TRUE(Vals.count(Val3)); |
158 | Vals = PV.getValuesForPhi(PN: Phi3); |
159 | EXPECT_EQ(Vals.size(), 3u); |
160 | EXPECT_TRUE(Vals.count(Val4)); |
161 | EXPECT_TRUE(Vals.count(Val2)); |
162 | EXPECT_TRUE(Vals.count(Val3)); |
163 | |
164 | // Check that replacing an incoming phi with a value works |
165 | Phi3->setIncomingValue(i: 0, V: Val1); |
166 | PV.invalidateValue(V: Phi3); |
167 | Vals = PV.getValuesForPhi(PN: Phi1); |
168 | EXPECT_EQ(Vals.size(), 2u); |
169 | EXPECT_TRUE(Vals.count(Val4)); |
170 | EXPECT_TRUE(Vals.count(Val2)); |
171 | Vals = PV.getValuesForPhi(PN: Phi2); |
172 | EXPECT_EQ(Vals.size(), 2u); |
173 | EXPECT_TRUE(Vals.count(Val2)); |
174 | EXPECT_TRUE(Vals.count(Val3)); |
175 | Vals = PV.getValuesForPhi(PN: Phi3); |
176 | EXPECT_EQ(Vals.size(), 2u); |
177 | EXPECT_TRUE(Vals.count(Val1)); |
178 | EXPECT_TRUE(Vals.count(Val3)); |
179 | |
180 | // Check that adding a phi as an incoming value works |
181 | Phi3->setIncomingValue(i: 1, V: Phi2); |
182 | PV.invalidateValue(V: Phi3); |
183 | Vals = PV.getValuesForPhi(PN: Phi1); |
184 | EXPECT_EQ(Vals.size(), 2u); |
185 | EXPECT_TRUE(Vals.count(Val4)); |
186 | EXPECT_TRUE(Vals.count(Val2)); |
187 | Vals = PV.getValuesForPhi(PN: Phi2); |
188 | EXPECT_EQ(Vals.size(), 2u); |
189 | EXPECT_TRUE(Vals.count(Val2)); |
190 | EXPECT_TRUE(Vals.count(Val3)); |
191 | Vals = PV.getValuesForPhi(PN: Phi3); |
192 | EXPECT_EQ(Vals.size(), 3u); |
193 | EXPECT_TRUE(Vals.count(Val1)); |
194 | EXPECT_TRUE(Vals.count(Val2)); |
195 | EXPECT_TRUE(Vals.count(Val3)); |
196 | |
197 | // Check that replacing an incoming phi then deleting it works |
198 | Phi3->setIncomingValue(i: 1, V: Val2); |
199 | PV.invalidateValue(V: Phi2); |
200 | Phi2->eraseFromParent(); |
201 | PV.invalidateValue(V: Phi3); |
202 | Vals = PV.getValuesForPhi(PN: Phi1); |
203 | EXPECT_EQ(Vals.size(), 2u); |
204 | EXPECT_TRUE(Vals.count(Val4)); |
205 | EXPECT_TRUE(Vals.count(Val2)); |
206 | Vals = PV.getValuesForPhi(PN: Phi3); |
207 | EXPECT_EQ(Vals.size(), 2u); |
208 | EXPECT_TRUE(Vals.count(Val1)); |
209 | EXPECT_TRUE(Vals.count(Val2)); |
210 | } |
211 | |