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 } 209