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

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