nsz Git - libfirm/blob - ir/ir/irpass.c

   1 /*
   2  * Copyright (C) 1995-2009 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     Manager for optimization passes.
  23  * @author    Michael Beck
  24  * @version   $Id$
  25  */
  26 #include "config.h"
  27
  28 #include <string.h>
  29 #include "adt/list.h"
  30 #include "irpass_t.h"
  31 #include "irgraph_t.h"
  32 #include "irprog_t.h"
  33 #include "irdump.h"
  34 #include "irvrfy.h"
  35 #include "xmalloc.h"
  36
  37 /*Add a graph pass to a graph pass manager. */
  38 void ir_graph_pass_mgr_add(ir_graph_pass_manager_t *mgr, ir_graph_pass_t *pass)
  39 {
  40         list_add_tail(&pass->list, &mgr->passes);
  41         ++mgr->n_passes;
  42         if (pass->add_to_mgr)
  43                 pass->add_to_mgr(pass->context);
  44 }
  45
  46 /* Add an irprog pass to an irprog pass manager. */
  47 void ir_prog_pass_mgr_add(ir_prog_pass_manager_t *mgr, ir_prog_pass_t *pass)
  48 {
  49         list_add_tail(&pass->list, &mgr->passes);
  50         ++mgr->n_passes;
  51         if (pass->add_to_mgr)
  52                 pass->add_to_mgr(pass->context);
  53 }
  54
  55 /**
  56  * wrapper for running a graph pass manager as a pass on an irprog
  57  * pass manager.
  58  */
  59 static int run_wrapper(ir_prog *prog, void *ctx)
  60 {
  61         ir_graph_pass_manager_t *mgr = ctx;
  62
  63         (void)prog;
  64         return ir_graph_pass_mgr_run(mgr);
  65 }
  66
  67 /* Ensure that no verifier is run an ir_prog pass. */
  68 int ir_prog_no_verify(ir_prog *prog, void *ctx)
  69 {
  70         (void)prog;
  71         (void)ctx;
  72         return 0;
  73 }
  74
  75 /* Ensure that no dumper is run from an ir_prog pass. */
  76 void ir_prog_no_dump(ir_prog *prog, void *ctx, unsigned idx)
  77 {
  78         (void)prog;
  79         (void)ctx;
  80         (void)idx;
  81 }
  82
  83 /**
  84  * Term wrapper for a wrapped ir_graph pass manager.
  85  */
  86 static void term_wrapper(void *context)
  87 {
  88         ir_graph_pass_manager_t *mgr = context;
  89         term_graph_pass_mgr(mgr);
  90 }
  91
  92 /**
  93  * Create a wrapper ir_prog pass for an ir_graph manager.
  94  */
  95 static ir_prog_pass_t *create_wrapper_pass(ir_graph_pass_manager_t *graph_mgr)
  96 {
  97         /* create a wrapper pass */
  98         ir_prog_pass_t *pass = XMALLOCZ(ir_prog_pass_t);
  99
 100         pass->run_on_irprog = run_wrapper;
 101         pass->context       = graph_mgr;
 102         pass->name          = graph_mgr->name;
 103
 104         /* do not verify nor dump: this is handled by the graph manager */
 105         pass->verify_irprog = ir_prog_no_verify;
 106         pass->dump_irprog   = ir_prog_no_dump;
 107         pass->is_wrapper    = 1;
 108
 109         pass->add_to_mgr   = NULL;
 110         pass->rem_from_mgr = term_wrapper;
 111
 112         return pass;
 113 }
 114
 115 /* Add an ir_graph_pass as a pass to an ir_prog pass manager. */
 116 void ir_prog_pass_mgr_add_graph_pass(
 117         ir_prog_pass_manager_t *mgr, ir_graph_pass_t *pass)
 118 {
 119         ir_graph_pass_manager_t *graph_mgr;
 120         ir_prog_pass_t          *wrapper;
 121
 122         /* check if the last pass is a graph_pass wrapper */
 123         if (! list_empty(&mgr->passes)) {
 124                 wrapper = list_entry(mgr->passes.prev, ir_prog_pass_t, list);
 125                 if (wrapper->is_wrapper) {
 126                         graph_mgr = wrapper->context;
 127
 128                         ir_graph_pass_mgr_add(graph_mgr, pass);
 129                         ++mgr->n_passes;
 130                         return;
 131                 }
 132         }
 133
 134         /* not found, create a new wrapper */
 135         graph_mgr = new_graph_pass_mgr(
 136                 "graph_pass_wrapper", mgr->verify_all, mgr->dump_all);
 137         graph_mgr->run_idx = mgr->run_idx + mgr->n_passes;
 138
 139         ir_graph_pass_mgr_add(graph_mgr, pass);
 140
 141         wrapper = create_wrapper_pass(graph_mgr);
 142         ir_prog_pass_mgr_add(mgr, wrapper);
 143 }
 144
 145 /* Add an ir_graph_pass_manager as a pass to an ir_prog pass manager. */
 146 void ir_prog_pass_mgr_add_graph_mgr(
 147         ir_prog_pass_manager_t *mgr, ir_graph_pass_manager_t *graph_mgr)
 148 {
 149         ir_prog_pass_t *pass = create_wrapper_pass(graph_mgr);
 150
 151         if (mgr->dump_all)
 152                 graph_mgr->dump_all = 1;
 153         if (mgr->verify_all)
 154                 graph_mgr->verify_all = 1;
 155         graph_mgr->run_idx = mgr->n_passes;
 156
 157         ir_prog_pass_mgr_add(mgr, pass);
 158 }
 159
 160 /**
 161  * Create a suffix for dumping.
 162  */
 163 static void create_suffix(char *suffix, size_t n, const char *pass_name,
 164                           unsigned index)
 165 {
 166         snprintf(suffix, n, "-%02u_%s", index, pass_name);
 167 }
 168
 169 /* Run all passes of an ir_graph pass manager. */
 170 int ir_graph_pass_mgr_run(ir_graph_pass_manager_t *mgr)
 171 {
 172         ir_graph_pass_t *pass;
 173         int             i, res = 0;
 174         ir_graph        *rem = current_ir_graph;
 175
 176         /* on all graphs: beware: number of irgs might be changed */
 177         for (i = 0; i < get_irp_n_irgs(); ++i) {
 178                 ir_graph *irg = current_ir_graph = get_irp_irg(i);
 179                 unsigned idx = mgr->run_idx;
 180                 /* run every pass on every graph */
 181                 list_for_each_entry(ir_graph_pass_t, pass, &mgr->passes, list) {
 182                         int pass_res = pass->run_on_irg(irg, pass->context);
 183                         if (pass_res != 0)
 184                                 res = 1;
 185                         /* verify is necessary */
 186                         if (mgr->verify_all) {
 187                                 if (pass->verify_irg) {
 188                                         pass->verify_irg(irg, pass->context);
 189                                 } else {
 190                                         irg_verify(irg, 0);
 191                                 }
 192                         }
 193                         /* dump */
 194                         if (mgr->dump_all) {
 195                                 if (pass->dump_irg) {
 196                                         pass->dump_irg(irg, pass->context, idx);
 197                                 } else {
 198                                         char suffix[1024];
 199                                         create_suffix(suffix, sizeof(suffix), pass->name, idx);
 200                                         dump_ir_block_graph(irg, suffix);
 201                                 }
 202                         }
 203                         ++idx;
 204                 }
 205         }
 206         current_ir_graph = rem;
 207         return res;
 208 }
 209
 210 /**
 211  * Verify all graphs on the given ir_prog.
 212  */
 213 static int irp_verify_irgs(void)
 214 {
 215         int i, res = 1;
 216
 217         for (i = get_irp_n_irgs() - 1; i >= 0; --i)
 218                 res &= irg_verify(get_irp_irg(i), 0);
 219         return res;
 220 }
 221
 222 /* Run all passes of an ir_prog pass manager. */
 223 int ir_prog_pass_mgr_run(ir_prog_pass_manager_t *mgr)
 224 {
 225         ir_prog_pass_t *pass;
 226         int            res = 0;
 227
 228         /* run every pass on every graph */
 229         unsigned idx = mgr->run_idx;
 230         list_for_each_entry(ir_prog_pass_t, pass, &mgr->passes, list) {
 231                 int pass_res = pass->run_on_irprog(irp, pass->context);
 232                 if (pass_res != 0)
 233                         res = 1;
 234                 /* verify is necessary */
 235                 if (mgr->verify_all) {
 236                         if (pass->verify_irprog) {
 237                                 pass->verify_irprog(irp, pass->context);
 238                         } else {
 239                                 irp_verify_irgs();
 240                         }
 241                 }
 242                 /* dump */
 243                 if (mgr->dump_all) {
 244                         if (pass->dump_irprog) {
 245                                 pass->dump_irprog(irp, pass->context, idx);
 246                         } else {
 247                                 char suffix[1024];
 248                                 create_suffix(suffix, sizeof(suffix), pass->name, idx);
 249                                 dump_all_ir_graphs(dump_ir_block_graph, suffix);
 250                         }
 251                 }
 252                 if (pass->is_wrapper) {
 253                         ir_graph_pass_manager_t *graph_mgr = pass->context;
 254                         idx += graph_mgr->n_passes;
 255                 } else
 256                         ++idx;
 257         }
 258         return res;
 259 }
 260
 261 /* Creates a new ir_graph pass manager. */
 262 ir_graph_pass_manager_t *new_graph_pass_mgr(
 263         const char *name, int verify_all, int dump_all)
 264 {
 265         ir_graph_pass_manager_t *res = XMALLOCZ(ir_graph_pass_manager_t);
 266
 267         INIT_LIST_HEAD(&res->passes);
 268         res->kind       = k_ir_graph_pass_mgr;
 269         res->name       = name;
 270         res->run_idx    = 0;
 271         res->verify_all = verify_all != 0;
 272         res->dump_all   = dump_all   != 0;
 273
 274         return res;
 275 }
 276
 277 /* Creates a new ir_prog pass manager. */
 278 ir_prog_pass_manager_t *new_prog_pass_mgr(
 279         const char *name, int verify_all, int dump_all)
 280 {
 281         ir_prog_pass_manager_t *res = XMALLOCZ(ir_prog_pass_manager_t);
 282
 283         INIT_LIST_HEAD(&res->passes);
 284         res->kind       = k_ir_prog_pass_mgr;
 285         res->name       = name;
 286         res->run_idx    = 0;
 287         res->verify_all = verify_all != 0;
 288         res->dump_all   = dump_all   != 0;
 289
 290         return res;
 291 }
 292
 293 /* Terminate an ir_graph pass manager and all owned passes. */
 294 void term_graph_pass_mgr(ir_graph_pass_manager_t *mgr)
 295 {
 296         ir_graph_pass_t *pass, *next;
 297
 298         list_for_each_entry_safe(ir_graph_pass_t, pass, next, &mgr->passes, list) {
 299                 if (pass->rem_from_mgr)
 300                         pass->rem_from_mgr(pass->context);
 301                 pass->kind = k_BAD;
 302                 xfree(pass);
 303         }
 304         mgr->kind = k_BAD;
 305         xfree(mgr);
 306 }
 307
 308 /* Terminate an ir_prog pass manager and all owned passes. */
 309 void term_prog_pass_mgr(ir_prog_pass_manager_t *mgr)
 310 {
 311         ir_prog_pass_t *pass, *next;
 312
 313         list_for_each_entry_safe(ir_prog_pass_t, pass, next, &mgr->passes, list) {
 314                 if (pass->rem_from_mgr)
 315                         pass->rem_from_mgr(pass->context);
 316                 pass->kind = k_BAD;
 317                 xfree(pass);
 318         }
 319         mgr->kind = k_BAD;
 320         xfree(mgr);
 321 }
 322
 323 /**
 324  * Set the run index for an irgraph pass manager.
 325  *
 326  * @param mgr      the manager
 327  * @param run_idx  the index for the first pass of this manager
 328  */
 329 void ir_graph_pass_mgr_set_run_idx(
 330         ir_graph_pass_manager_t *mgr, unsigned run_idx)
 331 {
 332         mgr->run_idx = run_idx;
 333 }
 334
 335 /**
 336  * Set the run index for an irprog pass manager.
 337  *
 338  * @param mgr      the manager
 339  * @param run_idx  the index for the first pass of this manager
 340  */
 341 void ir_prog_pass_mgr_set_run_idx(
 342         ir_prog_pass_manager_t *mgr, unsigned run_idx)
 343 {
 344         mgr->run_idx = run_idx;
 345 }
 346
 347 /**
 348  * Wrapper for running void function(ir_graph *irg) as an ir_graph pass.
 349  */
 350 static int void_graph_wrapper(ir_graph *irg, void *context)
 351 {
 352         void (*function)(ir_graph *irg) = context;
 353         function(irg);
 354         return 0;
 355 }  /* void_graph_wrapper */
 356
 357 /* Creates an ir_graph pass for running void function(ir_graph *irg). */
 358 ir_graph_pass_t *def_graph_pass(
 359         const char *name, void (*function)(ir_graph *irg))
 360 {
 361         struct ir_graph_pass_t *pass = XMALLOCZ(ir_graph_pass_t);
 362
 363         pass->kind       = k_ir_graph_pass;
 364         pass->run_on_irg = void_graph_wrapper;
 365         pass->context    = function;
 366         pass->name       = name;
 367
 368         INIT_LIST_HEAD(&pass->list);
 369
 370         return pass;
 371 }  /* def_graph_pass */
 372
 373 /**
 374  * Wrapper for running void function(ir_graph *irg) as an ir_graph pass.
 375  */
 376 static int int_graph_wrapper(ir_graph *irg, void *context)
 377 {
 378         int (*function)(ir_graph *irg) = context;
 379         return function(irg);
 380 }  /* int_graph_wrapper */
 381
 382 /* Creates an ir_graph pass for running void function(ir_graph *irg). */
 383 ir_graph_pass_t *def_graph_pass_ret(
 384                 const char *name, int (*function)(ir_graph *irg))
 385 {
 386         struct ir_graph_pass_t *pass = XMALLOCZ(ir_graph_pass_t);
 387
 388         pass->kind       = k_ir_graph_pass;
 389         pass->run_on_irg = int_graph_wrapper;
 390         pass->context    = function;
 391         pass->name       = name;
 392
 393         INIT_LIST_HEAD(&pass->list);
 394
 395         return pass;
 396 }  /* def_graph_pass_ret */
 397
 398 /* constructor for a default graph pass */
 399 ir_graph_pass_t *def_graph_pass_constructor(
 400         ir_graph_pass_t *pass,
 401         const char *name, int (*function)(ir_graph *irg, void *context)) {
 402         if (pass == NULL)
 403                 pass = XMALLOCZ(ir_graph_pass_t);
 404         else
 405                 memset(pass, 0, sizeof(ir_graph_pass_t));
 406         pass->kind       = k_ir_graph_pass;
 407         pass->run_on_irg = function;
 408         pass->context    = pass;
 409         pass->name       = name;
 410
 411         INIT_LIST_HEAD(&pass->list);
 412
 413         return pass;
 414 }  /* def_graph_pass_constructor */
 415
 416 /* set the run parallel property */
 417 void ir_graph_pass_set_parallel(ir_graph_pass_t *pass, int flag)
 418 {
 419         pass->run_parallel = flag != 0;
 420 }  /* ir_graph_pass_set_parallel */
 421
 422 /**
 423  * Wrapper for running void function(void) as an ir_prog pass.
 424  */
 425 static int void_prog_wrapper(ir_prog *irp, void *context)
 426 {
 427         void (*function)(void) = context;
 428
 429         (void)irp;
 430         function();
 431         return 0;
 432 }  /* void_graph_wrapper */
 433
 434 /* Creates an ir_prog pass for running void function(void). */
 435 ir_prog_pass_t *def_prog_pass(
 436         const char *name,
 437         void (*function)(void))
 438 {
 439         struct ir_prog_pass_t *pass = XMALLOCZ(ir_prog_pass_t);
 440
 441         pass->kind          = k_ir_prog_pass;
 442         pass->run_on_irprog = void_prog_wrapper;
 443         pass->context       = function;
 444         pass->name          = name;
 445
 446         INIT_LIST_HEAD(&pass->list);
 447
 448         return pass;
 449 }  /* def_prog_pass */
 450
 451 /* Creates an ir_prog pass for running void function(void). */
 452 ir_prog_pass_t *def_prog_pass_constructor(
 453         ir_prog_pass_t *pass,
 454         const char *name,
 455         int (*function)(ir_prog *irp, void *context))
 456 {
 457         if (pass == NULL)
 458                 pass = XMALLOCZ(ir_prog_pass_t);
 459         else
 460                 memset(pass, 0, sizeof(ir_prog_pass_t));
 461
 462         pass->kind          = k_ir_prog_pass;
 463         pass->run_on_irprog = function;
 464         pass->context       = pass;
 465         pass->name          = name;
 466
 467         INIT_LIST_HEAD(&pass->list);
 468
 469         return pass;
 470 }  /* def_prog_pass_constructor */
 471
 472 struct pass_t {
 473         ir_prog_pass_t pass;
 474         void           *context;
 475         void (*function)(void *context);
 476 };
 477
 478 /**
 479  * Wrapper for the call_function pass.
 480  */
 481 static int call_function_wrapper(ir_prog *irp, void *context)
 482 {
 483         struct pass_t *pass = context;
 484
 485         (void)irp;
 486         pass->function(pass->context);
 487         return 0;
 488 }  /* call_function_wrapper */
 489
 490 ir_prog_pass_t *call_function_pass(
 491         const char *name, void (*function)(void *context), void *context) {
 492         struct pass_t *pass = XMALLOCZ(struct pass_t);
 493
 494         def_prog_pass_constructor(
 495                 &pass->pass, name ? name : "set_function", call_function_wrapper);
 496
 497         pass->pass.verify_irprog = ir_prog_no_verify;
 498         pass->pass.dump_irprog   = ir_prog_no_dump;
 499         pass->pass.context       = pass;
 500
 501         pass->function = function;
 502         pass->context  = context;
 503
 504         return &pass->pass;
 505 }  /* call_function_pass */