1  /*
  2   * Copyright (C) 2017 Apple Inc. All rights reserved.
  3   *
  4   * Redistribution and use in source and binary forms, with or without
  5   * modification, are permitted provided that the following conditions
  6   * are met:
  7   * 1. Redistributions of source code must retain the above copyright
  8   *    notice, this list of conditions and the following disclaimer.
  9   * 2. Redistributions in binary form must reproduce the above copyright
 10   *    notice, this list of conditions and the following disclaimer in the
 11   *    documentation and/or other materials provided with the distribution.
 12   *
 13   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 14   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 16   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 17   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 18   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 19   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 20   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 21   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 23   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 24   */
 25  
 26  #include "config.h"
 27  #include "B3HoistLoopInvariantValues.h"
 28  
 29  #if ENABLE(B3_JIT)
 30  
 31  #include "B3BackwardsDominators.h"
 32  #include "B3Dominators.h"
 33  #include "B3EnsureLoopPreHeaders.h"
 34  #include "B3NaturalLoops.h"
 35  #include "B3PhaseScope.h"
 36  #include "B3ProcedureInlines.h"
 37  #include "B3ValueInlines.h"
 38  #include <wtf/RangeSet.h>
 39  
 40  namespace JSC { namespace B3 {
 41  
 42  bool hoistLoopInvariantValues(Procedure& proc)
 43  {
 44      PhaseScope phaseScope(proc, "hoistLoopInvariantValues");
 45      
 46      ensureLoopPreHeaders(proc);
 47      
 48      NaturalLoops& loops = proc.naturalLoops();
 49      if (!loops.numLoops())
 50          return false;
 51  
 52      proc.resetValueOwners();
 53      Dominators& dominators = proc.dominators();
 54      BackwardsDominators& backwardsDominators = proc.backwardsDominators();
 55      
 56      // FIXME: We should have a reusable B3::EffectsSet data structure.
 57      // https://bugs.webkit.org/show_bug.cgi?id=174762
 58      struct LoopData {
 59          RangeSet<HeapRange> writes;
 60          bool writesLocalState { false };
 61          bool writesPinned { false };
 62          bool sideExits { false };
 63          BasicBlock* preHeader { nullptr };
 64      };
 65      
 66      IndexMap<NaturalLoop, LoopData> data(loops.numLoops());
 67      
 68      for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
 69          const NaturalLoop& loop = loops.loop(loopIndex);
 70          for (BasicBlock* predecessor : loop.header()->predecessors()) {
 71              if (loops.belongsTo(predecessor, loop))
 72                  continue;
 73              RELEASE_ASSERT(!data[loop].preHeader);
 74              data[loop].preHeader = predecessor;
 75          }
 76      }
 77      
 78      for (BasicBlock* block : proc) {
 79          const NaturalLoop* loop = loops.innerMostLoopOf(block);
 80          if (!loop)
 81              continue;
 82          for (Value* value : *block) {
 83              Effects effects = value->effects();
 84              data[*loop].writes.add(effects.writes);
 85              data[*loop].writesLocalState |= effects.writesLocalState;
 86              data[*loop].writesPinned |= effects.writesPinned;
 87              data[*loop].sideExits |= effects.exitsSideways;
 88          }
 89      }
 90      
 91      for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
 92          const NaturalLoop& loop = loops.loop(loopIndex);
 93          for (const NaturalLoop* current = loops.innerMostOuterLoop(loop); current; current = loops.innerMostOuterLoop(*current)) {
 94              data[*current].writes.addAll(data[loop].writes);
 95              data[*current].writesLocalState |= data[loop].writesLocalState;
 96              data[*current].writesPinned |= data[loop].writesPinned;
 97              data[*current].sideExits |= data[loop].sideExits;
 98          }
 99      }
100      
101      bool changed = false;
102      
103      // Pre-order ensures that we visit our dominators before we visit ourselves. Otherwise we'd miss some
104      // hoisting opportunities in complex CFGs.
105      for (BasicBlock* block : proc.blocksInPreOrder()) {
106          Vector<const NaturalLoop*> blockLoops = loops.loopsOf(block);
107          if (blockLoops.isEmpty())
108              continue;
109          
110          for (Value*& value : *block) {
111              Effects effects = value->effects();
112              
113              // We never hoist write effects or control constructs.
114              if (effects.mustExecute())
115                  continue;
116  
117              // Try outermost loop first.
118              for (unsigned i = blockLoops.size(); i--;) {
119                  const NaturalLoop& loop = *blockLoops[i];
120                  
121                  bool ok = true;
122                  for (Value* child : value->children()) {
123                      if (!dominators.dominates(child->owner, data[loop].preHeader)) {
124                          ok = false;
125                          break;
126                      }
127                  }
128                  if (!ok)
129                      continue;
130                  
131                  if (effects.controlDependent) {
132                      if (!backwardsDominators.dominates(block, data[loop].preHeader))
133                          continue;
134                      
135                      // FIXME: This is super conservative. In reality, we just need to make sure that there
136                      // aren't any side exits between here and the pre-header according to backwards search.
137                      // https://bugs.webkit.org/show_bug.cgi?id=174763
138                      if (data[loop].sideExits)
139                          continue;
140                  }
141                  
142                  if (effects.readsPinned && data[loop].writesPinned)
143                      continue;
144                  
145                  if (effects.readsLocalState && data[loop].writesLocalState)
146                      continue;
147                  
148                  if (data[loop].writes.overlaps(effects.reads))
149                      continue;
150                  
151                  data[loop].preHeader->appendNonTerminal(value);
152                  value = proc.add<Value>(Nop, Void, value->origin());
153                  changed = true;
154              }
155          }
156      }
157      
158      return changed;
159  }
160  
161  } } // namespace JSC::B3
162  
163  #endif // ENABLE(B3_JIT)
164