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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20
  21 /**
  22  * @file   bechordal_draw.c
  23  * @date   12.05.2005
  24  * @author Sebastian Hack
  25  *
  26  * Paint chordal graphs.
  27  *
  28  * Copyright (C) 2005 Universitaet Karlsruhe
  29  * Released under the GPL
  30  */
  31 #ifdef HAVE_CONFIG_H
  32 #include "config.h"
  33 #endif
  34
  35 #include <limits.h>
  36
  37 #include "pmap.h"
  38 #include "pset.h"
  39
  40 #include "irgwalk.h"
  41 #include "irprintf.h"
  42 #include "iredges_t.h"
  43
  44 #include "belive_t.h"
  45 #include "bechordal_t.h"
  46 #include "besched_t.h"
  47 #include "bechordal_draw.h"
  48
  49 typedef struct {
  50   be_chordal_env_t *env;
  51   plotter_t inh;
  52   const color_t *color;
  53   int width;
  54 } base_plotter_t;
  55
  56 #define decl_self(type, from) \
  57   type *self = (type *) from
  58
  59 static void set_color(plotter_t *_self, const color_t *color)
  60 {
  61   decl_self(base_plotter_t, _self);
  62   self->color = color;
  63 }
  64
  65 static const color_t *get_color(const plotter_t *_self)
  66 {
  67   decl_self(const base_plotter_t, _self);
  68   return self->color;
  69 }
  70
  71 static void set_width(plotter_t *_self, int width)
  72 {
  73   decl_self(base_plotter_t, _self);
  74   self->width = width;
  75 }
  76
  77 static int get_width(const plotter_t *_self)
  78 {
  79   decl_self(const base_plotter_t, _self);
  80   return self->width;
  81 }
  82
  83 static void plotter_default_free(plotter_t *self)
  84 {
  85 }
  86
  87 typedef struct {
  88   base_plotter_t inh;
  89   const char *filename;
  90   FILE *f;
  91 } ps_plotter_t;
  92
  93
  94 /*
  95   ____  ____    ____  _       _   _
  96  |  _ \/ ___|  |  _ \| | ___ | |_| |_ ___ _ __
  97  | |_) \___ \  | |_) | |/ _ \| __| __/ _ \ '__|
  98  |  __/ ___) | |  __/| | (_) | |_| ||  __/ |
  99  |_|   |____/  |_|   |_|\___/ \__|\__\___|_|
 100
 101 */
 102
 103 static void ps_begin(plotter_t *_self, const rect_t *vis)
 104 {
 105   FILE *f;
 106   decl_self(ps_plotter_t, _self);
 107
 108   f = self->f = fopen(self->filename, "wt");
 109   fprintf(f, "%%!PS-Adobe-2.0\n");
 110   fprintf(f, "%%%%BoundingBox: %d %d %d %d\n", vis->x, vis->y, vis->w, vis->h);
 111 #if 0
 112   fprintf(f, "/mainfont /Courier findfont %f scalefont def\n", 10.0);
 113   fprintf(f, "mainfont setfont\n");
 114 #endif
 115 }
 116
 117 static void ps_setcolor(plotter_t *_self, const color_t *color)
 118 {
 119   decl_self(ps_plotter_t, _self);
 120   set_color(_self, color);
 121
 122   fprintf(self->f, "%.2f %.2f %.2f setrgbcolor\n",
 123       color->r, color->g, color->b);
 124 }
 125
 126 static void ps_line(plotter_t *_self, int x1, int y1, int x2, int y2)
 127 {
 128   decl_self(ps_plotter_t, _self);
 129
 130   fprintf(self->f, "%d %d moveto\n", x1, y1);
 131   fprintf(self->f, "%d %d lineto\n", x2, y2);
 132   fprintf(self->f, "stroke\n");
 133 }
 134
 135 static void ps_box(plotter_t *_self, const rect_t *rect)
 136 {
 137   decl_self(ps_plotter_t, _self);
 138
 139   fprintf(self->f, "%d %d %d %d rectstroke\n",
 140       rect->x, rect->y, rect->w, rect->h);
 141 }
 142
 143 void ps_text(plotter_t *_self, int x, int y, const char *str)
 144 {
 145   decl_self(ps_plotter_t, _self);
 146
 147   fprintf(self->f, "%d %d moveto\n", x, y);
 148   fprintf(self->f, "(%s) show\n", str);
 149 }
 150
 151 static void ps_finish(plotter_t *_self)
 152 {
 153   decl_self(ps_plotter_t, _self);
 154   fclose(self->f);
 155 }
 156
 157 const plotter_if_t ps_plotter_vtab = {
 158   ps_begin,
 159   ps_setcolor,
 160   get_color,
 161   set_width,
 162   get_width,
 163   ps_line,
 164   ps_box,
 165   ps_text,
 166   ps_finish,
 167   plotter_default_free
 168 };
 169
 170 plotter_t *new_plotter_ps(const char *filename)
 171 {
 172   ps_plotter_t *ps_plotter = xmalloc(sizeof(*ps_plotter));
 173   plotter_t *p = (plotter_t *) ps_plotter;
 174
 175   ps_plotter->filename = filename;
 176   p->vtab = &ps_plotter_vtab;
 177   return p;
 178 }
 179
 180 /*
 181    _____ _ _     _____  ____  _       _   _
 182   |_   _(_) | __|__  / |  _ \| | ___ | |_| |_ ___ _ __
 183     | | | | |/ /  / /  | |_) | |/ _ \| __| __/ _ \ '__|
 184     | | | |   <  / /_  |  __/| | (_) | |_| ||  __/ |
 185     |_| |_|_|\_\/____| |_|   |_|\___/ \__|\__\___|_|
 186
 187 */
 188
 189 #if 0
 190 typedef struct {
 191   base_plotter_t inh;
 192   const char *filename;
 193   FILE *f;
 194 } tikz_plotter_t;
 195
 196 static void tikz_begin(plotter_t *_self, const rect_t *vis)
 197 {
 198   FILE *f;
 199   decl_self(tikz_plotter_t, _self);
 200
 201   f = self->f = fopen(self->filename, "wt");
 202   fprintf(f, "\\begin{tikzpicture}\n");
 203 }
 204
 205 static void tikz_setcolor(plotter_t *_self, const color_t *color)
 206 {
 207   set_color(_self, color);
 208 }
 209
 210 static void tikz_line(plotter_t *_self, int x1, int y1, int x2, int y2)
 211 {
 212   decl_self(tikz_plotter_t, _self);
 213   fprintf(self->f, "\t\\draw (%d,%d) -- (%d,%d);\n", x1, y1, x2, y2);
 214 }
 215
 216 static void tikz_box(plotter_t *_self, const rect_t *rect)
 217 {
 218   decl_self(tikz_plotter_t, _self);
 219
 220   fprintf(self->f, "\t\\draw (%d,%d) rectangle (%d, %d)\n",
 221           rect->x, rect->y, rect->x + rect->w, rect->y + rect->h);
 222 }
 223
 224 void tikz_text(plotter_t *_self, int x, int y, const char *str)
 225 {
 226   decl_self(tikz_plotter_t, _self);
 227   fprintf(self->f, "\t\\draw (%d,%d) node {%s};\n", x, y, str);
 228 }
 229
 230 static void tikz_finish(plotter_t *_self)
 231 {
 232   decl_self(tikz_plotter_t, _self);
 233   fclose(self->f);
 234 }
 235 #endif
 236
 237
 238 extern void plotter_free(plotter_t *self)
 239 {
 240   self->vtab->free(self);
 241   free(self);
 242 }
 243
 244 const draw_chordal_opts_t draw_chordal_def_opts = {
 245   10, 10, 30, 8, 10, 10
 246 };
 247
 248 typedef struct _draw_chordal_env_t {
 249   const be_chordal_env_t *chordal_env;
 250   const arch_env_t *arch_env;
 251   const arch_register_class_t *cls;
 252   pmap *block_dims;
 253   plotter_t *plotter;
 254   const draw_chordal_opts_t *opts;
 255
 256   struct obstack obst;
 257   int max_color;
 258 } draw_chordal_env_t;
 259
 260 struct block_dims {
 261   int max_step;
 262   int min_step;
 263   int max_color;
 264   rect_t box;
 265   rect_t subtree_box;
 266 };
 267
 268 #undef min
 269 static INLINE int min(int a, int b)
 270 {
 271   return a < b ? a : b;
 272 }
 273
 274 #undef max
 275 static INLINE int max(int a, int b)
 276 {
 277   return a > b ? a : b;
 278 }
 279
 280 #define doz(a, b) max((a) - (b), 0)
 281
 282 static void block_dims_walker(ir_node *block, void *data)
 283 {
 284   draw_chordal_env_t *env = data;
 285   border_t *b;
 286         struct list_head *head = get_block_border_head(env->chordal_env, block);
 287   const draw_chordal_opts_t *opts = env->opts;
 288   struct block_dims *dims = obstack_alloc(&env->obst, sizeof(*dims));
 289
 290   memset(dims, 0, sizeof(*dims));
 291   dims->min_step = INT_MAX;
 292
 293         list_for_each_entry_reverse(border_t, b, head, list) {
 294     ir_node *irn = b->irn;
 295     const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn);
 296     int col = arch_register_get_index(reg);
 297
 298     dims->max_step = max(dims->max_step, b->step);
 299     dims->max_color = max(dims->max_color, col);
 300     env->max_color = max(env->max_color, col);
 301   }
 302
 303   dims->min_step = 1;
 304
 305 #if 1
 306   dims->box.w = (dims->max_color + 2) * opts->h_inter_gap;
 307   dims->box.h = dims->max_step * opts->v_inter_gap;
 308 #else
 309   dims->box.w = dims->box.h = 10;
 310 #endif
 311
 312   pmap_insert(env->block_dims, block, dims);
 313 }
 314
 315 static void layout(const draw_chordal_env_t *env, ir_node *bl, int x)
 316 {
 317   const draw_chordal_opts_t *opts = env->opts;
 318   struct block_dims *dims = pmap_get(env->block_dims, bl);
 319   ir_node *sub;
 320   rect_t *rect = &dims->subtree_box;
 321   int h_space = 0, v_space = 0;
 322
 323   memset(rect, 0, sizeof(*rect));
 324   rect->x = x;
 325
 326   dominates_for_each(bl, sub) {
 327     struct block_dims *bl_dim = pmap_get(env->block_dims, sub);
 328
 329     layout(env, sub, rect->x + rect->w);
 330
 331     rect->w += h_space + bl_dim->subtree_box.w;
 332     rect->h = max(rect->h, bl_dim->subtree_box.h);
 333
 334     h_space = opts->h_gap;
 335     v_space = opts->v_gap;
 336   }
 337
 338   rect->w = max(rect->w, dims->box.w + opts->h_gap);
 339
 340   dims->box.x = x + doz(rect->w, dims->box.w) / 2;
 341   dims->box.y = rect->h + v_space;
 342
 343   rect->h += dims->box.h + v_space;
 344 }
 345
 346 static void set_y(const draw_chordal_env_t *env, ir_node *bl, int up)
 347 {
 348   const draw_chordal_opts_t *opts = env->opts;
 349   struct block_dims *dims = pmap_get(env->block_dims, bl);
 350   int max_height = dims->subtree_box.h - dims->box.h - opts->v_gap;
 351   ir_node *sub;
 352
 353   dominates_for_each(bl, sub) {
 354     struct block_dims *bl_dim = pmap_get(env->block_dims, sub);
 355     int height_diff = max_height - bl_dim->subtree_box.h;
 356
 357     set_y(env, sub, up + height_diff);
 358   }
 359
 360   dims->subtree_box.y += up;
 361   dims->box.y += up;
 362 }
 363
 364 static color_t *reg_to_color(const draw_chordal_env_t *env,
 365     ir_node *rel_bl, ir_node *irn, color_t *color)
 366 {
 367   int phi_arg = 0;
 368   const ir_edge_t *edge;
 369
 370   foreach_out_edge(irn, edge)
 371     phi_arg |= is_Phi(edge->src);
 372
 373 #if 1
 374   color->r = is_Phi(irn) ? 0.5 : 0.0;
 375   color->g = phi_arg ? 0.5 : 0.0;
 376   color->b = 0.0;
 377 #else
 378   {
 379     int live_in = is_live_in(rel_bl, irn);
 380     int live_out = is_live_out(rel_bl, irn);
 381
 382     color->r = live_in;
 383     color->g = live_out;
 384     color->b = 0.0;
 385   }
 386 #endif
 387
 388   return color;
 389
 390 }
 391
 392 static void draw_block(ir_node *bl, void *data)
 393 {
 394         static const color_t black = { 0, 0, 0 };
 395
 396         const draw_chordal_env_t *env = data;
 397         const be_lv_t *lv = be_get_birg_liveness(env->chordal_env->birg);
 398         pset *live_in = be_lv_pset_put_in(lv, bl, pset_new_ptr_default());
 399         ir_node *irn;
 400         border_t *b;
 401         struct list_head *head = get_block_border_head(env->chordal_env, bl);
 402         ir_node *dom = get_Block_idom(bl);
 403         const draw_chordal_opts_t *opts = env->opts;
 404         struct block_dims *dims = pmap_get(env->block_dims, bl);
 405         char buf[64];
 406
 407         ir_snprintf(buf, sizeof(buf), "%F", bl);
 408
 409         env->plotter->vtab->set_color(env->plotter, &black);
 410         env->plotter->vtab->box(env->plotter, &dims->box);
 411
 412 #if 0
 413   env->plotter->vtab->text(env->plotter, dims->box.x, dims->box.y, buf);
 414 #endif
 415
 416   list_for_each_entry(border_t, b, head, list) {
 417           if(b->is_def) {
 418                   const arch_register_t *reg = arch_get_irn_register(env->arch_env, b->irn);
 419                   int col = arch_register_get_index(reg);
 420                   int live_out = be_is_live_out(lv, bl, b->irn);
 421                   int x = (col + 1) * opts->h_inter_gap;
 422                   int ystart = (b->step) * opts->v_inter_gap;
 423                   int ystop = (b->other_end->step)
 424                           * opts->v_inter_gap + (live_out ? 0 : opts->v_inter_gap / 2);
 425
 426                   color_t color;
 427                   reg_to_color(env, bl, b->irn, &color);
 428
 429                   x += dims->box.x;
 430                   ystart += dims->box.y;
 431                   ystop += dims->box.y;
 432
 433                   env->plotter->vtab->set_color(env->plotter, &color);
 434                   env->plotter->vtab->line(env->plotter, x, ystart, x, ystop);
 435
 436                   env->plotter->vtab->line(env->plotter, x - 2, ystart, x + 2, ystart);
 437                   env->plotter->vtab->line(env->plotter, x - 2, ystop, x + 2, ystop);
 438           }
 439   }
 440
 441   if(dom) {
 442           struct block_dims *dom_dims = pmap_get(env->block_dims, dom);
 443
 444           for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 445                   if(arch_irn_has_reg_class(env->arch_env, irn, -1, env->cls)) {
 446                           const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn);
 447                           int col = arch_register_get_index(reg);
 448                           int x = (col + 1) * opts->h_inter_gap;
 449
 450                           color_t color;
 451                           reg_to_color(env, bl, irn, &color);
 452
 453                           env->plotter->vtab->set_color(env->plotter, &color);
 454                           env->plotter->vtab->line(env->plotter,
 455                                           dims->box.x + x,
 456                                           dims->box.y + dims->box.h,
 457                                           dom_dims->box.x + x,
 458                                           dom_dims->box.y);
 459                   }
 460           }
 461   }
 462
 463   del_pset(live_in);
 464 }
 465
 466 static void draw(draw_chordal_env_t *env, const rect_t *start_box)
 467 {
 468   plotter_t *p = env->plotter;
 469   rect_t bbox;
 470
 471   bbox.x = bbox.y = 0;
 472   bbox.w = start_box->w + 2 * env->opts->x_margin;
 473   bbox.h = start_box->h + 2 * env->opts->y_margin;
 474
 475   be_assure_liveness(env->chordal_env->birg);
 476
 477   p->vtab->begin(p, &bbox);
 478   irg_block_walk_graph(env->chordal_env->irg, draw_block, NULL, env);
 479   p->vtab->finish(p);
 480 }
 481
 482 void draw_interval_tree(const draw_chordal_opts_t *opts,
 483                                                 const be_chordal_env_t *chordal_env,
 484                                                 plotter_t *plotter)
 485 {
 486   draw_chordal_env_t env;
 487   struct block_dims *start_dims;
 488   ir_node *start_block = get_irg_start_block(chordal_env->irg);
 489
 490   env.arch_env = chordal_env->birg->main_env->arch_env;
 491   env.opts = opts;
 492   env.block_dims = pmap_create();
 493   env.plotter = plotter;
 494   env.cls = chordal_env->cls;
 495   env.max_color = 0;
 496   env.chordal_env = chordal_env;
 497   obstack_init(&env.obst);
 498
 499   irg_block_walk_graph(chordal_env->irg, block_dims_walker, NULL, &env);
 500   layout(&env, start_block, opts->x_margin);
 501   set_y(&env, start_block, opts->y_margin);
 502   start_dims = pmap_get(env.block_dims, start_block);
 503   draw(&env, &start_dims->subtree_box);
 504
 505   pmap_destroy(env.block_dims);
 506   obstack_free(&env.obst, NULL);
 507 }