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

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