Go patch committed: Fix order of evaluation of boolean expressions

Message ID CAOyqgcXmc3TzM1rkBwf_0Loyzxt=6X5X-1+eJ=C=svKAhV_EeA@mail.gmail.com
State New
Headers show
Series
  • Go patch committed: Fix order of evaluation of boolean expressions
Related show

Commit Message

Ian Lance Taylor July 20, 2018, 7:56 p.m.
This patch by Cherry Zhang changes the Go frontend to run the
order_evaluations before the remove_shortcuts pass.

In remove_shortcuts, the shortcut expressions (&&, ||) are rewritten
to if statements, which are lifted out before the statement containing
the shortcut expression.  If the containing statement has other
(sub)expressions that should be evaluated before the shortcut
expression, which has not been lifted out, this will result in
incorrect evaluation order.

For example, F() + G(A() && B()), the evaluation order per the
language spec is F, A, B (if A returns true), G. If we lift A() and
B() out first, they will be called before F, which is wrong.

To fix this, this patch splits order_evaluations to two phases.  The
first phase, which runs before remove_shortcuts, skips shortcut
expressions' components.  So it won't lift out subexpressions that are
evaluated conditionally.  The shortcut expression itself is ordered,
since it may have side effects.  Then we run remove_shortcuts.  At
this point the subexpressions that should be evaluated before the
shortcut expression are already lifted out.  The remove_shortcuts pass
also runs the second phase of order_evaluations to order the
components of shortcut expressions, which were skipped during the
first phase.

This reorders the code blocks of remove_shortcuts and
order_evaluations, since remove_shortcuts now calls Order_eval.

This fixes https://golang.org/issue/26495.

Bootstrapped and ran Go testsuite on x86_64-pc-linux-gnu.  Committed
to mainline.

Ian

Patch

Index: gcc/go/gofrontend/MERGE
===================================================================
--- gcc/go/gofrontend/MERGE	(revision 262833)
+++ gcc/go/gofrontend/MERGE	(working copy)
@@ -1,4 +1,4 @@ 
-38850073f25f9de4f3daa33d799def3a33c942ab
+39d4d755db7d71b5e770ca435a8b1d1f08f53185
 
 The first line of this file holds the git revision number of the last
 merge done from the gofrontend repository.
Index: gcc/go/gofrontend/go.cc
===================================================================
--- gcc/go/gofrontend/go.cc	(revision 262658)
+++ gcc/go/gofrontend/go.cc	(working copy)
@@ -143,12 +143,12 @@  go_parse_input_files(const char** filena
   // Export global identifiers as appropriate.
   ::gogo->do_exports();
 
-  // Turn short-cut operators (&&, ||) into explicit if statements.
-  ::gogo->remove_shortcuts();
-
   // Use temporary variables to force order of evaluation.
   ::gogo->order_evaluations();
 
+  // Turn short-cut operators (&&, ||) into explicit if statements.
+  ::gogo->remove_shortcuts();
+
   // Convert named types to backend representation.
   ::gogo->convert_named_types();
 
Index: gcc/go/gofrontend/gogo.cc
===================================================================
--- gcc/go/gofrontend/gogo.cc	(revision 262658)
+++ gcc/go/gofrontend/gogo.cc	(working copy)
@@ -3432,210 +3432,6 @@  Gogo::check_types_in_block(Block* block)
   block->traverse(&traverse);
 }
 
