nsz Git - libfirm/blob - ir/be/test/pbqpHeur3.c

   1 /**
   2  * This test case shows that it's not possible to find a PBQP solution for
   3  * arbitrary pattern sets.
   4  *
   5  * To get infinity costs you have to remove the following Lea rules:
   6  * - Add(Shl(ShiftConst(), index=IR_node()), imm=Const())
   7  * - Add(Shl(ShiftConst(), index=IR_node()), base=IR_node())
   8  *
   9  * You also have to use the following compiler flags:
  10  * -O3 -fno-reassociation
  11  *
  12  * For more details take a look at the diamond function.
  13  */
  14 unsigned   a;
  15 unsigned   b;
  16 unsigned  *gi1, gi2, gi3, gi4, gi5;
  17 unsigned  *gi101, gi102, gi103, gi104, gi105;
  18 unsigned  *gi201, gi202, gi203, gi204, gi205;
  19 unsigned  *gi211, gi212, gi213, gi214, gi215;
  20 unsigned  *gi301, gi302, gi303, gi304, gi305;
  21 unsigned  *gi311, gi312, gi313, gi314, gi315;
  22 unsigned  *gi401, gi402, gi403, gi404, gi405;
  23 unsigned  *gi411, gi412, gi413, gi414, gi415;
  24 unsigned  *gi501, gi502, gi503, gi504, gi505;
  25 unsigned  *gi511, gi512, gi513, gi514, gi515;
  26 unsigned  *gi601, gi602, gi603, gi604, gi605;
  27 unsigned  *gi611, gi612, gi613, gi614, gi615;
  28 unsigned  *gi701, gi702, gi703, gi704, gi705;
  29 unsigned  *gi711, gi712, gi713, gi714, gi715;
  30 unsigned  *gi801, gi802, gi803, gi804, gi805;
  31 unsigned  *gi811, gi812, gi813, gi814, gi815;
  32 unsigned **gp;
  33 unsigned   use;
  34
  35 int main(int argc, char **argv)
  36 {
  37         return 0;
  38 }
  39
  40 unsigned add_1_shift_users(unsigned i1, unsigned i2, unsigned i3,
  41                 char *k1, char *k2,     char *k3,
  42                 unsigned **gp1, unsigned **gp2, unsigned **gp3, unsigned **gp4,
  43                 unsigned **gp5, unsigned **gp6, unsigned **gp7, unsigned **gp8,
  44                 unsigned **gp9,
  45                 const int c1, const int c2, const int c3)
  46 {
  47         unsigned tmp1 = i1 + c1;
  48         unsigned tmp2 = (i2 << 3) + c2;
  49         unsigned tmp3 = (i3 << 3) + c3;
  50
  51         *gp1 = tmp1 + k1;
  52         *gp2 = tmp2 + k1;
  53         *gp3 = tmp3 + k1;
  54
  55         *gp4 = tmp1 + k2;
  56         *gp5 = tmp2 + k2;
  57         *gp6 = tmp3 + k2;
  58
  59         *gp7 = tmp1 + k3;
  60         *gp8 = tmp2 + k3;
  61         *gp9 = tmp3 + k3;
  62
  63         return 0;
  64 }
  65
  66 unsigned add_3_add_const_shift_users(unsigned i1, unsigned i2, unsigned i3,
  67                 char *k1, char *k2,     char *k3,
  68                 unsigned **gp1, unsigned **gp2, unsigned **gp3, unsigned **gp4,
  69                 unsigned **gp5, unsigned **gp6, unsigned **gp7, unsigned **gp8,
  70                 unsigned **gp9,
  71                 const int c1, const int c2)
  72 {
  73         unsigned tmp2 = (i2 << 3) + c1;
  74         unsigned tmp3 = (i3 << 3) + c2;
  75
  76         *gp1 = i1 + k1;
  77         *gp2 = tmp2 + k1;
  78         *gp3 = tmp3 + k1;
  79
  80         *gp4 = i1 + k2;
  81         *gp5 = tmp2 + k2;
  82         *gp6 = tmp3 + k2;
  83
  84         *gp7 = i1 + k3;
  85         *gp8 = tmp2 + k3;
  86         *gp9 = tmp3 + k3;
  87
  88         return 0;
  89 }
  90
  91 void diamond(void)
  92 {
  93         /*
  94          * This is the basic structure.
  95          *
  96          *             as
  97          *            /  \
  98          *          asb  asc
  99          *            \  /
 100          *             sum
 101          *
 102          * The basic idea is to make a heuristical "consume me" decision for "as".
 103          * If "asb" and "asc" have no terminal rules which consumes "as", they also
 104          * have to be consumed. Therefore "sum" has to consume both paths up to
 105          * "as", which isn't possible.
 106          */
 107         unsigned as  = a << 3;
 108         unsigned asb = as + 123235;
 109         unsigned asc = as + 235346;
 110         unsigned sum = asb + asc;
 111
 112         b = sum;
 113
 114         /* Add 3 users for asb. */
 115         use = add_3_add_const_shift_users(asb, gi1, gi2,
 116                         &gi3, &gi4, &gi5,
 117                         &gp[0], &gp[1], &gp[2], &gp[3], &gp[4], &gp[5], &gp[6], &gp[7], &gp[8],
 118                         7, 8);
 119
 120         /* Add 3 users for asc. */
 121         use = add_3_add_const_shift_users(asc, gi101, gi102,
 122                         &gi103, &gi104, &gi105,
 123                         &gp[100], &gp[101], &gp[102], &gp[103], &gp[104], &gp[105], &gp[106], &gp[107], &gp[108],
 124                         107, 108);
 125
 126         /* Add 4 users for as. */
 127         use = add_1_shift_users(as, gi201, gi202,
 128                         &gi203, &gi204, &gi205,
 129                         &gp[200], &gp[201], &gp[202], &gp[203], &gp[204], &gp[205], &gp[206], &gp[207], &gp[208],
 130                         200, 201, 202);
 131         use = add_1_shift_users(as, gi301, gi302,
 132                         &gi303, &gi304, &gi305,
 133                         &gp[300], &gp[301], &gp[302], &gp[303], &gp[304], &gp[305], &gp[306], &gp[307], &gp[308],
 134                         300, 301, 302);
 135         use = add_1_shift_users(as, gi401, gi402,
 136                         &gi403, &gi404, &gi405,
 137                         &gp[400], &gp[401], &gp[402], &gp[403], &gp[404], &gp[405], &gp[406], &gp[407], &gp[408],
 138                         400, 401, 402);
 139         use = add_1_shift_users(as, gi501, gi502,
 140                         &gi503, &gi504, &gi505,
 141                         &gp[500], &gp[501], &gp[502], &gp[503], &gp[504], &gp[505], &gp[506], &gp[507], &gp[508],
 142                         500, 501, 502);
 143 }