unittests/VMCore/DominatorTreeTest.cpp

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