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 Propagate();
+  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();
+  Propagate();
+  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()) {

[Florian Schneider, 2014/07/08 12:24:29]

Add a TODO to handle smi operations as well:

BinarySmiOp can be converted into Uint32 as well. For example when doing n smi
shifts or smi multiplication we currently have to tag the result or the untag
input. These tag/untag operations could be eliminated by doing untagged uint32
arithmetic.  

[Cutch, 2014/07/09 17:48:26]

Done.

+    // Not a mint op.
+    return false;
+  }
+  if (def->IsLoadField()) {

[Florian Schneider, 2014/07/08 12:24:29]

Why is this needed? I'd rather enumerate the operations that you want to
consider here (for now *MintOp, Box-/UnboxInteger, etc), since IsMintDefinition
does not do the right thing here (because of e.g. LoadField, but potentially
others as well)

[Cutch, 2014/07/09 17:48:25]

Done.

+    // 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 =

[Florian Schneider, 2014/07/08 12:24:28]

Initial definitions are only Parameter or Constant. So I don't think it's
necessary to handle them here.

[Cutch, 2014/07/09 17:48:26]

Done.

+      *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();
+
+    if (block->IsCatchBlockEntry()) {
+      const GrowableArray<Definition*>& initial =
+          *block->AsCatchBlockEntry()->initial_definitions();
+      for (intptr_t i = 0; i < initial.length(); ++i) {

[Florian Schneider, 2014/07/08 12:24:28]

No need to handle initial definitions here either.

[Cutch, 2014/07/09 17:48:26]

Done.

+        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()) {

[Vyacheslav Egorov (Google), 2014/07/08 12:39:31]

should be checking the range of input for the high bits

(1 << 48) >> 32 fits into Uint32 but (1 << 48) can't be truncated to Uint32.
 

[Cutch, 2014/07/09 17:48:26]

Done.

+    ShiftMintOpInstr* op = def->AsShiftMintOp();
+    if (op->op_kind() == Token::kSHR) {
+      Range* range = op->range();

[Florian Schneider, 2014/07/08 12:24:29]

I think you need to check the range of the input so that the hi-half of the
input is 0. Please also add a test for this case.

[Cutch, 2014/07/09 17:48:25]

Done.

+      if ((range == NULL) ||
+          !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) {
+        return false;
+      }
+    }
+  }
+  if (!def->HasUses()) {
+    // No uses, skip.
+    return false;
+  }
+  // All input uses are candidates.
+  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;
+    }
+  }
+
+  // All environment uses are candidates.

[Vyacheslav Egorov (Google), 2014/07/08 12:39:30]

ShiftUint32OpInstr can deopt even though it is truncating/narrowing, but it
throws at this point.

I can't construct the bad case immediately, it is a bit spooky. We need to think
about this.

[Cutch, 2014/07/09 17:48:26]

We are conservatively replacing MintOps with Uint32Ops and the Uint32Ops deopt
cases are a subset of the MintOps deopt cases. So, we aren't introducing any new
potential deoptimization points, just possibly removing them. 

BTW- for my own knowledge, I could use some more information/context about
environment uses and the expectations around them.

+  for (Value* use = def->env_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;
+}
+
+
+void IntegerInstructionSelector::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/08 12:39:31]

Why there is no truncation here?

[Cutch, 2014/07/09 17:48:25]

Are you saying the constant resulting from HandleBinaryOp should be truncated to
32-bits?

[Vyacheslav Egorov (Google), 2014/07/11 16:00:08]

Yes, to uint32 range, to ensure that constant_value computed by constant
propagation would match what instruction would produce when running the same
instruction native code.

[Cutch, 2014/07/11 22:04:13]

Done.

+}
+
+
+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