gcc/go/gofrontend/dataflow.cc

   1 // dataflow.cc -- Go frontend dataflow.
   2
   3 // Copyright 2009 The Go Authors. All rights reserved.
   4 // Use of this source code is governed by a BSD-style
   5 // license that can be found in the LICENSE file.
   6
   7 #include "go-system.h"
   8
   9 #include "gogo.h"
  10 #include "expressions.h"
  11 #include "statements.h"
  12 #include "dataflow.h"
  13
  14 // This class is used to traverse the tree to look for uses of
  15 // variables.
  16
  17 class Dataflow_traverse_expressions : public Traverse
  18 {
  19  public:
  20   Dataflow_traverse_expressions(Dataflow* dataflow, Statement* statement)
  21     : Traverse(traverse_blocks | traverse_expressions),
  22       dataflow_(dataflow), statement_(statement)
  23   { }
  24
  25  protected:
  26   // Only look at top-level expressions: do not descend into blocks.
  27   // They will be examined via Dataflow_traverse_statements.
  28   int
  29   block(Block*)
  30   { return TRAVERSE_SKIP_COMPONENTS; }
  31
  32   int
  33   expression(Expression**);
  34
  35  private:
  36   // The dataflow information.
  37   Dataflow* dataflow_;
  38   // The Statement in which we are looking.
  39   Statement* statement_;
  40 };
  41
  42 // Given an expression, return the Named_object that it refers to, if
  43 // it is a local variable.
  44
  45 static Named_object*
  46 get_var(Expression* expr)
  47 {
  48   Var_expression* ve = expr->var_expression();
  49   if (ve == NULL)
  50     return NULL;
  51   Named_object* no = ve->named_object();
  52   go_assert(no->is_variable() || no->is_result_variable());
  53   if (no->is_variable() && no->var_value()->is_global())
  54     return NULL;
  55   return no;
  56 }
  57
  58 // Look for a reference to a variable in an expression.
  59
  60 int
  61 Dataflow_traverse_expressions::expression(Expression** expr)
  62 {
  63   Named_object* no = get_var(*expr);
  64   if (no != NULL)
  65     this->dataflow_->add_ref(no, this->statement_);
  66   return TRAVERSE_CONTINUE;
  67 }
  68
  69 // This class is used to handle an assignment statement.
  70
  71 class Dataflow_traverse_assignment : public Traverse_assignments
  72 {
  73  public:
  74   Dataflow_traverse_assignment(Dataflow* dataflow, Statement* statement)
  75     : dataflow_(dataflow), statement_(statement)
  76   { }
  77
  78  protected:
  79   void
  80   initialize_variable(Named_object*);
  81
  82   void
  83   assignment(Expression** lhs, Expression** rhs);
  84
  85   void
  86   value(Expression**, bool, bool);
  87
  88  private:
  89   // The dataflow information.
  90   Dataflow* dataflow_;
  91   // The Statement in which we are looking.
  92   Statement* statement_;
  93 };
  94
  95 // Handle a variable initialization.
  96
  97 void
  98 Dataflow_traverse_assignment::initialize_variable(Named_object* var)
  99 {
 100   Expression* init = var->var_value()->init();
 101   this->dataflow_->add_def(var, init, this->statement_, true);
 102   if (init != NULL)
 103     {
 104       Expression* e = init;
 105       this->value(&e, true, true);
 106       go_assert(e == init);
 107     }
 108 }
 109
 110 // Handle an assignment in a statement.
 111
 112 void
 113 Dataflow_traverse_assignment::assignment(Expression** plhs, Expression** prhs)
 114 {
 115   Named_object* no = get_var(*plhs);
 116   if (no != NULL)
 117     {
 118       Expression* rhs = prhs == NULL ? NULL : *prhs;
 119       this->dataflow_->add_def(no, rhs, this->statement_, false);
 120     }
 121   else
 122     {
 123       // If this is not a variable it may be some computed lvalue, and
 124       // we want to look for references to variables in that lvalue.
 125       this->value(plhs, false, false);
 126     }
 127   if (prhs != NULL)
 128     this->value(prhs, true, false);
 129 }
 130
 131 // Handle a value in a statement.
 132
 133 void
 134 Dataflow_traverse_assignment::value(Expression** pexpr, bool, bool)
 135 {
 136   Named_object* no = get_var(*pexpr);
 137   if (no != NULL)
 138     this->dataflow_->add_ref(no, this->statement_);
 139   else
 140     {
 141       Dataflow_traverse_expressions dte(this->dataflow_, this->statement_);
 142       Expression::traverse(pexpr, &dte);
 143     }
 144 }
 145
 146 // This class is used to traverse the tree to look for statements.
 147
 148 class Dataflow_traverse_statements : public Traverse
 149 {
 150  public:
 151   Dataflow_traverse_statements(Dataflow* dataflow)
 152     : Traverse(traverse_statements),
 153       dataflow_(dataflow)
 154   { }
 155
 156  protected:
 157   int
 158   statement(Block*, size_t* pindex, Statement*);
 159
 160  private:
 161   // The dataflow information.
 162   Dataflow* dataflow_;
 163 };
 164
 165 // For each Statement, we look for expressions.
 166
 167 int
 168 Dataflow_traverse_statements::statement(Block* block, size_t* pindex,
 169                                         Statement *statement)
 170 {
 171   Dataflow_traverse_assignment dta(this->dataflow_, statement);
 172   if (!statement->traverse_assignments(&dta))
 173     {
 174       Dataflow_traverse_expressions dte(this->dataflow_, statement);
 175       statement->traverse(block, pindex, &dte);
 176     }
 177   return TRAVERSE_CONTINUE;
 178 }
 179
 180 // Compare variables.
 181
 182 bool
 183 Dataflow::Compare_vars::operator()(const Named_object* no1,
 184                                    const Named_object* no2) const
 185 {
 186   if (no1->name() < no2->name())
 187     return true;
 188   if (no1->name() > no2->name())
 189     return false;
 190
 191   // We can have two different variables with the same name.
 192   Location loc1 = no1->location();
 193   Location loc2 = no2->location();
 194   if (loc1 < loc2)
 195     return false;
 196   if (loc1 > loc2)
 197     return true;
 198
 199   if (no1 == no2)
 200     return false;
 201
 202   // We can't have two variables with the same name in the same
 203   // location.
 204   go_unreachable();
 205 }
 206
 207 // Class Dataflow.
 208
 209 Dataflow::Dataflow()
 210   : defs_(), refs_()
 211 {
 212 }
 213
 214 // Build the dataflow information.
 215
 216 void
 217 Dataflow::initialize(Gogo* gogo)
 218 {
 219   Dataflow_traverse_statements dts(this);
 220   gogo->traverse(&dts);
 221 }
 222
 223 // Add a definition of a variable.
 224
 225 void
 226 Dataflow::add_def(Named_object* var, Expression* val, Statement* statement,
 227                   bool is_init)
 228 {
 229   Defs* defnull = NULL;
 230   std::pair<Defmap::iterator, bool> ins =
 231     this->defs_.insert(std::make_pair(var, defnull));
 232   if (ins.second)
 233     ins.first->second = new Defs;
 234   Def def;
 235   def.statement = statement;
 236   def.val = val;
 237   def.is_init = is_init;
 238   ins.first->second->push_back(def);
 239 }
 240
 241 // Add a reference to a variable.
 242
 243 void
 244 Dataflow::add_ref(Named_object* var, Statement* statement)
 245 {
 246   Refs* refnull = NULL;
 247   std::pair<Refmap::iterator, bool> ins =
 248     this->refs_.insert(std::make_pair(var, refnull));
 249   if (ins.second)
 250     ins.first->second = new Refs;
 251   Ref ref;
 252   ref.statement = statement;
 253   ins.first->second->push_back(ref);
 254 }
 255
 256 // Return the definitions of a variable.
 257
 258 const Dataflow::Defs*
 259 Dataflow::find_defs(Named_object* var) const
 260 {
 261   Defmap::const_iterator p = this->defs_.find(var);
 262   if (p == this->defs_.end())
 263     return NULL;
 264   else
 265     return p->second;
 266 }
 267
 268 // Return the references of a variable.
 269
 270 const Dataflow::Refs*
 271 Dataflow::find_refs(Named_object* var) const
 272 {
 273   Refmap::const_iterator p = this->refs_.find(var);
 274   if (p == this->refs_.end())
 275     return NULL;
 276   else
 277     return p->second;
 278 }