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      min_step;
 182         int      max_color;
 183         rect_t   box;
 184         rect_t   subtree_box;
 185 };
 186
 187 #define doz(a, b) MAX((a) - (b), 0)
 188
 189 static void block_dims_walker(ir_node *block, void *data)
 190 {
 191         draw_chordal_env_t        *env  = (draw_chordal_env_t*)data;
 192         struct list_head          *head = get_block_border_head(env->chordal_env, block);
 193         const draw_chordal_opts_t *opts = env->opts;
 194         struct block_dims         *dims = OALLOCZ(&env->obst, struct block_dims);
 195
 196         dims->min_step = INT_MAX;
 197
 198         foreach_border_head(head, b) {
 199                 ir_node               *irn = b->irn;
 200                 const arch_register_t *reg = arch_get_irn_register(irn);
 201                 int                    col = reg->index;
 202
 203                 dims->max_step  = MAX(dims->max_step, b->step);
 204                 dims->max_color = MAX(dims->max_color, col);
 205                 env->max_color  = MAX(env->max_color, col);
 206         }
 207
 208         dims->min_step = 1;
 209
 210         dims->box.w = (dims->max_color + 2) * opts->h_inter_gap;
 211         dims->box.h = dims->max_step * opts->v_inter_gap;
 212
 213         pmap_insert(env->block_dims, block, dims);
 214 }
 215
 216 static void layout(const draw_chordal_env_t *env, ir_node *bl, int x)
 217 {
 218         const draw_chordal_opts_t *opts   = env->opts;
 219         struct block_dims         *dims   = pmap_get(struct block_dims, env->block_dims, bl);
 220         rect_t                    *rect   = &dims->subtree_box;
 221         int                       h_space = 0;
 222         int                       v_space = 0;
 223         ir_node                   *sub;
 224
 225         memset(rect, 0, sizeof(*rect));
 226         rect->x = x;
 227
 228         dominates_for_each(bl, sub) {
 229                 struct block_dims *bl_dim = pmap_get(struct block_dims, env->block_dims, sub);
 230
 231                 layout(env, sub, rect->x + rect->w);
 232
 233                 rect->w += h_space + bl_dim->subtree_box.w;
 234                 rect->h  = MAX(rect->h, bl_dim->subtree_box.h);
 235
 236                 h_space = opts->h_gap;
 237                 v_space = opts->v_gap;
 238         }
 239
 240         rect->w = MAX(rect->w, dims->box.w + opts->h_gap);
 241
 242         dims->box.x = x + doz(rect->w, dims->box.w) / 2;
 243         dims->box.y = rect->h + v_space;
 244
 245         rect->h = dims->box.y + dims->box.h;
 246 }
 247
 248 static void set_y(const draw_chordal_env_t *env, ir_node *bl, int up)
 249 {
 250         const draw_chordal_opts_t *opts      = env->opts;
 251         struct block_dims         *dims      = pmap_get(struct block_dims, env->block_dims, bl);
 252         int                       max_height = dims->subtree_box.h - dims->box.h - opts->v_gap;
 253         ir_node                   *sub;
 254
 255         dominates_for_each(bl, sub) {
 256                 struct block_dims *bl_dim = pmap_get(struct block_dims, env->block_dims, sub);
 257                 int height_diff = max_height - bl_dim->subtree_box.h;
 258
 259                 set_y(env, sub, up + height_diff);
 260         }
 261
 262         dims->subtree_box.y += up;
 263         dims->box.y         += up;
 264 }
 265
 266 static color_t *reg_to_color(const draw_chordal_env_t *env,
 267                                                          ir_node *rel_bl, ir_node *irn, color_t *color)
 268 {
 269         int phi_arg = 0;
 270         (void) env;
 271         (void) rel_bl;
 272
 273         foreach_out_edge(irn, edge)
 274                 phi_arg |= is_Phi(edge->src);
 275
 276         color->r = is_Phi(irn) ? 0.5 : 0.0;
 277         color->g = phi_arg ? 0.5 : 0.0;
 278         color->b = 0.0;
 279         return color;
 280 }
 281
 282 static void draw_block(ir_node *bl, void *data)
 283 {
 284         static const color_t      black    = { 0, 0, 0 };
 285         const draw_chordal_env_t  *env     = (const draw_chordal_env_t*)data;
 286         const be_lv_t             *lv      = be_get_irg_liveness(env->chordal_env->irg);
 287         struct list_head          *head    = get_block_border_head(env->chordal_env, bl);
 288         ir_node                   *dom     = get_Block_idom(bl);
 289         const draw_chordal_opts_t *opts    = env->opts;
 290         struct block_dims         *dims    = pmap_get(struct block_dims, env->block_dims, bl);
 291         char                      buf[64];
 292
 293         ir_snprintf(buf, sizeof(buf), "%F", bl);
 294
 295         env->plotter->vtab->set_color(env->plotter, &black);
 296         env->plotter->vtab->box(env->plotter, &dims->box);
 297
 298         env->plotter->vtab->text(env->plotter, dims->box.x, dims->box.y, buf);
 299
 300         foreach_border_head(head, b) {
 301                 if (b->is_def) {
 302                         /* Walk from def to use, so the link is set before retrieved. */
 303                         set_irn_link(b->irn, b);
 304                 } else {
 305                         ir_node               *const irn = b->irn;
 306                         border_t        const *const def = (border_t const*)get_irn_link(irn);
 307                         arch_register_t const *const reg = arch_get_irn_register(irn);
 308
 309                         int live_out = be_is_live_out(lv, bl, irn);
 310                         int x        = (reg->index + 1) * opts->h_inter_gap;
 311                         int ystart   = def->step * opts->v_inter_gap;
 312                         int ystop    =   b->step * opts->v_inter_gap + (live_out ? 0 : opts->v_inter_gap / 2);
 313
 314                         color_t color;
 315                         reg_to_color(env, bl, irn, &color);
 316
 317                         x      += dims->box.x;
 318                         ystart += dims->box.y;
 319                         ystop  += dims->box.y;
 320
 321                         env->plotter->vtab->set_color(env->plotter, &color);
 322                         env->plotter->vtab->line(env->plotter, x, ystart, x, ystop);
 323
 324                         env->plotter->vtab->line(env->plotter, x - 2, ystart, x + 2, ystart);
 325                         env->plotter->vtab->line(env->plotter, x - 2, ystop, x + 2, ystop);
 326                 }
 327         }
 328
 329         if (dom) {
 330                 struct block_dims *dom_dims = pmap_get(struct block_dims, env->block_dims, dom);
 331
 332                 be_lv_foreach_cls(lv, bl, be_lv_state_in, env->cls, irn) {
 333                         const arch_register_t *reg = arch_get_irn_register(irn);
 334                         int                    x   = (reg->index + 1) * opts->h_inter_gap;
 335                         color_t                color;
 336
 337                         reg_to_color(env, bl, irn, &color);
 338
 339                         env->plotter->vtab->set_color(env->plotter, &color);
 340                         env->plotter->vtab->line(env->plotter,
 341                                 dims->box.x + x,
 342                                 dims->box.y + dims->box.h,
 343                                 dom_dims->box.x + x,
 344                                 dom_dims->box.y);
 345                 }
 346         }
 347 }
 348
 349 static void draw(draw_chordal_env_t *env, const rect_t *start_box)
 350 {
 351         ir_graph  *irg = env->chordal_env->irg;
 352         plotter_t *p = env->plotter;
 353         rect_t bbox;
 354
 355         bbox.x = bbox.y = 0;
 356         bbox.w = start_box->w + 2 * env->opts->x_margin;
 357         bbox.h = start_box->h + 2 * env->opts->y_margin;
 358
 359         be_assure_live_sets(irg);
 360         be_assure_live_chk(irg);
 361
 362         p->vtab->begin(p, &bbox);
 363         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 364         irg_block_walk_graph(irg, draw_block, NULL, env);
 365         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 366         p->vtab->finish(p);
 367 }
 368
 369 void draw_interval_tree(const draw_chordal_opts_t *opts,
 370                         const be_chordal_env_t *chordal_env, plotter_t *plotter)
 371 {
 372         draw_chordal_env_t env;
 373         struct block_dims  *start_dims;
 374         ir_node            *start_block = get_irg_start_block(chordal_env->irg);
 375
 376         env.opts        = opts;
 377         env.block_dims  = pmap_create();
 378         env.plotter     = plotter;
 379         env.cls         = chordal_env->cls;
 380         env.max_color   = 0;
 381         env.chordal_env = chordal_env;
 382         obstack_init(&env.obst);
 383
 384         irg_block_walk_graph(chordal_env->irg, block_dims_walker, NULL, &env);
 385         layout(&env, start_block, opts->x_margin);
 386         set_y(&env, start_block, opts->y_margin);
 387         start_dims = pmap_get(struct block_dims, env.block_dims, start_block);
 388         draw(&env, &start_dims->subtree_box);
 389
 390         pmap_destroy(env.block_dims);
 391         obstack_free(&env.obst, NULL);
 392 }