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