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_t.h"
  15
  16 #include "irnode.h"
  17 #include "irgraph.h"
  18 #include "irgwalk.h"
  19 #include "irprintf.h"
  20 #include "irdump_t.h"
  21 #include "benode_t.h"
  22
  23 typedef struct be_verify_register_pressure_env_t_ {
  24         ir_graph                    *irg;                 /**< the irg to verify */
  25          be_lv_t                    *lv;                  /**< Liveness information. */
  26         const arch_env_t            *arch_env;            /**< an architecture environment */
  27         const arch_register_class_t *cls;                 /**< the register class to check for */
  28         int                         registers_available;  /**< number of available registers */
  29         int                         problem_found;        /**< flag indicating if a problem was found */
  30 } be_verify_register_pressure_env_t;
  31
  32 /**
  33  * Print all nodes of a pset into a file.
  34  */
  35 static void print_living_values(FILE *F, pset *live_nodes)
  36 {
  37         ir_node *node;
  38
  39         ir_fprintf(F, "\t");
  40         foreach_pset(live_nodes, node) {
  41                 ir_fprintf(F, "%+F ", node);
  42         }
  43         ir_fprintf(F, "\n");
  44 }
  45
  46 /**
  47  * Check if number of live nodes never exceeds the number of available registers.
  48  */
  49 static void verify_liveness_walker(ir_node *block, void *data)
  50 {
  51         be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
  52         pset    *live_nodes = pset_new_ptr_default();
  53         ir_node *irn;
  54         int pressure;
  55
  56         /* collect register pressure info, start with end of a block */
  57         be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, live_nodes);
  58
  59         pressure = pset_count(live_nodes);
  60         if(pressure > env->registers_available) {
  61                 ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n",
  62                         block, get_irg_dump_name(env->irg), pressure, env->registers_available);
  63                 print_living_values(stderr, live_nodes);
  64                 env->problem_found = 1;
  65         }
  66
  67         sched_foreach_reverse(block, irn) {
  68                 if (is_Phi(irn))
  69                         break;
  70
  71                 be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes);
  72
  73                 pressure = pset_count(live_nodes);
  74
  75                 if(pressure > env->registers_available) {
  76                         ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n",
  77                                 irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available);
  78                         print_living_values(stderr, live_nodes);
  79                         env->problem_found = 1;
  80                 }
  81         }
  82         del_pset(live_nodes);
  83 }
  84
  85 /**
  86  * Start a walk over the irg and check the register pressure.
  87  */
  88 int be_verify_register_pressure(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_graph *irg)
  89 {
  90         be_verify_register_pressure_env_t env;
  91
  92         env.lv                  = be_liveness(irg);
  93         env.irg                 = irg;
  94         env.arch_env            = arch_env;
  95         env.cls                 = cls;
  96         env.registers_available = arch_count_non_ignore_regs(arch_env, cls);
  97         env.problem_found       = 0;
  98
  99         irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
 100         be_liveness_free(env.lv);
 101
 102         return ! env.problem_found;
 103 }
 104
 105 typedef struct be_verify_schedule_env_t_ {
 106         int      problem_found;    /**< flags indicating if there was a problem */
 107         ir_graph *irg;             /**< the irg to check */
 108 } be_verify_schedule_env_t;
 109
 110 /**
 111  * Simple schedule checker.
 112  */
 113 static void verify_schedule_walker(ir_node *block, void *data)
 114 {
 115         be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
 116         ir_node *node;
 117         int non_phi_found  = 0;
 118         int cfchange_found = 0;
 119         // TODO ask arch about delay branches
 120         int delay_branches = 0;
 121         pset *uses = pset_new_ptr_default();
 122
 123         /*
 124          * Tests for the following things:
 125          *   1. Make sure that all phi nodes are scheduled at the beginning of the block
 126          *   2. There is 1 or no control flow changing node scheduled and exactly delay_branches operations after it.
 127          *   3. No value is defined after it has been used
 128          */
 129         sched_foreach(block, node) {
 130                 int i, arity;
 131
 132                 // 1. Check for phis
 133                 if (is_Phi(node)) {
 134                         if (non_phi_found) {
 135                                 ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n",
 136                                         node, block, get_irg_dump_name(env->irg));
 137                                 env->problem_found = 1;
 138                         }
 139                 } else {
 140                         non_phi_found = 1;
 141                 }
 142
 143                 // 2. Check for control flow changing nodes
 144                 if (is_cfop(node) && get_irn_opcode(node) != iro_Start) {
 145                         /* check, that only one CF operation is scheduled */
 146                         if (cfchange_found == 1) {
 147                                 ir_fprintf(stderr, "Verify Warning: More than 1 control flow changing node (%+F) scheduled in block %+F (%s)\n",
 148                                         node, block, get_irg_dump_name(env->irg));
 149                                 env->problem_found = 1;
 150                         }
 151                         cfchange_found = 1;
 152                 } else if (cfchange_found) {
 153                         // proj and keepany aren't real instructions...
 154                         if(!is_Proj(node) && !be_is_Keep(node)) {
 155                                 /* check for delay branches */
 156                                 if (delay_branches == 0) {
 157                                         ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node (+delay branches) in block %+F (%s)\n",
 158                                                 node, block, get_irg_dump_name(env->irg));
 159                                         env->problem_found = 1;
 160                                 } else {
 161                                         delay_branches--;
 162                                 }
 163                         }
 164                 }
 165
 166                 // 3. Check for uses
 167                 if(pset_find_ptr(uses, node)) {
 168                         ir_fprintf(stderr, "Verify Warning: Value %+F used before it was defined in block %+F (%s)\n",
 169                                 node, block, get_irg_dump_name(env->irg));
 170                         env->problem_found = 1;
 171                 }
 172                 if(!is_Phi(node)) {
 173                         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 174                                 pset_insert_ptr(uses, get_irn_n(node, i));
 175                         }
 176                 }
 177         }
 178         del_pset(uses);
 179
 180         /* check that all delay branches are filled (at least with NOPs) */
 181         if (cfchange_found && delay_branches != 0) {
 182                 ir_fprintf(stderr, "Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
 183                         block, get_irg_dump_name(env->irg));
 184                 env->problem_found = 1;
 185         }
 186 }
 187
 188 /**
 189  * Start a walk over the irg and check schedule.
 190  */
 191 int be_verify_schedule(ir_graph *irg)
 192 {
 193         be_verify_schedule_env_t env;
 194
 195         env.problem_found = 0;
 196         env.irg           = irg;
 197
 198         irg_block_walk_graph(irg, verify_schedule_walker, NULL, &env);
 199
 200         return ! env.problem_found;
 201 }