Add Uint32 representation

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 26 matching lines @@
 DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
 DEFINE_FLAG(bool, trace_constant_propagation, false,
     "Print constant propagation and useless code elimination.");
 DEFINE_FLAG(bool, trace_load_optimization, false,
     "Print live sets for load optimization pass.");
 DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details.");
 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress");
 DEFINE_FLAG(bool, truncating_left_shift, true,
     "Optimize left shift to truncate if possible");
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
+DEFINE_FLAG(bool, trace_integer_ir_selection, false,
+    "Print integer IR selection optimization pass.");
 DECLARE_FLAG(bool, enable_type_checks);
 DECLARE_FLAG(bool, source_lines);
 DECLARE_FLAG(bool, trace_type_check_elimination);
 DECLARE_FLAG(bool, warn_on_javascript_compatibility);
 
 // Quick access to the locally defined isolate() method.
 #define I (isolate())
 
 static bool ShouldInlineSimd() {
   return FlowGraphCompiler::SupportsUnboxedSimd128();
@@ skipping 544 matching lines @@
     deopt_target = insert_before = use->instruction();
   }
 
   Definition* converted = NULL;
   if ((from == kTagged) && (to == kUnboxedMint)) {
     ASSERT((deopt_target != NULL) ||
            (use->Type()->ToCid() == kUnboxedMint));
     const intptr_t deopt_id = (deopt_target != NULL) ?
         deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId;
     converted = new(I) UnboxIntegerInstr(use->CopyWithType(), deopt_id);
-
   } else if ((from == kUnboxedMint) && (to == kTagged)) {
     converted = new(I) BoxIntegerInstr(use->CopyWithType());
-
+  } else if ((from == kUnboxedMint) && (to == kUnboxedUint32)) {
+    converted = new(I) UnboxedIntConverterInstr(from, to, use->CopyWithType());
+  } else if ((from == kUnboxedUint32) && (to == kUnboxedMint)) {
+    converted = new(I) UnboxedIntConverterInstr(from, to, use->CopyWithType());
   } else if (from == kUnboxedMint && to == kUnboxedDouble) {
     ASSERT(CanUnboxDouble());
     // Convert by boxing/unboxing.
     // TODO(fschneider): Implement direct unboxed mint-to-double conversion.
     BoxIntegerInstr* boxed =
         new(I) BoxIntegerInstr(use->CopyWithType());
     use->BindTo(boxed);
     InsertBefore(insert_before, boxed, NULL, FlowGraph::kValue);
 
     const intptr_t deopt_id = (deopt_target != NULL) ?
@@ skipping 4515 matching lines @@
   }
 }
 
 
 void FlowGraphOptimizer::InferIntRanges() {
   RangeAnalysis range_analysis(flow_graph_);
   range_analysis.Analyze();
 }
 
 
+// Replaces Mint IL instructions with Uint32 IL instructions
+// when possible. Uses output of RangeAnalysis.
+class IntegerInstructionSelector : public ValueObject {
+ public:
+  explicit IntegerInstructionSelector(FlowGraph* flow_graph)
+      : flow_graph_(flow_graph),
+        isolate_(NULL),
+        changed_(true) {
+    ASSERT(flow_graph_ != NULL);
+    isolate_ = flow_graph_->isolate();
+    ASSERT(isolate_ != NULL);
+    selected_uint32_defs_ =
+        new(I) BitVector(flow_graph_->current_ssa_temp_index());
+  }
+
+  void Select();
+
+ private:
+  bool IsPotentialUint32Definition(Definition* def);
+  void FindPotentialUint32Definitions();
+  bool IsInitialUint32Candidate(Definition* def);
+  void SelectInitialUint32Definitions();
+  bool IsUint32Candidate(Definition* def);
+  void Iterate();
+  Definition* ConstructReplacementFor(Definition* def);
+  void ReplaceInstructions();
+
+  Isolate* isolate() const { return isolate_; }
+
+  GrowableArray<Definition*> potential_uint32_defs_;
+  BitVector* selected_uint32_defs_;
+
+  FlowGraph* flow_graph_;
+  Isolate* isolate_;
+  bool changed_;
+};
+
+
+void IntegerInstructionSelector::Select() {
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("---- starting integer ir selection -------\n");
+  }
+  FindPotentialUint32Definitions();
+  SelectInitialUint32Definitions();

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

"InitialDefinition" is a confusing name. I would call it
"FindNarrowingOperations" as we are looking for operations that narrow to Uint32
range.

Likewise in all other method names I suggest using Narrowing (or truncating -
which is a name we already use in a couple of places, though I like narrowing
more) to signify what we are looking for. 

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

"InitialDefinition" is a confusing name. I would call it
"FindNarrowingOperations" as we are looking for operations that narrow to Uint32
range.