-// A traversal class used to find a single shortcut operator within an
-// expression.
-
-class Find_shortcut : public Traverse
-{
- public:
-  Find_shortcut()
-    : Traverse(traverse_blocks
-	       | traverse_statements
-	       | traverse_expressions),
-      found_(NULL)
-  { }
-
-  // A pointer to the expression which was found, or NULL if none was
-  // found.
-  Expression**
-  found() const
-  { return this->found_; }
-
- protected:
-  int
-  block(Block*)
-  { return TRAVERSE_SKIP_COMPONENTS; }
-
-  int
-  statement(Block*, size_t*, Statement*)
-  { return TRAVERSE_SKIP_COMPONENTS; }
-
-  int
-  expression(Expression**);
-
- private:
-  Expression** found_;
-};
-
-// Find a shortcut expression.
-
-int
-Find_shortcut::expression(Expression** pexpr)
-{
-  Expression* expr = *pexpr;
-  Binary_expression* be = expr->binary_expression();
-  if (be == NULL)
-    return TRAVERSE_CONTINUE;
-  Operator op = be->op();
-  if (op != OPERATOR_OROR && op != OPERATOR_ANDAND)
-    return TRAVERSE_CONTINUE;
-  go_assert(this->found_ == NULL);
-  this->found_ = pexpr;
-  return TRAVERSE_EXIT;
-}
-
-// A traversal class used to turn shortcut operators into explicit if
-// statements.
-
-class Shortcuts : public Traverse
-{
- public:
-  Shortcuts(Gogo* gogo)
-    : Traverse(traverse_variables
-	       | traverse_statements),
-      gogo_(gogo)
-  { }
-
- protected:
-  int
-  variable(Named_object*);
-
-  int
-  statement(Block*, size_t*, Statement*);
-
- private:
-  // Convert a shortcut operator.
-  Statement*
-  convert_shortcut(Block* enclosing, Expression** pshortcut);
-
-  // The IR.
-  Gogo* gogo_;
-};
-
-// Remove shortcut operators in a single statement.
-
-int
-Shortcuts::statement(Block* block, size_t* pindex, Statement* s)
-{
-  // FIXME: This approach doesn't work for switch statements, because
-  // we add the new statements before the whole switch when we need to
-  // instead add them just before the switch expression.  The right
-  // fix is probably to lower switch statements with nonconstant cases
-  // to a series of conditionals.
-  if (s->switch_statement() != NULL)
-    return TRAVERSE_CONTINUE;
-
-  while (true)
-    {
-      Find_shortcut find_shortcut;
-
-      // If S is a variable declaration, then ordinary traversal won't
-      // do anything.  We want to explicitly traverse the
-      // initialization expression if there is one.
-      Variable_declaration_statement* vds = s->variable_declaration_statement();
-      Expression* init = NULL;
-      if (vds == NULL)
-	s->traverse_contents(&find_shortcut);
-      else
-	{
-	  init = vds->var()->var_value()->init();
-	  if (init == NULL)
-	    return TRAVERSE_CONTINUE;
-	  init->traverse(&init, &find_shortcut);
-	}
-      Expression** pshortcut = find_shortcut.found();
-      if (pshortcut == NULL)
-	return TRAVERSE_CONTINUE;
-
-      Statement* snew = this->convert_shortcut(block, pshortcut);
-      block->insert_statement_before(*pindex, snew);
-      ++*pindex;
-
-      if (pshortcut == &init)
-	vds->var()->var_value()->set_init(init);
-    }
-}
-
-// Remove shortcut operators in the initializer of a global variable.
-
-int
-Shortcuts::variable(Named_object* no)
-{
-  if (no->is_result_variable())
-    return TRAVERSE_CONTINUE;
-  Variable* var = no->var_value();
-  Expression* init = var->init();
-  if (!var->is_global() || init == NULL)
-    return TRAVERSE_CONTINUE;
-
-  while (true)
-    {
-      Find_shortcut find_shortcut;
-      init->traverse(&init, &find_shortcut);
-      Expression** pshortcut = find_shortcut.found();
-      if (pshortcut == NULL)
-	return TRAVERSE_CONTINUE;
-
-      Statement* snew = this->convert_shortcut(NULL, pshortcut);
-      var->add_preinit_statement(this->gogo_, snew);
-      if (pshortcut == &init)
-	var->set_init(init);
-    }
-}
-
-// Given an expression which uses a shortcut operator, return a
-// statement which implements it, and update *PSHORTCUT accordingly.
-
-Statement*
-Shortcuts::convert_shortcut(Block* enclosing, Expression** pshortcut)
-{
-  Binary_expression* shortcut = (*pshortcut)->binary_expression();
-  Expression* left = shortcut->left();
-  Expression* right = shortcut->right();
-  Location loc = shortcut->location();
-
-  Block* retblock = new Block(enclosing, loc);
-  retblock->set_end_location(loc);
-
-  Temporary_statement* ts = Statement::make_temporary(shortcut->type(),
-						      left, loc);
-  retblock->add_statement(ts);
-
-  Block* block = new Block(retblock, loc);
-  block->set_end_location(loc);
-  Expression* tmpref = Expression::make_temporary_reference(ts, loc);
-  Statement* assign = Statement::make_assignment(tmpref, right, loc);
-  block->add_statement(assign);
-
-  Expression* cond = Expression::make_temporary_reference(ts, loc);
-  if (shortcut->binary_expression()->op() == OPERATOR_OROR)
-    cond = Expression::make_unary(OPERATOR_NOT, cond, loc);
-
-  Statement* if_statement = Statement::make_if_statement(cond, block, NULL,
-							 loc);
-  retblock->add_statement(if_statement);
-
-  *pshortcut = Expression::make_temporary_reference(ts, loc);
-
-  delete shortcut;
-
-  // Now convert any shortcut operators in LEFT and RIGHT.
-  Shortcuts shortcuts(this->gogo_);
-  retblock->traverse(&shortcuts);
-
-  return Statement::make_block_statement(retblock, loc);
-}
-
-// Turn shortcut operators into explicit if statements.  Doing this
-// considerably simplifies the order of evaluation rules.
-
-void
-Gogo::remove_shortcuts()
-{
-  Shortcuts shortcuts(this);
-  this->traverse(&shortcuts);
-}
-
 // A traversal class which finds all the expressions which must be
 // evaluated in order within a statement or larger expression.  This
 // is used to implement the rules about order of evaluation.
