llvm/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/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, 0);
  28
  29   // Create a function with phis that do not have other phis as incoming values
  30   Function *F = Function::Create(FunctionType::get(VoidTy, false),
  31                                  Function::ExternalLinkage, "f", M);
  32
  33   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
  34   BasicBlock *If = BasicBlock::Create(C, "if", F);
  35   BasicBlock *Else = BasicBlock::Create(C, "else", F);
  36   BasicBlock *Then = BasicBlock::Create(C, "then", F);
  37   BranchInst::Create(If, Else, PoisonValue::get(I1Ty), Entry);
  38   BranchInst::Create(Then, If);
  39   BranchInst::Create(Then, Else);
  40
  41   Value *Val1 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val1", Entry);
  42   Value *Val2 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val2", Entry);
  43   Value *Val3 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val3", Entry);
  44   Value *Val4 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val4", Entry);
  45
  46   PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
  47   Phi1->addIncoming(Val1, If);
  48   Phi1->addIncoming(Val2, Else);
  49   PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
  50   Phi2->addIncoming(Val1, If);
  51   Phi2->addIncoming(Val3, Else);
  52
  53   PhiValues PV(*F);
  54   PhiValues::ValueSet Vals;
  55
  56   // Check that simple usage works
  57   Vals = PV.getValuesForPhi(Phi1);
  58   EXPECT_EQ(Vals.size(), 2u);
  59   EXPECT_TRUE(Vals.count(Val1));
  60   EXPECT_TRUE(Vals.count(Val2));
  61   Vals = PV.getValuesForPhi(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(Val4);
  68   PV.invalidateValue(Val1);
  69   Vals = PV.getValuesForPhi(Phi1);
  70   EXPECT_EQ(Vals.size(), 2u);
  71   EXPECT_TRUE(Vals.count(Val4));
  72   EXPECT_TRUE(Vals.count(Val2));
  73   Vals = PV.getValuesForPhi(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(0, Val1);
  80   PV.invalidateValue(Phi1);
  81   Vals = PV.getValuesForPhi(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, 0);
  95
  96   // Create a function with a phi that has another phi as an incoming value
  97   Function *F = Function::Create(FunctionType::get(VoidTy, false),
  98                                  Function::ExternalLinkage, "f", M);
  99
 100   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
 101   BasicBlock *If1 = BasicBlock::Create(C, "if1", F);
 102   BasicBlock *Else1 = BasicBlock::Create(C, "else1", F);
 103   BasicBlock *Then = BasicBlock::Create(C, "then", F);
 104   BasicBlock *If2 = BasicBlock::Create(C, "if2", F);
 105   BasicBlock *Else2 = BasicBlock::Create(C, "else2", F);
 106   BasicBlock *End = BasicBlock::Create(C, "then", F);
 107   BranchInst::Create(If1, Else1, PoisonValue::get(I1Ty), Entry);
 108   BranchInst::Create(Then, If1);
 109   BranchInst::Create(Then, Else1);
 110   BranchInst::Create(If2, Else2, PoisonValue::get(I1Ty), Then);
 111   BranchInst::Create(End, If2);
 112   BranchInst::Create(End, Else2);
 113
 114   Value *Val1 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val1", Entry);
 115   Value *Val2 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val2", Entry);
 116   Value *Val3 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val3", Entry);
 117   Value *Val4 = new LoadInst(I32Ty, PoisonValue::get(PtrTy), "val4", Entry);
 118
 119   PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
 120   Phi1->addIncoming(Val1, If1);
 121   Phi1->addIncoming(Val2, Else1);
 122   PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
 123   Phi2->addIncoming(Val2, If1);
 124   Phi2->addIncoming(Val3, Else1);
 125   PHINode *Phi3 = PHINode::Create(I32Ty, 2, "phi3", End);
 126   Phi3->addIncoming(Phi1, If2);
 127   Phi3->addIncoming(Val3, Else2);
 128
 129   PhiValues PV(*F);
 130   PhiValues::ValueSet Vals;
 131
 132   // Check that simple usage works
 133   Vals = PV.getValuesForPhi(Phi1);
 134   EXPECT_EQ(Vals.size(), 2u);
 135   EXPECT_TRUE(Vals.count(Val1));
 136   EXPECT_TRUE(Vals.count(Val2));
 137   Vals = PV.getValuesForPhi(Phi2);
 138   EXPECT_EQ(Vals.size(), 2u);
 139   EXPECT_TRUE(Vals.count(Val2));
 140   EXPECT_TRUE(Vals.count(Val3));
 141   Vals = PV.getValuesForPhi(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(0, Val4);
 149   PV.invalidateValue(Phi1);
 150   Vals = PV.getValuesForPhi(Phi1);
 151   EXPECT_EQ(Vals.size(), 2u);
 152   EXPECT_TRUE(Vals.count(Val4));
 153   EXPECT_TRUE(Vals.count(Val2));
 154   Vals = PV.getValuesForPhi(Phi2);
 155   EXPECT_EQ(Vals.size(), 2u);
 156   EXPECT_TRUE(Vals.count(Val2));
 157   EXPECT_TRUE(Vals.count(Val3));
 158   Vals = PV.getValuesForPhi(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(0, Val1);
 166   PV.invalidateValue(Phi3);
 167   Vals = PV.getValuesForPhi(Phi1);
 168   EXPECT_EQ(Vals.size(), 2u);
 169   EXPECT_TRUE(Vals.count(Val4));
 170   EXPECT_TRUE(Vals.count(Val2));
 171   Vals = PV.getValuesForPhi(Phi2);
 172   EXPECT_EQ(Vals.size(), 2u);
 173   EXPECT_TRUE(Vals.count(Val2));
 174   EXPECT_TRUE(Vals.count(Val3));
 175   Vals = PV.getValuesForPhi(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(1, Phi2);
 182   PV.invalidateValue(Phi3);
 183   Vals = PV.getValuesForPhi(Phi1);
 184   EXPECT_EQ(Vals.size(), 2u);
 185   EXPECT_TRUE(Vals.count(Val4));
 186   EXPECT_TRUE(Vals.count(Val2));
 187   Vals = PV.getValuesForPhi(Phi2);
 188   EXPECT_EQ(Vals.size(), 2u);
 189   EXPECT_TRUE(Vals.count(Val2));
 190   EXPECT_TRUE(Vals.count(Val3));
 191   Vals = PV.getValuesForPhi(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(1, Val2);
 199   PV.invalidateValue(Phi2);
 200   Phi2->eraseFromParent();
 201   PV.invalidateValue(Phi3);
 202   Vals = PV.getValuesForPhi(Phi1);
 203   EXPECT_EQ(Vals.size(), 2u);
 204   EXPECT_TRUE(Vals.count(Val4));
 205   EXPECT_TRUE(Vals.count(Val2));
 206   Vals = PV.getValuesForPhi(Phi3);
 207   EXPECT_EQ(Vals.size(), 2u);
 208   EXPECT_TRUE(Vals.count(Val1));
 209   EXPECT_TRUE(Vals.count(Val2));
 210 }