+  Iterate();
+  ReplaceInstructions();
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("---- after integer ir selection -------\n");
+    FlowGraphPrinter printer(*flow_graph_);
+    printer.PrintBlocks();
+  }
+}
+
+
+bool IntegerInstructionSelector::IsPotentialUint32Definition(Definition* def) {
+  if (!def->IsMintDefinition()) {
+    // Not a mint op.
+    return false;
+  }
+  if (def->IsLoadField()) {
+    // A load of a mint field.
+    return false;
+  }
+  return true;
+}
+
+
+void IntegerInstructionSelector::FindPotentialUint32Definitions() {
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("++++ Finding potential Uint32 definitions:\n");
+  }
+  const GrowableArray<Definition*>& initial =
+      *flow_graph_->graph_entry()->initial_definitions();
+  for (intptr_t i = 0; i < initial.length(); ++i) {
+    Definition* current = initial[i];
+    if (IsPotentialUint32Definition(current)) {
+      if (FLAG_trace_integer_ir_selection) {
+        OS::Print("Adding %s\n", current->ToCString());
+      }
+      potential_uint32_defs_.Add(current);
+    }
+  }
+
+  for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
+       !block_it.Done();
+       block_it.Advance()) {
+    BlockEntryInstr* block = block_it.Current();
+
+

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

remove empty line

[Cutch, 2014/07/07 22:34:28]

Done.

+    if (block->IsGraphEntry() || block->IsCatchBlockEntry()) {
+      const GrowableArray<Definition*>& initial = block->IsGraphEntry()
+          ? *block->AsGraphEntry()->initial_definitions()

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

Did not we already iterate over graph entry above?

[Cutch, 2014/07/07 22:34:28]

Done.

+          : *block->AsCatchBlockEntry()->initial_definitions();
+      for (intptr_t i = 0; i < initial.length(); ++i) {
+        Definition* current = initial[i];
+        if (IsPotentialUint32Definition(current)) {
+          if (FLAG_trace_integer_ir_selection) {
+           OS::Print("Adding %s\n", current->ToCString());
+          }
+          potential_uint32_defs_.Add(current);
+        }
+      }
+    }
+
+    for (ForwardInstructionIterator instr_it(block);
+         !instr_it.Done();
+         instr_it.Advance()) {
+      Instruction* current = instr_it.Current();
+      Definition* defn = current->AsDefinition();
+      if ((defn != NULL) && (defn->ssa_temp_index() != -1)) {
+        if (IsPotentialUint32Definition(defn)) {
+          if (FLAG_trace_integer_ir_selection) {
+           OS::Print("Adding %s\n", current->ToCString());
+          }
+          potential_uint32_defs_.Add(defn);
+        }
+      }
+    }
+  }
+}
+
+
+// BinaryMintOp masks and stores into unsigned typed arrays that truncate the
+// value into a Uint32 range.
+bool IntegerInstructionSelector::IsInitialUint32Candidate(Definition* def) {
+  if (def->IsBinaryMintOp()) {
+    BinaryMintOpInstr* op = def->AsBinaryMintOp();
+    // Must be a mask operation.
+    if (op->op_kind() != Token::kBIT_AND) {
+      return false;
+    }
+    Range* range = op->range();
+    if ((range == NULL) ||
+        !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) {
+      return false;
+    }
+    return true;
+  }
+  // TODO(johnmccutchan): Add typed array stores.
+  return false;
+}
+
+
+void IntegerInstructionSelector::SelectInitialUint32Definitions() {
+  ASSERT(selected_uint32_defs_ != NULL);
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("++++ Selecting Uint32 definitions:\n");
+    OS::Print("++++ Initial set:\n");
+  }
+  for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) {
+    Definition* defn = potential_uint32_defs_[i];
+    if (IsInitialUint32Candidate(defn)) {
+      if (FLAG_trace_integer_ir_selection) {
+        OS::Print("Adding %s\n", defn->ToCString());
+      }
+      selected_uint32_defs_->Add(defn->ssa_temp_index());
+    }
+  }
+}
+
+
+bool IntegerInstructionSelector::IsUint32Candidate(Definition* def) {
+  ASSERT(def->IsMintDefinition());
+  if (def->IsBoxInteger()) {
+    // If a BoxInteger's input is a candidate, the box is a candidate.
+    BoxIntegerInstr* box = def->AsBoxInteger();
+    Definition* box_input = box->value()->definition();
+    return selected_uint32_defs_->Contains(box_input->ssa_temp_index());
+  }
+  // A right shift with a range outside Uint32 cannot be converted because we
+  // may need the high bits.
+  if (def->IsShiftMintOp()) {
+    ShiftMintOpInstr* op = def->AsShiftMintOp();
+    if (op->op_kind() == Token::kSHR) {
+      Range* range = op->range();
+      if ((range == NULL) ||
+          !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) {
+        return false;
+      }
+    }
+  }
+  if (!def->HasUses()) {
+    // No uses, skip.

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

[sidenote: we should DCE those instructions :)]

+    return false;
+  }
+  // All uses are candidates.
+  Value* use = def->input_use_list();

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

