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 249 matching lines @@
 
 static bool IsPositiveOrZeroSmiConst(Definition* d) {
   ConstantInstr* const_instr = d->AsConstant();
   if ((const_instr != NULL) && (const_instr->value().IsSmi())) {
     return Smi::Cast(const_instr->value()).Value() >= 0;
   }
   return false;
 }
 
 
+Definition* FlowGraphOptimizer::OptimizeMint32BitMasks(
+    BinaryMintOpInstr* mask) {
+  ASSERT(mask != NULL);
+  ASSERT(mask->op_kind() == Token::kBIT_AND);
+  Range* range = mask->range();
+  if ((range == NULL) || !range->Is32BitMask()) {

[Florian Schneider, 2014/06/25 11:36:00]

This should work for any positive mask value, not just 0xffffffff.

+    // No range or range is not exactly [0, 0xFFFFFFFF].
+    return NULL;
+  }
+  // Find the mask target by looking for the input that isn't the constant
+  // 0xFFFFFFFF.
+  Value* target = NULL;
+  if (mask->InputAt(0)->BindsTo32BitMaskConstant()) {
+    target = mask->InputAt(1);
+  } else if (mask->InputAt(1)->BindsTo32BitMaskConstant()) {
+    target = mask->InputAt(0);
+  } else {
+    return NULL;
+  }
+  // If the target has multiple uses, we can't assume its range can be safely
+  // constrained by this mask.
+  if (!target->IsSingleUse()) {

[Florian Schneider, 2014/06/25 11:36:00]

That's too strict: It's ok as long as target is masked with a 32-bit unsigned
integer at all uses.

This also includes for instance stores to Uint8, Uint16, Uint32 typed arrays.
(alternatively, we could make implicit masking for those array stores explicit
in the IL)

+    return NULL;
+  }
+
+  Definition* def = target->definition();
+  if (!def->IsMintDefinition()) {
+    // TODO(johnmccutchan): Should this be an ASSERT?
+    return NULL;
+  }
+  def->range()->Make32BitMask();
+
+  return def;
+}
+
+
+bool FlowGraphOptimizer::TryMarkMint32Bit(Definition* mintop) {
+  ASSERT(mintop != NULL);
+  ASSERT(mintop->IsMintDefinition());
+
+  Range* range = mintop->range();
+  if (range == NULL) {
+    return false;
+  }
+  bool is_32_bit = false;
+  if (range->Is32BitMask()) {
+    is_32_bit = true;
+  } else if (range->IsWithin(0, kMaxUint32)) {
+    is_32_bit = true;
+  }
+
+  if (!is_32_bit) {
+    return false;
+  }
+
+  if (mintop->IsBinaryMintOp()) {
+    BinaryMintOpInstr* instr = mintop->AsBinaryMintOp();
+    instr->set_is_32_bit(true);
+  } else if (mintop->IsShiftMintOp()) {
+    ShiftMintOpInstr* instr = mintop->AsShiftMintOp();
+    instr->set_is_32_bit(true);
+  } else if (mintop->IsUnboxInteger()) {
+    UnboxIntegerInstr* instr = mintop->AsUnboxInteger();
+    instr->set_is_32_bit(true);
+  } else if (mintop->IsUnaryMintOp()) {
+    UnaryMintOpInstr* instr = mintop->AsUnaryMintOp();
+    instr->set_is_32_bit(true);
+  } else {
+    return false;
+  }
+
+  return true;
+}
+
+
 void FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp(
     Definition* bit_and_instr,
     Definition* left_instr,
     Definition* right_instr) {
   ASSERT(bit_and_instr != NULL);
   ASSERT((left_instr != NULL) && (right_instr != NULL));
 
   // Check for pattern, smi_shift_left must be single-use.
   bool is_positive_or_zero = IsPositiveOrZeroSmiConst(left_instr);
   if (!is_positive_or_zero) {
     is_positive_or_zero = IsPositiveOrZeroSmiConst(right_instr);
   }
-  if (!is_positive_or_zero) return;
+  if (!is_positive_or_zero) {
+    return;
+  }
 
   BinarySmiOpInstr* smi_shift_left = NULL;
   if (bit_and_instr->InputAt(0)->IsSingleUse()) {
     smi_shift_left = AsSmiShiftLeftInstruction(left_instr);
   }
   if ((smi_shift_left == NULL) && (bit_and_instr->InputAt(1)->IsSingleUse())) {
     smi_shift_left = AsSmiShiftLeftInstruction(right_instr);
   }
-  if (smi_shift_left == NULL) return;
+  if (smi_shift_left == NULL) {
+    return;
+  }
 
   // Pattern recognized.
   smi_shift_left->set_is_truncating(true);
   ASSERT(bit_and_instr->IsBinarySmiOp() || bit_and_instr->IsBinaryMintOp());
   if (bit_and_instr->IsBinaryMintOp()) {
     // Replace Mint op with Smi op.
     BinarySmiOpInstr* smi_op = new(I) BinarySmiOpInstr(
         Token::kBIT_AND,
         new(I) Value(left_instr),
         new(I) Value(right_instr),
@@ skipping 216 matching lines @@
           }
         }
       }
     }
     TryMergeTruncDivMod(&div_mod_merge);
     TryMergeMathUnary(&sin_cos_merge);
     current_iterator_ = NULL;
   }
 }
 
