function_analysis.cpp 19.6 KB
Newer Older
Marius Wachtler's avatar
Marius Wachtler committed
1
// Copyright (c) 2014-2016 Dropbox, Inc.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
2
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
Kevin Modzelewski's avatar
Kevin Modzelewski committed
6
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
7
//    http://www.apache.org/licenses/LICENSE-2.0
Kevin Modzelewski's avatar
Kevin Modzelewski committed
8
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16
#include "analysis/function_analysis.h"

Kevin Modzelewski's avatar
Kevin Modzelewski committed
17 18 19
#include <cstdio>
#include <cstdlib>
#include <deque>
20
#include <unordered_set>
Kevin Modzelewski's avatar
Kevin Modzelewski committed
21

22 23
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
24
#include "llvm/ADT/StringSet.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
25

26 27
#include "analysis/fpc.h"
#include "analysis/scoping_analysis.h"
28
#include "codegen/osrentry.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
29 30
#include "core/ast.h"
#include "core/cfg.h"
31
#include "core/common.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
32 33 34 35 36
#include "core/util.h"

namespace pyston {

class LivenessBBVisitor : public NoopASTVisitor {
37 38
private:
    struct Status {
39
        enum Usage : char {
40 41 42 43 44 45 46 47 48 49 50 51 52
            NONE,
            USED,
            DEFINED,
        };

        Usage first = NONE;
        Usage second = NONE;

        void addUsage(Usage u) {
            if (first == NONE)
                first = u;
            second = u;
        }
53
    };
Kevin Modzelewski's avatar
Kevin Modzelewski committed
54

55
    VRegMap<Status> statuses;
56
    LivenessAnalysis* analysis;
57

58 59
    void _doLoad(int vreg, AST_Name* node) {
        Status& status = statuses[vreg];
60
        status.addUsage(Status::USED);
61
    }
62

63 64 65
    void _doStore(int vreg) {
        assert(vreg >= 0);
        Status& status = statuses[vreg];
66
        status.addUsage(Status::DEFINED);
67 68
    }

69
    Status::Usage getStatusFirst(int vreg) const { return statuses[vreg].first; }
70

71
public:
72 73
    LivenessBBVisitor(LivenessAnalysis* analysis)
        : statuses(analysis->cfg->getVRegInfo().getTotalNumOfVRegs()), analysis(analysis) {}
74

75
    bool firstIsUse(int vreg) const { return getStatusFirst(vreg) == Status::USED; }
76

77
    bool firstIsDef(int vreg) const { return getStatusFirst(vreg) == Status::DEFINED; }
78

79
    bool isKilledAt(AST_Name* node, bool is_live_at_end) { return node->is_kill; }
80

81
    bool visit_import(AST_Import* node) { RELEASE_ASSERT(0, "these should all get removed by the cfg"); }
82 83

