nsz Git - libfirm/blob - ir/be/beverify.c

   1 /*
   2  * Author:    Matthias Braun
   3  * Date:      05.05.2006
   4  * Copyright: (c) Universitaet Karlsruhe
   5  * License:   This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  * CVS-Id:    $Id$
   7  */
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #include "beverify.h"
  13 #include "belive.h"
  14 #include "besched.h"
  15
  16 #include "irnode.h"
  17 #include "irgraph.h"
  18 #include "irgwalk.h"
  19 #include "irprintf.h"
  20 #include "irdump_t.h"
  21
  22 typedef struct be_verify_register_pressure_env_t_ {
  23         ir_graph                    *irg;                 /**< the irg to verify */
  24         const arch_env_t            *arch_env;            /**< an architecture environment */
  25         const arch_register_class_t *cls;                 /**< the register class to check for */
  26         int                         registers_available;  /**< number of available registers */
  27         int                         problem_found;        /**< flag indicating if a problem was found */
  28 } be_verify_register_pressure_env_t;
  29
  30 /**
  31  * Print all nodes of a pset into a file.
  32  */
  33 static void print_living_values(FILE *F, pset *live_nodes)
  34 {
  35         ir_node *node;
  36
  37         ir_fprintf(F, "\t");
  38         foreach_pset(live_nodes, node) {
  39                 ir_fprintf(F, "%+F ", node);
  40         }
  41         ir_fprintf(F, "\n");
  42 }
  43
  44 /**
  45  * Check if number of live nodes never exceeds the number of available registers.
  46  */
  47 static void verify_liveness_walker(ir_node *bl, void *data)
  48 {
  49         be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
  50         pset    *live_nodes = pset_new_ptr_default();
  51         ir_node *irn;
  52
  53         /* collect register pressure info, start with end of a block */
  54         be_liveness_end_of_block(env->arch_env, env->cls, bl, live_nodes);
  55
  56         sched_foreach_reverse(bl, irn) {
  57                 int pressure = pset_count(live_nodes);
  58
  59                 if (is_Phi(irn))
  60                         break;
  61
  62                 if(pressure > env->registers_available) {
  63                         ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n",
  64                                 bl, get_irg_dump_name(env->irg), pressure, env->registers_available);
  65                         print_living_values(stderr, live_nodes);
  66                         env->problem_found = 1;
  67                 }
  68
  69                 be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes);
  70         }
  71         del_pset(live_nodes);
  72 }
  73
  74 /**
  75  * Start a walk over the irg and check the register pressure.
  76  */
  77 int be_verify_register_pressure(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_graph *irg)
  78 {
  79         be_verify_register_pressure_env_t env;
  80
  81         be_liveness(irg);
  82
  83         env.irg                 = irg;
  84         env.arch_env            = arch_env;
  85         env.cls                 = cls;
  86         env.registers_available = arch_count_non_ignore_regs(arch_env, cls);
  87         env.problem_found       = 0;
  88
  89         irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
  90
  91         return ! env.problem_found;
  92 }
  93
  94 typedef struct be_verify_schedule_env_t_ {
  95         int      problem_found;    /**< flags indicating if there was a problem */
  96         ir_graph *irg;             /**< the irg to check */
  97 } be_verify_schedule_env_t;
  98
  99 /**
 100  * Simple schedule checker.
 101  */
 102 static void verify_schedule_walker(ir_node *bl, void *data)
 103 {
 104         be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
 105         ir_node *irn;
 106         int non_phi_found  = 0;
 107         int cfchange_found = 0;
 108         // TODO ask ABI about delay branches
 109         int delay_branches = 0;
 110
 111         /*
 112          * Make sure that all phi nodes are scheduled at the beginning of the block, and that there
 113          * is 1 or no control flow changing node scheduled and exactly delay_branches operations after it.
 114          */
 115         sched_foreach(bl, irn) {
 116                 if (is_Phi(irn)) {
 117                         if (non_phi_found) {
 118                                 ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n",
 119                                         irn, bl, get_irg_dump_name(env->irg));
 120                                 env->problem_found = 1;
 121                         }
 122                         continue;
 123                 }
 124                 non_phi_found = 1;
 125
 126                 if (is_cfop(irn) && get_irn_opcode(irn) != iro_Start) {
 127                         /* check, that only one CF operation is scheduled */
 128                         if (cfchange_found == 1) {
 129                                 ir_fprintf(stderr, "Verify Warning: More than 1 control flow changing node (%+F) scheduled in block %+F (%s)\n",
 130                                         irn, bl, get_irg_dump_name(env->irg));
 131                                 env->problem_found = 1;
 132                         }
 133                         cfchange_found = 1;
 134                 } else if (cfchange_found) {
 135                         /* check for delay branches */
 136                         if (delay_branches == 0) {
 137                                 ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node (+delay branches) in block %+F (%s)\n",
 138                                         irn, bl, get_irg_dump_name(env->irg));
 139                                 env->problem_found = 1;
 140                         } else {
 141                                 delay_branches--;
 142                         }
 143                 }
 144         }
 145
 146         /* check that all delay branches are used (at least with NOPs) */
 147         if (cfchange_found && delay_branches != 0) {
 148                 ir_fprintf(stderr, "Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
 149                         bl, get_irg_dump_name(env->irg));
 150                 env->problem_found = 1;
 151         }
 152 }
 153
 154 /**
 155  * Start a walk over the irg and check schedule.
 156  */
 157 int be_verify_schedule(ir_graph *irg)
 158 {
 159         be_verify_schedule_env_t env;
 160
 161         env.problem_found = 0;
 162         env.irg           = irg;
 163
 164         irg_block_walk_graph(irg, verify_schedule_walker, NULL, &env);
 165
 166         return ! env.problem_found;
 167 }