LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-gvn.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 320 375 85.3 %
Date: 2017-04-26 Functions: 28 35 80.0 %

          Line data    Source code
       1             : // Copyright 2013 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/crankshaft/hydrogen-gvn.h"
       6             : 
       7             : #include "src/crankshaft/hydrogen.h"
       8             : #include "src/objects-inl.h"
       9             : #include "src/v8.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : 
      14             : class HInstructionMap final : public ZoneObject {
      15             :  public:
      16      288971 :   HInstructionMap(Zone* zone, SideEffectsTracker* side_effects_tracker)
      17             :       : array_size_(0),
      18             :         lists_size_(0),
      19             :         count_(0),
      20             :         array_(NULL),
      21             :         lists_(NULL),
      22             :         free_list_head_(kNil),
      23      577942 :         side_effects_tracker_(side_effects_tracker) {
      24      288971 :     ResizeLists(kInitialSize, zone);
      25      288975 :     Resize(kInitialSize, zone);
      26      288970 :   }
      27             : 
      28             :   void Kill(SideEffects side_effects);
      29             : 
      30     7825212 :   void Add(HInstruction* instr, Zone* zone) {
      31     7825212 :     present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr));
      32     7825218 :     Insert(instr, zone);
      33     7825272 :   }
      34             : 
      35             :   HInstruction* Lookup(HInstruction* instr) const;
      36             : 
      37     2096088 :   HInstructionMap* Copy(Zone* zone) const {
      38     2096090 :     return new(zone) HInstructionMap(zone, this);
      39             :   }
      40             : 
      41             :   bool IsEmpty() const { return count_ == 0; }
      42             : 
      43             :  private:
      44             :   // A linked list of HInstruction* values.  Stored in arrays.
      45             :   struct HInstructionMapListElement {
      46             :     HInstruction* instr;
      47             :     int next;  // Index in the array of the next list element.
      48             :   };
      49             :   static const int kNil = -1;  // The end of a linked list
      50             : 
      51             :   // Must be a power of 2.
      52             :   static const int kInitialSize = 16;
      53             : 
      54             :   HInstructionMap(Zone* zone, const HInstructionMap* other);
      55             : 
      56             :   void Resize(int new_size, Zone* zone);
      57             :   void ResizeLists(int new_size, Zone* zone);
      58             :   void Insert(HInstruction* instr, Zone* zone);
      59    26743915 :   uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); }
      60             : 
      61             :   int array_size_;
      62             :   int lists_size_;
      63             :   int count_;  // The number of values stored in the HInstructionMap.
      64             :   SideEffects present_depends_on_;
      65             :   HInstructionMapListElement* array_;
      66             :   // Primary store - contains the first value
      67             :   // with a given hash.  Colliding elements are stored in linked lists.
      68             :   HInstructionMapListElement* lists_;
      69             :   // The linked lists containing hash collisions.
      70             :   int free_list_head_;  // Unused elements in lists_ are on the free list.
      71             :   SideEffectsTracker* side_effects_tracker_;
      72             : };
      73             : 
      74             : 
      75             : class HSideEffectMap final BASE_EMBEDDED {
      76             :  public:
      77             :   HSideEffectMap();
      78             :   explicit HSideEffectMap(HSideEffectMap* other);
      79             :   HSideEffectMap& operator= (const HSideEffectMap& other);
      80             : 
      81             :   void Kill(SideEffects side_effects);
      82             : 
      83             :   void Store(SideEffects side_effects, HInstruction* instr);
      84             : 
      85             :   bool IsEmpty() const { return count_ == 0; }
      86             : 
      87             :   inline HInstruction* operator[](int i) const {
      88             :     DCHECK(0 <= i);
      89             :     DCHECK(i < kNumberOfTrackedSideEffects);
      90      293087 :     return data_[i];
      91             :   }
      92             :   inline HInstruction* at(int i) const { return operator[](i); }
      93             : 
      94             :  private:
      95             :   int count_;
      96             :   HInstruction* data_[kNumberOfTrackedSideEffects];
      97             : };
      98             : 
      99             : 
     100           0 : void TraceGVN(const char* msg, ...) {
     101             :   va_list arguments;
     102           0 :   va_start(arguments, msg);
     103           0 :   base::OS::VPrint(msg, arguments);
     104           0 :   va_end(arguments);
     105           0 : }
     106             : 
     107             : 
     108             : // Wrap TraceGVN in macros to avoid the expense of evaluating its arguments when
     109             : // --trace-gvn is off.
     110             : #define TRACE_GVN_1(msg, a1)                    \
     111             :   if (FLAG_trace_gvn) {                         \
     112             :     TraceGVN(msg, a1);                          \
     113             :   }
     114             : 
     115             : #define TRACE_GVN_2(msg, a1, a2)                \
     116             :   if (FLAG_trace_gvn) {                         \
     117             :     TraceGVN(msg, a1, a2);                      \
     118             :   }
     119             : 
     120             : #define TRACE_GVN_3(msg, a1, a2, a3)            \
     121             :   if (FLAG_trace_gvn) {                         \
     122             :     TraceGVN(msg, a1, a2, a3);                  \
     123             :   }
     124             : 
     125             : #define TRACE_GVN_4(msg, a1, a2, a3, a4)        \
     126             :   if (FLAG_trace_gvn) {                         \
     127             :     TraceGVN(msg, a1, a2, a3, a4);              \
     128             :   }
     129             : 
     130             : #define TRACE_GVN_5(msg, a1, a2, a3, a4, a5)    \
     131             :   if (FLAG_trace_gvn) {                         \
     132             :     TraceGVN(msg, a1, a2, a3, a4, a5);          \
     133             :   }
     134             : 
     135             : 
     136     2096090 : HInstructionMap::HInstructionMap(Zone* zone, const HInstructionMap* other)
     137             :     : array_size_(other->array_size_),
     138             :       lists_size_(other->lists_size_),
     139             :       count_(other->count_),
     140             :       present_depends_on_(other->present_depends_on_),
     141     2096090 :       array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)),
     142     2096099 :       lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)),
     143             :       free_list_head_(other->free_list_head_),
     144     6288284 :       side_effects_tracker_(other->side_effects_tracker_) {
     145             :   MemCopy(array_, other->array_,
     146     2096095 :           array_size_ * sizeof(HInstructionMapListElement));
     147             :   MemCopy(lists_, other->lists_,
     148     2096095 :           lists_size_ * sizeof(HInstructionMapListElement));
     149     2096095 : }
     150             : 
     151             : 
     152     4945254 : void HInstructionMap::Kill(SideEffects changes) {
     153     9890430 :   if (!present_depends_on_.ContainsAnyOf(changes)) return;
     154             :   present_depends_on_.RemoveAll();
     155   211795897 :   for (int i = 0; i < array_size_; ++i) {
     156   211016412 :     HInstruction* instr = array_[i].instr;
     157   211016412 :     if (instr != NULL) {
     158             :       // Clear list of collisions first, so we know if it becomes empty.
     159             :       int kept = kNil;  // List of kept elements.
     160             :       int next;
     161   124618741 :       for (int current = array_[i].next; current != kNil; current = next) {
     162    20871084 :         next = lists_[current].next;
     163    20871084 :         HInstruction* instr = lists_[current].instr;
     164    20871084 :         SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
     165    20871003 :         if (depends_on.ContainsAnyOf(changes)) {
     166             :           // Drop it.
     167      409039 :           count_--;
     168      409039 :           lists_[current].next = free_list_head_;
     169      409039 :           free_list_head_ = current;
     170             :         } else {
     171             :           // Keep it.
     172    20461964 :           lists_[current].next = kept;
     173             :           kept = current;
     174             :           present_depends_on_.Add(depends_on);
     175             :         }
     176             :       }
     177    51873788 :       array_[i].next = kept;
     178             : 
     179             :       // Now possibly drop directly indexed element.
     180    51873788 :       instr = array_[i].instr;
     181    51873788 :       SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
     182    51873791 :       if (depends_on.ContainsAnyOf(changes)) {  // Drop it.
     183     1121743 :         count_--;
     184     1121743 :         int head = array_[i].next;
     185     1121743 :         if (head == kNil) {
     186     1070971 :           array_[i].instr = NULL;
     187             :         } else {
     188       50772 :           array_[i].instr = lists_[head].instr;
     189       50772 :           array_[i].next = lists_[head].next;
     190       50772 :           lists_[head].next = free_list_head_;
     191       50772 :           free_list_head_ = head;
     192             :         }
     193             :       } else {
     194             :         present_depends_on_.Add(depends_on);  // Keep it.
     195             :       }
     196             :     }
     197             :   }
     198             : }
     199             : 
     200             : 
     201    22799963 : HInstruction* HInstructionMap::Lookup(HInstruction* instr) const {
     202    11400015 :   uint32_t hash = static_cast<uint32_t>(instr->Hashcode());
     203             :   uint32_t pos = Bound(hash);
     204    11399948 :   if (array_[pos].instr != NULL) {
     205     7210621 :     if (array_[pos].instr->Equals(instr)) return array_[pos].instr;
     206     5265673 :     int next = array_[pos].next;
     207    15591588 :     while (next != kNil) {
     208     6690128 :       if (lists_[next].instr->Equals(instr)) return lists_[next].instr;
     209     5060242 :       next = lists_[next].next;
     210             :     }
     211             :   }
     212             :   return NULL;
     213             : }
     214             : 
     215             : 
     216      719656 : void HInstructionMap::Resize(int new_size, Zone* zone) {
     217             :   DCHECK(new_size > count_);
     218             :   // Hashing the values into the new array has no more collisions than in the
     219             :   // old hash map, so we can use the existing lists_ array, if we are careful.
     220             : 
     221             :   // Make sure we have at least one free element.
     222      719656 :   if (free_list_head_ == kNil) {
     223        4095 :     ResizeLists(lists_size_ << 1, zone);
     224             :   }
     225             : 
     226             :   HInstructionMapListElement* new_array =
     227      719656 :       zone->NewArray<HInstructionMapListElement>(new_size);
     228             :   memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size);
     229             : 
     230      719654 :   HInstructionMapListElement* old_array = array_;
     231      719654 :   int old_size = array_size_;
     232             : 
     233             :   int old_count = count_;
     234      719654 :   count_ = 0;
     235             :   // Do not modify present_depends_on_.  It is currently correct.
     236      719654 :   array_size_ = new_size;
     237      719654 :   array_ = new_array;
     238             : 
     239      719654 :   if (old_array != NULL) {
     240             :     // Iterate over all the elements in lists, rehashing them.
     241    15037546 :     for (int i = 0; i < old_size; ++i) {
     242    15037516 :       if (old_array[i].instr != NULL) {
     243     4399406 :         int current = old_array[i].next;
     244    11918191 :         while (current != kNil) {
     245     3119392 :           Insert(lists_[current].instr, zone);
     246     3119379 :           int next = lists_[current].next;
     247     3119379 :           lists_[current].next = free_list_head_;
     248     3119379 :           free_list_head_ = current;
     249             :           current = next;
     250             :         }
     251             :         // Rehash the directly stored instruction.
     252     4399393 :         Insert(old_array[i].instr, zone);
     253             :       }
     254             :     }
     255             :   }
     256             :   USE(old_count);
     257             :   DCHECK(count_ == old_count);
     258      719684 : }
     259             : 
     260             : 
     261      322329 : void HInstructionMap::ResizeLists(int new_size, Zone* zone) {
     262             :   DCHECK(new_size > lists_size_);
     263             : 
     264             :   HInstructionMapListElement* new_lists =
     265      322329 :       zone->NewArray<HInstructionMapListElement>(new_size);
     266             :   memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size);
     267             : 
     268      322334 :   HInstructionMapListElement* old_lists = lists_;
     269      322334 :   int old_size = lists_size_;
     270             : 
     271      322334 :   lists_size_ = new_size;
     272      322334 :   lists_ = new_lists;
     273             : 
     274      322334 :   if (old_lists != NULL) {
     275       33359 :     MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement));
     276             :   }
     277     5790942 :   for (int i = old_size; i < lists_size_; ++i) {
     278     5468608 :     lists_[i].next = free_list_head_;
     279     5468608 :     free_list_head_ = i;
     280             :   }
     281      322334 : }
     282             : 
     283             : 
     284    30687685 : void HInstructionMap::Insert(HInstruction* instr, Zone* zone) {
     285             :   DCHECK(instr != NULL);
     286             :   // Resizing when half of the hashtable is filled up.
     287    15343718 :   if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone);
     288             :   DCHECK(count_ < array_size_);
     289    15343718 :   count_++;
     290    15343718 :   uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode()));
     291    15343967 :   if (array_[pos].instr == NULL) {
     292     9602111 :     array_[pos].instr = instr;
     293     9602111 :     array_[pos].next = kNil;
     294             :   } else {
     295     5741856 :     if (free_list_head_ == kNil) {
     296       29264 :       ResizeLists(lists_size_ << 1, zone);
     297             :     }
     298     5741855 :     int new_element_pos = free_list_head_;
     299             :     DCHECK(new_element_pos != kNil);
     300     5741855 :     free_list_head_ = lists_[free_list_head_].next;
     301     5741855 :     lists_[new_element_pos].instr = instr;
     302     5741855 :     lists_[new_element_pos].next = array_[pos].next;
     303             :     DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL);
     304     5741855 :     array_[pos].next = new_element_pos;
     305             :   }
     306    15343966 : }
     307             : 
     308             : 
     309      571070 : HSideEffectMap::HSideEffectMap() : count_(0) {
     310      571070 :   memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize);
     311           0 : }
     312             : 
     313             : 
     314           0 : HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) {
     315             :   *this = *other;  // Calls operator=.
     316           0 : }
     317             : 
     318             : 
     319           0 : HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) {
     320     5508648 :   if (this != &other) {
     321     1807131 :     MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
     322             :   }
     323           0 :   return *this;
     324             : }
     325             : 
     326             : 
     327           0 : void HSideEffectMap::Kill(SideEffects side_effects) {
     328     1881593 :   for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
     329     1881593 :     if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
     330      318865 :       if (data_[i] != NULL) count_--;
     331      318865 :       data_[i] = NULL;
     332             :     }
     333             :   }
     334           0 : }
     335             : 
     336             : 
     337           0 : void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) {
     338     3063667 :   for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
     339     3063667 :     if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
     340     2682672 :       if (data_[i] == NULL) count_++;
     341     2682672 :       data_[i] = instr;
     342             :     }
     343             :   }
     344           0 : }
     345             : 
     346             : 
     347    65356966 : SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) {
     348             :   int index;
     349             :   SideEffects result(instr->ChangesFlags());
     350    65356966 :   if (result.ContainsFlag(kGlobalVars)) {
     351     7337565 :     if (instr->IsStoreNamedField()) {
     352             :       HStoreNamedField* store = HStoreNamedField::cast(instr);
     353             :       HConstant* target = HConstant::cast(store->object());
     354       22827 :       if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()),
     355             :                            &index)) {
     356             :         result.RemoveFlag(kGlobalVars);
     357       22336 :         result.AddSpecial(GlobalVar(index));
     358       22336 :         return result;
     359             :       }
     360             :     }
     361    18232235 :     for (index = 0; index < kNumberOfGlobalVars; ++index) {
     362             :       result.AddSpecial(GlobalVar(index));
     363             :     }
     364    61688184 :   } else if (result.ContainsFlag(kInobjectFields)) {
     365      783102 :     if (instr->IsStoreNamedField() &&
     366      259995 :         ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) {
     367             :       result.RemoveFlag(kInobjectFields);
     368      259995 :       result.AddSpecial(InobjectField(index));
     369             :     } else {
     370       66994 :       for (index = 0; index < kNumberOfInobjectFields; ++index) {
     371             :         result.AddSpecial(InobjectField(index));
     372             :       }
     373             :     }
     374             :   }
     375    65334630 :   return result;
     376             : }
     377             : 
     378             : 
     379    83084182 : SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) {
     380             :   int index;
     381             :   SideEffects result(instr->DependsOnFlags());
     382    83084182 :   if (result.ContainsFlag(kGlobalVars)) {
     383      104818 :     if (instr->IsLoadNamedField()) {
     384             :       HLoadNamedField* load = HLoadNamedField::cast(instr);
     385             :       HConstant* target = HConstant::cast(load->object());
     386       52409 :       if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()),
     387             :                            &index)) {
     388             :         result.RemoveFlag(kGlobalVars);
     389       50762 :         result.AddSpecial(GlobalVar(index));
     390       50762 :         return result;
     391             :       }
     392             :     }
     393        8235 :     for (index = 0; index < kNumberOfGlobalVars; ++index) {
     394             :       result.AddSpecial(GlobalVar(index));
     395             :     }
     396    83031773 :   } else if (result.ContainsFlag(kInobjectFields)) {
     397     1123476 :     if (instr->IsLoadNamedField() &&
     398      374493 :         ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) {
     399             :       result.RemoveFlag(kInobjectFields);
     400      374490 :       result.AddSpecial(InobjectField(index));
     401             :     } else {
     402           0 :       for (index = 0; index < kNumberOfInobjectFields; ++index) {
     403             :         result.AddSpecial(InobjectField(index));
     404             :       }
     405             :     }
     406             :   }
     407    83033417 :   return result;
     408             : }
     409             : 
     410             : 
     411           0 : std::ostream& operator<<(std::ostream& os, const TrackedEffects& te) {
     412           0 :   SideEffectsTracker* t = te.tracker;
     413             :   const char* separator = "";
     414           0 :   os << "[";
     415           0 :   for (int bit = 0; bit < kNumberOfFlags; ++bit) {
     416             :     GVNFlag flag = GVNFlagFromInt(bit);
     417           0 :     if (te.effects.ContainsFlag(flag)) {
     418           0 :       os << separator;
     419             :       separator = ", ";
     420           0 :       switch (flag) {
     421             : #define DECLARE_FLAG(Type) \
     422             :   case k##Type:            \
     423             :     os << #Type;           \
     424             :     break;
     425           0 : GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
     426           0 : GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
     427             : #undef DECLARE_FLAG
     428             :         default:
     429             :             break;
     430             :       }
     431             :     }
     432             :   }
     433           0 :   for (int index = 0; index < t->num_global_vars_; ++index) {
     434           0 :     if (te.effects.ContainsSpecial(t->GlobalVar(index))) {
     435           0 :       os << separator << "[" << *t->global_vars_[index].handle() << "]";
     436             :       separator = ", ";
     437             :     }
     438             :   }
     439           0 :   for (int index = 0; index < t->num_inobject_fields_; ++index) {
     440           0 :     if (te.effects.ContainsSpecial(t->InobjectField(index))) {
     441           0 :       os << separator << t->inobject_fields_[index];
     442             :       separator = ", ";
     443             :     }
     444             :   }
     445           0 :   os << "]";
     446           0 :   return os;
     447             : }
     448             : 
     449             : 
     450       75236 : bool SideEffectsTracker::ComputeGlobalVar(Unique<PropertyCell> cell,
     451             :                                           int* index) {
     452      124034 :   for (int i = 0; i < num_global_vars_; ++i) {
     453      111612 :     if (cell == global_vars_[i]) {
     454       62814 :       *index = i;
     455       62814 :       return true;
     456             :     }
     457             :   }
     458       12422 :   if (num_global_vars_ < kNumberOfGlobalVars) {
     459       10284 :     if (FLAG_trace_gvn) {
     460           0 :       OFStream os(stdout);
     461           0 :       os << "Tracking global var [" << *cell.handle() << "] "
     462           0 :          << "(mapped to index " << num_global_vars_ << ")" << std::endl;
     463             :     }
     464       10284 :     *index = num_global_vars_;
     465       10284 :     global_vars_[num_global_vars_++] = cell;
     466       10284 :     return true;
     467             :   }
     468             :   return false;
     469             : }
     470             : 
     471             : 
     472      634440 : bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access,
     473             :                                               int* index) {
     474     2737542 :   for (int i = 0; i < num_inobject_fields_; ++i) {
     475     2643199 :     if (access.Equals(inobject_fields_[i])) {
     476      540097 :       *index = i;
     477      540097 :       return true;
     478             :     }
     479             :   }
     480       94343 :   if (num_inobject_fields_ < kNumberOfInobjectFields) {
     481       94343 :     if (FLAG_trace_gvn) {
     482           0 :       OFStream os(stdout);
     483           0 :       os << "Tracking inobject field access " << access << " (mapped to index "
     484           0 :          << num_inobject_fields_ << ")" << std::endl;
     485             :     }
     486       94343 :     *index = num_inobject_fields_;
     487       94343 :     inobject_fields_[num_inobject_fields_++] = access;
     488       94343 :     return true;
     489             :   }
     490             :   return false;
     491             : }
     492             : 
     493             : 
     494      283648 : HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph)
     495             :     : HPhase("H_Global value numbering", graph),
     496             :       removed_side_effects_(false),
     497             :       block_side_effects_(graph->blocks()->length(), zone()),
     498             :       loop_side_effects_(graph->blocks()->length(), zone()),
     499      283650 :       visited_on_paths_(graph->blocks()->length(), zone()) {
     500             :   DCHECK(!AllowHandleAllocation::IsAllowed());
     501             :   block_side_effects_.AddBlock(
     502      567300 :       SideEffects(), graph->blocks()->length(), zone());
     503             :   loop_side_effects_.AddBlock(
     504      567298 :       SideEffects(), graph->blocks()->length(), zone());
     505      283649 : }
     506             : 
     507             : 
     508      283649 : void HGlobalValueNumberingPhase::Run() {
     509             :   DCHECK(!removed_side_effects_);
     510      288973 :   for (int i = FLAG_gvn_iterations; i > 0; --i) {
     511             :     // Compute the side effects.
     512      288973 :     ComputeBlockSideEffects();
     513             : 
     514             :     // Perform loop invariant code motion if requested.
     515      288974 :     if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion();
     516             : 
     517             :     // Perform the actual value numbering.
     518      288975 :     AnalyzeGraph();
     519             : 
     520             :     // Continue GVN if we removed any side effects.
     521      288975 :     if (!removed_side_effects_) break;
     522        5324 :     removed_side_effects_ = false;
     523             : 
     524             :     // Clear all side effects.
     525             :     DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length());
     526             :     DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length());
     527     1292486 :     for (int i = 0; i < graph()->blocks()->length(); ++i) {
     528     1287162 :       block_side_effects_[i].RemoveAll();
     529     1287162 :       loop_side_effects_[i].RemoveAll();
     530             :     }
     531        5324 :     visited_on_paths_.Clear();
     532             :   }
     533      283651 : }
     534             : 
     535             : 
     536      288981 : void HGlobalValueNumberingPhase::ComputeBlockSideEffects() {
     537     6086510 :   for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
     538             :     // Compute side effects for the block.
     539    14169553 :     HBasicBlock* block = graph()->blocks()->at(i);
     540             :     SideEffects side_effects;
     541    10036745 :     if (block->IsReachable() && !block->IsDeoptimizing()) {
     542             :       int id = block->block_id();
     543    32119550 :       for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     544             :         HInstruction* instr = it.Current();
     545    27933522 :         side_effects.Add(side_effects_tracker_.ComputeChanges(instr));
     546             :       }
     547     4186028 :       block_side_effects_[id].Add(side_effects);
     548             : 
     549             :       // Loop headers are part of their loop.
     550     4186028 :       if (block->IsLoopHeader()) {
     551     1038010 :         loop_side_effects_[id].Add(side_effects);
     552             :       }
     553             : 
     554             :       // Propagate loop side effects upwards.
     555     4186028 :       if (block->HasParentLoopHeader()) {
     556     1933930 :         HBasicBlock* with_parent = block;
     557      864421 :         if (block->IsLoopHeader()) side_effects = loop_side_effects_[id];
     558      966965 :         do {
     559      966965 :           HBasicBlock* parent_block = with_parent->parent_loop_header();
     560             :           loop_side_effects_[parent_block->block_id()].Add(side_effects);
     561             :           with_parent = parent_block;
     562             :         } while (with_parent->HasParentLoopHeader());
     563             :       }
     564             :     }
     565             :   }
     566      288974 : }
     567             : 
     568             : 
     569      288975 : void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() {
     570     7627262 :   TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n",
     571             :               graph()->use_optimistic_licm() ? "yes" : "no");
     572     6086697 :   for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
     573     6021194 :     HBasicBlock* block = graph()->blocks()->at(i);
     574     5797722 :     if (block->IsLoopHeader()) {
     575      148982 :       SideEffects side_effects = loop_side_effects_[block->block_id()];
     576       74491 :       if (FLAG_trace_gvn) {
     577           0 :         OFStream os(stdout);
     578           0 :         os << "Try loop invariant motion for " << *block << " changes "
     579           0 :            << Print(side_effects) << std::endl;
     580             :       }
     581     1689546 :       HBasicBlock* last = block->loop_information()->GetLastBackEdge();
     582     3230110 :       for (int j = block->block_id(); j <= last->block_id(); ++j) {
     583     1540565 :         ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects);
     584             :       }
     585             :     }
     586             :   }
     587      288975 : }
     588             : 
     589             : 
     590     1540565 : void HGlobalValueNumberingPhase::ProcessLoopBlock(
     591     1540565 :     HBasicBlock* block,
     592             :     HBasicBlock* loop_header,
     593             :     SideEffects loop_kills) {
     594     2502807 :   HBasicBlock* pre_header = loop_header->predecessors()->at(0);
     595     1540565 :   if (FLAG_trace_gvn) {
     596           0 :     OFStream os(stdout);
     597           0 :     os << "Loop invariant code motion for " << *block << " depends on "
     598           0 :        << Print(loop_kills) << std::endl;
     599             :   }
     600     8456233 :   HInstruction* instr = block->first();
     601    11537363 :   while (instr != NULL) {
     602             :     HInstruction* next = instr->next();
     603    16912466 :     if (instr->CheckFlag(HValue::kUseGVN)) {
     604     2515218 :       SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
     605     2515219 :       SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr);
     606     2515218 :       if (FLAG_trace_gvn) {
     607           0 :         OFStream os(stdout);
     608           0 :         os << "Checking instruction i" << instr->id() << " ("
     609           0 :            << instr->Mnemonic() << ") changes " << Print(changes)
     610           0 :            << ", depends on " << Print(depends_on) << ". Loop changes "
     611           0 :            << Print(loop_kills) << std::endl;
     612             :       }
     613     2515218 :       bool can_hoist = !depends_on.ContainsAnyOf(loop_kills);
     614     2515218 :       if (can_hoist && !graph()->use_optimistic_licm()) {
     615             :         can_hoist = block->IsLoopSuccessorDominator();
     616             :       }
     617             : 
     618     2515218 :       if (can_hoist) {
     619             :         bool inputs_loop_invariant = true;
     620     1373664 :         for (int i = 0; i < instr->OperandCount(); ++i) {
     621     1373664 :           if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
     622             :             inputs_loop_invariant = false;
     623             :           }
     624             :         }
     625             : 
     626     1886274 :         if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
     627      962242 :           TRACE_GVN_2("Hoisting loop invariant instruction i%d to block B%d\n",
     628             :                       instr->id(), pre_header->block_id());
     629             :           // Move the instruction out of the loop.
     630      962242 :           instr->Unlink();
     631      962242 :           instr->InsertBefore(pre_header->end());
     632      962242 :           if (instr->HasSideEffects()) removed_side_effects_ = true;
     633             :         }
     634             :       }
     635             :     }
     636             :     instr = next;
     637             :   }
     638     1540565 : }
     639             : 
     640             : 
     641     1313233 : bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr,
     642             :                                             HBasicBlock* loop_header) {
     643             :   // If we've disabled code motion or we're in a block that unconditionally
     644             :   // deoptimizes, don't move any instructions.
     645     3745437 :   return graph()->allow_code_motion() && !instr->block()->IsDeoptimizing() &&
     646     1313233 :          instr->block()->IsReachable();
     647             : }
     648             : 
     649             : 
     650             : SideEffects
     651    13310878 : HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
     652    30095050 :     HBasicBlock* dominator, HBasicBlock* dominated) {
     653             :   SideEffects side_effects;
     654    29506485 :   for (int i = 0; i < dominated->predecessors()->length(); ++i) {
     655    32391130 :     HBasicBlock* block = dominated->predecessors()->at(i);
     656    30095050 :     if (dominator->block_id() < block->block_id() &&
     657    29909768 :         block->block_id() < dominated->block_id() &&
     658    25218013 :         !visited_on_paths_.Contains(block->block_id())) {
     659             :       visited_on_paths_.Add(block->block_id());
     660    11503810 :       side_effects.Add(block_side_effects_[block->block_id()]);
     661    11503810 :       if (block->IsLoopHeader()) {
     662      185280 :         side_effects.Add(loop_side_effects_[block->block_id()]);
     663             :       }
     664             :       side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock(
     665    11503810 :           dominator, block));
     666             :     }
     667             :   }
     668    13310920 :   return side_effects;
     669             : }
     670             : 
     671             : 
     672             : // Each instance of this class is like a "stack frame" for the recursive
     673             : // traversal of the dominator tree done during GVN (the stack is handled
     674             : // as a double linked list).
     675             : // We reuse frames when possible so the list length is limited by the depth
     676             : // of the dominator tree but this forces us to initialize each frame calling
     677             : // an explicit "Initialize" method instead of a using constructor.
     678             : class GvnBasicBlockState: public ZoneObject {
     679             :  public:
     680      288970 :   static GvnBasicBlockState* CreateEntry(Zone* zone,
     681             :                                          HBasicBlock* entry_block,
     682             :                                          HInstructionMap* entry_map) {
     683             :     return new(zone)
     684      288971 :         GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone);
     685             :   }
     686             : 
     687             :   HBasicBlock* block() { return block_; }
     688             :   HInstructionMap* map() { return map_; }
     689             :   HSideEffectMap* dominators() { return &dominators_; }
     690             : 
     691     5797608 :   GvnBasicBlockState* next_in_dominator_tree_traversal(
     692             :       Zone* zone,
     693     5797608 :       HBasicBlock** dominator) {
     694             :     // This assignment needs to happen before calling next_dominated() because
     695             :     // that call can reuse "this" if we are at the last dominated block.
     696     5797608 :     *dominator = block();
     697     5797608 :     GvnBasicBlockState* result = next_dominated(zone);
     698     5797609 :     if (result == NULL) {
     699     3903228 :       GvnBasicBlockState* dominator_state = pop();
     700     2096103 :       if (dominator_state != NULL) {
     701             :         // This branch is guaranteed not to return NULL because pop() never
     702             :         // returns a state where "is_done() == true".
     703     1807128 :         *dominator = dominator_state->block();
     704     1807128 :         result = dominator_state->next_dominated(zone);
     705             :       } else {
     706             :         // Unnecessary (we are returning NULL) but done for cleanness.
     707      288975 :         *dominator = NULL;
     708             :       }
     709             :     }
     710     5797610 :     return result;
     711             :   }
     712             : 
     713             :  private:
     714     5797609 :   void Initialize(HBasicBlock* block,
     715             :                   HInstructionMap* map,
     716             :                   HSideEffectMap* dominators,
     717             :                   bool copy_map,
     718             :                   Zone* zone) {
     719     5797609 :     block_ = block;
     720     5797609 :     map_ = copy_map ? map->Copy(zone) : map;
     721     5797621 :     dominated_index_ = -1;
     722     5797621 :     length_ = block->dominated_blocks()->length();
     723     5797621 :     if (dominators != NULL) {
     724     5508648 :       dominators_ = *dominators;
     725             :     }
     726     5797621 :   }
     727             :   bool is_done() { return dominated_index_ >= length_; }
     728             : 
     729      571070 :   GvnBasicBlockState(GvnBasicBlockState* previous,
     730             :                      HBasicBlock* block,
     731             :                      HInstructionMap* map,
     732             :                      HSideEffectMap* dominators,
     733             :                      Zone* zone)
     734      571070 :       : previous_(previous), next_(NULL) {
     735      571070 :     Initialize(block, map, dominators, true, zone);
     736      571071 :   }
     737             : 
     738    11306338 :   GvnBasicBlockState* next_dominated(Zone* zone) {
     739     7604774 :     dominated_index_++;
     740     7604774 :     if (dominated_index_ == length_ - 1) {
     741             :       // No need to copy the map for the last child in the dominator tree.
     742     3701564 :       Initialize(block_->dominated_blocks()->at(dominated_index_),
     743             :                  map(),
     744             :                  dominators(),
     745             :                  false,
     746     7403128 :                  zone);
     747     3701566 :       return this;
     748     3903210 :     } else if (dominated_index_ < length_) {
     749     3614248 :       return push(zone, block_->dominated_blocks()->at(dominated_index_));
     750             :     } else {
     751             :       return NULL;
     752             :     }
     753             :   }
     754             : 
     755     3614254 :   GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) {
     756     1807127 :     if (next_ == NULL) {
     757             :       next_ =
     758      564198 :           new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone);
     759             :     } else {
     760     3050056 :       next_->Initialize(block, map(), dominators(), true, zone);
     761             :     }
     762     1807132 :     return next_;
     763             :   }
     764     2096100 :   GvnBasicBlockState* pop() {
     765     3903227 :     GvnBasicBlockState* result = previous_;
     766     5999327 :     while (result != NULL && result->is_done()) {
     767           0 :       TRACE_GVN_2("Backtracking from block B%d to block b%d\n",
     768             :                   block()->block_id(),
     769             :                   previous_->block()->block_id())
     770           0 :       result = result->previous_;
     771             :     }
     772     2096100 :     return result;
     773             :   }
     774             : 
     775             :   GvnBasicBlockState* previous_;
     776             :   GvnBasicBlockState* next_;
     777             :   HBasicBlock* block_;
     778             :   HInstructionMap* map_;
     779             :   HSideEffectMap dominators_;
     780             :   int dominated_index_;
     781             :   int length_;
     782             : };
     783             : 
     784             : 
     785             : // This is a recursive traversal of the dominator tree but it has been turned
     786             : // into a loop to avoid stack overflows.
     787             : // The logical "stack frames" of the recursion are kept in a list of
     788             : // GvnBasicBlockState instances.
     789      288971 : void HGlobalValueNumberingPhase::AnalyzeGraph() {
     790      288971 :   HBasicBlock* entry_block = graph()->entry_block();
     791             :   HInstructionMap* entry_map =
     792      577941 :       new(zone()) HInstructionMap(zone(), &side_effects_tracker_);
     793     5797615 :   GvnBasicBlockState* current =
     794      288970 :       GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map);
     795             : 
     796     6375563 :   while (current != NULL) {
     797      148980 :     HBasicBlock* block = current->block();
     798             :     HInstructionMap* map = current->map();
     799             :     HSideEffectMap* dominators = current->dominators();
     800             : 
     801     5797615 :     TRACE_GVN_2("Analyzing block B%d%s\n",
     802             :                 block->block_id(),
     803             :                 block->IsLoopHeader() ? " (loop header)" : "");
     804             : 
     805             :     // If this is a loop header kill everything killed by the loop.
     806     5797535 :     if (block->IsLoopHeader()) {
     807      223470 :       map->Kill(loop_side_effects_[block->block_id()]);
     808             :       dominators->Kill(loop_side_effects_[block->block_id()]);
     809             :     }
     810             : 
     811             :     // Go through all instructions of the current block.
     812    40708642 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     813             :       HInstruction* instr = it.Current();
     814   104733109 :       if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) {
     815      293082 :         for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
     816           0 :           HValue* other = dominators->at(i);
     817             :           GVNFlag flag = GVNFlagFromInt(i);
     818      293087 :           if (instr->DependsOnFlags().Contains(flag) && other != NULL) {
     819      271042 :             TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n",
     820             :                         i,
     821             :                         instr->id(),
     822             :                         instr->Mnemonic(),
     823             :                         other->id(),
     824             :                         other->Mnemonic());
     825      271042 :             if (instr->HandleSideEffectDominator(flag, other)) {
     826        2829 :               removed_side_effects_ = true;
     827             :             }
     828             :           }
     829             :         }
     830             :       }
     831             :       // Instruction was unlinked during graph traversal.
     832    34911033 :       if (!instr->IsLinked()) continue;
     833             : 
     834    34911033 :       SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
     835    34911034 :       if (!changes.IsEmpty()) {
     836             :         // Clear all instructions in the map that are affected by side effects.
     837             :         // Store instruction as the dominating one for tracked side effects.
     838     3063674 :         map->Kill(changes);
     839             :         dominators->Store(changes, instr);
     840     3063673 :         if (FLAG_trace_gvn) {
     841           0 :           OFStream os(stdout);
     842           0 :           os << "Instruction i" << instr->id() << " changes " << Print(changes)
     843           0 :              << std::endl;
     844             :         }
     845             :       }
     846    46311041 :       if (instr->CheckFlag(HValue::kUseGVN) &&
     847             :           !instr->CheckFlag(HValue::kCantBeReplaced)) {
     848             :         DCHECK(!instr->HasObservableSideEffects());
     849    11400011 :         HInstruction* other = map->Lookup(instr);
     850    11400084 :         if (other != NULL) {
     851             :           DCHECK(instr->Equals(other) && other->Equals(instr));
     852     3574877 :           TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n",
     853             :                       instr->id(),
     854             :                       instr->Mnemonic(),
     855             :                       other->id(),
     856             :                       other->Mnemonic());
     857     3574878 :           if (instr->HasSideEffects()) removed_side_effects_ = true;
     858     3574878 :           instr->DeleteAndReplaceWith(other);
     859             :         } else {
     860     7825207 :           map->Add(instr, zone());
     861             :         }
     862             :       }
     863             :     }
     864             : 
     865             :     HBasicBlock* dominator_block;
     866     5508646 :     GvnBasicBlockState* next =
     867             :         current->next_in_dominator_tree_traversal(zone(),
     868     5797604 :                                                   &dominator_block);
     869             : 
     870     5797617 :     if (next != NULL) {
     871     5508405 :       HBasicBlock* dominated = next->block();
     872     5508646 :       HInstructionMap* successor_map = next->map();
     873         354 :       HSideEffectMap* successor_dominators = next->dominators();
     874             : 
     875             :       // Kill everything killed on any path between this block and the
     876             :       // dominated block.  We don't have to traverse these paths if the
     877             :       // value map and the dominators list is already empty.  If the range
     878             :       // of block ids (block_id, dominated_id) is empty there are no such
     879             :       // paths.
     880    11017405 :       if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) &&
     881     5508405 :           dominator_block->block_id() + 1 < dominated->block_id()) {
     882     1807102 :         visited_on_paths_.Clear();
     883             :         SideEffects side_effects_on_all_paths =
     884             :             CollectSideEffectsOnPathsToDominatedBlock(dominator_block,
     885     1807102 :                                                       dominated);
     886     1807105 :         successor_map->Kill(side_effects_on_all_paths);
     887             :         successor_dominators->Kill(side_effects_on_all_paths);
     888             :       }
     889             :     }
     890             :     current = next;
     891             :   }
     892      288975 : }
     893             : 
     894             : }  // namespace internal
     895             : }  // namespace v8

Generated by: LCOV version 1.10