1f4a2713aSLionel Sambuc //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// 2f4a2713aSLionel Sambuc // 3f4a2713aSLionel Sambuc // The LLVM Compiler Infrastructure 4f4a2713aSLionel Sambuc // 5f4a2713aSLionel Sambuc // This file is distributed under the University of Illinois Open Source 6f4a2713aSLionel Sambuc // License. See LICENSE.TXT for details. 7f4a2713aSLionel Sambuc // 8f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===// 9f4a2713aSLionel Sambuc 10*0a6a1f1dSLionel Sambuc #include "llvm/IR/Dominators.h" 11*0a6a1f1dSLionel Sambuc #include "llvm/Analysis/PostDominators.h" 12*0a6a1f1dSLionel Sambuc #include "llvm/AsmParser/Parser.h" 13f4a2713aSLionel Sambuc #include "llvm/IR/Instructions.h" 14f4a2713aSLionel Sambuc #include "llvm/IR/LLVMContext.h" 15f4a2713aSLionel Sambuc #include "llvm/IR/Module.h" 16f4a2713aSLionel Sambuc #include "llvm/PassManager.h" 17f4a2713aSLionel Sambuc #include "llvm/Support/SourceMgr.h" 18f4a2713aSLionel Sambuc #include "gtest/gtest.h" 19f4a2713aSLionel Sambuc 20f4a2713aSLionel Sambuc using namespace llvm; 21f4a2713aSLionel Sambuc 22f4a2713aSLionel Sambuc namespace llvm { 23f4a2713aSLionel Sambuc void initializeDPassPass(PassRegistry&); 24f4a2713aSLionel Sambuc 25f4a2713aSLionel Sambuc namespace { 26f4a2713aSLionel Sambuc struct DPass : public FunctionPass { 27f4a2713aSLionel Sambuc static char ID; runOnFunctionllvm::__anond1810d3e0111::DPass28f4a2713aSLionel Sambuc virtual bool runOnFunction(Function &F) { 29*0a6a1f1dSLionel Sambuc DominatorTree *DT = 30*0a6a1f1dSLionel Sambuc &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 31*0a6a1f1dSLionel Sambuc PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>(); 32f4a2713aSLionel Sambuc Function::iterator FI = F.begin(); 33f4a2713aSLionel Sambuc 34f4a2713aSLionel Sambuc BasicBlock *BB0 = FI++; 35f4a2713aSLionel Sambuc BasicBlock::iterator BBI = BB0->begin(); 36f4a2713aSLionel Sambuc Instruction *Y1 = BBI++; 37f4a2713aSLionel Sambuc Instruction *Y2 = BBI++; 38f4a2713aSLionel Sambuc Instruction *Y3 = BBI++; 39f4a2713aSLionel Sambuc 40f4a2713aSLionel Sambuc BasicBlock *BB1 = FI++; 41f4a2713aSLionel Sambuc BBI = BB1->begin(); 42f4a2713aSLionel Sambuc Instruction *Y4 = BBI++; 43f4a2713aSLionel Sambuc 44f4a2713aSLionel Sambuc BasicBlock *BB2 = FI++; 45f4a2713aSLionel Sambuc BBI = BB2->begin(); 46f4a2713aSLionel Sambuc Instruction *Y5 = BBI++; 47f4a2713aSLionel Sambuc 48f4a2713aSLionel Sambuc BasicBlock *BB3 = FI++; 49f4a2713aSLionel Sambuc BBI = BB3->begin(); 50f4a2713aSLionel Sambuc Instruction *Y6 = BBI++; 51f4a2713aSLionel Sambuc Instruction *Y7 = BBI++; 52f4a2713aSLionel Sambuc 53f4a2713aSLionel Sambuc BasicBlock *BB4 = FI++; 54f4a2713aSLionel Sambuc BBI = BB4->begin(); 55f4a2713aSLionel Sambuc Instruction *Y8 = BBI++; 56f4a2713aSLionel Sambuc Instruction *Y9 = BBI++; 57f4a2713aSLionel Sambuc 58f4a2713aSLionel Sambuc // Reachability 59f4a2713aSLionel Sambuc EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 60f4a2713aSLionel Sambuc EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 61f4a2713aSLionel Sambuc EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 62f4a2713aSLionel Sambuc EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 63f4a2713aSLionel Sambuc EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 64f4a2713aSLionel Sambuc 65f4a2713aSLionel Sambuc // BB dominance 66f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB0, BB0)); 67f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB0, BB1)); 68f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB0, BB2)); 69f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB0, BB3)); 70f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB0, BB4)); 71f4a2713aSLionel Sambuc 72f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB1, BB0)); 73f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB1, BB1)); 74f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB1, BB2)); 75f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB1, BB3)); 76f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB1, BB4)); 77f4a2713aSLionel Sambuc 78f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB2, BB0)); 79f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB2, BB1)); 80f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB2, BB2)); 81f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB2, BB3)); 82f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB2, BB4)); 83f4a2713aSLionel Sambuc 84f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB3, BB0)); 85f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB3, BB1)); 86f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB3, BB2)); 87f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(BB3, BB3)); 88f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(BB3, BB4)); 89f4a2713aSLionel Sambuc 90f4a2713aSLionel Sambuc // BB proper dominance 91f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 92f4a2713aSLionel Sambuc EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 93f4a2713aSLionel Sambuc EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 94f4a2713aSLionel Sambuc EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 95f4a2713aSLionel Sambuc 96f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 97f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 98f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 99f4a2713aSLionel Sambuc EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 100f4a2713aSLionel Sambuc 101f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 102f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 103f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 104f4a2713aSLionel Sambuc EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 105f4a2713aSLionel Sambuc 106f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 107f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 108f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 109f4a2713aSLionel Sambuc EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 110f4a2713aSLionel Sambuc 111f4a2713aSLionel Sambuc // Instruction dominance in the same reachable BB 112f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y1, Y1)); 113f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, Y2)); 114f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y2, Y1)); 115f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y2, Y2)); 116f4a2713aSLionel Sambuc 117f4a2713aSLionel Sambuc // Instruction dominance in the same unreachable BB 118f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y6, Y6)); 119f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y6, Y7)); 120f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y7, Y6)); 121f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y7, Y7)); 122f4a2713aSLionel Sambuc 123f4a2713aSLionel Sambuc // Invoke 124f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y3, Y4)); 125f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y3, Y5)); 126f4a2713aSLionel Sambuc 127f4a2713aSLionel Sambuc // Phi 128f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y2, Y9)); 129f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y3, Y9)); 130f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y8, Y9)); 131f4a2713aSLionel Sambuc 132f4a2713aSLionel Sambuc // Anything dominates unreachable 133f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, Y6)); 134f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y3, Y6)); 135f4a2713aSLionel Sambuc 136f4a2713aSLionel Sambuc // Unreachable doesn't dominate reachable 137f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y6, Y1)); 138f4a2713aSLionel Sambuc 139f4a2713aSLionel Sambuc // Instruction, BB dominance 140f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y1, BB0)); 141f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, BB1)); 142f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, BB2)); 143f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, BB3)); 144f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y1, BB4)); 145f4a2713aSLionel Sambuc 146f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y3, BB0)); 147f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y3, BB1)); 148f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y3, BB2)); 149f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y3, BB3)); 150f4a2713aSLionel Sambuc EXPECT_FALSE(DT->dominates(Y3, BB4)); 151f4a2713aSLionel Sambuc 152f4a2713aSLionel Sambuc EXPECT_TRUE(DT->dominates(Y6, BB3)); 153f4a2713aSLionel Sambuc 154*0a6a1f1dSLionel Sambuc // Post dominance. 155*0a6a1f1dSLionel Sambuc EXPECT_TRUE(PDT->dominates(BB0, BB0)); 156*0a6a1f1dSLionel Sambuc EXPECT_FALSE(PDT->dominates(BB1, BB0)); 157*0a6a1f1dSLionel Sambuc EXPECT_FALSE(PDT->dominates(BB2, BB0)); 158*0a6a1f1dSLionel Sambuc EXPECT_FALSE(PDT->dominates(BB3, BB0)); 159*0a6a1f1dSLionel Sambuc EXPECT_TRUE(PDT->dominates(BB4, BB1)); 160*0a6a1f1dSLionel Sambuc 161*0a6a1f1dSLionel Sambuc // Dominance descendants. 162*0a6a1f1dSLionel Sambuc SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 163*0a6a1f1dSLionel Sambuc 164*0a6a1f1dSLionel Sambuc DT->getDescendants(BB0, DominatedBBs); 165*0a6a1f1dSLionel Sambuc PDT->getDescendants(BB0, PostDominatedBBs); 166*0a6a1f1dSLionel Sambuc EXPECT_EQ(DominatedBBs.size(), 4UL); 167*0a6a1f1dSLionel Sambuc EXPECT_EQ(PostDominatedBBs.size(), 1UL); 168*0a6a1f1dSLionel Sambuc 169*0a6a1f1dSLionel Sambuc // BB3 is unreachable. It should have no dominators nor postdominators. 170*0a6a1f1dSLionel Sambuc DominatedBBs.clear(); 171*0a6a1f1dSLionel Sambuc PostDominatedBBs.clear(); 172*0a6a1f1dSLionel Sambuc DT->getDescendants(BB3, DominatedBBs); 173*0a6a1f1dSLionel Sambuc DT->getDescendants(BB3, PostDominatedBBs); 174*0a6a1f1dSLionel Sambuc EXPECT_EQ(DominatedBBs.size(), 0UL); 175*0a6a1f1dSLionel Sambuc EXPECT_EQ(PostDominatedBBs.size(), 0UL); 176*0a6a1f1dSLionel Sambuc 177f4a2713aSLionel Sambuc return false; 178f4a2713aSLionel Sambuc } getAnalysisUsagellvm::__anond1810d3e0111::DPass179f4a2713aSLionel Sambuc virtual void getAnalysisUsage(AnalysisUsage &AU) const { 180*0a6a1f1dSLionel Sambuc AU.addRequired<DominatorTreeWrapperPass>(); 181*0a6a1f1dSLionel Sambuc AU.addRequired<PostDominatorTree>(); 182f4a2713aSLionel Sambuc } DPassllvm::__anond1810d3e0111::DPass183f4a2713aSLionel Sambuc DPass() : FunctionPass(ID) { 184f4a2713aSLionel Sambuc initializeDPassPass(*PassRegistry::getPassRegistry()); 185f4a2713aSLionel Sambuc } 186f4a2713aSLionel Sambuc }; 187f4a2713aSLionel Sambuc char DPass::ID = 0; 188f4a2713aSLionel Sambuc makeLLVMModule(DPass * P)189*0a6a1f1dSLionel Sambuc std::unique_ptr<Module> makeLLVMModule(DPass *P) { 190f4a2713aSLionel Sambuc const char *ModuleStrig = 191f4a2713aSLionel Sambuc "declare i32 @g()\n" \ 192f4a2713aSLionel Sambuc "define void @f(i32 %x) {\n" \ 193f4a2713aSLionel Sambuc "bb0:\n" \ 194f4a2713aSLionel Sambuc " %y1 = add i32 %x, 1\n" \ 195f4a2713aSLionel Sambuc " %y2 = add i32 %x, 1\n" \ 196f4a2713aSLionel Sambuc " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \ 197f4a2713aSLionel Sambuc "bb1:\n" \ 198f4a2713aSLionel Sambuc " %y4 = add i32 %x, 1\n" \ 199f4a2713aSLionel Sambuc " br label %bb4\n" \ 200f4a2713aSLionel Sambuc "bb2:\n" \ 201f4a2713aSLionel Sambuc " %y5 = landingpad i32 personality i32 ()* @g\n" \ 202f4a2713aSLionel Sambuc " cleanup\n" \ 203f4a2713aSLionel Sambuc " br label %bb4\n" \ 204f4a2713aSLionel Sambuc "bb3:\n" \ 205f4a2713aSLionel Sambuc " %y6 = add i32 %x, 1\n" \ 206f4a2713aSLionel Sambuc " %y7 = add i32 %x, 1\n" \ 207f4a2713aSLionel Sambuc " ret void\n" \ 208f4a2713aSLionel Sambuc "bb4:\n" \ 209f4a2713aSLionel Sambuc " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 210f4a2713aSLionel Sambuc " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 211f4a2713aSLionel Sambuc " ret void\n" \ 212f4a2713aSLionel Sambuc "}\n"; 213f4a2713aSLionel Sambuc LLVMContext &C = getGlobalContext(); 214f4a2713aSLionel Sambuc SMDiagnostic Err; 215*0a6a1f1dSLionel Sambuc return parseAssemblyString(ModuleStrig, Err, C); 216f4a2713aSLionel Sambuc } 217f4a2713aSLionel Sambuc TEST(DominatorTree,Unreachable)218f4a2713aSLionel Sambuc TEST(DominatorTree, Unreachable) { 219f4a2713aSLionel Sambuc DPass *P = new DPass(); 220*0a6a1f1dSLionel Sambuc std::unique_ptr<Module> M = makeLLVMModule(P); 221f4a2713aSLionel Sambuc PassManager Passes; 222f4a2713aSLionel Sambuc Passes.add(P); 223f4a2713aSLionel Sambuc Passes.run(*M); 224f4a2713aSLionel Sambuc } 225f4a2713aSLionel Sambuc } 226f4a2713aSLionel Sambuc } 227f4a2713aSLionel Sambuc 228f4a2713aSLionel Sambuc INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false) 229*0a6a1f1dSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 230*0a6a1f1dSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 231f4a2713aSLionel Sambuc INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false) 232