summaryrefslogtreecommitdiffstats
path: root/gfx/angle/checkout/src/compiler/translator/CallDAG.h
blob: 7e80f2e855dccf5397a476d9e51d5521a8590fc7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//
// Copyright 2002 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//

// CallDAG.h: Defines a call graph DAG of functions to be re-used accross
// analyses, allows to efficiently traverse the functions in topological
// order.

#ifndef COMPILER_TRANSLATOR_CALLDAG_H_
#define COMPILER_TRANSLATOR_CALLDAG_H_

#include <map>

#include "compiler/translator/IntermNode.h"

namespace sh
{

// The translator needs to analyze the the graph of the function calls
// to run checks and analyses; since in GLSL recursion is not allowed
// that graph is a DAG.
// This class is used to precompute that function call DAG so that it
// can be reused by multiple analyses.
//
// It stores a vector of function records, with one record per defined function.
// Records are accessed by index but a function symbol id can be converted
// to the index of the corresponding record. The records contain the AST node
// of the function definition and the indices of the function's callees.
//
// In addition, records are in reverse topological order: a function F being
// called by a function G will have index index(F) < index(G), that way
// depth-first analysis becomes analysis in the order of indices.

class CallDAG : angle::NonCopyable
{
  public:
    CallDAG();
    ~CallDAG();

    struct Record
    {
        TIntermFunctionDefinition *node;  // Guaranteed to be non-null.
        std::vector<int> callees;
    };

    enum InitResult
    {
        INITDAG_SUCCESS,
        INITDAG_RECURSION,
        INITDAG_UNDEFINED,
    };

    // Returns INITDAG_SUCCESS if it was able to create the DAG, otherwise prints
    // the initialization error in diagnostics, if present.
    InitResult init(TIntermNode *root, TDiagnostics *diagnostics);

    // Returns InvalidIndex if the function wasn't found
    size_t findIndex(const TSymbolUniqueId &id) const;

    const Record &getRecordFromIndex(size_t index) const;
    size_t size() const;
    void clear();

    const static size_t InvalidIndex;

  private:
    std::vector<Record> mRecords;
    std::map<int, int> mFunctionIdToIndex;

    class CallDAGCreator;
};

}  // namespace sh

#endif  // COMPILER_TRANSLATOR_CALLDAG_H_