-
 static void EnsureSSATempIndex(FlowGraph* graph,
                                Definition* defn,
                                Definition* replacement) {
   if ((replacement->ssa_temp_index() == -1) &&
       (defn->ssa_temp_index() != -1)) {
     replacement->set_ssa_temp_index(graph->alloc_ssa_temp_index());
   }
 }
 
 
@@ skipping 18 matching lines @@
       OS::Print("Removing %s\n", current->DebugName());
     } else {
       ASSERT(!current_defn->HasUses());
       OS::Print("Removing v%" Pd ".\n", current_defn->ssa_temp_index());
     }
   }
   iterator->RemoveCurrentFromGraph();
 }
 
 
+void FlowGraphOptimizer::TryRangeDerivedOptimizations() {
+  ASSERT(current_iterator_ == NULL);
+
+  for (intptr_t i = 0; i < block_order_.length(); ++i) {
+    BlockEntryInstr* entry = block_order_[i];
+    // First set range information on inputs to a mint mask. The following two
+    // patterns are supported:
+    // v7 & 0xFFFFFFFF;
+    // 0xFFFFFFFF & v7;
+    // Afterwards, if v7 only has a single use, v7 is marked as having
+    // a 32-bit range. Also, the mask operation is removed.
+    {
+      ForwardInstructionIterator it(entry);
+      current_iterator_ = &it;
+      for (; !it.Done(); it.Advance()) {
+        // Constrain ranges of mint operations whose only use is a mint mask op.
+        if (it.Current()->IsBinaryMintOp()) {
+          BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp();
+          if (mintop->op_kind() == Token::kBIT_AND) {
+            Definition* masked = OptimizeMint32BitMasks(mintop);
+            if (masked != NULL) {
+              // Replace mask instruction with masked input.
+              ReplaceCurrentInstruction(current_iterator(),
+                                        mintop,
+                                        masked,
+                                        flow_graph());
+            }
+          }
+        }
+      }
+      current_iterator_ = NULL;
+    }
+    // Mark mint instructions whose range information says they are positive
+    // and fit in 32-bits as 32-bit.
+    {
+      ForwardInstructionIterator it(entry);
+      current_iterator_ = &it;
+      for (; !it.Done(); it.Advance()) {
+        if (!it.Current()->IsDefinition()) {
+          continue;
+        }
+        Definition* def = it.Current()->AsDefinition();
+        if (def->IsMintDefinition()) {
+          TryMarkMint32Bit(def);
+        }
+      }
+      current_iterator_ = NULL;
+    }
+  }
+}
+
+
 bool FlowGraphOptimizer::Canonicalize() {
   bool changed = false;
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* entry = block_order_[i];
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       Instruction* replacement = current->Canonicalize(flow_graph());
       if (replacement != current) {
         // For non-definitions Canonicalize should return either NULL or
         // this.
@@ skipping 27 matching lines @@
   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 == kUnboxedMint32)) {
+    converted = new(I) MintConverterInstr(MintConverterInstr::kMintToMint32,
+                                          use->CopyWithType());
+  } else if ((from == kUnboxedMint32) && (to == kUnboxedMint)) {
+    converted = new(I) MintConverterInstr(MintConverterInstr::kMint32ToMint,
+                                          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 7870 matching lines @@
   // TODO(kmillikin): Handle unbox operation.
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitBinaryMintOp(BinaryMintOpInstr* instr) {
   HandleBinaryOp(instr, instr->op_kind(), *instr->left(), *instr->right());
 }
 
 
+void ConstantPropagator::VisitMintConverter(MintConverterInstr* instr) {
+  SetValue(instr, non_constant_);
+}
+
+
 void ConstantPropagator::VisitShiftMintOp(ShiftMintOpInstr* instr) {
   HandleBinaryOp(instr, instr->op_kind(), *instr->left(), *instr->right());
 }
 
 
 void ConstantPropagator::VisitUnaryMintOp(UnaryMintOpInstr* instr) {
   // TODO(kmillikin): Handle unary operations.
   SetValue(instr, non_constant_);
 }
 
@@ skipping 1303 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