What about environment uses? It is not safe to ignore them:

class Good {
  use(x) { return x & 0x1; }
}

class Bad {
  use(x) { return x & 0x100000000; }
}

f(o, x) => o.use(x << 1);

main() {
  final good = new Good(), bad = new Bad();
  for (...) f(good, 0x80000000);
  f(bad, 0x80000000);
}

when f() is optimized for Good object then x << 1 can be considered truncating,
but when f() is optimized for Bad it can't.

Fixpointing should take environment uses into account and also take into account
the fact that uint32 operation will not deoptimized if they are converted to
uint32.

+  bool only_candidate_uses = true;
+  while ((use != NULL) && only_candidate_uses) {
+    Instruction* instr = use->instruction();
+    if (!instr->IsDefinition()) {
+      // Not a definition.
+      only_candidate_uses = false;

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

return false;

[Cutch, 2014/07/07 22:34:28]

Done.

+      break;
+    }
+    Definition* defn = instr->AsDefinition();
+    if (!defn->IsMintDefinition()) {
+      // Not a mint definition.
+      only_candidate_uses = false;

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

return false;

[Cutch, 2014/07/07 22:34:28]

Done.

+      break;
+    }
+    only_candidate_uses = only_candidate_uses &&

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

only_candidate_uses are true at this point no need to && it.

[Cutch, 2014/07/07 22:34:28]

Done.

+        selected_uint32_defs_->Contains(defn->ssa_temp_index());

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

You can just do:

for (Value* use = def->input_use_list(); use != NULL; use = use->next_use()) {
  Definition* defn = use->instruction()->AsDefinition();
  if ((defn == NULL) ||
      (defn->ssa_temp_index() == -1) ||
      !selected_uint32_defs_->Contains(defn->ssa_temp_index())) {
    return false;
  }
}
return true;

this will cover also previous if (because selcted_uint32_defs_ would not contain
anything but MintDefinitions).

[Cutch, 2014/07/07 22:34:28]

Done.

+    use = use->next_use();
+  }
+  return only_candidate_uses;

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

return true;