    bool visit_classdef(AST_ClassDef* node) {
84 85 86 87 88
        for (auto e : node->bases)
            e->accept(this);
        for (auto e : node->decorator_list)
            e->accept(this);

89 90
        return true;
    }
91

92
    bool visit_functiondef(AST_FunctionDef* node) {
93
        for (auto* d : node->decorator_list)
94
            d->accept(this);
95 96
        for (auto* d : node->args->defaults)
            d->accept(this);
97

98 99
        return true;
    }
100

101
    bool visit_name(AST_Name* node) {
102 103 104
        if (node->vreg == -1)
            return true;

105
        if (node->ctx_type == AST_TYPE::Load)
106
            _doLoad(node->vreg, node);
107 108
        else if (node->ctx_type == AST_TYPE::Del) {
            // Hack: we don't have a bytecode for temporary-kills:
109
            if (node->vreg >= analysis->cfg->getVRegInfo().getNumOfUserVisibleVRegs())
110
                return true;
111 112
            _doLoad(node->vreg, node);
            _doStore(node->vreg);
113
        } else if (node->ctx_type == AST_TYPE::Store || node->ctx_type == AST_TYPE::Param)
114
            _doStore(node->vreg);
115
        else {
116
            ASSERT(0, "%d", node->ctx_type);
117
            abort();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
118
        }
119 120
        return true;
    }
121

122
    bool visit_alias(AST_alias* node) { RELEASE_ASSERT(0, "these should be removed by the cfg"); }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
123 124
};

125
LivenessAnalysis::LivenessAnalysis(CFG* cfg) : cfg(cfg), result_cache(cfg->getVRegInfo().getTotalNumOfVRegs()) {
126
    Timer _t("LivenessAnalysis()", 100);
127

128 129 130 131 132 133 134
    for (CFGBlock* b : cfg->blocks) {
        auto visitor = new LivenessBBVisitor(this); // livenessCache unique_ptr will delete it.
        for (AST_stmt* stmt : b->body) {
            stmt->accept(visitor);
        }
        liveness_cache.insert(std::make_pair(b, std::unique_ptr<LivenessBBVisitor>(visitor)));
    }
135 136 137

    static StatCounter us_liveness("us_compiling_analysis_liveness");
    us_liveness.log(_t.end());
138 139
}

140 141 142
LivenessAnalysis::~LivenessAnalysis() {
}

143
bool LivenessAnalysis::isKill(AST_Name* node, CFGBlock* parent_block) {
144
    if (node->id.s()[0] != '#')
145 146
        return false;

147
    return liveness_cache[parent_block]->isKilledAt(node, isLiveAtEnd(node->vreg, parent_block));
148 149
}

150 151 152
bool LivenessAnalysis::isLiveAtEnd(int vreg, CFGBlock* block) {
    // Is a user-visible name, always live:
    if (vreg < block->cfg->getVRegInfo().getNumOfUserVisibleVRegs())
153 154
        return true;

155
#ifndef NDEBUG
156 157
    if (block->cfg->getVRegInfo().isBlockLocalVReg(vreg))
        return false;
158
#endif
159

Kevin Modzelewski's avatar
Kevin Modzelewski committed
160 161 162
    if (block->successors.size() == 0)
        return false;

163
    if (!result_cache[vreg].size()) {
164 165
        Timer _t("LivenessAnalysis()", 10);

166
        llvm::DenseMap<CFGBlock*, bool>& map = result_cache[vreg];
167 168 169 170

        // Approach:
        // - Find all uses (blocks where the status is USED)
        // - Trace backwards, marking all blocks as live-at-end
171
        // - If we hit a block that is DEFINED, stop
172
        for (CFGBlock* b : cfg->blocks) {
173
            if (!liveness_cache[b]->firstIsUse(vreg))
174 175 176 177 178
                continue;

            std::deque<CFGBlock*> q;
            for (CFGBlock* pred : b->predecessors) {
                q.push_back(pred);
179
            }
180

181 182 183
            while (q.size()) {
                CFGBlock* thisblock = q.front();
                q.pop_front();
184

185 186 187 188
                if (map[thisblock])
                    continue;

                map[thisblock] = true;
189
                if (!liveness_cache[thisblock]->firstIsDef(vreg)) {
190 191 192 193
                    for (CFGBlock* pred : thisblock->predecessors) {
                        q.push_back(pred);
                    }
                }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
194 195 196
            }
        }

197 198 199 200
        // Note: this one gets counted as part of us_compiling_irgen as well:
        static StatCounter us_liveness("us_compiling_analysis_liveness");
        us_liveness.log(_t.end());
    }
201

202 203 204 205 206 207 208 209
    // For block-local vregs, this query doesn't really make sense,
    // since the vreg will be live but that's probably not what we care about.
    // It's probably safe to return false, but let's just error for now.
    if (block->cfg->getVRegInfo().isBlockLocalVReg(vreg)) {
        ASSERT(!result_cache[vreg][block], "%d in %d", vreg, block->idx);
        return false;
    }

210
    return result_cache[vreg][block];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
211 212 213
}

class DefinednessBBAnalyzer : public BBAnalyzer<DefinednessAnalysis::DefinitionLevel> {
214 215
private:
    typedef DefinednessAnalysis::DefinitionLevel DefinitionLevel;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
216

217
public:
218
    DefinednessBBAnalyzer() {}
219 220

