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