Corentin Wallez | 71d147f | 2015-02-11 11:15:24 -0800 | [diff] [blame] | 1 | // |
| 2 | // Copyright (c) 2002-2015 The ANGLE Project Authors. All rights reserved. |
| 3 | // Use of this source code is governed by a BSD-style license that can be |
| 4 | // found in the LICENSE file. |
| 5 | // |
| 6 | |
| 7 | // CallDAG.h: Implements a call graph DAG of functions to be re-used accross |
| 8 | // analyses, allows to efficiently traverse the functions in topological |
| 9 | // order. |
| 10 | |
| 11 | #include "compiler/translator/CallDAG.h" |
| 12 | #include "compiler/translator/InfoSink.h" |
| 13 | |
| 14 | // The CallDAGCreator does all the processing required to create the CallDAG |
| 15 | // structure so that the latter contains only the necessary variables. |
| 16 | class CallDAG::CallDAGCreator : public TIntermTraverser |
| 17 | { |
| 18 | public: |
| 19 | CallDAGCreator(TInfoSinkBase *info) |
| 20 | : TIntermTraverser(true, false, true), |
| 21 | mCurrentFunction(nullptr), |
| 22 | mCurrentIndex(0), |
| 23 | mCreationInfo(info) |
| 24 | { |
| 25 | } |
| 26 | |
| 27 | InitResult assignIndices() |
| 28 | { |
| 29 | int skipped = 0; |
| 30 | for (auto &it : mFunctions) |
| 31 | { |
| 32 | // Skip unimplemented functions |
| 33 | if (it.second.node) |
| 34 | { |
| 35 | InitResult result = assignIndicesInternal(&it.second); |
| 36 | if (result != INITDAG_SUCCESS) |
| 37 | { |
| 38 | return result; |
| 39 | } |
| 40 | } |
| 41 | else |
| 42 | { |
| 43 | skipped++; |
| 44 | } |
| 45 | } |
| 46 | ASSERT(mFunctions.size() == mCurrentIndex + skipped); |
| 47 | return INITDAG_SUCCESS; |
| 48 | } |
| 49 | |
| 50 | void fillDataStructures(std::vector<Record> *records, std::map<int, int> *idToIndex) |
| 51 | { |
| 52 | ASSERT(records->empty()); |
| 53 | ASSERT(idToIndex->empty()); |
| 54 | |
| 55 | records->resize(mCurrentIndex); |
| 56 | |
| 57 | for (auto &it : mFunctions) |
| 58 | { |
| 59 | CreatorFunctionData &data = it.second; |
| 60 | // Skip unimplemented functions |
| 61 | if (!data.node) |
| 62 | { |
| 63 | continue; |
| 64 | } |
| 65 | ASSERT(data.index < records->size()); |
| 66 | Record &record = (*records)[data.index]; |
| 67 | |
| 68 | record.name = data.name.data(); |
| 69 | record.node = data.node; |
| 70 | |
| 71 | record.callees.reserve(data.callees.size()); |
| 72 | for (auto &callee : data.callees) |
| 73 | { |
| 74 | record.callees.push_back(callee->index); |
| 75 | } |
| 76 | |
| 77 | (*idToIndex)[data.node->getFunctionId()] = data.index; |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | private: |
| 82 | |
| 83 | struct CreatorFunctionData |
| 84 | { |
| 85 | CreatorFunctionData() |
| 86 | : node(nullptr), |
| 87 | index(0), |
| 88 | indexAssigned(false), |
| 89 | visiting(false) |
| 90 | { |
| 91 | } |
| 92 | |
| 93 | std::set<CreatorFunctionData*> callees; |
| 94 | TIntermAggregate *node; |
| 95 | TString name; |
| 96 | size_t index; |
| 97 | bool indexAssigned; |
| 98 | bool visiting; |
| 99 | }; |
| 100 | |
| 101 | // Aggregates the AST node for each function as well as the name of the functions called by it |
| 102 | bool visitAggregate(Visit visit, TIntermAggregate *node) override |
| 103 | { |
| 104 | switch (node->getOp()) |
| 105 | { |
| 106 | case EOpPrototype: |
| 107 | if (visit == PreVisit) |
| 108 | { |
| 109 | // Function declaration, create an empty record. |
| 110 | mFunctions[node->getName()]; |
| 111 | } |
| 112 | break; |
| 113 | case EOpFunction: |
| 114 | { |
| 115 | // Function definition, create the record if need be and remember the node. |
| 116 | if (visit == PreVisit) |
| 117 | { |
| 118 | auto it = mFunctions.find(node->getName()); |
| 119 | |
| 120 | if (it == mFunctions.end()) |
| 121 | { |
| 122 | mCurrentFunction = &mFunctions[node->getName()]; |
| 123 | } |
| 124 | else |
| 125 | { |
| 126 | mCurrentFunction = &it->second; |
| 127 | } |
| 128 | |
| 129 | mCurrentFunction->node = node; |
| 130 | mCurrentFunction->name = node->getName(); |
| 131 | |
| 132 | } |
| 133 | else if (visit == PostVisit) |
| 134 | { |
| 135 | mCurrentFunction = nullptr; |
| 136 | } |
| 137 | break; |
| 138 | } |
| 139 | case EOpFunctionCall: |
| 140 | { |
| 141 | // Function call, add the callees |
| 142 | if (visit == PreVisit) |
| 143 | { |
| 144 | // Do not handle calls to builtin functions |
| 145 | if (node->isUserDefined()) |
| 146 | { |
| 147 | auto it = mFunctions.find(node->getName()); |
| 148 | ASSERT(it != mFunctions.end()); |
| 149 | |
| 150 | // We might be in a top-level function call to set a global variable |
| 151 | if (mCurrentFunction) |
| 152 | { |
| 153 | mCurrentFunction->callees.insert(&it->second); |
| 154 | } |
| 155 | } |
| 156 | } |
| 157 | break; |
| 158 | } |
| 159 | default: |
| 160 | break; |
| 161 | } |
| 162 | return true; |
| 163 | } |
| 164 | |
| 165 | // Recursively assigns indices to a sub DAG |
| 166 | InitResult assignIndicesInternal(CreatorFunctionData *function) |
| 167 | { |
| 168 | ASSERT(function); |
| 169 | |
| 170 | if (!function->node) |
| 171 | { |
| 172 | *mCreationInfo << "Undefined function: " << function->name; |
| 173 | return INITDAG_UNDEFINED; |
| 174 | } |
| 175 | |
| 176 | if (function->indexAssigned) |
| 177 | { |
| 178 | return INITDAG_SUCCESS; |
| 179 | } |
| 180 | |
| 181 | if (function->visiting) |
| 182 | { |
| 183 | if (mCreationInfo) |
| 184 | { |
| 185 | *mCreationInfo << "Recursive function call in the following call chain: " << function->name; |
| 186 | } |
| 187 | return INITDAG_RECURSION; |
| 188 | } |
| 189 | function->visiting = true; |
| 190 | |
| 191 | for (auto &callee : function->callees) |
| 192 | { |
| 193 | InitResult result = assignIndicesInternal(callee); |
| 194 | if (result == INITDAG_RECURSION) |
| 195 | { |
| 196 | // We know that there is a recursive function call chain in the AST, |
| 197 | // print the link of the chain we were processing. |
| 198 | if (mCreationInfo) |
| 199 | { |
| 200 | *mCreationInfo << " <- " << function->name; |
| 201 | } |
| 202 | return INITDAG_RECURSION; |
| 203 | } |
| 204 | else if (result == INITDAG_UNDEFINED) |
| 205 | { |
| 206 | return INITDAG_UNDEFINED; |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | function->index = mCurrentIndex++; |
| 211 | function->indexAssigned = true; |
| 212 | |
| 213 | function->visiting = false; |
| 214 | return INITDAG_SUCCESS; |
| 215 | } |
| 216 | |
| 217 | TInfoSinkBase *mCreationInfo; |
| 218 | |
| 219 | std::map<TString, CreatorFunctionData> mFunctions; |
| 220 | CreatorFunctionData *mCurrentFunction; |
| 221 | size_t mCurrentIndex; |
| 222 | }; |
| 223 | |
| 224 | // CallDAG |
| 225 | |
| 226 | CallDAG::CallDAG() |
| 227 | { |
| 228 | } |
| 229 | |
| 230 | CallDAG::~CallDAG() |
| 231 | { |
| 232 | } |
| 233 | |
| 234 | const size_t CallDAG::InvalidIndex = std::numeric_limits<size_t>::max(); |
| 235 | |
| 236 | size_t CallDAG::findIndex(const TIntermAggregate *function) const |
| 237 | { |
| 238 | TOperator op = function->getOp(); |
| 239 | ASSERT(op == EOpPrototype || op == EOpFunction || op == EOpFunctionCall); |
Olli Etuaho | d57e0db | 2015-04-24 15:05:08 +0300 | [diff] [blame^] | 240 | UNUSED_ASSERTION_VARIABLE(op); |
Corentin Wallez | 71d147f | 2015-02-11 11:15:24 -0800 | [diff] [blame] | 241 | |
| 242 | auto it = mFunctionIdToIndex.find(function->getFunctionId()); |
| 243 | |
| 244 | if (it == mFunctionIdToIndex.end()) |
| 245 | { |
| 246 | return InvalidIndex; |
| 247 | } |
| 248 | else |
| 249 | { |
| 250 | return it->second; |
| 251 | } |
| 252 | } |
| 253 | |
| 254 | const CallDAG::Record &CallDAG::getRecordFromIndex(size_t index) const |
| 255 | { |
| 256 | ASSERT(index != InvalidIndex && index < mRecords.size()); |
| 257 | return mRecords[index]; |
| 258 | } |
| 259 | |
| 260 | const CallDAG::Record &CallDAG::getRecord(const TIntermAggregate *function) const |
| 261 | { |
| 262 | size_t index = findIndex(function); |
| 263 | ASSERT(index != InvalidIndex && index < mRecords.size()); |
| 264 | return mRecords[index]; |
| 265 | } |
| 266 | |
| 267 | size_t CallDAG::size() const |
| 268 | { |
| 269 | return mRecords.size(); |
| 270 | } |
| 271 | |
| 272 | void CallDAG::clear() |
| 273 | { |
| 274 | mRecords.clear(); |
| 275 | mFunctionIdToIndex.clear(); |
| 276 | } |
| 277 | |
| 278 | CallDAG::InitResult CallDAG::init(TIntermNode *root, TInfoSinkBase *info) |
| 279 | { |
| 280 | CallDAGCreator creator(info); |
| 281 | |
| 282 | // Creates the mapping of functions to callees |
| 283 | root->traverse(&creator); |
| 284 | |
| 285 | // Does the topological sort and detects recursions |
| 286 | InitResult result = creator.assignIndices(); |
| 287 | if (result != INITDAG_SUCCESS) |
| 288 | { |
| 289 | return result; |
| 290 | } |
| 291 | |
| 292 | creator.fillDataStructures(&mRecords, &mFunctionIdToIndex); |
| 293 | return INITDAG_SUCCESS; |
| 294 | } |