    virtual DefinitionLevel merge(DefinitionLevel from, DefinitionLevel into) const {
221 222 223 224 225 226 227 228 229 230
        assert(from != DefinitionLevel::Unknown);
        if (into == DefinitionLevel::Unknown)
            return from;

        if (into == DefinednessAnalysis::Undefined && from == DefinednessAnalysis::Undefined)
            return DefinednessAnalysis::Undefined;

        if (into == DefinednessAnalysis::Defined && from == DefinednessAnalysis::Defined)
            return DefinednessAnalysis::Defined;
        return DefinednessAnalysis::PotentiallyDefined;
231 232
    }
    virtual void processBB(Map& starting, CFGBlock* block) const;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
233
};
234

Kevin Modzelewski's avatar
Kevin Modzelewski committed
235
class DefinednessVisitor : public ASTVisitor {
236 237 238 239
private:
    typedef DefinednessBBAnalyzer::Map Map;
    Map& state;

240 241 242
    void _doSet(int vreg) {
        assert(vreg >= 0 && vreg < state.numVregs());
        state[vreg] = DefinednessAnalysis::Defined;
243
    }
244 245 246 247 248 249

    void _doSet(AST* t) {
        switch (t->type) {
            case AST_TYPE::Attribute:
                // doesn't affect definedness (yet?)
                break;
250 251 252 253 254
            case AST_TYPE::Name: {
                auto name = ast_cast<AST_Name>(t);
                if (name->lookup_type == ScopeInfo::VarScopeType::FAST
                    || name->lookup_type == ScopeInfo::VarScopeType::CLOSURE) {
                    assert(name->vreg != -1);
255
                    _doSet(name->vreg);
256 257 258 259 260 261 262
                } else if (name->lookup_type == ScopeInfo::VarScopeType::GLOBAL
                           || name->lookup_type == ScopeInfo::VarScopeType::NAME) {
                    assert(name->vreg == -1);
                    // skip
                } else {
                    RELEASE_ASSERT(0, "%d", name->lookup_type);
                }
263
                break;
264
            }
265 266 267 268 269 270
            case AST_TYPE::Subscript:
                break;
            case AST_TYPE::Tuple: {
                AST_Tuple* tt = ast_cast<AST_Tuple>(t);
                for (int i = 0; i < tt->elts.size(); i++) {
                    _doSet(tt->elts[i]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
271
                }
272
                break;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
273
            }
274 275
            default:
                ASSERT(0, "Unknown type for DefinednessVisitor: %d", t->type);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
276
        }
277
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
278

279 280 281 282 283 284 285
public:
    DefinednessVisitor(Map& state) : state(state) {}

    virtual bool visit_assert(AST_Assert* node) { return true; }
    virtual bool visit_branch(AST_Branch* node) { return true; }
    virtual bool visit_expr(AST_Expr* node) { return true; }
    virtual bool visit_global(AST_Global* node) { return true; }
286
    virtual bool visit_invoke(AST_Invoke* node) { return false; }
287 288 289
    virtual bool visit_jump(AST_Jump* node) { return true; }
    virtual bool visit_pass(AST_Pass* node) { return true; }
    virtual bool visit_print(AST_Print* node) { return true; }
290
    virtual bool visit_raise(AST_Raise* node) { return true; }
291 292
    virtual bool visit_return(AST_Return* node) { return true; }

293 294 295 296
    virtual bool visit_delete(AST_Delete* node) {
        for (auto t : node->targets) {
            if (t->type == AST_TYPE::Name) {
                AST_Name* name = ast_cast<AST_Name>(t);
297 298
                if (name->lookup_type != ScopeInfo::VarScopeType::GLOBAL
                    && name->lookup_type != ScopeInfo::VarScopeType::NAME) {
299 300
                    assert(name->vreg != -1);
                    state[name->vreg] = DefinednessAnalysis::Undefined;
301 302
                } else
                    assert(name->vreg == -1);
303 304 305 306 307 308 309 310 311 312
            } else {
                // The CFG pass should reduce all deletes to the "basic" deletes on names/attributes/subscripts.
                // If not, probably the best way to do this would be to just do a full AST traversal
                // and look for AST_Name's with a ctx of Del
                assert(t->type == AST_TYPE::Attribute || t->type == AST_TYPE::Subscript);
            }
        }
        return true;
    }

313
    virtual bool visit_classdef(AST_ClassDef* node) {
314 315
        assert(0 && "I think this isn't needed");
        //_doSet(node->name);
316 317
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
318

319
    virtual bool visit_functiondef(AST_FunctionDef* node) {
320 321
        assert(0 && "I think this isn't needed");
        //_doSet(node->name);
322 323
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
324

325
    virtual bool visit_alias(AST_alias* node) {
326
        int vreg = node->name_vreg;
327
        if (node->asname.s().size())
328
            vreg = node->asname_vreg;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
329

330
        _doSet(vreg);
331 332 333 334
        return true;
    }
    virtual bool visit_import(AST_Import* node) { return false; }
    virtual bool visit_importfrom(AST_ImportFrom* node) { return false; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
335

336 337 338
    virtual bool visit_assign(AST_Assign* node) {
        for (int i = 0; i < node->targets.size(); i++) {
            _doSet(node->targets[i]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
339
        }
340 341
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
342

343
    virtual bool visit_arguments(AST_arguments* node) {
344 345 346 347
        if (node->kwarg)
            _doSet(node->kwarg);
        if (node->vararg)
            _doSet(node->vararg);
348 349
        for (int i = 0; i < node->args.size(); i++) {
            _doSet(node->args[i]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
350
        }
351 352
        return true;
    }
353

Travis Hance's avatar
exec  
Travis Hance committed
354 355
    virtual bool visit_exec(AST_Exec* node) { return true; }

356
    friend class DefinednessBBAnalyzer;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
357
};
358

359
void DefinednessBBAnalyzer::processBB(Map& starting, CFGBlock* block) const {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
360
    DefinednessVisitor visitor(starting);
361

Kevin Modzelewski's avatar
Kevin Modzelewski committed
362 363 364
    for (int i = 0; i < block->body.size(); i++) {
        block->body[i]->accept(&visitor);
    }
365

366
    if (VERBOSITY("analysis") >= 3) {
367
        printf("At end of block %d:\n", block->idx);
368
        for (const auto& p : starting) {
369 370
            if (p.second != DefinednessAnalysis::Undefined)
                printf("%s: %d\n", block->cfg->getVRegInfo().getName(p.first).c_str(), p.second);
371 372
        }
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
373 374
}

375
void DefinednessAnalysis::run(VRegMap<DefinednessAnalysis::DefinitionLevel> initial_map, CFGBlock* initial_block) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
376
    Timer _t("DefinednessAnalysis()", 10);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
377

378 379
    // Don't run this twice:
    assert(!defined_at_end.size());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
380

381
    auto cfg = initial_block->cfg;
382 383
    int nvregs = cfg->getVRegInfo().getTotalNumOfVRegs();
    assert(initial_map.numVregs() == nvregs);
384 385

    auto&& vreg_info = cfg->getVRegInfo();
386 387
    computeFixedPoint(std::move(initial_map), initial_block, DefinednessBBAnalyzer(), false, defined_at_beginning,
                      defined_at_end);
388 389

    for (const auto& p : defined_at_end) {
390
        assert(p.second.numVregs() == nvregs);
391 392

        assert(!defined_at_end_sets.count(p.first));
393
        VRegSet& required = defined_at_end_sets.insert(std::make_pair(p.first, VRegSet(nvregs))).first->second;
394

395
        // required.resize(nvregs, /* value= */ false);
396 397

        for (int vreg = 0; vreg < nvregs; vreg++) {
398 399 400
            auto status = p.second[vreg];
            // assert(p.second.count(name));
            // auto status = p.second.find(name)->second;
401 402 403
            assert(status != DefinednessAnalysis::Unknown);
            if (status != DefinednessAnalysis::Undefined)
                required.set(vreg);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
404 405
        }
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
406

407
    static StatCounter us_definedness("us_compiling_analysis_definedness");
Kevin Modzelewski's avatar
Kevin Modzelewski committed
408
    us_definedness.log(_t.end());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
409 410
}

411
DefinednessAnalysis::DefinitionLevel DefinednessAnalysis::isDefinedAtEnd(int vreg, CFGBlock* block) {
412
    assert(defined_at_end.count(block));
413
    auto&& map = defined_at_end.find(block)->second;
414
    return map[vreg];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
415 416
}

417
const VRegSet& DefinednessAnalysis::getDefinedVregsAtEnd(CFGBlock* block) {
418
    assert(defined_at_end_sets.count(block));
419
    return defined_at_end_sets.find(block)->second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
420 421
}

422
PhiAnalysis::PhiAnalysis(VRegMap<DefinednessAnalysis::DefinitionLevel> initial_map, CFGBlock* initial_block,
423
                         bool initials_need_phis, LivenessAnalysis* liveness)
424
    : definedness(), empty_set(initial_map.numVregs()), liveness(liveness) {
425 426 427
    auto cfg = initial_block->cfg;
    auto&& vreg_info = cfg->getVRegInfo();

428 429 430 431
    // I think this should always be the case -- if we're going to generate phis for the initial block,
    // then we should include the initial arguments as an extra entry point.
    assert(initials_need_phis == (initial_block->predecessors.size() > 0));

432 433 434
    int num_vregs = initial_map.numVregs();
    assert(num_vregs == vreg_info.getTotalNumOfVRegs());

435
    definedness.run(std::move(initial_map), initial_block);
436

437 438
    Timer _t("PhiAnalysis()", 10);

439 440
    for (const auto& p : definedness.defined_at_end) {
        CFGBlock* block = p.first;
441 442
        assert(!required_phis.count(block));
        VRegSet& required = required_phis.insert(std::make_pair(block, VRegSet(num_vregs))).first->second;
443 444 445 446 447 448 449 450

        int npred = 0;
        for (CFGBlock* pred : block->predecessors) {
            if (definedness.defined_at_end.count(pred))
                npred++;
        }

        if (npred > 1 || (initials_need_phis && block == initial_block)) {
451
            for (CFGBlock* pred : block->predecessors) {
452 453 454
                if (!definedness.defined_at_end.count(pred))
                    continue;

455
                const VRegSet& defined = definedness.getDefinedVregsAtEnd(pred);
456
                for (int vreg : defined) {
457
                    if (!required[vreg] && liveness->isLiveAtEnd(vreg, pred)) {
458
                        // printf("%d-%d %s\n", pred->idx, block->idx, vreg_info.getName(vreg).c_str());
459

460
                        required.set(vreg);
461 462
                    }
                }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
463 464
            }
        }
465 466 467 468 469 470 471 472

        if (VERBOSITY() >= 3) {
            printf("Phis required at end of %d:", block->idx);
            for (auto vreg : required) {
                printf(" %s", vreg_info.getName(vreg).c_str());
            }
            printf("\n");
        }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
473
    }
474 475 476

    static StatCounter us_phis("us_compiling_analysis_phis");
    us_phis.log(_t.end());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
477 478
}

479
const VRegSet& PhiAnalysis::getAllRequiredAfter(CFGBlock* block) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
480
    if (block->successors.size() == 0)
481
        return empty_set;
482
    assert(required_phis.count(block->successors[0]));
483
    return required_phis.find(block->successors[0])->second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
484 485
}

486
const VRegSet& PhiAnalysis::getAllRequiredFor(CFGBlock* block) {
487
    assert(required_phis.count(block));
488
    return required_phis.find(block)->second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
489 490
}

491
bool PhiAnalysis::isRequired(int vreg, CFGBlock* block) {
492
    assert(required_phis.count(block));
493
    return required_phis.find(block)->second[vreg];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
494 495
}

496
bool PhiAnalysis::isRequiredAfter(int vreg, CFGBlock* block) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
497 498 499 500 501 502
    // If there are multiple successors, then none of them are allowed
    // to require any phi nodes
    if (block->successors.size() != 1)
        return false;

    // Fall back to the other method:
503
    return isRequired(vreg, block->successors[0]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
504 505
}

506
bool PhiAnalysis::isPotentiallyUndefinedAfter(int vreg, CFGBlock* block) {
507
    for (auto b : block->successors) {
508
        if (isPotentiallyUndefinedAt(vreg, b))
509 510 511
            return true;
    }
    return false;
512 513
}

514
bool PhiAnalysis::isPotentiallyUndefinedAt(int vreg, CFGBlock* block) {
515
    assert(definedness.defined_at_beginning.count(block));
516
    return definedness.defined_at_beginning.find(block)->second[vreg] != DefinednessAnalysis::Defined;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
517 518
}

519 520 521 522 523
std::unique_ptr<LivenessAnalysis> computeLivenessInfo(CFG* cfg) {
    static StatCounter counter("num_liveness_analysis");
    counter.log();

    return std::unique_ptr<LivenessAnalysis>(new LivenessAnalysis(cfg));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
524 525
}

526
std::unique_ptr<PhiAnalysis> computeRequiredPhis(const ParamNames& args, CFG* cfg, LivenessAnalysis* liveness) {
527 528 529
    static StatCounter counter("num_phi_analysis");
    counter.log();

530
    auto&& vreg_info = cfg->getVRegInfo();
531 532 533
    int num_vregs = vreg_info.getTotalNumOfVRegs();

    VRegMap<DefinednessAnalysis::DefinitionLevel> initial_map(num_vregs);
534

535
    assert(vreg_info.hasVRegsAssigned());
536 537 538
    for (int vreg = 0; vreg < num_vregs; vreg++) {
        initial_map[vreg] = DefinednessAnalysis::Undefined;
    }
539

540
    for (AST_Name* n : args.allArgsAsName()) {
541 542
        ScopeInfo::VarScopeType vst = n->lookup_type;
        assert(vst != ScopeInfo::VarScopeType::UNKNOWN);
543
        assert(vst != ScopeInfo::VarScopeType::GLOBAL); // global-and-local error
544
        if (vst == ScopeInfo::VarScopeType::NAME)
545
            continue;
546 547
        assert(n->vreg >= 0);
        initial_map[n->vreg] = DefinednessAnalysis::Defined;
548
    }
549

550
    assert(initial_map.numVregs() == vreg_info.getTotalNumOfVRegs());
551

552
    return std::unique_ptr<PhiAnalysis>(
553
        new PhiAnalysis(std::move(initial_map), cfg->getStartingBlock(), false, liveness));
554 555
}

556 557
std::unique_ptr<PhiAnalysis> computeRequiredPhis(const OSREntryDescriptor* entry_descriptor,
                                                 LivenessAnalysis* liveness) {
558 559 560
    static StatCounter counter("num_phi_analysis");
    counter.log();

561 562 563
    auto cfg = entry_descriptor->md->source->cfg;
    int num_vregs = cfg->getVRegInfo().getTotalNumOfVRegs();
    VRegMap<DefinednessAnalysis::DefinitionLevel> initial_map(num_vregs);
564

565 566
    for (int vreg = 0; vreg < num_vregs; vreg++) {
        initial_map[vreg] = DefinednessAnalysis::Undefined;
567 568
    }

569
    for (const auto& p : entry_descriptor->args) {
570 571 572
        int vreg = p.first;
        ASSERT(initial_map[vreg] == DefinednessAnalysis::Undefined, "%d %d", vreg, initial_map[vreg]);
        if (entry_descriptor->potentially_undefined[vreg])
573
            initial_map[vreg] = DefinednessAnalysis::PotentiallyDefined;
574
        else
575
            initial_map[vreg] = DefinednessAnalysis::Defined;
576 577
    }

578
    return std::unique_ptr<PhiAnalysis>(
579
        new PhiAnalysis(std::move(initial_map), entry_descriptor->backedge->target, true, liveness));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
580 581
}
}