src/v8/src/hydrogen-gvn.h

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