dfg/DFGBlockWorklist.h

   1 /*
   2  * Copyright (C) 2014 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 #ifndef DFGBlockWorklist_h
  27 #define DFGBlockWorklist_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlock.h"
  32 #include "DFGBlockSet.h"
  33 #include <wtf/Vector.h>
  34
  35 namespace JSC { namespace DFG {
  36
  37 struct BasicBlock;
  38
  39 class BlockWorklist {
  40 public:
  41     BlockWorklist();
  42     ~BlockWorklist();
  43
  44     bool push(BasicBlock*); // Returns true if we didn't know about the block before.
  45
  46     bool notEmpty() const { return !m_stack.isEmpty(); }
  47     BasicBlock* pop();
  48
  49 private:
  50     BlockSet m_seen;
  51     Vector<BasicBlock*, 16> m_stack;
  52 };
  53
  54 // When you say BlockWith<int> you should read it as "block with an int".
  55 template<typename T>
  56 struct BlockWith {
  57     BlockWith()
  58         : block(nullptr)
  59     {
  60     }
  61
  62     BlockWith(BasicBlock* block, const T& data)
  63         : block(block)
  64         , data(data)
  65     {
  66     }
  67
  68     explicit operator bool() const { return block; }
  69
  70     BasicBlock* block;
  71     T data;
  72 };
  73
  74 // Extended block worklist is useful for enqueueing some meta-data along with the block. It also
  75 // permits forcibly enqueueing things even if the block has already been seen. It's useful for
  76 // things like building a spanning tree, in which case T (the auxiliary payload) would be the
  77 // successor index.
  78 template<typename T>
  79 class ExtendedBlockWorklist {
  80 public:
  81     ExtendedBlockWorklist() { }
  82
  83     void forcePush(const BlockWith<T>& entry)
  84     {
  85         m_stack.append(entry);
  86     }
  87
  88     void forcePush(BasicBlock* block, const T& data)
  89     {
  90         forcePush(BlockWith<T>(block, data));
  91     }
  92
  93     bool push(const BlockWith<T>& entry)
  94     {
  95         if (!m_seen.add(entry.block))
  96             return false;
  97
  98         forcePush(entry);
  99         return true;
 100     }
 101
 102     bool push(BasicBlock* block, const T& data)
 103     {
 104         return push(BlockWith<T>(block, data));
 105     }
 106
 107     bool notEmpty() const { return !m_stack.isEmpty(); }
 108
 109     BlockWith<T> pop()
 110     {
 111         if (m_stack.isEmpty())
 112             return BlockWith<T>();
 113
 114         return m_stack.takeLast();
 115     }
 116
 117 private:
 118     BlockSet m_seen;
 119     Vector<BlockWith<T>> m_stack;
 120 };
 121
 122 enum VisitOrder {
 123     PreOrder,
 124     PostOrder
 125 };
 126
 127 struct BlockWithOrder {
 128     BlockWithOrder()
 129         : block(nullptr)
 130         , order(PreOrder)
 131     {
 132     }
 133
 134     BlockWithOrder(BasicBlock* block, VisitOrder order)
 135         : block(block)
 136         , order(order)
 137     {
 138     }
 139
 140     explicit operator bool() const { return block; }
 141
 142     BasicBlock* block;
 143     VisitOrder order;
 144 };
 145
 146 // Block worklist suitable for post-order traversal.
 147 class PostOrderBlockWorklist {
 148 public:
 149     PostOrderBlockWorklist();
 150     ~PostOrderBlockWorklist();
 151
 152     bool pushPre(BasicBlock*);
 153     void pushPost(BasicBlock*);
 154
 155     bool push(BasicBlock* block, VisitOrder order = PreOrder)
 156     {
 157         switch (order) {
 158         case PreOrder:
 159             return pushPre(block);
 160         case PostOrder:
 161             pushPost(block);
 162             return true;
 163         }
 164         RELEASE_ASSERT_NOT_REACHED();
 165         return false;
 166     }
 167     bool push(const BlockWithOrder& data)
 168     {
 169         return push(data.block, data.order);
 170     }
 171
 172     bool notEmpty() const { return m_worklist.notEmpty(); }
 173     BlockWithOrder pop();
 174
 175 private:
 176     ExtendedBlockWorklist<VisitOrder> m_worklist;
 177 };
 178
 179 } } // namespace JSC::DFG
 180
 181 #endif // ENABLE(DFG_JIT)
 182
 183 #endif // DFGBlockWorklist_h
 184