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