Add Uint32 representation

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 1160b9f9bc53148aa4af538e99925cfb3224466e..85e8429630c7f012ae61cb739482d8e1e8b05648 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -44,6 +44,8 @@ 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);
@@ -608,10 +610,12 @@ void FlowGraphOptimizer::InsertConversion(Representation from,
     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.
@@ -5147,6 +5151,320 @@ void FlowGraphOptimizer::InferIntRanges() {
 }
 
 
+// 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
@@ -8912,6 +9230,40 @@ void ConstantPropagator::VisitBoxInt32x4(BoxInt32x4Instr* instr) {
 }
 
 
+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());