+}
+
+
+void IntegerInstructionSelector::Iterate() {

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

I would call it Propagate().

+  ASSERT(selected_uint32_defs_ != NULL);
+  ASSERT(changed_);
+  intptr_t iteration = 0;
+  while (changed_) {
+    if (FLAG_trace_integer_ir_selection) {
+      OS::Print("+++ Iteration: %" Pd "\n", iteration++);
+    }
+    changed_ = false;
+    for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) {
+      Definition* defn = potential_uint32_defs_[i];
+      if (selected_uint32_defs_->Contains(defn->ssa_temp_index())) {
+        // Already marked as a candidate, skip.
+        continue;
+      }
+      if (defn->IsConstant()) {
+        // Skip constants.
+        continue;
+      }
+      if (IsUint32Candidate(defn)) {
+        if (FLAG_trace_integer_ir_selection) {
+          OS::Print("Adding %s\n", defn->ToCString());
+        }
+        // Found a new candidate.
+        selected_uint32_defs_->Add(defn->ssa_temp_index());
+        // Haven't reached fixed point yet.
+        changed_ = true;
+      }
+    }
+  }
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("Reached fixed point\n");
+  }
+}
+
+
+Definition* IntegerInstructionSelector::ConstructReplacementFor(
+    Definition* def) {
+  // Should only see mint definitions.
+  ASSERT(def->IsMintDefinition());
+  // Should not see constant instructions.
+  ASSERT(!def->IsConstant());
+  if (def->IsBinaryMintOp()) {
+    BinaryMintOpInstr* op = def->AsBinaryMintOp();
+    Token::Kind op_kind = op->op_kind();
+    Value* left = op->left()->CopyWithType();
+    Value* right = op->right()->CopyWithType();
+    intptr_t deopt_id = op->DeoptimizationTarget();
+    return new(I) BinaryUint32OpInstr(op_kind, left, right, deopt_id);
+  } else if (def->IsBoxInteger()) {
+    BoxIntegerInstr* box = def->AsBoxInteger();
+    Value* value = box->value()->CopyWithType();
+    return new(I) BoxUint32Instr(value);
+  } else if (def->IsUnboxInteger()) {
+    UnboxIntegerInstr* unbox = def->AsUnboxInteger();
+    Value* value = unbox->value()->CopyWithType();
+    intptr_t deopt_id = unbox->deopt_id();
+    return new(I) UnboxUint32Instr(value, deopt_id);
+  } else if (def->IsUnaryMintOp()) {
+    UnaryMintOpInstr* op = def->AsUnaryMintOp();
+    Token::Kind op_kind = op->op_kind();
+    Value* value = op->value()->CopyWithType();
+    intptr_t deopt_id = op->DeoptimizationTarget();
+    return new(I) UnaryUint32OpInstr(op_kind, value, deopt_id);
+  } else if (def->IsShiftMintOp()) {
+    ShiftMintOpInstr* op = def->AsShiftMintOp();
+    Token::Kind op_kind = op->op_kind();
+    Value* left = op->left()->CopyWithType();
+    Value* right = op->right()->CopyWithType();
+    intptr_t deopt_id = op->DeoptimizationTarget();
+    return new(I) ShiftUint32OpInstr(op_kind, left, right, deopt_id);
+  }
+  printf("%s\n", def->ToCString());
+  UNREACHABLE();
+  return NULL;
+}
+
+
+void IntegerInstructionSelector::ReplaceInstructions() {
+  if (FLAG_trace_integer_ir_selection) {
+    OS::Print("++++ Replacing instructions:\n");
+  }
+  for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) {
+    Definition* defn = potential_uint32_defs_[i];
+    if (!selected_uint32_defs_->Contains(defn->ssa_temp_index())) {
+      // Not a candidate.
+      continue;
+    }
+    Definition* replacement = ConstructReplacementFor(defn);
+    ASSERT(replacement != NULL);
+    if (FLAG_trace_integer_ir_selection) {
+      OS::Print("Replacing %s with %s\n", defn->ToCString(),
+                                          replacement->ToCString());
+    }
+    defn->ReplaceWith(replacement, NULL);
+    ASSERT(flow_graph_->VerifyUseLists());
+  }
+}
+
+void FlowGraphOptimizer::SelectIntegerInstructions() {
+  IntegerInstructionSelector iis(flow_graph_);
+  iis.Select();
+}
+
+
 void TryCatchAnalyzer::Optimize(FlowGraph* flow_graph) {
   // For every catch-block: Iterate over all call instructions inside the
   // corresponding try-block and figure out for each environment value if it
   // is the same constant at all calls. If yes, replace the initial definition
   // at the catch-entry with this constant.
   const GrowableArray<CatchBlockEntryInstr*>& catch_entries =
       flow_graph->graph_entry()->catch_entries();
   intptr_t base = kFirstLocalSlotFromFp + flow_graph->num_non_copied_params();
   for (intptr_t catch_idx = 0;
        catch_idx < catch_entries.length();
@@ skipping 3745 matching lines @@
   const Object& value = instr->value()->definition()->constant_value();
   if (IsNonConstant(value)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(value)) {
     // TODO(kmillikin): Handle conversion.
     SetValue(instr, non_constant_);
   }
 }
 
 
+void ConstantPropagator::VisitBoxUint32(BoxUint32Instr* instr) {
+  // TODO(kmillikin): Handle box operation.
+  SetValue(instr, non_constant_);
+}
+
+
+void ConstantPropagator::VisitUnboxUint32(UnboxUint32Instr* instr) {
+  // TODO(kmillikin): Handle unbox operation.
+  SetValue(instr, non_constant_);
+}
+
+
+void ConstantPropagator::VisitUnboxedIntConverter(
+    UnboxedIntConverterInstr* instr) {
+  SetValue(instr, non_constant_);
+}
+
+
+void ConstantPropagator::VisitBinaryUint32Op(BinaryUint32OpInstr* instr) {
+  HandleBinaryOp(instr, instr->op_kind(), *instr->left(), *instr->right());

[Vyacheslav Egorov (Google), 2014/07/07 16:16:03]

Should result of HandleBinaryOp be truncated to match the semantics of the
Uint32 operations?

+}
+
+
+void ConstantPropagator::VisitShiftUint32Op(ShiftUint32OpInstr* instr) {
+  HandleBinaryOp(instr, instr->op_kind(), *instr->left(), *instr->right());
+}
+
+
+void ConstantPropagator::VisitUnaryUint32Op(UnaryUint32OpInstr* instr) {
+  // TODO(kmillikin): Handle unary operations.
+  SetValue(instr, non_constant_);
+}
+
+
 void ConstantPropagator::Analyze() {
   GraphEntryInstr* entry = graph_->graph_entry();
   reachable_->Add(entry->preorder_number());
   block_worklist_.Add(entry);
 
   while (true) {
     if (block_worklist_.is_empty()) {
       if (definition_worklist_.is_empty()) break;
       Definition* definition = definition_worklist_.RemoveLast();
       definition_marks_->Remove(definition->ssa_temp_index());
@@ skipping 893 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart