New array bounds check elimination pass (focused on induction variables and bitwise operations).

src/hydrogen.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 50 matching lines @@
   int block_id() const { return block_id_; }
   void set_block_id(int id) { block_id_ = id; }
   HGraph* graph() const { return graph_; }
   Isolate* isolate() const;
   const ZoneList<HPhi*>* phis() const { return &phis_; }
   HInstruction* first() const { return first_; }
   HInstruction* last() const { return last_; }
   void set_last(HInstruction* instr) { last_ = instr; }
   HControlInstruction* end() const { return end_; }
   HLoopInformation* loop_information() const { return loop_information_; }
+  HLoopInformation* current_loop() const {
+    return IsLoopHeader() ? loop_information()
+                          : (parent_loop_header() != NULL
+                            ? parent_loop_header()->loop_information() : NULL);
+  }
   const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
   bool HasPredecessor() const { return predecessors_.length() > 0; }
   const ZoneList<HBasicBlock*>* dominated_blocks() const {
     return &dominated_blocks_;
   }
   const ZoneList<int>* deleted_phis() const {
     return &deleted_phis_;
   }
   void RecordDeletedPhi(int merge_index) {
     deleted_phis_.Add(merge_index, zone());
@@ skipping 163 matching lines @@
   const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
   HBasicBlock* loop_header() const { return loop_header_; }
   HBasicBlock* GetLastBackEdge() const;
   void RegisterBackEdge(HBasicBlock* block);
 
   HStackCheck* stack_check() const { return stack_check_; }
   void set_stack_check(HStackCheck* stack_check) {
     stack_check_ = stack_check;
   }
 
+  bool IsNestedInThisLoop(HLoopInformation* other) {
+    while (other != NULL) {
+      if (other == this) {
+        return true;
+      }
+      other = other->parent_loop();
+    }
+    return false;
+  }
+  bool IsNestedInThisLoop(HBasicBlock* other_block) {

[titzer, 2013/06/24 14:03:30]

This method overloading is just for convenience; I think it's better just to
have one version and inline this one into its caller(s). Or, you could inline
the other version into this method and remove the current_loop() method.

[Massi, 2013/07/01 13:10:49]

Removed and inlined.

+    return IsNestedInThisLoop(other_block->current_loop());
+  }
+  HLoopInformation* parent_loop() {
+    HBasicBlock* parent_header = loop_header()->parent_loop_header();
+    return parent_header != NULL ? parent_header->loop_information() : NULL;
+  }
+
  private:
   void AddBlock(HBasicBlock* block);
 
   ZoneList<HBasicBlock*> back_edges_;
   HBasicBlock* loop_header_;
   ZoneList<HBasicBlock*> blocks_;
   HStackCheck* stack_check_;
 };
 
 
 class BoundsCheckTable;
+class InductionVariableBlocksTable;
 class HGraph: public ZoneObject {
  public:
   explicit HGraph(CompilationInfo* info);
 
   Isolate* isolate() const { return isolate_; }
   Zone* zone() const { return zone_; }
   CompilationInfo* info() const { return info_; }
 
   const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
   const ZoneList<HPhi*>* phi_list() const { return phi_list_; }
@@ skipping 164 matching lines @@
                                         HValue* use_value,
                                         int use_index,
                                         Representation to);
   void InsertRepresentationChangesForValue(HValue* value);
   void InferTypes(ZoneList<HValue*>* worklist);
   void InitializeInferredTypes(int from_inclusive, int to_inclusive);
   void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
   void SetupInformativeDefinitionsInBlock(HBasicBlock* block);
   void SetupInformativeDefinitionsRecursively(HBasicBlock* block);
   void EliminateRedundantBoundsChecks(HBasicBlock* bb, BoundsCheckTable* table);
+  void EliminateRedundantBoundsChecksUsingInductionVariables();
+  void CollectInductionVariableData(HBasicBlock* bb,
+                                      InductionVariableBlocksTable* table);
+  void EliminateRedundantBoundsChecksUsingInductionVariables(
+      HBasicBlock* bb,
+      InductionVariableBlocksTable* table);
 
   Isolate* isolate_;
   int next_block_id_;
   HBasicBlock* entry_block_;
   HEnvironment* start_environment_;
   ZoneList<HBasicBlock*> blocks_;
   ZoneList<HValue*> values_;
   ZoneList<HPhi*>* phi_list_;
   ZoneList<HInstruction*>* uint32_instructions_;
   SetOncePointer<HConstant> undefined_constant_;
@@ skipping 1579 matching lines @@
   EmbeddedVector<char, 64> filename_;
   HeapStringAllocator string_allocator_;
   StringStream trace_;
   int indent_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_H_