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

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