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