Home | History | Annotate | Download | only in crankshaft 
      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 #ifndef V8_CRANKSHAFT_HYDROGEN_GVN_H_
      6 #define V8_CRANKSHAFT_HYDROGEN_GVN_H_
      7 
      8 #include <iosfwd>
      9 
     10 #include "src/crankshaft/hydrogen.h"
     11 #include "src/crankshaft/hydrogen-instructions.h"
     12 #include "src/zone.h"
     13 
     14 namespace v8 {
     15 namespace internal {
     16 
     17 // This class extends GVNFlagSet with additional "special" dynamic side effects,
     18 // which can be used to represent side effects that cannot be expressed using
     19 // the GVNFlags of an HInstruction. These special side effects are tracked by a
     20 // SideEffectsTracker (see below).
     21 class SideEffects final {
     22  public:
     23   static const int kNumberOfSpecials = 64 - kNumberOfFlags;
     24 
     25   SideEffects() : bits_(0) {
     26     DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
     27   }
     28   explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
     29   bool IsEmpty() const { return bits_ == 0; }
     30   bool ContainsFlag(GVNFlag flag) const {
     31     return (bits_ & MaskFlag(flag)) != 0;
     32   }
     33   bool ContainsSpecial(int special) const {
     34     return (bits_ & MaskSpecial(special)) != 0;
     35   }
     36   bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
     37   void Add(SideEffects set) { bits_ |= set.bits_; }
     38   void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
     39   void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
     40   void RemoveAll() { bits_ = 0; }
     41   uint64_t ToIntegral() const { return bits_; }
     42 
     43  private:
     44   uint64_t MaskFlag(GVNFlag flag) const {
     45     return static_cast<uint64_t>(1) << static_cast<unsigned>(flag);
     46   }
     47   uint64_t MaskSpecial(int special) const {
     48     DCHECK(special >= 0);
     49     DCHECK(special < kNumberOfSpecials);
     50     return static_cast<uint64_t>(1) << static_cast<unsigned>(
     51         special + kNumberOfFlags);
     52   }
     53 
     54   uint64_t bits_;
     55 };
     56 
     57 
     58 struct TrackedEffects;
     59 
     60 // Tracks global variable and inobject field loads/stores in a fine grained
     61 // fashion, and represents them using the "special" dynamic side effects of the
     62 // SideEffects class (see above). This way unrelated global variable/inobject
     63 // field stores don't prevent hoisting and merging of global variable/inobject
     64 // field loads.
     65 class SideEffectsTracker final BASE_EMBEDDED {
     66  public:
     67   SideEffectsTracker() : num_global_vars_(0), num_inobject_fields_(0) {}
     68   SideEffects ComputeChanges(HInstruction* instr);
     69   SideEffects ComputeDependsOn(HInstruction* instr);
     70 
     71  private:
     72   friend std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
     73   bool ComputeGlobalVar(Unique<PropertyCell> cell, int* index);
     74   bool ComputeInobjectField(HObjectAccess access, int* index);
     75 
     76   static int GlobalVar(int index) {
     77     DCHECK(index >= 0);
     78     DCHECK(index < kNumberOfGlobalVars);
     79     return index;
     80   }
     81   static int InobjectField(int index) {
     82     DCHECK(index >= 0);
     83     DCHECK(index < kNumberOfInobjectFields);
     84     return index + kNumberOfGlobalVars;
     85   }
     86 
     87   // Track up to four global vars.
     88   static const int kNumberOfGlobalVars = 4;
     89   Unique<PropertyCell> global_vars_[kNumberOfGlobalVars];
     90   int num_global_vars_;
     91 
     92   // Track up to n inobject fields.
     93   static const int kNumberOfInobjectFields =
     94       SideEffects::kNumberOfSpecials - kNumberOfGlobalVars;
     95   HObjectAccess inobject_fields_[kNumberOfInobjectFields];
     96   int num_inobject_fields_;
     97 };
     98 
     99 
    100 // Helper class for printing, because the effects don't know their tracker.
    101 struct TrackedEffects {
    102   TrackedEffects(SideEffectsTracker* t, SideEffects e)
    103       : tracker(t), effects(e) {}
    104   SideEffectsTracker* tracker;
    105   SideEffects effects;
    106 };
    107 
    108 
    109 std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
    110 
    111 
    112 // Perform common subexpression elimination and loop-invariant code motion.
    113 class HGlobalValueNumberingPhase final : public HPhase {
    114  public:
    115   explicit HGlobalValueNumberingPhase(HGraph* graph);
    116 
    117   void Run();
    118 
    119  private:
    120   SideEffects CollectSideEffectsOnPathsToDominatedBlock(
    121       HBasicBlock* dominator,
    122       HBasicBlock* dominated);
    123   void AnalyzeGraph();
    124   void ComputeBlockSideEffects();
    125   void LoopInvariantCodeMotion();
    126   void ProcessLoopBlock(HBasicBlock* block,
    127                         HBasicBlock* before_loop,
    128                         SideEffects loop_kills);
    129   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
    130   TrackedEffects Print(SideEffects side_effects) {
    131     return TrackedEffects(&side_effects_tracker_, side_effects);
    132   }
    133 
    134   SideEffectsTracker side_effects_tracker_;
    135   bool removed_side_effects_;
    136 
    137   // A map of block IDs to their side effects.
    138   ZoneList<SideEffects> block_side_effects_;
    139 
    140   // A map of loop header block IDs to their loop's side effects.
    141   ZoneList<SideEffects> loop_side_effects_;
    142 
    143   // Used when collecting side effects on paths from dominator to
    144   // dominated.
    145   BitVector visited_on_paths_;
    146 
    147   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
    148 };
    149 
    150 }  // namespace internal
    151 }  // namespace v8
    152 
    153 #endif  // V8_CRANKSHAFT_HYDROGEN_GVN_H_
    154