nsz Git - libfirm/blob - ir/opt/boolopt.c

   1 #include <assert.h>
   2 #include "ircons.h"
   3 #include "irgmod.h"
   4 #include "irgwalk.h"
   5 #include "irnode.h"
   6 #include "tv.h"
   7
   8 typedef struct cond_pair {
   9         ir_node *cmp_lo;
  10         ir_node *cmp_hi;
  11         pn_Cmp   pnc_lo;
  12         pn_Cmp   pnc_hi;
  13         ir_node *proj_lo;
  14         ir_node *proj_hi;
  15         tarval  *tv_lo;
  16         tarval  *tv_hi;
  17 } cond_pair;
  18
  19 static int find_cond_pair(ir_node *const l, ir_node *const r, cond_pair *const res)
  20 {
  21         if (is_Proj(l) && is_Proj(r)) {
  22                 ir_node *const lo = get_Proj_pred(l);
  23                 ir_node *const ro = get_Proj_pred(r);
  24
  25                 if (is_Cmp(lo) && is_Cmp(ro)) {
  26                         ir_node *const lol = get_Cmp_left(lo);
  27                         ir_node *const lor = get_Cmp_right(lo);
  28                         ir_node *const rol = get_Cmp_left(ro);
  29                         ir_node *const ror = get_Cmp_right(ro);
  30
  31                         /* TODO float */
  32                         /* The constants shall be unequal.  Local optimisations handle the equal
  33                          * case */
  34                         if (lol == rol && mode_is_int(get_irn_mode(lol)) && lor != ror && is_Const(lor) && is_Const(ror)) {
  35                                 tarval *const tv_l  = get_Const_tarval(lor);
  36                                 tarval *const tv_r  = get_Const_tarval(ror);
  37                                 pn_Cmp  const pnc_l = get_Proj_proj(l);
  38                                 pn_Cmp  const pnc_r = get_Proj_proj(r);
  39                                 pn_Cmp  const rel   = tarval_cmp(tv_l, tv_r);
  40
  41                                 assert(rel != pn_Cmp_Eq);
  42
  43                                 if (rel == pn_Cmp_Lt) {
  44                                         res->cmp_lo  = lo;
  45                                         res->cmp_hi  = ro;
  46                                         res->pnc_lo  = pnc_l;
  47                                         res->pnc_hi  = pnc_r;
  48                                         res->proj_lo = l;
  49                                         res->proj_hi = r;
  50                                         res->tv_lo   = tv_l;
  51                                         res->tv_hi   = tv_r;
  52                                 } else {
  53                                         assert(rel == pn_Cmp_Gt);
  54                                         res->cmp_lo  = ro;
  55                                         res->cmp_hi  = lo;
  56                                         res->pnc_lo  = pnc_r;
  57                                         res->pnc_hi  = pnc_l;
  58                                         res->proj_lo = r;
  59                                         res->proj_hi = l;
  60                                         res->tv_lo   = tv_r;
  61                                         res->tv_hi   = tv_l;
  62                                 }
  63                                 return 1;
  64                         }
  65                 }
  66         }
  67         return 0;
  68 }
  69
  70 static void bool_and(ir_node *const n)
  71 {
  72         ir_node *const l = get_And_left(n);
  73         ir_node *const r = get_And_right(n);
  74         cond_pair      res;
  75         if (find_cond_pair(l, r, &res)) {
  76                 ir_node *const cmp_lo  = res.cmp_lo;
  77                 ir_node *const cmp_hi  = res.cmp_hi;
  78                 pn_Cmp   const pnc_lo  = res.pnc_lo;
  79                 pn_Cmp   const pnc_hi  = res.pnc_hi;
  80                 ir_node *const proj_lo = res.proj_lo;
  81                 ir_node *const proj_hi = res.proj_hi;
  82                 tarval  *const tv_lo   = res.tv_lo;
  83                 tarval  *const tv_hi   = res.tv_hi;
  84
  85                 if ((pnc_lo == pn_Cmp_Lt || pnc_lo == pn_Cmp_Le || pnc_lo == pn_Cmp_Eq) &&
  86                                 (pnc_hi == pn_Cmp_Eq || pnc_hi == pn_Cmp_Ge || pnc_hi == pn_Cmp_Gt)) {
  87                         /* x <|<=|== lo | x ==|>=|> hi -> false */
  88                         ir_node *const t = new_Const(mode_b, tarval_b_false);
  89                         exchange(n, t);
  90                 } else if ((pnc_lo == pn_Cmp_Lt || pnc_lo == pn_Cmp_Le || pnc_lo == pn_Cmp_Eq) &&
  91                                                          (pnc_hi == pn_Cmp_Lt || pnc_hi == pn_Cmp_Le || pnc_hi == pn_Cmp_Ne)) {
  92                         /* x <|<=|== lo && x <|<=|!= hi -> x <|<=|== lo */
  93                         exchange(n, proj_lo);
  94                 } else if ((pnc_lo == pn_Cmp_Ge || pnc_lo == pn_Cmp_Gt || pnc_lo == pn_Cmp_Ne) &&
  95                                                          (pnc_hi == pn_Cmp_Eq || pnc_hi == pn_Cmp_Ge || pnc_hi == pn_Cmp_Gt)) {
  96                         /* x >=|>|!= lo || x ==|>=|> hi -> x ==|>=|> hi */
  97                         exchange(n, proj_hi);
  98                 } else if (tarval_is_one(tarval_sub(tv_hi, tv_lo))) { /* lo + 1 == hi */
  99                         if (pnc_lo == pn_Cmp_Ge && pnc_hi == pn_Cmp_Lt) {
 100                                 /* x >= c || x < c + 1 -> x == c */
 101                                 ir_graph *const irg   = current_ir_graph;
 102                                 ir_node  *const block = get_nodes_block(cmp_lo);
 103                                 ir_node  *const p = new_r_Proj(irg, block, cmp_lo, mode_b, pn_Cmp_Eq);
 104                                 exchange(n, p);
 105                         } else if (pnc_lo == pn_Cmp_Gt) {
 106                                 if (pnc_hi == pn_Cmp_Ne) {
 107                                         /* x > c || x != c + 1 -> x > c + 1 */
 108                                         ir_graph *const irg   = current_ir_graph;
 109                                         ir_node  *const block = get_nodes_block(cmp_hi);
 110                                         ir_node  *const p = new_r_Proj(irg, block, cmp_hi, mode_b, pn_Cmp_Gt);
 111                                         exchange(n, p);
 112                                 } else if (pnc_hi == pn_Cmp_Lt) {
 113                                         /* x > c || x < c + 1 -> false */
 114                                         ir_node *const t = new_Const(mode_b, tarval_b_false);
 115                                         exchange(n, t);
 116                                 } else if (pnc_hi == pn_Cmp_Le) {
 117                                         /* x > c || x <= c + 1 -> x != c + 1 */
 118                                         ir_graph *const irg   = current_ir_graph;
 119                                         ir_node  *const block = get_nodes_block(cmp_hi);
 120                                         ir_node  *const p = new_r_Proj(irg, block, cmp_hi, mode_b, pn_Cmp_Eq);
 121                                         exchange(n, p);
 122                                 }
 123                         } else if (pnc_lo == pn_Cmp_Ne && pnc_hi == pn_Cmp_Lt) {
 124                                 /* x != c || c < c + 1 -> x < c */
 125                                 ir_graph *const irg   = current_ir_graph;
 126                                 ir_node  *const block = get_nodes_block(cmp_lo);
 127                                 ir_node  *const p     = new_r_Proj(irg, block, cmp_lo, mode_b, pn_Cmp_Lt);
 128                                 exchange(n, p);
 129                         }
 130                 }
 131         }
 132 }
 133
 134 static void bool_or(ir_node *const n)
 135 {
 136         ir_node *const l = get_Or_left(n);
 137         ir_node *const r = get_Or_right(n);
 138         cond_pair      res;
 139         if (find_cond_pair(l, r, &res)) {
 140                 ir_node *const cmp_lo  = res.cmp_lo;
 141                 ir_node *const cmp_hi  = res.cmp_hi;
 142                 pn_Cmp   const pnc_lo  = res.pnc_lo;
 143                 pn_Cmp   const pnc_hi  = res.pnc_hi;
 144                 ir_node *const proj_lo = res.proj_lo;
 145                 ir_node *const proj_hi = res.proj_hi;
 146                 tarval  *const tv_lo   = res.tv_lo;
 147                 tarval  *const tv_hi   = res.tv_hi;
 148
 149                 if ((pnc_lo == pn_Cmp_Ge || pnc_lo == pn_Cmp_Gt || pnc_lo == pn_Cmp_Ne) &&
 150                                 (pnc_hi == pn_Cmp_Lt || pnc_hi == pn_Cmp_Le || pnc_hi == pn_Cmp_Ne)) {
 151                         /* x >=|>|!= lo | x <|<=|!= hi -> true */
 152                         ir_node *const t = new_Const(mode_b, tarval_b_true);
 153                         exchange(n, t);
 154                 } else if ((pnc_lo == pn_Cmp_Lt || pnc_lo == pn_Cmp_Le || pnc_lo == pn_Cmp_Eq) &&
 155                                                          (pnc_hi == pn_Cmp_Lt || pnc_hi == pn_Cmp_Le || pnc_hi == pn_Cmp_Ne)) {
 156                         /* x <|<=|== lo || x <|<=|!= hi -> x <|<=|!= hi */
 157                         exchange(n, proj_hi);
 158                 } else if ((pnc_lo == pn_Cmp_Ge || pnc_lo == pn_Cmp_Gt || pnc_lo == pn_Cmp_Ne) &&
 159                                                          (pnc_hi == pn_Cmp_Eq || pnc_hi == pn_Cmp_Ge || pnc_hi == pn_Cmp_Gt)) {
 160                         /* x >=|>|!= lo || x ==|>=|> hi -> x >=|>|!= lo */
 161                         exchange(n, proj_lo);
 162                 } else if (tarval_is_one(tarval_sub(tv_hi, tv_lo))) { /* lo + 1 == hi */
 163                         if (pnc_lo == pn_Cmp_Lt && pnc_hi == pn_Cmp_Ge) {
 164                                 /* x < c || x >= c + 1 -> x != c */
 165                                 ir_graph *const irg   = current_ir_graph;
 166                                 ir_node  *const block = get_nodes_block(cmp_lo);
 167                                 ir_node  *const p = new_r_Proj(irg, block, cmp_lo, mode_b, pn_Cmp_Ne);
 168                                 exchange(n, p);
 169                         } else if (pnc_lo == pn_Cmp_Le) {
 170                                 if (pnc_hi == pn_Cmp_Eq) {
 171                                         /* x <= c || x == c + 1 -> x <= c + 1 */
 172                                         ir_graph *const irg   = current_ir_graph;
 173                                         ir_node  *const block = get_nodes_block(cmp_hi);
 174                                         ir_node  *const p = new_r_Proj(irg, block, cmp_hi, mode_b, pn_Cmp_Le);
 175                                         exchange(n, p);
 176                                 } else if (pnc_hi == pn_Cmp_Ge) {
 177                                         /* x <= c || x >= c + 1 -> true */
 178                                         ir_node *const t = new_Const(mode_b, tarval_b_true);
 179                                         exchange(n, t);
 180                                 } else if (pnc_hi == pn_Cmp_Gt) {
 181                                         /* x <= c || x > c + 1 -> x != c + 1 */
 182                                         ir_graph *const irg   = current_ir_graph;
 183                                         ir_node  *const block = get_nodes_block(cmp_hi);
 184                                         ir_node  *const p = new_r_Proj(irg, block, cmp_hi, mode_b, pn_Cmp_Ne);
 185                                         exchange(n, p);
 186                                 }
 187                         } else if (pnc_lo == pn_Cmp_Eq && pnc_hi == pn_Cmp_Ge) {
 188                                 /* x == c || c >= c + 1 -> x >= c */
 189                                 ir_graph *const irg   = current_ir_graph;
 190                                 ir_node  *const block = get_nodes_block(cmp_lo);
 191                                 ir_node  *const p     = new_r_Proj(irg, block, cmp_lo, mode_b, pn_Cmp_Ge);
 192                                 exchange(n, p);
 193                         }
 194                 }
 195         }
 196 }
 197
 198 static void bool_walk(ir_node *n, void *env)
 199 {
 200         (void)env;
 201
 202         if (get_irn_mode(n) != mode_b) return;
 203
 204         if (is_And(n)) {
 205                 bool_and(n);
 206         } else if (is_Or(n)) {
 207                 bool_or(n);
 208         }
 209 }
 210
 211 void opt_bool(ir_graph *irg)
 212 {
 213         irg_walk_graph(irg, NULL, bool_walk, NULL);
 214 }