@@ -3689,6 +3485,18 @@  class Find_eval_ordering : public Traver
 int
 Find_eval_ordering::expression(Expression** expression_pointer)
 {
+  Binary_expression* binexp = (*expression_pointer)->binary_expression();
+  if (binexp != NULL
+      && (binexp->op() == OPERATOR_ANDAND || binexp->op() == OPERATOR_OROR))
+    {
+      // Shortcut expressions may potentially have side effects which need
+      // to be ordered, so add them to the list.
+      // We don't order its subexpressions here since they may be evaluated
+      // conditionally. This is handled in remove_shortcuts.
+      this->exprs_.push_back(expression_pointer);
+      return TRAVERSE_SKIP_COMPONENTS;
+    }
+
   // We have to look at subexpressions before this one.
   if ((*expression_pointer)->traverse_subexpressions(this) == TRAVERSE_EXIT)
     return TRAVERSE_EXIT;
@@ -3925,6 +3733,215 @@  Gogo::order_evaluations()
   this->traverse(&order_eval);
 }
 
+// A traversal class used to find a single shortcut operator within an
+// expression.
+
+class Find_shortcut : public Traverse
+{
+ public:
+  Find_shortcut()
+    : Traverse(traverse_blocks
+	       | traverse_statements
+	       | traverse_expressions),
+      found_(NULL)
+  { }
+
+  // A pointer to the expression which was found, or NULL if none was
+  // found.
+  Expression**
+  found() const
+  { return this->found_; }
+
+ protected:
+  int
+  block(Block*)
+  { return TRAVERSE_SKIP_COMPONENTS; }
+
+  int
+  statement(Block*, size_t*, Statement*)
+  { return TRAVERSE_SKIP_COMPONENTS; }
+
+  int
+  expression(Expression**);
+
+ private:
+  Expression** found_;
+};
+
+// Find a shortcut expression.
+
+int
+Find_shortcut::expression(Expression** pexpr)
+{
+  Expression* expr = *pexpr;
+  Binary_expression* be = expr->binary_expression();
+  if (be == NULL)
+    return TRAVERSE_CONTINUE;
+  Operator op = be->op();
+  if (op != OPERATOR_OROR && op != OPERATOR_ANDAND)
+    return TRAVERSE_CONTINUE;
+  go_assert(this->found_ == NULL);
+  this->found_ = pexpr;
+  return TRAVERSE_EXIT;
+}
+
+// A traversal class used to turn shortcut operators into explicit if
+// statements.
+
+class Shortcuts : public Traverse
+{
+ public:
+  Shortcuts(Gogo* gogo)
+    : Traverse(traverse_variables
+	       | traverse_statements),
+      gogo_(gogo)
+  { }
+
+ protected:
+  int
+  variable(Named_object*);
+
+  int
+  statement(Block*, size_t*, Statement*);
+
+ private:
+  // Convert a shortcut operator.
+  Statement*
+  convert_shortcut(Block* enclosing, Expression** pshortcut);
+
+  // The IR.
+  Gogo* gogo_;
+};
+
+// Remove shortcut operators in a single statement.
+
+int
+Shortcuts::statement(Block* block, size_t* pindex, Statement* s)
+{
+  // FIXME: This approach doesn't work for switch statements, because
+  // we add the new statements before the whole switch when we need to
+  // instead add them just before the switch expression.  The right
+  // fix is probably to lower switch statements with nonconstant cases
+  // to a series of conditionals.
+  if (s->switch_statement() != NULL)
+    return TRAVERSE_CONTINUE;
+
+  while (true)
+    {
+      Find_shortcut find_shortcut;
+
+      // If S is a variable declaration, then ordinary traversal won't
+      // do anything.  We want to explicitly traverse the
+      // initialization expression if there is one.
+      Variable_declaration_statement* vds = s->variable_declaration_statement();
+      Expression* init = NULL;
+      if (vds == NULL)
+	s->traverse_contents(&find_shortcut);
+      else
+	{
+	  init = vds->var()->var_value()->init();
+	  if (init == NULL)
+	    return TRAVERSE_CONTINUE;
+	  init->traverse(&init, &find_shortcut);
+	}
+      Expression** pshortcut = find_shortcut.found();
+      if (pshortcut == NULL)
+	return TRAVERSE_CONTINUE;
+
+      Statement* snew = this->convert_shortcut(block, pshortcut);
+      block->insert_statement_before(*pindex, snew);
+      ++*pindex;
+
+      if (pshortcut == &init)
+	vds->var()->var_value()->set_init(init);
+    }
+}
+
+// Remove shortcut operators in the initializer of a global variable.
+
+int
+Shortcuts::variable(Named_object* no)
+{
+  if (no->is_result_variable())
+    return TRAVERSE_CONTINUE;
+  Variable* var = no->var_value();
+  Expression* init = var->init();
+  if (!var->is_global() || init == NULL)
+    return TRAVERSE_CONTINUE;
+
+  while (true)
+    {
+      Find_shortcut find_shortcut;
+      init->traverse(&init, &find_shortcut);
+      Expression** pshortcut = find_shortcut.found();
+      if (pshortcut == NULL)
+	return TRAVERSE_CONTINUE;
+
+      Statement* snew = this->convert_shortcut(NULL, pshortcut);
+      var->add_preinit_statement(this->gogo_, snew);
+      if (pshortcut == &init)
+	var->set_init(init);
+    }
+}
+
+// Given an expression which uses a shortcut operator, return a
+// statement which implements it, and update *PSHORTCUT accordingly.
+
+Statement*
+Shortcuts::convert_shortcut(Block* enclosing, Expression** pshortcut)
+{
+  Binary_expression* shortcut = (*pshortcut)->binary_expression();
+  Expression* left = shortcut->left();
+  Expression* right = shortcut->right();
+  Location loc = shortcut->location();
+
+  Block* retblock = new Block(enclosing, loc);
+  retblock->set_end_location(loc);
+
+  Temporary_statement* ts = Statement::make_temporary(shortcut->type(),
+						      left, loc);
+  retblock->add_statement(ts);
+
+  Block* block = new Block(retblock, loc);
+  block->set_end_location(loc);
+  Expression* tmpref = Expression::make_temporary_reference(ts, loc);
+  Statement* assign = Statement::make_assignment(tmpref, right, loc);
+  block->add_statement(assign);
+
+  Expression* cond = Expression::make_temporary_reference(ts, loc);
+  if (shortcut->binary_expression()->op() == OPERATOR_OROR)
+    cond = Expression::make_unary(OPERATOR_NOT, cond, loc);
+
+  Statement* if_statement = Statement::make_if_statement(cond, block, NULL,
+							 loc);
+  retblock->add_statement(if_statement);
+
+  *pshortcut = Expression::make_temporary_reference(ts, loc);
+
+  delete shortcut;
+
+  // Now convert any shortcut operators in LEFT and RIGHT.
+  // LEFT and RIGHT were skipped in the top level
+  // Gogo::order_evaluations. We need to order their
+  // components first.
+  Order_eval order_eval(this->gogo_);
+  retblock->traverse(&order_eval);
+  Shortcuts shortcuts(this->gogo_);
+  retblock->traverse(&shortcuts);
+
+  return Statement::make_block_statement(retblock, loc);
+}
+
+// Turn shortcut operators into explicit if statements.  Doing this
+// considerably simplifies the order of evaluation rules.
+
+void
+Gogo::remove_shortcuts()
+{
+  Shortcuts shortcuts(this);
+  this->traverse(&shortcuts);
+}
+
 // Traversal to flatten parse tree after order of evaluation rules are applied.
 
 class Flatten : public Traverse