nsz Git - libfirm/blob - ir/be/bespillilp.c

   1 /**
   2  * @file   bespillilp.c
   3  * @date   15.07.2005
   4  * @author Sebastian Hack
   5  *
   6  * ILP based spilling
   7  *
   8  * Copyright (C) 2005 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11 #include <math.h>
  12
  13 #include "hashptr.h"
  14 #include "debug.h"
  15 #include "obst.h"
  16 #include "set.h"
  17 #include "list.h"
  18 #include "pmap.h"
  19
  20 #include "irprintf.h"
  21 #include "irgwalk.h"
  22 #include "irnode_t.h"
  23 #include "ircons_t.h"
  24
  25 #include <lpp/lpp.h>
  26 #include <lpp/lpp_net.h>
  27 #include <lpp/lpp_cplex.h>
  28
  29 #include "be_t.h"
  30 #include "belive_t.h"
  31 #include "besched_t.h"
  32 #include "beirgmod.h"
  33 #include "bearch.h"
  34 #include "benode_t.h"
  35 #include "beutil.h"
  36 #include "bespillilp.h"
  37
  38 #define BIGM 1000.0
  39
  40 #define MAX(a,b) ((a) > (b) ? (a) : (b))
  41
  42 #define DBG_LEVEL SET_LEVEL_4
  43
  44 #undef DUMP_SOLUTION
  45 #define DUMP_ILP
  46 #undef DUMP_STATS
  47
  48 #define LPP_SERVER "i44pc52"
  49 #define LPP_SOLVER "cplex"
  50
  51 #define COST_LOAD      10
  52 #define COST_STORE     50
  53 #define COST_REMAT     (-9)
  54
  55 #define is_end_of_block_use(lr) (is_Block((lr)->user))
  56
  57 typedef struct _spill_stat_t {
  58         int n_spills;
  59         int n_reloads;
  60         int n_remat;
  61 } spill_stat_t;
  62
  63 typedef struct _spill_ilp_t {
  64         const arch_register_class_t *cls;
  65         firm_dbg_module_t *dbg;
  66         lpp_t *lpp;
  67         set *irn_use_heads;
  68         set *live_ranges;
  69         spill_env_t senv;
  70         struct obstack *obst;
  71         int enable_store : 1;
  72         int enable_remat : 1;
  73 } spill_ilp_t;
  74
  75 typedef struct _live_range_t live_range_t;
  76
  77 typedef struct _irn_use_head_t {
  78         struct list_head head;
  79         ir_node *irn;
  80         int spill_var;
  81         int n_uses;
  82         live_range_t *closest_use;
  83 } irn_use_head_t;
  84
  85 struct _live_range_t {
  86   struct list_head list;
  87         irn_use_head_t *use_head;
  88   ir_node *user;
  89   ir_node *irn;
  90         int pos;
  91   int in_mem_var;
  92   int is_remat_var;
  93 };
  94
  95 static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
  96 {
  97   return arch_irn_has_reg_class(si->senv.session->main_env->arch_env,
  98       irn, arch_pos_make_out(0), si->cls);
  99 }
 100
 101 static int cmp_live_range(const void *a, const void *b, size_t n)
 102 {
 103   const live_range_t *p = a;
 104   const live_range_t *q = b;
 105
 106   return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
 107 }
 108
 109 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
 110 {
 111   const irn_use_head_t *p = a;
 112   const irn_use_head_t *q = b;
 113
 114         return !(p->irn == q->irn);
 115 }
 116
 117 /**
 118  * Checks, if a vertain node can be recomputed at a certain position.
 119  * @param si    The spill ILP environment.
 120  * @param irn   The node to recompute.
 121  * @param live  The nodes live at the place where @p irn shall be
 122  *              recomputed.
 123  * @return      1, if irn can be recomputed, 0 if not.
 124  */
 125 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
 126 {
 127         int i, n;
 128   const arch_env_t *arch_env    = si->senv.session->main_env->arch_env;
 129         int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
 130
 131         for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
 132                 ir_node *op = get_irn_n(irn, i);
 133                 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
 134         }
 135
 136         return remat;
 137 }
 138
 139 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
 140 {
 141   live_range_t lr, *res;
 142         irn_use_head_t iuh, *head;
 143         int is_new;
 144   unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
 145
 146   lr.user    = user;
 147   lr.irn     = irn;
 148   lr.pos     = pos;
 149   lr.in_mem_var = -1;
 150         lr.is_remat_var = -1;
 151
 152   res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
 153         is_new = res->in_mem_var == -1;
 154
 155   if(is_new) {
 156     char buf[128];
 157     ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
 158                                 is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
 159     res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0);
 160   }
 161
 162         memset(&iuh, 0, sizeof(iuh));
 163         iuh.irn = irn;
 164         iuh.n_uses = -1;
 165         head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
 166         if(head->n_uses == -1) {
 167                 head->n_uses = 0;
 168                 INIT_LIST_HEAD(&head->head);
 169         }
 170
 171         if(is_new) {
 172                 list_add_tail(&res->list, &head->head);
 173                 head->n_uses++;
 174         }
 175
 176         res->use_head = head;
 177
 178   return res;
 179 }
 180
 181 static ir_node *process_irn(spill_ilp_t *si, pset *live, ir_node *irn, int *demand)
 182 {
 183         int i, n;
 184         int relevant_args = 0, results = 0;
 185
 186         DBG((si->dbg, LEVEL_1, "at %+F\n", irn));
 187
 188         while(is_Proj(irn)) {
 189                 if(has_reg_class(si, irn)) {
 190                         assert(pset_find_ptr(live, irn) && "node must be live");
 191                         pset_remove_ptr(live, irn);
 192                         results++;
 193                 }
 194
 195                 DBG((si->dbg, LEVEL_1, "skipped proj %+F\n", irn));
 196                 irn = sched_prev(irn);
 197         }
 198
 199         DBG((si->dbg, LEVEL_1, "\tlanded at irn %+F\n", irn));
 200
 201         if(results > 0)
 202                 assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
 203
 204         if(has_reg_class(si, irn)) {
 205                 assert( pset_find_ptr(live, irn) && "node must be live");
 206                 pset_remove_ptr(live, irn);
 207                 results = 1;
 208         }
 209
 210         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 211                 ir_node *op = get_irn_n(irn, i);
 212                 if(has_reg_class(si, op) && !pset_find_ptr(live, op)) {
 213                         relevant_args++;
 214                         DBG((si->dbg, LEVEL_1, "\trelevant arg %+F\n", op));
 215                 }
 216         }
 217
 218         *demand = MAX(results, relevant_args);
 219         DBG((si->dbg, LEVEL_1, "\tdemand: %d\n", *demand));
 220         return irn;
 221 }
 222
 223 static void process_block(ir_node *bl, void *data)
 224 {
 225         char buf[128];
 226         int i, n;
 227   spill_ilp_t *si  = data;
 228   int step         = 0;
 229   int n_regs       = arch_register_class_n_regs(si->cls);
 230         int n_preds      = get_irn_arity(bl);
 231   pset *live       = pset_new_ptr_default();
 232   irn_live_t *li;
 233   ir_node *irn, *next_irn;
 234
 235   /* as always, bring the live end nodes to life here */
 236   live_foreach(bl, li) {
 237     if(live_is_end(li) && has_reg_class(si, li->irn)) {
 238       ir_node *irn = (ir_node *) li->irn;
 239       pset_insert_ptr(live, irn);
 240
 241       /*
 242        * The "user" of the live range to the end of a block
 243        * is the block itself. This is quite arbitrary.
 244        */
 245       set_irn_link(irn, get_live_range(si, irn, bl, -1));
 246     }
 247   }
 248
 249         for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
 250                 ir_node *l;
 251                 int cst;
 252                 int demand;
 253                 int n_live;
 254                 int must_be_in_mem;
 255
 256                 /* We handle phi togther with live ins after this loop (see below). */
 257                 if(is_Phi(irn))
 258                         break;
 259
 260 #if 0
 261                 if(has_reg_class(si, irn))
 262                         pset_remove_ptr(live, irn);
 263
 264                 demand = register_demand(si, live, irn);
 265                 n_live = pset_count(live);
 266 #endif
 267
 268                 irn = process_irn(si, live, irn, &demand);
 269                 n_live = pset_count(live);
 270
 271                 /*
 272                  * Determine, how many values (which are not used at the label)
 273                  * must be in memory.
 274                  * demand means the number of registers, the operation will consume.
 275                  * So there are n_regs - demand registers available to store values
 276                  * which are not used at this label. The rest must reside in memory.
 277                  */
 278                 must_be_in_mem = MAX(n_live + demand - n_regs, 0);
 279
 280                 if(must_be_in_mem > 0) {
 281
 282                         /*
 283                          * The constraint limiting the pressure at this label to
 284                          * the number of free registers.
 285                          */
 286                         ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step);
 287                         cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
 288
 289                         for(l = pset_first(live); l; l = pset_next(live)) {
 290                                 live_range_t *lr = get_irn_link(l);
 291                                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 292                         }
 293                 }
 294
 295                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 296                         ir_node *op = get_irn_n(irn, i);
 297
 298                         if(has_reg_class(si, op)) {
 299                                 live_range_t *op_lr = get_live_range(si, op, irn, i);
 300
 301                                 set_irn_link(op, op_lr);
 302
 303                                 /*
 304                                  * The operand is reloaded at its usage, so it must not occur
 305                                  * in the constraint which determines which values live at the
 306                                  * instruction must reside in memory.
 307                                  */
 308                                 if(must_be_in_mem > 0) {
 309                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
 310                                 }
 311
 312                                 /*
 313                                  * Check, if the node is a rematerializable node and
 314                                  * if its operands are live here.
 315                                  */
 316                                 if(si->enable_remat && can_remat(si, op, live)) {
 317                                         int cst;
 318                                         int j, n;
 319                                         int n_operands = 0;
 320
 321                                         for(j = 0, n = get_irn_arity(op); j < n; ++j)
 322                                                 n_operands += has_reg_class(si, get_irn_n(op, j));
 323
 324                                         /* Make the remat constraint for this operand */
 325                                         ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
 326                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
 327
 328                                         /* Make the rematerialize variable for the operand */
 329                                         ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
 330                                         op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
 331                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
 332
 333                                         for(j = 0, n = get_irn_arity(op); j < n; ++j) {
 334                                                 ir_node *oop = get_irn_n(op, j);
 335                                                 if(has_reg_class(si, oop)) {
 336                                                         live_range_t *lr = get_irn_link(oop);
 337                                                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 338                                                 }
 339                                         }
 340
 341                                         ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
 342                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
 343                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
 344                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
 345                                 }
 346                         }
 347                 }
 348
 349                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 350                                 ir_node *op = get_irn_n(irn, i);
 351                                 if(has_reg_class(si, op) && !is_Phi(irn))
 352                                         pset_insert_ptr(live, op);
 353                         }
 354
 355                 step++;
 356         }
 357
 358         if(bl == get_irg_start_block(get_irn_irg(bl)))
 359                 goto end;
 360
 361         /*
 362          * Here, only the phis in the block and the values live in are in the
 363          * live set.
 364          *
 365          * If a value is live in, it must be in a register in all predecessor
 366          * blocks or in memory at the end of all predecessor blocks. Also, the
 367          * closest use in the current block must then be from register or
 368          * memory, respectively.
 369          */
 370         for(irn = pset_first(live); irn; irn = pset_next(live)) {
 371                 live_range_t *lr = get_irn_link(irn);
 372                 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
 373                 int cst;
 374
 375                 if(is_phi)
 376                         lr->use_head->closest_use = lr;
 377
 378                 assert(has_reg_class(si, irn));
 379                 assert(is_Phi(irn) || is_live_in(bl, irn));
 380
 381 #if 0
 382                 ir_snprintf(buf, sizeof(buf), "c%s_%N_%N", (is_phi ? "phi" : "li"), irn, bl);
 383                 cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
 384                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -n_preds);
 385
 386                 for(i = 0; i < n_preds; ++i) {
 387                         ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
 388                         ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
 389                         live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
 390
 391                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
 392                 }
 393 #endif
 394
 395                 for(i = 0; i < n_preds; ++i) {
 396                         ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
 397                         ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
 398                         live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
 399
 400                         ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i);
 401                         cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
 402                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
 403                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
 404                 }
 405         }
 406
 407 end:
 408
 409   del_pset(live);
 410 }
 411
 412 /**
 413  * Add the costs for a store.
 414  *
 415  * If one of the uses is from memory, add additional costs for the
 416  * spill.
 417  *
 418  * m_1 + ... + m_n - M * s <= 0
 419  *
 420  * @param si The ILP spilling environment.
 421  */
 422 static void add_store_costs(spill_ilp_t *si)
 423 {
 424         char buf[64];
 425         irn_use_head_t *uh;
 426         double costs = si->enable_store ? COST_STORE : 0.0;
 427
 428         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 429                 int cst;
 430                 live_range_t *lr;
 431
 432                 ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
 433                 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
 434
 435                 ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
 436                 uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs);
 437                 lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
 438
 439     list_for_each_entry(live_range_t, lr, &uh->head, list)
 440                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 441         }
 442 }
 443
 444 static INLINE int is_zero(double x)
 445 {
 446   return fabs(x) < 0.00001;
 447 }
 448
 449 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
 450 {
 451         return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
 452 }
 453
 454 static void writeback_results(spill_ilp_t *si)
 455 {
 456         const be_node_factory_t *fact = si->senv.session->main_env->node_factory;
 457         irn_use_head_t *uh;
 458         si->senv.mem_phis = pset_new_ptr_default();
 459
 460         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 461                 if(is_Phi(uh->irn) && is_spilled(si, uh->closest_use))
 462                         pset_insert_ptr(si->senv.mem_phis, uh->irn);
 463         }
 464
 465         /* Look at each node and examine the usages. */
 466         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 467                 live_range_t *lr;
 468                 ir_node **reloads;
 469
 470                 int n_reloads           = 0;
 471                 ir_node *irn            = uh->irn;
 472                 ir_mode *mode           = get_irn_mode(irn);
 473
 474                 /* Go through all live ranges of the node. */
 475                 list_for_each_entry(live_range_t, lr, &uh->head, list) {
 476                         int spilled = is_spilled(si, lr);
 477                         // int rematd  = !is_zero(lpp_get_var_sol(si->lpp, lr->is_remat_var));
 478
 479                         if(spilled && !is_end_of_block_use(lr)) {
 480                                 ir_node *bl      = get_nodes_block(lr->user);
 481
 482
 483                                 ir_node *spill   = be_spill_node(&si->senv, lr->irn);
 484                                 ir_node *reload  = new_Reload(fact, si->cls, si->senv.session->irg, bl, mode, spill);
 485
 486                                 /* inc_stats_reload(si); */
 487                                 obstack_ptr_grow(si->obst, reload);
 488                                 n_reloads++;
 489
 490                                 sched_add_before(lr->user, reload);
 491                         }
 492                 }
 493
 494                 if(n_reloads > 0) {
 495                         reloads = obstack_finish(si->obst);
 496                         be_introduce_copies_ignore(si->senv.session->dom_front, irn, n_reloads, reloads, si->senv.mem_phis);
 497                         obstack_free(si->obst, reloads);
 498                 }
 499         }
 500         be_remove_spilled_phis(&si->senv);
 501 }
 502
 503 void be_spill_ilp(const be_main_session_env_t *session_env,
 504     const arch_register_class_t *cls)
 505 {
 506         char problem_name[256];
 507         struct obstack obst;
 508         spill_ilp_t si;
 509
 510         ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
 511
 512         obstack_init(&obst);
 513         si.obst            = &obst;
 514         si.dbg             = firm_dbg_register("be.ra.spillilp");
 515         si.senv.session    = session_env;
 516         si.cls             = cls;
 517         si.lpp             = new_lpp(problem_name, lpp_minimize);
 518         si.irn_use_heads   = new_set(cmp_irn_use_head, 4096);
 519         si.live_ranges     = new_set(cmp_live_range, 16384);
 520         si.senv.spill_ctxs = new_set(be_set_cmp_spillctx, 4096);
 521         si.enable_remat    = 0;
 522         si.enable_store    = 0;
 523
 524         firm_dbg_set_mask(si.dbg, DBG_LEVEL);
 525         irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
 526         if(si.enable_store)
 527                 add_store_costs(&si);
 528
 529 #ifdef DUMP_ILP
 530         {
 531                 FILE *f;
 532                 char buf[256];
 533
 534                 ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
 535                 if((f = fopen(buf, "wt")) != NULL) {
 536                         lpp_dump_plain(si.lpp, f);
 537                         fclose(f);
 538                 }
 539         }
 540 #endif
 541
 542         DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
 543 //      lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
 544         lpp_solve_cplex(si.lpp);
 545         assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
 546
 547         DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
 548                                 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
 549         DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
 550                                 si.lpp->iterations, si.lpp->sol_time));
 551
 552 #ifdef DUMP_SOLUTION
 553         {
 554                 FILE *f;
 555                 char buf[256];
 556
 557                 ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
 558                 if((f = fopen(buf, "wt")) != NULL) {
 559                         int i;
 560                         for(i = 0; i < si.lpp->var_next; ++i) {
 561                                 lpp_name_t *name = si.lpp->vars[i];
 562                                 fprintf(f, "%10s %4d %10f\n", name->name, name->nr, name->value);
 563                         }
 564                         fclose(f);
 565                 }
 566         }
 567 #endif
 568
 569   writeback_results(&si);
 570
 571 #ifdef DUMP_STATS
 572         {
 573                 FILE *f;
 574
 575                 ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
 576                 if((f = fopen(buf, "wt")) != NULL) {
 577                         fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
 578                         fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
 579                         fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
 580                         fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
 581                         fprintf(f, "%20s: %d\n", "spills", si->stats.n_spills);
 582                         fprintf(f, "%20s: %d\n", "reloads", si->stats.n_reloads);
 583                         fprintf(f, "%20s: %d\n", "remats", si->stats.n_remat);
 584                         fclose(f);
 585                 }
 586         }
 587 #endif
 588
 589   del_set(si.irn_use_heads);
 590   del_set(si.live_ranges);
 591   free_lpp(si.lpp);
 592   obstack_free(&obst, NULL);
 593 }