unittests/IR/DominatorTreeTest.cpp

   1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants 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/Dominators.h"
  11 #include "llvm/Assembly/Parser.h"
  12 #include "llvm/IR/Instructions.h"
  13 #include "llvm/IR/LLVMContext.h"
  14 #include "llvm/IR/Module.h"
  15 #include "llvm/PassManager.h"
  16 #include "llvm/Support/SourceMgr.h"
  17 #include "gtest/gtest.h"
  18
  19 using namespace llvm;
  20
  21 namespace llvm {
  22   void initializeDPassPass(PassRegistry&);
  23
  24   namespace {
  25     struct DPass : public FunctionPass {
  26       static char ID;
  27       virtual bool runOnFunction(Function &F) {
  28         DominatorTree *DT = &getAnalysis<DominatorTree>();
  29         Function::iterator FI = F.begin();
  30
  31         BasicBlock *BB0 = FI++;
  32         BasicBlock::iterator BBI = BB0->begin();
  33         Instruction *Y1 = BBI++;
  34         Instruction *Y2 = BBI++;
  35         Instruction *Y3 = BBI++;
  36
  37         BasicBlock *BB1 = FI++;
  38         BBI = BB1->begin();
  39         Instruction *Y4 = BBI++;
  40
  41         BasicBlock *BB2 = FI++;
  42         BBI = BB2->begin();
  43         Instruction *Y5 = BBI++;
  44
  45         BasicBlock *BB3 = FI++;
  46         BBI = BB3->begin();
  47         Instruction *Y6 = BBI++;
  48         Instruction *Y7 = BBI++;
  49
  50         BasicBlock *BB4 = FI++;
  51         BBI = BB4->begin();
  52         Instruction *Y8 = BBI++;
  53         Instruction *Y9 = BBI++;
  54
  55         // Reachability
  56         EXPECT_TRUE(DT->isReachableFromEntry(BB0));
  57         EXPECT_TRUE(DT->isReachableFromEntry(BB1));
  58         EXPECT_TRUE(DT->isReachableFromEntry(BB2));
  59         EXPECT_FALSE(DT->isReachableFromEntry(BB3));
  60         EXPECT_TRUE(DT->isReachableFromEntry(BB4));
  61
  62         // BB dominance
  63         EXPECT_TRUE(DT->dominates(BB0, BB0));
  64         EXPECT_TRUE(DT->dominates(BB0, BB1));
  65         EXPECT_TRUE(DT->dominates(BB0, BB2));
  66         EXPECT_TRUE(DT->dominates(BB0, BB3));
  67         EXPECT_TRUE(DT->dominates(BB0, BB4));
  68
  69         EXPECT_FALSE(DT->dominates(BB1, BB0));
  70         EXPECT_TRUE(DT->dominates(BB1, BB1));
  71         EXPECT_FALSE(DT->dominates(BB1, BB2));
  72         EXPECT_TRUE(DT->dominates(BB1, BB3));
  73         EXPECT_FALSE(DT->dominates(BB1, BB4));
  74
  75         EXPECT_FALSE(DT->dominates(BB2, BB0));
  76         EXPECT_FALSE(DT->dominates(BB2, BB1));
  77         EXPECT_TRUE(DT->dominates(BB2, BB2));
  78         EXPECT_TRUE(DT->dominates(BB2, BB3));
  79         EXPECT_FALSE(DT->dominates(BB2, BB4));
  80
  81         EXPECT_FALSE(DT->dominates(BB3, BB0));
  82         EXPECT_FALSE(DT->dominates(BB3, BB1));
  83         EXPECT_FALSE(DT->dominates(BB3, BB2));
  84         EXPECT_TRUE(DT->dominates(BB3, BB3));
  85         EXPECT_FALSE(DT->dominates(BB3, BB4));
  86
  87         // BB proper dominance
  88         EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
  89         EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
  90         EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
  91         EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
  92
  93         EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
  94         EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
  95         EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
  96         EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
  97
  98         EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
  99         EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
 100         EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
 101         EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
 102
 103         EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
 104         EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
 105         EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
 106         EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
 107
 108         // Instruction dominance in the same reachable BB
 109         EXPECT_FALSE(DT->dominates(Y1, Y1));
 110         EXPECT_TRUE(DT->dominates(Y1, Y2));
 111         EXPECT_FALSE(DT->dominates(Y2, Y1));
 112         EXPECT_FALSE(DT->dominates(Y2, Y2));
 113
 114         // Instruction dominance in the same unreachable BB
 115         EXPECT_TRUE(DT->dominates(Y6, Y6));
 116         EXPECT_TRUE(DT->dominates(Y6, Y7));
 117         EXPECT_TRUE(DT->dominates(Y7, Y6));
 118         EXPECT_TRUE(DT->dominates(Y7, Y7));
 119
 120         // Invoke
 121         EXPECT_TRUE(DT->dominates(Y3, Y4));
 122         EXPECT_FALSE(DT->dominates(Y3, Y5));
 123
 124         // Phi
 125         EXPECT_TRUE(DT->dominates(Y2, Y9));
 126         EXPECT_FALSE(DT->dominates(Y3, Y9));
 127         EXPECT_FALSE(DT->dominates(Y8, Y9));
 128
 129         // Anything dominates unreachable
 130         EXPECT_TRUE(DT->dominates(Y1, Y6));
 131         EXPECT_TRUE(DT->dominates(Y3, Y6));
 132
 133         // Unreachable doesn't dominate reachable
 134         EXPECT_FALSE(DT->dominates(Y6, Y1));
 135
 136         // Instruction, BB dominance
 137         EXPECT_FALSE(DT->dominates(Y1, BB0));
 138         EXPECT_TRUE(DT->dominates(Y1, BB1));
 139         EXPECT_TRUE(DT->dominates(Y1, BB2));
 140         EXPECT_TRUE(DT->dominates(Y1, BB3));
 141         EXPECT_TRUE(DT->dominates(Y1, BB4));
 142
 143         EXPECT_FALSE(DT->dominates(Y3, BB0));
 144         EXPECT_TRUE(DT->dominates(Y3, BB1));
 145         EXPECT_FALSE(DT->dominates(Y3, BB2));
 146         EXPECT_TRUE(DT->dominates(Y3, BB3));
 147         EXPECT_FALSE(DT->dominates(Y3, BB4));
 148
 149         EXPECT_TRUE(DT->dominates(Y6, BB3));
 150
 151         return false;
 152       }
 153       virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 154         AU.addRequired<DominatorTree>();
 155       }
 156       DPass() : FunctionPass(ID) {
 157         initializeDPassPass(*PassRegistry::getPassRegistry());
 158       }
 159     };
 160     char DPass::ID = 0;
 161
 162
 163     Module* makeLLVMModule(DPass *P) {
 164       const char *ModuleStrig =
 165         "declare i32 @g()\n" \
 166         "define void @f(i32 %x) {\n" \
 167         "bb0:\n" \
 168         "  %y1 = add i32 %x, 1\n" \
 169         "  %y2 = add i32 %x, 1\n" \
 170         "  %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \
 171         "bb1:\n" \
 172         "  %y4 = add i32 %x, 1\n" \
 173         "  br label %bb4\n" \
 174         "bb2:\n" \
 175         "  %y5 = landingpad i32 personality i32 ()* @g\n" \
 176         "          cleanup\n" \
 177         "  br label %bb4\n" \
 178         "bb3:\n" \
 179         "  %y6 = add i32 %x, 1\n" \
 180         "  %y7 = add i32 %x, 1\n" \
 181         "  ret void\n" \
 182         "bb4:\n" \
 183         "  %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
 184         "  %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
 185         "  ret void\n" \
 186         "}\n";
 187       LLVMContext &C = getGlobalContext();
 188       SMDiagnostic Err;
 189       return ParseAssemblyString(ModuleStrig, NULL, Err, C);
 190     }
 191
 192     TEST(DominatorTree, Unreachable) {
 193       DPass *P = new DPass();
 194       OwningPtr<Module> M(makeLLVMModule(P));
 195       PassManager Passes;
 196       Passes.add(P);
 197       Passes.run(*M);
 198     }
 199   }
 200 }
 201
 202 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
 203 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 204 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)