← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/JavaScriptCore/dfg/DFGDominators.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/JavaScriptCore/dfg/DFGDominators.cpp
 
1
/*
 
2
 * Copyright (C) 2011 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 "DFGDominators.h"
 
28
 
 
29
#if ENABLE(DFG_JIT)
 
30
 
 
31
#include "DFGGraph.h"
 
32
 
 
33
namespace JSC { namespace DFG {
 
34
 
 
35
Dominators::Dominators()
 
36
    : m_valid(false)
 
37
{
 
38
}
 
39
 
 
40
Dominators::~Dominators()
 
41
{
 
42
}
 
43
 
 
44
void Dominators::compute(Graph& graph)
 
45
{
 
46
    // This implements a naive dominator solver.
 
47
    
 
48
    ASSERT(graph.m_blocks[0]->m_predecessors.isEmpty());
 
49
    
 
50
    unsigned numBlocks = graph.m_blocks.size();
 
51
    
 
52
    if (numBlocks > m_results.size()) {
 
53
        m_results.grow(numBlocks);
 
54
        for (unsigned i = numBlocks; i--;)
 
55
            m_results[i].resize(numBlocks);
 
56
        m_scratch.resize(numBlocks);
 
57
    }
 
58
    
 
59
    m_results[0].clearAll();
 
60
    m_results[0].set(0);
 
61
    
 
62
    m_scratch.clearAll();
 
63
    for (unsigned i = numBlocks; i--;) {
 
64
        if (!graph.m_blocks[i])
 
65
            continue;
 
66
        m_scratch.set(i);
 
67
    }
 
68
    
 
69
    for (unsigned i = numBlocks; i-- > 1;) {
 
70
        if (!graph.m_blocks[i] || graph.m_blocks[i]->m_predecessors.isEmpty())
 
71
            m_results[i].clearAll();
 
72
        else
 
73
            m_results[i].set(m_scratch);
 
74
    }
 
75
    
 
76
    bool changed;
 
77
    do {
 
78
        changed = false;
 
79
        for (unsigned i = 1; i < numBlocks; ++i)
 
80
            changed |= iterateForBlock(graph, i);
 
81
        if (!changed)
 
82
            break;
 
83
        
 
84
        changed = false;
 
85
        for (unsigned i = numBlocks; i-- > 1;)
 
86
            changed |= iterateForBlock(graph, i);
 
87
    } while (changed);
 
88
    
 
89
    m_valid = true;
 
90
}
 
91
 
 
92
bool Dominators::iterateForBlock(Graph& graph, BlockIndex i)
 
93
{
 
94
    BasicBlock* block = graph.m_blocks[i].get();
 
95
    if (!block)
 
96
        return false;
 
97
    if (block->m_predecessors.isEmpty())
 
98
        return false;
 
99
    m_scratch.set(m_results[block->m_predecessors[0]]);
 
100
    for (unsigned j = block->m_predecessors.size(); j-- > 1;)
 
101
        m_scratch.filter(m_results[block->m_predecessors[j]]);
 
102
    m_scratch.set(i);
 
103
    return m_results[i].setAndCheck(m_scratch);
 
104
}
 
105
 
 
106
} } // namespace JSC::DFG
 
107
 
 
108
#endif // ENABLE(DFG_JIT)
 
109