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
17class 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
45static Named_object*
46get_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
60int
61Dataflow_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
71class 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
97void
98Dataflow_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
112void
113Dataflow_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
133void
134Dataflow_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
148class 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
167int
168Dataflow_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
182bool
183Dataflow::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
209Dataflow::Dataflow()
210  : defs_(), refs_()
211{
212}
213
214// Build the dataflow information.
215
216void
217Dataflow::initialize(Gogo* gogo)
218{
219  Dataflow_traverse_statements dts(this);
220  gogo->traverse(&dts);
221}
222
223// Add a definition of a variable.
224
225void
226Dataflow::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
243void
244Dataflow::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
258const Dataflow::Defs*
259Dataflow::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
270const Dataflow::Refs*
271Dataflow::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}
279