tests/test_dfg_analysis.cpp

   1 //===-- tests/test_dfg_analysis.cpp -----------------------------*- C++ -*-===//
   2 // Test of the dataflow analysis of a not totally simple function.
   3 //
   4 // Copyright (C) 2013-2014 Dirk Steinke.
   5 // See copyright and license notice in COPYRIGHT or include/jitcs.h
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "jitcs_int.h"
   9 #include "unittest.h"
  10 #include "jitcs_instructionstream.h"
  11 #include "jitcs_dumper.h"
  12 #include "jitcs_int_dfg_analysis.h"
  13 #include "jitcs_int_adt_dynslice.h"
  14
  15 using namespace jitcs;
  16
  17 static void test(UnitTest& t) {
  18   typedef void (__cdecl *FT0_c)();
  19   RefCounter<IMachineInfo> mi = host::GetMachineInfo();
  20   RefCounter<TempAllocator> alloc(new TempAllocator);
  21   {
  22     std::unique_ptr<Function> fn = mi->createFnc<FT0_c>(alloc);
  23     InstructionStreamBuffer<256> ibuf;
  24
  25     Ref<BasicBlock> bb1 = fn->getStartBlock();
  26     Ref<BasicBlock> bb2 = fn->createBasicBlock();
  27     Ref<BasicBlock> bb3 = fn->createBasicBlock();
  28     Ref<BasicBlock> bb4 = fn->createBasicBlock();
  29     Ref<BasicBlock> bb5 = fn->createBasicBlock();
  30     Ref<BasicBlock> bb6 = fn->createBasicBlock();
  31     Ref<const VirtualRegister> v1 = fn->createRegister(host::RCL_GR);
  32     Ref<const VirtualRegister> v2 = fn->createRegister(host::RCL_GR);
  33     Ref<const VirtualRegister> v3 = fn->createRegister(host::RCL_GR);
  34     Ref<const VirtualRegister> v4 = fn->createRegister(host::RCL_GR);
  35
  36     //   BB1(entry)
  37     //    |
  38     //    v
  39     //   BB2 <------.
  40     //    |---.     |
  41     //    v   v     |
  42     //   BB3  BB4   |
  43     //    |---.     |
  44     //    v         |
  45     //   BB5        |
  46     //    |---------.
  47     //    v
  48     //   BB6
  49     //    |
  50     //    v
  51     //   BB7 (exit)
  52     //
  53     // v1: induction variable, defined in BB1, used in BB5,
  54     //     live thru-out the loop
  55     // v2: defined in BB2, used in BB3, not live in any other BB
  56     // v3: defined in BB1, used in BB6, live thru-out the loop
  57     // v3: defined and used in BB4, not live anywhere else
  58
  59     ibuf.start(bb1);
  60     host::MOV_RI32U(ibuf, v1, 0);
  61     host::MOV_RI32U(ibuf, v3, 4);
  62     host::JMP_FT(ibuf, bb2);
  63     ibuf.end();
  64
  65     ibuf.start(bb2);
  66     host::MOV_RI32U(ibuf, v2, 1);
  67     host::CMP_RI(ibuf, v1, 5);
  68     host::JGE_BB_FT(ibuf, bb4, bb3);
  69     ibuf.end();
  70
  71     ibuf.start(bb3);
  72     host::ADD_RR(ibuf, v1, v2);
  73     host::JMP_BB(ibuf, bb5);
  74     ibuf.end();
  75
  76     ibuf.start(bb4);
  77     host::MOV_RI32U(ibuf, v4, 2);
  78     host::ADD_RR(ibuf, v1, v4);
  79     host::JMP_FT(ibuf, bb5);
  80     ibuf.end();
  81
  82     ibuf.start(bb5);
  83     host::ADD_RI(ibuf, v1, 1);
  84     host::CMP_RI(ibuf, v1, 100);
  85     host::JB_BB_FT(ibuf, bb2, bb6);
  86     ibuf.end();
  87
  88     ibuf.start(bb6);
  89     host::MOV_RR(ibuf, host::EAX, v3);
  90     host::RET(ibuf);
  91     ibuf.end();
  92
  93     DynSlice<u32,8> touchedFixed(mi->details()->getResClassCount());
  94     DFGAnalysis a;
  95     a.init(reinterpret_cast<FunctionImpl&>(*fn), DFGAnalysis::M_Global,
  96            touchedFixed);
  97
  98     t.check("v1/bb1/use", !a.isUsed(bb1, v1));
  99     t.check("v1/bb1/def", a.isDefined(bb1, v1));
 100     t.check("v1/bb1/live-in", !a.isLiveIn(bb1, v1));
 101     t.check("v1/bb1/live-out", a.isLiveOut(bb1, v1));
 102
 103     t.check("v1/bb2/use", a.isUsed(bb2, v1));
 104     t.check("v1/bb2/def", !a.isDefined(bb2, v1));
 105     t.check("v1/bb2/live-in", a.isLiveIn(bb2, v1));
 106     t.check("v1/bb2/live-out", a.isLiveOut(bb2, v1));
 107
 108     t.check("v1/bb3/use", a.isUsed(bb3, v1));
 109     t.check("v1/bb3/def", a.isDefined(bb3, v1));
 110     t.check("v1/bb3/live-in", a.isLiveIn(bb3, v1));
 111     t.check("v1/bb3/live-out", a.isLiveOut(bb3, v1));
 112
 113     t.check("v1/bb4/use", a.isUsed(bb4, v1));
 114     t.check("v1/bb4/def", a.isDefined(bb4, v1));
 115     t.check("v1/bb4/live-in", a.isLiveIn(bb4, v1));
 116     t.check("v1/bb4/live-out", a.isLiveOut(bb4, v1));
 117
 118     t.check("v1/bb5/use", a.isUsed(bb5, v1));
 119     t.check("v1/bb5/def", a.isDefined(bb5, v1));
 120     t.check("v1/bb5/live-in", a.isLiveIn(bb5, v1));
 121     t.check("v1/bb5/live-out", a.isLiveOut(bb5, v1));
 122
 123     t.check("v1/bb6/use", !a.isUsed(bb6, v1));
 124     t.check("v1/bb6/def", !a.isDefined(bb6, v1));
 125     t.check("v1/bb6/live-in", !a.isLiveIn(bb6, v1));
 126     t.check("v1/bb6/live-out", !a.isLiveOut(bb6, v1));
 127
 128     t.check("v2/bb2/use", !a.isUsed(bb2, v2));
 129     t.check("v2/bb2/def", a.isDefined(bb2, v2));
 130     t.check("v2/bb2/live-in", !a.isLiveIn(bb2, v2));
 131     t.check("v2/bb2/live-out", a.isLiveOut(bb2, v2));
 132
 133     t.check("v2/bb3/use", a.isUsed(bb3, v2));
 134     t.check("v2/bb3/def", !a.isDefined(bb3, v2));
 135     t.check("v2/bb3/live-in", a.isLiveIn(bb3, v2));
 136     t.check("v2/bb3/live-out", !a.isLiveOut(bb3, v2));
 137
 138     t.check("v2/bb4/use", !a.isUsed(bb4, v2));
 139     t.check("v2/bb4/def", !a.isDefined(bb4, v2));
 140     t.check("v2/bb4/live-in", !a.isLiveIn(bb4, v2));
 141     t.check("v2/bb4/live-out", !a.isLiveOut(bb4, v2));
 142
 143     t.check("v2/bb5/use", !a.isUsed(bb5, v2));
 144     t.check("v2/bb5/def", !a.isDefined(bb5, v2));
 145     t.check("v2/bb5/live-in", !a.isLiveIn(bb5, v2));
 146     t.check("v2/bb5/live-out", !a.isLiveOut(bb5, v2));
 147
 148     t.check("v3/bb1/use", !a.isUsed(bb1, v3));
 149     t.check("v3/bb1/def", a.isDefined(bb1, v3));
 150     t.check("v3/bb1/live-in", !a.isLiveIn(bb1, v3));
 151     t.check("v3/bb1/live-out", a.isLiveOut(bb1, v3));
 152
 153     t.check("v3/bb2/use", !a.isUsed(bb2, v3));
 154     t.check("v3/bb2/def", !a.isDefined(bb2, v3));
 155     t.check("v3/bb2/live-in", a.isLiveIn(bb2, v3));
 156     t.check("v3/bb2/live-out", a.isLiveOut(bb2, v3));
 157
 158     t.check("v3/bb5/use", !a.isUsed(bb5, v3));
 159     t.check("v3/bb5/def", !a.isDefined(bb5, v3));
 160     t.check("v3/bb5/live-in", a.isLiveIn(bb5, v3));
 161     t.check("v3/bb5/live-out", a.isLiveOut(bb5, v3));
 162
 163     t.check("v3/bb6/use", a.isUsed(bb6, v3));
 164     t.check("v3/bb6/def", !a.isDefined(bb6, v3));
 165     t.check("v3/bb6/live-in", a.isLiveIn(bb6, v3));
 166     t.check("v3/bb6/live-out", !a.isLiveOut(bb6, v3));
 167
 168     t.check("v4/bb4/use", !a.isUsed(bb4, v4));
 169     t.check("v4/bb4/def", a.isDefined(bb4, v4));
 170     t.check("v4/bb4/live-in", !a.isLiveIn(bb4, v4));
 171     t.check("v4/bb4/live-out", !a.isLiveOut(bb4, v4));
 172
 173     u32 d = host::ResClassInfoCT<host::RESCL_GRRSC>::RES_Idx;
 174     u32 tf_gr = touchedFixed[host::RESCL_GRRSC];
 175     t.check("fixed/eax", (tf_gr & (1 << (host::RegInfoCT<host::R_EAX>::RES_Id - d))) != 0);
 176     t.check("fixed/edx", (tf_gr & (1 << (host::RegInfoCT<host::R_EDX>::RES_Id - d))) == 0);
 177   }
 178 }
 179
 180 static UnitTestRun _("DFG Analysis", test);