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