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

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