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