ast_interpreter.cpp 68.8 KB
Newer Older
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1
// Copyright (c) 2014-2015 Dropbox, Inc.
Marius Wachtler's avatar
Marius Wachtler committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//
// 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
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// 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.

#include "codegen/ast_interpreter.h"

17
#include <llvm/ADT/DenseMap.h>
Kevin Modzelewski's avatar
Kevin Modzelewski committed
18
#include <llvm/ADT/StringMap.h>
Marius Wachtler's avatar
Marius Wachtler committed
19 20 21 22
#include <unordered_map>

#include "analysis/function_analysis.h"
#include "analysis/scoping_analysis.h"
23
#include "codegen/baseline_jit.h"
Marius Wachtler's avatar
Marius Wachtler committed
24
#include "codegen/codegen.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
25 26
#include "codegen/compvars.h"
#include "codegen/irgen.h"
Marius Wachtler's avatar
Marius Wachtler committed
27 28 29 30
#include "codegen/irgen/hooks.h"
#include "codegen/irgen/irgenerator.h"
#include "codegen/irgen/util.h"
#include "codegen/osrentry.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
31
#include "core/ast.h"
Marius Wachtler's avatar
Marius Wachtler committed
32 33
#include "core/cfg.h"
#include "core/common.h"
34
#include "core/contiguous_map.h"
Marius Wachtler's avatar
Marius Wachtler committed
35 36 37
#include "core/stats.h"
#include "core/thread_utils.h"
#include "core/util.h"
38
#include "gc/roots.h"
Marius Wachtler's avatar
Marius Wachtler committed
39 40 41
#include "runtime/generator.h"
#include "runtime/import.h"
#include "runtime/inline/boxing.h"
42
#include "runtime/inline/list.h"
Marius Wachtler's avatar
Marius Wachtler committed
43
#include "runtime/long.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
44
#include "runtime/objmodel.h"
Marius Wachtler's avatar
Marius Wachtler committed
45 46
#include "runtime/set.h"
#include "runtime/types.h"
47
#include "runtime/util.h"
Marius Wachtler's avatar
Marius Wachtler committed
48

49 50 51 52 53 54
#ifndef NDEBUG
#define DEBUG 1
#else
#define DEBUG 0
#endif

Marius Wachtler's avatar
Marius Wachtler committed
55 56
namespace pyston {

57 58
namespace {

59
class ASTInterpreter;
60
extern "C" Box* executeInnerAndSetupFrame(ASTInterpreter& interpreter, CFGBlock* start_block, AST_stmt* start_at);
61

Rudi Chen's avatar
Rudi Chen committed
62 63 64 65
/*
 * ASTInterpreters exist per function frame - there's no global interpreter object that executes
 * all non-jitted code!
 *
66
 * All ASTInterpreter instances have to live on the stack because otherwise the GC won't scan the fields.
Rudi Chen's avatar
Rudi Chen committed
67
 */
68
class ASTInterpreter {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
69
public:
70
    ASTInterpreter(CLFunction* clfunc, Box** vregs);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
71 72 73

    void initArguments(int nargs, BoxedClosure* closure, BoxedGenerator* generator, Box* arg1, Box* arg2, Box* arg3,
                       Box** args);
74

75 76
    static Box* execute(ASTInterpreter& interpreter, CFGBlock* start_block = NULL, AST_stmt* start_at = NULL);
    static Box* executeInner(ASTInterpreter& interpreter, CFGBlock* start_block, AST_stmt* start_at);
77

Kevin Modzelewski's avatar
Kevin Modzelewski committed
78
private:
79
    Value createFunction(AST* node, AST_arguments* args, const std::vector<AST_stmt*>& body);
80
    Value doBinOp(Value left, Value right, int op, BinExpType exp_type);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
81
    void doStore(AST_expr* node, Value value);
82
    void doStore(AST_Name* name, Value value);
83 84
    Box* doOSR(AST_Jump* node);
    Value getNone();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
85 86 87 88 89 90 91

    Value visit_assert(AST_Assert* node);
    Value visit_assign(AST_Assign* node);
    Value visit_binop(AST_BinOp* node);
    Value visit_call(AST_Call* node);
    Value visit_compare(AST_Compare* node);
    Value visit_delete(AST_Delete* node);
Travis Hance's avatar
exec  
Travis Hance committed
92
    Value visit_exec(AST_Exec* node);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
93 94 95 96 97 98 99 100 101 102 103 104
    Value visit_global(AST_Global* node);
    Value visit_module(AST_Module* node);
    Value visit_print(AST_Print* node);
    Value visit_raise(AST_Raise* node);
    Value visit_return(AST_Return* node);
    Value visit_stmt(AST_stmt* node);
    Value visit_unaryop(AST_UnaryOp* node);

    Value visit_attribute(AST_Attribute* node);
    Value visit_dict(AST_Dict* node);
    Value visit_expr(AST_expr* node);
    Value visit_expr(AST_Expr* node);
105
    Value visit_extslice(AST_ExtSlice* node);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
106 107 108 109 110 111 112 113 114
    Value visit_index(AST_Index* node);
    Value visit_lambda(AST_Lambda* node);
    Value visit_list(AST_List* node);
    Value visit_name(AST_Name* node);
    Value visit_num(AST_Num* node);
    Value visit_repr(AST_Repr* node);
    Value visit_set(AST_Set* node);
    Value visit_str(AST_Str* node);
    Value visit_subscript(AST_Subscript* node);
115 116
    Value visit_slice(AST_Slice* node);
    Value visit_slice(AST_slice* node);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
117 118 119
    Value visit_tuple(AST_Tuple* node);
    Value visit_yield(AST_Yield* node);

120 121
    Value visit_makeClass(AST_MakeClass* node);
    Value visit_makeFunction(AST_MakeFunction* node);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
122 123 124 125 126 127 128 129 130

    // pseudo
    Value visit_augBinOp(AST_AugBinOp* node);
    Value visit_branch(AST_Branch* node);
    Value visit_clsAttribute(AST_ClsAttribute* node);
    Value visit_invoke(AST_Invoke* node);
    Value visit_jump(AST_Jump* node);
    Value visit_langPrimitive(AST_LangPrimitive* node);

131 132
    // for doc on 'exit_offset' have a look at JitFragmentWriter::num_bytes_exit and num_bytes_overlapping
    void startJITing(CFGBlock* block, int exit_offset = 0);
133 134
    void abortJITing();
    void finishJITing(CFGBlock* continue_block = NULL);
135
    Box* execJITedBlock(CFGBlock* b);
136

137 138 139 140 141
    // this variables are used by the baseline JIT, make sure they have an offset < 0x80 so we can use shorter
    // instructions
    CFGBlock* next_block, *current_block;
    AST_stmt* current_inst;

142
    CLFunction* clfunc;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
143 144
    SourceInfo* source_info;
    ScopeInfo* scope_info;
145
    PhiAnalysis* phis;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
146

147
    Box** vregs;
148
    ExcInfo last_exception;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
149 150 151
    BoxedClosure* passed_closure, *created_closure;
    BoxedGenerator* generator;
    unsigned edgecount;
152
    FrameInfo frame_info;
153
    BoxedModule* parent_module;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
154

Travis Hance's avatar
Travis Hance committed
155 156
    // This is either a module or a dict
    Box* globals;
157
    std::unique_ptr<JitFragmentWriter> jit;
158
    bool should_jit;
Travis Hance's avatar
Travis Hance committed
159

Kevin Modzelewski's avatar
Kevin Modzelewski committed
160
public:
161 162 163 164 165
    llvm::DenseMap<InternedString, int>& getSymVRegMap() {
        assert(source_info->cfg);
        return source_info->cfg->sym_vreg_map;
    }

166 167 168 169 170
    AST_stmt* getCurrentStatement() {
        assert(current_inst);
        return current_inst;
    }

171 172 173 174 175
    Box* getGlobals() {
        assert(globals);
        return globals;
    }

176
    CLFunction* getCL() { return clfunc; }
177
    FrameInfo* getFrameInfo() { return &frame_info; }
178
    BoxedClosure* getPassedClosure() { return passed_closure; }
179
    Box** getVRegs() { return vregs; }
180 181
    const ScopeInfo* getScopeInfo() { return scope_info; }

182
    void addSymbol(InternedString name, Box* value, bool allow_duplicates);
Travis Hance's avatar
exec  
Travis Hance committed
183 184 185 186 187
    void setGenerator(Box* gen);
    void setPassedClosure(Box* closure);
    void setCreatedClosure(Box* closure);
    void setBoxedLocals(Box*);
    void setFrameInfo(const FrameInfo* frame_info);
Travis Hance's avatar
Travis Hance committed
188
    void setGlobals(Box* globals);
Travis Hance's avatar
exec  
Travis Hance committed
189

190
    friend struct pyston::ASTInterpreterJitInterface;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
191 192
};

193
void ASTInterpreter::addSymbol(InternedString name, Box* value, bool allow_duplicates) {
194
    assert(getSymVRegMap().count(name));
195
    if (!allow_duplicates)
196 197
        assert(vregs[getSymVRegMap()[name]] == NULL);
    vregs[getSymVRegMap()[name]] = value;
198 199
}

Travis Hance's avatar
exec  
Travis Hance committed
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
void ASTInterpreter::setGenerator(Box* gen) {
    assert(!this->generator); // This should only used for initialization
    assert(gen->cls == generator_cls);
    this->generator = static_cast<BoxedGenerator*>(gen);
}

void ASTInterpreter::setPassedClosure(Box* closure) {
    assert(!this->passed_closure); // This should only used for initialization
    assert(closure->cls == closure_cls);
    this->passed_closure = static_cast<BoxedClosure*>(closure);
}

void ASTInterpreter::setCreatedClosure(Box* closure) {
    assert(!this->created_closure); // This should only used for initialization
    assert(closure->cls == closure_cls);
    this->created_closure = static_cast<BoxedClosure*>(closure);
}

void ASTInterpreter::setBoxedLocals(Box* boxedLocals) {
    this->frame_info.boxedLocals = boxedLocals;
}

void ASTInterpreter::setFrameInfo(const FrameInfo* frame_info) {
    this->frame_info = *frame_info;
}

Travis Hance's avatar
Travis Hance committed
226
void ASTInterpreter::setGlobals(Box* globals) {
227
    assert(gc::isValidGCObject(globals));
Travis Hance's avatar
Travis Hance committed
228 229
    this->globals = globals;
}
230

231
ASTInterpreter::ASTInterpreter(CLFunction* clfunc, Box** vregs)
232 233
    : current_block(0),
      current_inst(0),
234 235
      clfunc(clfunc),
      source_info(clfunc->source.get()),
236 237
      scope_info(0),
      phis(NULL),
238
      vregs(vregs),
239 240 241 242 243
      last_exception(NULL, NULL, NULL),
      passed_closure(0),
      created_closure(0),
      generator(0),
      edgecount(0),
244
      frame_info(ExcInfo(NULL, NULL, NULL)),
245
      parent_module(source_info->parent_module),
246 247
      globals(0),
      should_jit(false) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
248

Marius Wachtler's avatar
Marius Wachtler committed
249
    scope_info = source_info->getScopeInfo();
Travis Hance's avatar
Travis Hance committed
250

251
    assert(scope_info);
Marius Wachtler's avatar
Marius Wachtler committed
252 253 254 255 256 257 258 259
}

void ASTInterpreter::initArguments(int nargs, BoxedClosure* _closure, BoxedGenerator* _generator, Box* arg1, Box* arg2,
                                   Box* arg3, Box** args) {
    passed_closure = _closure;
    generator = _generator;

    if (scope_info->createsClosure())
Travis Hance's avatar
Travis Hance committed
260
        created_closure = createClosure(passed_closure, scope_info->getClosureSize());
Marius Wachtler's avatar
Marius Wachtler committed
261

262
    const ParamNames& param_names = clfunc->param_names;
263

264 265 266 267 268
    // make sure the AST_Name nodes are set
    assert(param_names.args.size() == param_names.arg_names.size());
    assert(param_names.vararg.empty() == (param_names.vararg_name == NULL));
    assert(param_names.kwarg.empty() == (param_names.kwarg_name == NULL));

Marius Wachtler's avatar
Marius Wachtler committed
269
    int i = 0;
270 271
    for (auto& name : param_names.arg_names) {
        doStore(name, Value(getArg(i++, arg1, arg2, arg3, args), 0));
Marius Wachtler's avatar
Marius Wachtler committed
272 273
    }

274 275
    if (param_names.vararg_name)
        doStore(param_names.vararg_name, Value(getArg(i++, arg1, arg2, arg3, args), 0));
Marius Wachtler's avatar
Marius Wachtler committed
276

277 278 279 280 281 282
    if (param_names.kwarg_name) {
        Box* val = getArg(i++, arg1, arg2, arg3, args);
        if (!val)
            val = createDict();
        doStore(param_names.kwarg_name, Value(val, 0));
    }
283 284

    assert(nargs == i);
Marius Wachtler's avatar
Marius Wachtler committed
285 286
}

287
void ASTInterpreter::startJITing(CFGBlock* block, int exit_offset) {
288 289 290
    assert(ENABLE_BASELINEJIT);
    assert(!jit);

291
    auto& code_blocks = clfunc->code_blocks;
292 293 294 295 296
    JitCodeBlock* code_block = NULL;
    if (!code_blocks.empty())
        code_block = code_blocks[code_blocks.size() - 1].get();

    if (!code_block || code_block->shouldCreateNewBlock()) {
297
        code_blocks.push_back(std::unique_ptr<JitCodeBlock>(new JitCodeBlock(source_info->getName()->s())));
298
        code_block = code_blocks[code_blocks.size() - 1].get();
299
        exit_offset = 0;
300 301
    }

302
    jit = code_block->newFragment(block, exit_offset);
303 304 305 306
}

void ASTInterpreter::abortJITing() {
    if (jit) {
307 308
        static StatCounter bjit_aborts("num_baselinejit_aborts");
        bjit_aborts.log();
309 310 311 312 313 314 315 316
        jit->abortCompilation();
        jit.reset();
    }
}

void ASTInterpreter::finishJITing(CFGBlock* continue_block) {
    if (!jit)
        return;
317
    int exit_offset = jit->finishCompilation();
318 319
    jit.reset();
    if (continue_block && !continue_block->code)
320
        startJITing(continue_block, exit_offset);
321 322
}

323 324 325
Box* ASTInterpreter::execJITedBlock(CFGBlock* b) {
    try {
        UNAVOIDABLE_STAT_TIMER(t0, "us_timer_in_baseline_jitted_code");
326
        std::pair<CFGBlock*, Box*> rtn = b->entry_code(this, b, vregs);
327 328 329 330 331 332 333 334
        next_block = rtn.first;
        if (!next_block)
            return rtn.second;
    } catch (ExcInfo e) {
        AST_stmt* stmt = getCurrentStatement();
        if (stmt->type != AST_TYPE::Invoke)
            throw e;

335
        auto source = getCL()->source.get();
336
        stmt->cxx_exception_count++;
337
        caughtCxxException(LineInfo(stmt->lineno, stmt->col_offset, source->getFn(), source->getName()), &e);
338 339 340 341 342 343 344

        next_block = ((AST_Invoke*)stmt)->exc_dest;
        last_exception = e;
    }
    return nullptr;
}

345
Box* ASTInterpreter::executeInner(ASTInterpreter& interpreter, CFGBlock* start_block, AST_stmt* start_at) {
Marius Wachtler's avatar
Marius Wachtler committed
346
    Value v;
347

348 349
    bool from_start = start_block == NULL && start_at == NULL;

350 351 352 353 354 355
    assert((start_block == NULL) == (start_at == NULL));
    if (start_block == NULL) {
        start_block = interpreter.source_info->cfg->getStartingBlock();
        start_at = start_block->body[0];
    }

356 357 358 359 360
    // Important that this happens after RegisterHelper:
    interpreter.current_inst = start_at;
    threading::allowGLReadPreemption();
    interpreter.current_inst = NULL;

361 362 363 364 365 366 367 368 369 370 371 372
    if (!from_start) {
        interpreter.current_block = start_block;
        bool started = false;
        for (auto s : start_block->body) {
            if (!started) {
                if (s != start_at)
                    continue;
                started = true;
            }

            interpreter.current_inst = s;
            v = interpreter.visit_stmt(s);
373
        }
374 375
    } else {
        interpreter.next_block = start_block;
376 377
    }

378 379 380
    if (ENABLE_BASELINEJIT && interpreter.clfunc->times_interpreted >= REOPT_THRESHOLD_INTERPRETER)
        interpreter.should_jit = true;

381 382 383 384
    while (interpreter.next_block) {
        interpreter.current_block = interpreter.next_block;
        interpreter.next_block = 0;

385 386 387
        if (ENABLE_BASELINEJIT && !interpreter.jit) {
            CFGBlock* b = interpreter.current_block;
            if (b->entry_code) {
388 389 390
                Box* rtn = interpreter.execJITedBlock(b);
                if (interpreter.next_block)
                    continue;
391
                return rtn;
392 393 394
            }
        }

395
        if (ENABLE_BASELINEJIT && interpreter.should_jit && !interpreter.jit) {
396 397 398 399
            assert(!interpreter.current_block->code);
            interpreter.startJITing(interpreter.current_block);
        }

400 401
        for (AST_stmt* s : interpreter.current_block->body) {
            interpreter.current_inst = s;
402 403
            if (interpreter.jit)
                interpreter.jit->emitSetCurrentInst(s);
404
            v = interpreter.visit_stmt(s);
Marius Wachtler's avatar
Marius Wachtler committed
405 406
        }
    }
407
    return v.o;
Marius Wachtler's avatar
Marius Wachtler committed
408 409
}

410
Box* ASTInterpreter::execute(ASTInterpreter& interpreter, CFGBlock* start_block, AST_stmt* start_at) {
411
    UNAVOIDABLE_STAT_TIMER(t0, "us_timer_in_interpreter");
412

413 414 415 416 417 418 419 420 421 422
    // Note: due to some (avoidable) restrictions, this check is pretty constrained in where
    // it can go, due to the fact that it can throw an exception.
    // It can't go in the ASTInterpreter constructor, since that will cause the C++ runtime to
    // delete the partially-constructed memory which we don't currently handle.  It can't go into
    // executeInner since we want the SyntaxErrors to happen *before* the stack frame is entered.
    // (For instance, throwing the exception will try to fetch the current statement, but we determine
    // that by looking at the cfg.)
    if (!interpreter.source_info->cfg)
        interpreter.source_info->cfg = computeCFG(interpreter.source_info, interpreter.source_info->body);

423
    return executeInnerAndSetupFrame(interpreter, start_block, start_at);
424 425
}

426
Value ASTInterpreter::doBinOp(Value left, Value right, int op, BinExpType exp_type) {
Marius Wachtler's avatar
Marius Wachtler committed
427 428
    switch (exp_type) {
        case BinExpType::AugBinOp:
429
            return Value(augbinop(left.o, right.o, op), jit ? jit->emitAugbinop(left, right, op) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
430
        case BinExpType::BinOp:
431
            return Value(binop(left.o, right.o, op), jit ? jit->emitBinop(left, right, op) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
432
        case BinExpType::Compare:
433
            return Value(compare(left.o, right.o, op), jit ? jit->emitCompare(left, right, op) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
434 435 436 437 438 439
        default:
            RELEASE_ASSERT(0, "not implemented");
    }
    return Value();
}

440 441 442 443 444 445
void ASTInterpreter::doStore(AST_Name* node, Value value) {
    if (node->lookup_type == ScopeInfo::VarScopeType::UNKNOWN)
        node->lookup_type = scope_info->getScopeTypeOfName(node->id);

    InternedString name = node->id;
    ScopeInfo::VarScopeType vst = node->lookup_type;
Travis Hance's avatar
exec  
Travis Hance committed
446
    if (vst == ScopeInfo::VarScopeType::GLOBAL) {
447 448
        if (jit)
            jit->emitSetGlobal(globals, name.getBox(), value);
449
        setGlobal(globals, name.getBox(), value.o);
Travis Hance's avatar
exec  
Travis Hance committed
450
    } else if (vst == ScopeInfo::VarScopeType::NAME) {
451 452
        if (jit)
            jit->emitSetItemName(name.getBox(), value);
Travis Hance's avatar
exec  
Travis Hance committed
453 454
        assert(frame_info.boxedLocals != NULL);
        // TODO should probably pre-box the names when it's a scope that usesNameLookup
455
        assert(gc::isValidGCObject(value.o));
456
        setitem(frame_info.boxedLocals, name.getBox(), value.o);
Marius Wachtler's avatar
Marius Wachtler committed
457
    } else {
458 459 460 461 462
        bool closure = vst == ScopeInfo::VarScopeType::CLOSURE;
        if (jit) {
            if (!closure) {
                bool is_live = source_info->getLiveness()->isLiveAtEnd(name, current_block);
                if (is_live)
463
                    jit->emitSetLocal(name, node->vreg, closure, value);
464 465 466
                else
                    jit->emitSetBlockLocal(name, value);
            } else
467
                jit->emitSetLocal(name, node->vreg, closure, value);
468 469
        }

470 471 472 473
        assert(getSymVRegMap().count(name));
        assert(getSymVRegMap()[name] == node->vreg);
        vregs[node->vreg] = value.o;

474
        if (closure) {
Travis Hance's avatar
Travis Hance committed
475 476
            created_closure->elts[scope_info->getClosureOffset(name)] = value.o;
        }
Marius Wachtler's avatar
Marius Wachtler committed
477 478 479 480 481 482
    }
}

void ASTInterpreter::doStore(AST_expr* node, Value value) {
    if (node->type == AST_TYPE::Name) {
        AST_Name* name = (AST_Name*)node;
483
        doStore(name, value);
Marius Wachtler's avatar
Marius Wachtler committed
484 485
    } else if (node->type == AST_TYPE::Attribute) {
        AST_Attribute* attr = (AST_Attribute*)node;
486 487 488 489
        Value o = visit_expr(attr->value);
        if (jit)
            jit->emitSetAttr(o, attr->attr.getBox(), value);
        pyston::setattr(o.o, attr->attr.getBox(), value.o);
Marius Wachtler's avatar
Marius Wachtler committed
490 491 492
    } else if (node->type == AST_TYPE::Tuple) {
        AST_Tuple* tuple = (AST_Tuple*)node;
        Box** array = unpackIntoArray(value.o, tuple->elts.size());
493 494 495 496 497

        RewriterVar* array_var = NULL;
        if (jit)
            array_var = jit->emitUnpackIntoArray(value, tuple->elts.size());

Marius Wachtler's avatar
Marius Wachtler committed
498
        unsigned i = 0;
499 500 501 502
        for (AST_expr* e : tuple->elts) {
            doStore(e, Value(array[i], jit ? array_var->getAttr(i * sizeof(void*)) : NULL));
            ++i;
        }
Marius Wachtler's avatar
Marius Wachtler committed
503 504 505
    } else if (node->type == AST_TYPE::List) {
        AST_List* list = (AST_List*)node;
        Box** array = unpackIntoArray(value.o, list->elts.size());
506 507 508 509 510

        RewriterVar* array_var = NULL;
        if (jit)
            array_var = jit->emitUnpackIntoArray(value, list->elts.size());

Marius Wachtler's avatar
Marius Wachtler committed
511
        unsigned i = 0;
512 513 514 515
        for (AST_expr* e : list->elts) {
            doStore(e, Value(array[i], jit ? array_var->getAttr(i * sizeof(void*)) : NULL));
            ++i;
        }
Marius Wachtler's avatar
Marius Wachtler committed
516 517 518 519
    } else if (node->type == AST_TYPE::Subscript) {
        AST_Subscript* subscript = (AST_Subscript*)node;

        Value target = visit_expr(subscript->value);
520
        Value slice = visit_slice(subscript->slice);
Marius Wachtler's avatar
Marius Wachtler committed
521

522 523
        if (jit)
            jit->emitSetItem(target, slice, value);
Marius Wachtler's avatar
Marius Wachtler committed
524 525 526 527 528 529
        setitem(target.o, slice.o, value.o);
    } else {
        RELEASE_ASSERT(0, "not implemented");
    }
}

530 531 532 533
Value ASTInterpreter::getNone() {
    return Value(None, jit ? jit->imm(None) : NULL);
}

Marius Wachtler's avatar
Marius Wachtler committed
534 535 536
Value ASTInterpreter::visit_unaryop(AST_UnaryOp* node) {
    Value operand = visit_expr(node->operand);
    if (node->op_type == AST_TYPE::Not)
537
        return Value(boxBool(!nonzero(operand.o)), jit ? jit->emitNotNonzero(operand) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
538
    else
539
        return Value(unaryop(operand.o, node->op_type), jit ? jit->emitUnaryop(operand, node->op_type) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
540 541 542 543 544
}

Value ASTInterpreter::visit_binop(AST_BinOp* node) {
    Value left = visit_expr(node->left);
    Value right = visit_expr(node->right);
545
    return doBinOp(left, right, node->op_type, BinExpType::BinOp);
Marius Wachtler's avatar
Marius Wachtler committed
546 547
}

548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564
Value ASTInterpreter::visit_slice(AST_slice* node) {
    switch (node->type) {
        case AST_TYPE::ExtSlice:
            return visit_extslice(static_cast<AST_ExtSlice*>(node));
        case AST_TYPE::Ellipsis:
            RELEASE_ASSERT(0, "not implemented");
            break;
        case AST_TYPE::Index:
            return visit_index(static_cast<AST_Index*>(node));
        case AST_TYPE::Slice:
            return visit_slice(static_cast<AST_Slice*>(node));
        default:
            RELEASE_ASSERT(0, "Attempt to handle invalid slice type");
    }
    return Value();
}

Marius Wachtler's avatar
Marius Wachtler committed
565
Value ASTInterpreter::visit_slice(AST_Slice* node) {
566 567 568 569 570 571 572 573 574
    Value lower = node->lower ? visit_expr(node->lower) : getNone();
    Value upper = node->upper ? visit_expr(node->upper) : getNone();
    Value step = node->step ? visit_expr(node->step) : getNone();

    Value v;
    if (jit)
        v.var = jit->emitCreateSlice(lower, upper, step);
    v.o = createSlice(lower.o, upper.o, step.o);
    return v;
Marius Wachtler's avatar
Marius Wachtler committed
575 576
}

577
Value ASTInterpreter::visit_extslice(AST_ExtSlice* node) {
578 579
    llvm::SmallVector<RewriterVar*, 8> items;

580 581
    int num_slices = node->dims.size();
    BoxedTuple* rtn = BoxedTuple::create(num_slices);
582
    for (int i = 0; i < num_slices; ++i) {
583
        Value v = visit_slice(node->dims[i]);
584 585 586 587 588
        rtn->elts[i] = v.o;
        items.push_back(v);
    }

    return Value(rtn, jit ? jit->emitCreateTuple(items) : NULL);
589 590
}

Marius Wachtler's avatar
Marius Wachtler committed
591
Value ASTInterpreter::visit_branch(AST_Branch* node) {
592
    Value v = visit_expr(node->test);
593
    ASSERT(v.o == True || v.o == False, "Should have called NONZERO before this branch");
594

595 596 597
    if (jit)
        jit->emitSideExit(v, v.o, v.o == True ? node->iffalse : node->iftrue);

598
    if (v.o == True)
Marius Wachtler's avatar
Marius Wachtler committed
599 600 601
        next_block = node->iftrue;
    else
        next_block = node->iffalse;
602 603 604 605 606 607

    if (jit) {
        jit->emitJump(next_block);
        finishJITing(next_block);
    }

Marius Wachtler's avatar
Marius Wachtler committed
608 609 610 611
    return Value();
}

Value ASTInterpreter::visit_jump(AST_Jump* node) {
612
    bool backedge = node->target->idx < current_block->idx;
613
    if (backedge) {
614 615
        threading::allowGLReadPreemption();

616 617 618
        if (jit)
            jit->call(false, (void*)threading::allowGLReadPreemption);
    }
Marius Wachtler's avatar
Marius Wachtler committed
619

620 621 622 623 624
    if (jit) {
        if (backedge)
            jit->emitOSRPoint(node);
        jit->emitJump(node->target);
        finishJITing(node->target);
625 626 627 628 629

        // we may have started JITing because the OSR thresholds got triggered in this case we don't want to jit
        // additional blocks ouside of the loop if the function is cold.
        if (clfunc->times_interpreted < REOPT_THRESHOLD_INTERPRETER)
            should_jit = false;
630
    }
631

632 633
    if (backedge)
        ++edgecount;
Marius Wachtler's avatar
Marius Wachtler committed
634

635 636
    if (ENABLE_BASELINEJIT && backedge && edgecount == OSR_THRESHOLD_INTERPRETER && !jit && !node->target->code) {
        should_jit = true;
637
        startJITing(node->target);
638
    }
639

640 641 642 643 644
    if (backedge && edgecount == OSR_THRESHOLD_BASELINE) {
        Box* rtn = doOSR(node);
        if (rtn)
            return Value(rtn, NULL);
    }
645

646 647 648
    next_block = node->target;
    return Value();
}
649

650 651 652 653
Box* ASTInterpreter::doOSR(AST_Jump* node) {
    bool can_osr = ENABLE_OSR && !FORCE_INTERPRETER && source_info->scoping->areGlobalsFromModule();
    if (!can_osr)
        return NULL;
654

655 656
    static StatCounter ast_osrs("num_ast_osrs");
    ast_osrs.log();
657

658 659
    LivenessAnalysis* liveness = source_info->getLiveness();
    std::unique_ptr<PhiAnalysis> phis
660
        = computeRequiredPhis(clfunc->param_names, source_info->cfg, liveness, scope_info);
661

662 663 664 665 666
    llvm::DenseMap<int, InternedString> offset_name_map;
    for (auto&& v : getSymVRegMap()) {
        offset_name_map[v.second] = v.first;
    }

667
    std::vector<InternedString> dead_symbols;
668 669 670 671 672
    for (int i = 0; i < getSymVRegMap().size(); ++i) {
        if (!liveness->isLiveAtEnd(offset_name_map[i], current_block)) {
            dead_symbols.push_back(offset_name_map[i]);
        } else if (phis->isRequiredAfter(offset_name_map[i], current_block)) {
            assert(scope_info->getScopeTypeOfName(offset_name_map[i]) != ScopeInfo::VarScopeType::GLOBAL);
673 674 675
        } else {
        }
    }
676 677 678 679
    for (auto&& dead : dead_symbols) {
        assert(getSymVRegMap().count(dead));
        vregs[getSymVRegMap()[dead]] = NULL;
    }
Marius Wachtler's avatar
Marius Wachtler committed
680

681
    const OSREntryDescriptor* found_entry = nullptr;
682
    for (auto& p : clfunc->osr_versions) {
683 684
        if (p.first->backedge != node)
            continue;
Travis Hance's avatar
exec  
Travis Hance committed
685

686 687
        found_entry = p.first;
    }
688

689
    std::map<InternedString, Box*> sorted_symbol_table;
690

691 692 693
    // TODO: maybe use a different placeholder?
    static Box* const VAL_UNDEFINED = (Box*)-1;

694
    for (auto& name : phis->definedness.getDefinedNamesAtEnd(current_block)) {
695 696
        assert(getSymVRegMap().count(name));
        Box* val = vregs[getSymVRegMap()[name]];
697 698
        if (!liveness->isLiveAtEnd(name, current_block))
            continue;
699

700
        if (phis->isPotentiallyUndefinedAfter(name, current_block)) {
701
            bool is_defined = val != NULL;
702 703
            // TODO only mangle once
            sorted_symbol_table[getIsDefinedName(name, source_info->getInternedStrings())] = (Box*)is_defined;
704
            sorted_symbol_table[name] = is_defined ? val : VAL_UNDEFINED;
705
        } else {
706 707
            ASSERT(val != NULL, "%s", name.c_str());
            Box* v = sorted_symbol_table[name] = val;
708
            assert(gc::isValidGCObject(v));
709 710
        }
    }
711

712 713
    // Manually free these here, since we might not return from this scope for a long time.
    phis.reset(nullptr);
Marius Wachtler's avatar
Marius Wachtler committed
714

715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734
    // LLVM has a limit on the number of operands a machine instruction can have (~255),
    // in order to not hit the limit with the patchpoints cancel OSR when we have a high number of symbols.
    if (sorted_symbol_table.size() > 225) {
        static StatCounter times_osr_cancel("num_osr_cancel_too_many_syms");
        times_osr_cancel.log();
        return nullptr;
    }

    if (generator)
        sorted_symbol_table[source_info->getInternedStrings().get(PASSED_GENERATOR_NAME)] = generator;

    if (passed_closure)
        sorted_symbol_table[source_info->getInternedStrings().get(PASSED_CLOSURE_NAME)] = passed_closure;

    if (created_closure)
        sorted_symbol_table[source_info->getInternedStrings().get(CREATED_CLOSURE_NAME)] = created_closure;

    sorted_symbol_table[source_info->getInternedStrings().get(FRAME_INFO_PTR_NAME)] = (Box*)&frame_info;

    if (found_entry == nullptr) {
735
        OSREntryDescriptor* entry = OSREntryDescriptor::create(clfunc, node, CXX);
736 737 738 739 740 741 742 743 744 745 746 747 748 749

        for (auto& it : sorted_symbol_table) {
            if (isIsDefinedName(it.first))
                entry->args[it.first] = BOOL;
            else if (it.first.s() == PASSED_GENERATOR_NAME)
                entry->args[it.first] = GENERATOR;
            else if (it.first.s() == PASSED_CLOSURE_NAME || it.first.s() == CREATED_CLOSURE_NAME)
                entry->args[it.first] = CLOSURE;
            else if (it.first.s() == FRAME_INFO_PTR_NAME)
                entry->args[it.first] = FRAME_INFO;
            else {
                assert(it.first.s()[0] != '!');
                entry->args[it.first] = UNKNOWN;
            }
Marius Wachtler's avatar
Marius Wachtler committed
750
        }
751 752

        found_entry = entry;
Marius Wachtler's avatar
Marius Wachtler committed
753 754
    }

755
    OSRExit exit(found_entry);
756 757 758 759 760 761 762 763

    std::vector<Box*, StlCompatAllocator<Box*>> arg_array;
    for (auto& it : sorted_symbol_table) {
        arg_array.push_back(it.second);
    }

    UNAVOIDABLE_STAT_TIMER(t0, "us_timer_in_jitted_code");
    CompiledFunction* partial_func = compilePartialFuncInternal(&exit);
764

765 766 767 768
    auto arg_tuple = getTupleFromArgsArray(&arg_array[0], arg_array.size());
    Box* r = partial_func->call(std::get<0>(arg_tuple), std::get<1>(arg_tuple), std::get<2>(arg_tuple),
                                std::get<3>(arg_tuple));

769 770 771 772 773 774 775 776
    if (partial_func->exception_style == CXX) {
        assert(r);
        return r;
    } else {
        if (!r)
            throwCAPIException();
        return r;
    }
Marius Wachtler's avatar
Marius Wachtler committed
777 778 779 780 781 782 783
}

Value ASTInterpreter::visit_invoke(AST_Invoke* node) {
    Value v;
    try {
        v = visit_stmt(node->stmt);
        next_block = node->normal_dest;
784 785 786 787 788

        if (jit) {
            jit->emitJump(next_block);
            finishJITing(next_block);
        }
789
    } catch (ExcInfo e) {
790
        abortJITing();
791

792
        auto source = getCL()->source.get();
793
        node->cxx_exception_count++;
794
        caughtCxxException(LineInfo(node->lineno, node->col_offset, source->getFn(), source->getName()), &e);
795

Marius Wachtler's avatar
Marius Wachtler committed
796
        next_block = node->exc_dest;
797
        last_exception = e;
Marius Wachtler's avatar
Marius Wachtler committed
798 799 800 801 802 803
    }

    return v;
}

Value ASTInterpreter::visit_clsAttribute(AST_ClsAttribute* node) {
804 805 806
    Value obj = visit_expr(node->value);
    BoxedString* attr = node->attr.getBox();
    return Value(getclsattr(obj.o, attr), jit ? jit->emitGetClsAttr(obj, attr) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
807 808 809 810 811 812 813
}

Value ASTInterpreter::visit_augBinOp(AST_AugBinOp* node) {
    assert(node->op_type != AST_TYPE::Is && node->op_type != AST_TYPE::IsNot && "not tested yet");

    Value left = visit_expr(node->left);
    Value right = visit_expr(node->right);
814
    return doBinOp(left, right, node->op_type, BinExpType::AugBinOp);
Marius Wachtler's avatar
Marius Wachtler committed
815 816 817 818 819 820
}

Value ASTInterpreter::visit_langPrimitive(AST_LangPrimitive* node) {
    Value v;
    if (node->opcode == AST_LangPrimitive::GET_ITER) {
        assert(node->args.size() == 1);
821 822
        Value val = visit_expr(node->args[0]);
        v = Value(getPystonIter(val.o), jit ? jit->emitGetPystonIter(val) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
823 824 825 826 827 828
    } else if (node->opcode == AST_LangPrimitive::IMPORT_FROM) {
        assert(node->args.size() == 2);
        assert(node->args[0]->type == AST_TYPE::Name);
        assert(node->args[1]->type == AST_TYPE::Str);

        Value module = visit_expr(node->args[0]);
829 830 831
        auto ast_str = ast_cast<AST_Str>(node->args[1]);
        assert(ast_str->str_type == AST_Str::STR);
        const std::string& name = ast_str->str_data;
Marius Wachtler's avatar
Marius Wachtler committed
832
        assert(name.size());
833 834 835 836
        BoxedString* name_boxed = source_info->parent_module->getStringConstant(name, true);
        if (jit)
            v.var = jit->emitImportFrom(module, name_boxed);
        v.o = importFrom(module.o, name_boxed);
Marius Wachtler's avatar
Marius Wachtler committed
837 838 839 840 841 842 843 844
    } else if (node->opcode == AST_LangPrimitive::IMPORT_NAME) {
        assert(node->args.size() == 3);
        assert(node->args[0]->type == AST_TYPE::Num);
        assert(static_cast<AST_Num*>(node->args[0])->num_type == AST_Num::INT);
        assert(node->args[2]->type == AST_TYPE::Str);

        int level = static_cast<AST_Num*>(node->args[0])->n_int;
        Value froms = visit_expr(node->args[1]);
845 846 847
        auto ast_str = ast_cast<AST_Str>(node->args[2]);
        assert(ast_str->str_type == AST_Str::STR);
        const std::string& module_name = ast_str->str_data;
848 849
        if (jit)
            v.var = jit->emitImportName(level, froms, module_name);
850
        v.o = import(level, froms.o, module_name);
Marius Wachtler's avatar
Marius Wachtler committed
851 852 853 854
    } else if (node->opcode == AST_LangPrimitive::IMPORT_STAR) {
        assert(node->args.size() == 1);
        assert(node->args[0]->type == AST_TYPE::Name);

855 856
        RELEASE_ASSERT(source_info->ast->type == AST_TYPE::Module || source_info->ast->type == AST_TYPE::Suite,
                       "import * not supported in functions");
Marius Wachtler's avatar
Marius Wachtler committed
857 858

        Value module = visit_expr(node->args[0]);
859
        v = Value(importStar(module.o, globals), jit ? jit->emitImportStar(module) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
860
    } else if (node->opcode == AST_LangPrimitive::NONE) {
861
        v = getNone();
Marius Wachtler's avatar
Marius Wachtler committed
862
    } else if (node->opcode == AST_LangPrimitive::LANDINGPAD) {
863 864 865 866
        assert(last_exception.type);
        Box* type = last_exception.type;
        Box* value = last_exception.value ? last_exception.value : None;
        Box* traceback = last_exception.traceback ? last_exception.traceback : None;
867
        v = Value(BoxedTuple::create({ type, value, traceback }), jit ? jit->emitLandingpad() : NULL);
868
        last_exception = ExcInfo(NULL, NULL, NULL);
869 870
    } else if (node->opcode == AST_LangPrimitive::CHECK_EXC_MATCH) {
        assert(node->args.size() == 2);
Marius Wachtler's avatar
Marius Wachtler committed
871 872
        Value obj = visit_expr(node->args[0]);
        Value cls = visit_expr(node->args[1]);
873
        v = Value(boxBool(exceptionMatches(obj.o, cls.o)), jit ? jit->emitExceptionMatches(obj, cls) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
874
    } else if (node->opcode == AST_LangPrimitive::LOCALS) {
Travis Hance's avatar
exec  
Travis Hance committed
875
        assert(frame_info.boxedLocals != NULL);
876
        v = Value(frame_info.boxedLocals, jit ? jit->emitGetBoxedLocals() : NULL);
877 878 879
    } else if (node->opcode == AST_LangPrimitive::NONZERO) {
        assert(node->args.size() == 1);
        Value obj = visit_expr(node->args[0]);
880
        v = Value(boxBool(nonzero(obj.o)), jit ? jit->emitNonzero(obj) : NULL);
881 882 883 884 885 886 887 888 889 890
    } else if (node->opcode == AST_LangPrimitive::SET_EXC_INFO) {
        assert(node->args.size() == 3);

        Value type = visit_expr(node->args[0]);
        assert(type.o);
        Value value = visit_expr(node->args[1]);
        assert(value.o);
        Value traceback = visit_expr(node->args[2]);
        assert(traceback.o);

891 892
        if (jit)
            jit->emitSetExcInfo(type, value, traceback);
893
        getFrameInfo()->exc = ExcInfo(type.o, value.o, traceback.o);
894
        v = getNone();
895 896
    } else if (node->opcode == AST_LangPrimitive::UNCACHE_EXC_INFO) {
        assert(node->args.empty());
897 898
        if (jit)
            jit->emitUncacheExcInfo();
899
        getFrameInfo()->exc = ExcInfo(NULL, NULL, NULL);
900
        v = getNone();
901 902 903
    } else if (node->opcode == AST_LangPrimitive::HASNEXT) {
        assert(node->args.size() == 1);
        Value obj = visit_expr(node->args[0]);
904
        v = Value(boxBool(hasnext(obj.o)), jit ? jit->emitHasnext(obj) : NULL);
905 906 907 908 909
    } else if (node->opcode == AST_LangPrimitive::PRINT_EXPR) {
        abortJITing();
        Value obj = visit_expr(node->args[0]);
        printExprHelper(obj.o);
        v = getNone();
Marius Wachtler's avatar
Marius Wachtler committed
910
    } else
911
        RELEASE_ASSERT(0, "unknown opcode %d", node->opcode);
Marius Wachtler's avatar
Marius Wachtler committed
912 913 914 915
    return v;
}

Value ASTInterpreter::visit_yield(AST_Yield* node) {
916
    Value value = node->value ? visit_expr(node->value) : getNone();
Marius Wachtler's avatar
Marius Wachtler committed
917
    assert(generator && generator->cls == generator_cls);
918 919

    return Value(yield(generator, value.o), jit ? jit->emitYield(value) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
920 921
}

Kevin Modzelewski's avatar
Kevin Modzelewski committed
922
Value ASTInterpreter::visit_stmt(AST_stmt* node) {
923 924 925 926
#if ENABLE_SAMPLING_PROFILER
    threading::allowGLReadPreemption();
#endif

927
    if (0) {
928
        printf("%20s % 2d ", source_info->getName()->c_str(), current_block->idx);
929 930 931 932
        print_ast(node);
        printf("\n");
    }

Marius Wachtler's avatar
Marius Wachtler committed
933 934 935 936 937 938 939
    switch (node->type) {
        case AST_TYPE::Assert:
            return visit_assert((AST_Assert*)node);
        case AST_TYPE::Assign:
            return visit_assign((AST_Assign*)node);
        case AST_TYPE::Delete:
            return visit_delete((AST_Delete*)node);
Travis Hance's avatar
exec  
Travis Hance committed
940 941
        case AST_TYPE::Exec:
            return visit_exec((AST_Exec*)node);
Marius Wachtler's avatar
Marius Wachtler committed
942
        case AST_TYPE::Expr:
943 944 945 946 947
            // docstrings are str constant expression statements.
            // ignore those while interpreting.
            if ((((AST_Expr*)node)->value)->type != AST_TYPE::Str)
                return visit_expr((AST_Expr*)node);
            break;
Marius Wachtler's avatar
Marius Wachtler committed
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972
        case AST_TYPE::Pass:
            return Value(); // nothing todo
        case AST_TYPE::Print:
            return visit_print((AST_Print*)node);
        case AST_TYPE::Raise:
            return visit_raise((AST_Raise*)node);
        case AST_TYPE::Return:
            return visit_return((AST_Return*)node);
        case AST_TYPE::Global:
            return visit_global((AST_Global*)node);

        // pseudo
        case AST_TYPE::Branch:
            return visit_branch((AST_Branch*)node);
        case AST_TYPE::Jump:
            return visit_jump((AST_Jump*)node);
        case AST_TYPE::Invoke:
            return visit_invoke((AST_Invoke*)node);
        default:
            RELEASE_ASSERT(0, "not implemented");
    };
    return Value();
}

Value ASTInterpreter::visit_return(AST_Return* node) {
973 974 975 976 977 978 979
    Value s = node->value ? visit_expr(node->value) : getNone();

    if (jit) {
        jit->emitReturn(s);
        finishJITing();
    }

Marius Wachtler's avatar
Marius Wachtler committed
980 981 982 983
    next_block = 0;
    return s;
}

984
Value ASTInterpreter::createFunction(AST* node, AST_arguments* args, const std::vector<AST_stmt*>& body) {
Marius Wachtler's avatar
Marius Wachtler committed
985 986
    CLFunction* cl = wrapFunction(node, args, body, source_info);

987
    std::vector<Box*, StlCompatAllocator<Box*>> defaults;
988 989 990 991 992 993 994 995 996 997 998

    RewriterVar* defaults_var = NULL;
    if (jit)
        defaults_var = args->defaults.size() ? jit->allocate(args->defaults.size()) : jit->imm(0ul);
    int i = 0;
    for (AST_expr* d : args->defaults) {
        Value v = visit_expr(d);
        defaults.push_back(v.o);
        if (jit)
            defaults_var->setAttr(i++ * sizeof(void*), v);
    }
Marius Wachtler's avatar
Marius Wachtler committed
999 1000
    defaults.push_back(0);

1001 1002 1003 1004 1005 1006 1007 1008
    // FIXME: Using initializer_list is pretty annoying since you're not supposed to create them:
    union {
        struct {
            Box** ptr;
            size_t s;
        } d;
        std::initializer_list<Box*> il = {};
    } u;
Marius Wachtler's avatar
Marius Wachtler committed
1009

1010 1011
    u.d.ptr = &defaults[0];
    u.d.s = defaults.size() - 1;
Marius Wachtler's avatar
Marius Wachtler committed
1012

1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
    bool takes_closure;
    // Optimization: when compiling a module, it's nice to not have to run analyses into the
    // entire module's source code.
    // If we call getScopeInfoForNode, that will trigger an analysis of that function tree,
    // but we're only using it here to figure out if that function takes a closure.
    // Top level functions never take a closure, so we can skip the analysis.
    if (source_info->ast->type == AST_TYPE::Module)
        takes_closure = false;
    else {
        takes_closure = source_info->scoping->getScopeInfoForNode(node)->takesClosure();
    }

Marius Wachtler's avatar
Marius Wachtler committed
1025
    BoxedClosure* closure = 0;
1026
    RewriterVar* closure_var = NULL;
1027
    if (takes_closure) {
Marius Wachtler's avatar
Marius Wachtler committed
1028 1029
        if (scope_info->createsClosure()) {
            closure = created_closure;
1030 1031
            if (jit)
                closure_var = jit->getInterp()->getAttr(offsetof(ASTInterpreter, created_closure));
Marius Wachtler's avatar
Marius Wachtler committed
1032 1033 1034
        } else {
            assert(scope_info->passesThroughClosure());
            closure = passed_closure;
1035 1036
            if (jit)
                closure_var = jit->getInterp()->getAttr(offsetof(ASTInterpreter, passed_closure));
Marius Wachtler's avatar
Marius Wachtler committed
1037 1038 1039
        }
        assert(closure);
    }
1040 1041

    Box* passed_globals = NULL;
1042 1043
    RewriterVar* passed_globals_var = NULL;
    if (!getCL()->source->scoping->areGlobalsFromModule()) {
1044
        passed_globals = globals;
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
        if (jit)
            passed_globals_var = jit->getInterp()->getAttr(offsetof(ASTInterpreter, globals));
    }

    Value rtn;
    if (jit) {
        if (!closure_var)
            closure_var = jit->imm(0ul);
        if (!passed_globals_var)
            passed_globals_var = jit->imm(0ul);
        rtn.var = jit->call(false, (void*)boxCLFunction, jit->imm(cl), closure_var, passed_globals_var, defaults_var,
                            jit->imm(args->defaults.size()));
    }

    rtn.o = boxCLFunction(cl, closure, passed_globals, u.il);

    return rtn;
Marius Wachtler's avatar
Marius Wachtler committed
1062 1063
}

1064 1065
Value ASTInterpreter::visit_makeFunction(AST_MakeFunction* mkfn) {
    AST_FunctionDef* node = mkfn->function_def;
Marius Wachtler's avatar
Marius Wachtler committed
1066 1067
    AST_arguments* args = node->args;

1068
    std::vector<Value, StlCompatAllocator<Value>> decorators;
Marius Wachtler's avatar
Marius Wachtler committed
1069
    for (AST_expr* d : node->decorator_list)
1070
        decorators.push_back(visit_expr(d));
Marius Wachtler's avatar
Marius Wachtler committed
1071

1072
    Value func = createFunction(node, args, node->body);
Marius Wachtler's avatar
Marius Wachtler committed
1073

1074 1075 1076 1077 1078 1079
    for (int i = decorators.size() - 1; i >= 0; i--) {
        if (jit)
            func.var = jit->emitRuntimeCall(NULL, decorators[i], ArgPassSpec(1), { func }, NULL);
        func.o = runtimeCall(decorators[i].o, ArgPassSpec(1), func.o, 0, 0, 0, 0);
    }
    return func;
Marius Wachtler's avatar
Marius Wachtler committed
1080 1081
}

1082
Value ASTInterpreter::visit_makeClass(AST_MakeClass* mkclass) {
1083
    abortJITing();
1084
    AST_ClassDef* node = mkclass->class_def;
Marius Wachtler's avatar
Marius Wachtler committed
1085 1086 1087
    ScopeInfo* scope_info = source_info->scoping->getScopeInfoForNode(node);
    assert(scope_info);

1088 1089 1090 1091 1092
    BoxedTuple* basesTuple = BoxedTuple::create(node->bases.size());
    int base_idx = 0;
    for (AST_expr* b : node->bases) {
        basesTuple->elts[base_idx++] = visit_expr(b).o;
    }
Marius Wachtler's avatar
Marius Wachtler committed
1093

1094
    std::vector<Box*, StlCompatAllocator<Box*>> decorators;
Marius Wachtler's avatar
Marius Wachtler committed
1095 1096 1097
    for (AST_expr* d : node->decorator_list)
        decorators.push_back(visit_expr(d).o);

1098 1099 1100 1101 1102 1103 1104 1105
    BoxedClosure* closure = NULL;
    if (scope_info->takesClosure()) {
        if (this->scope_info->passesThroughClosure())
            closure = passed_closure;
        else
            closure = created_closure;
        assert(closure);
    }
Marius Wachtler's avatar
Marius Wachtler committed
1106
    CLFunction* cl = wrapFunction(node, nullptr, node->body, source_info);
1107 1108

    Box* passed_globals = NULL;
1109
    if (!getCL()->source->scoping->areGlobalsFromModule())
1110
        passed_globals = globals;
1111
    Box* attrDict = runtimeCall(boxCLFunction(cl, closure, passed_globals, {}), ArgPassSpec(0), 0, 0, 0, 0, 0);
Marius Wachtler's avatar
Marius Wachtler committed
1112

1113
    Box* classobj = createUserClass(node->name.getBox(), basesTuple, attrDict);
Marius Wachtler's avatar
Marius Wachtler committed
1114 1115 1116 1117

    for (int i = decorators.size() - 1; i >= 0; i--)
        classobj = runtimeCall(decorators[i], ArgPassSpec(1), classobj, 0, 0, 0, 0);

1118
    return Value(classobj, NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1119 1120 1121 1122 1123 1124
}

Value ASTInterpreter::visit_raise(AST_Raise* node) {
    if (node->arg0 == NULL) {
        assert(!node->arg1);
        assert(!node->arg2);
1125 1126 1127 1128 1129 1130

        if (jit) {
            jit->emitRaise0();
            finishJITing();
        }

1131
        ASTInterpreterJitInterface::raise0Helper(this);
Marius Wachtler's avatar
Marius Wachtler committed
1132 1133
    }

1134 1135 1136 1137 1138 1139 1140 1141 1142 1143
    Value arg0 = node->arg0 ? visit_expr(node->arg0) : getNone();
    Value arg1 = node->arg1 ? visit_expr(node->arg1) : getNone();
    Value arg2 = node->arg2 ? visit_expr(node->arg2) : getNone();

    if (jit) {
        jit->emitRaise3(arg0, arg1, arg2);
        finishJITing();
    }

    raise3(arg0.o, arg1.o, arg2.o);
Marius Wachtler's avatar
Marius Wachtler committed
1144 1145 1146 1147
    return Value();
}

Value ASTInterpreter::visit_assert(AST_Assert* node) {
1148
    abortJITing();
1149 1150 1151
#ifndef NDEBUG
    // Currently we only generate "assert 0" statements
    Value v = visit_expr(node->test);
1152
    assert(v.o->cls == int_cls && static_cast<BoxedInt*>(v.o)->n == 0);
1153
#endif
1154

1155
    static BoxedString* AssertionError_str = internStringImmortal("AssertionError");
1156
    Box* assertion_type = getGlobal(globals, AssertionError_str);
1157
    assertFail(assertion_type, node->msg ? visit_expr(node->msg).o : 0);
1158

Marius Wachtler's avatar
Marius Wachtler committed
1159 1160 1161 1162
    return Value();
}

Value ASTInterpreter::visit_global(AST_Global* node) {
1163
#ifndef NDEBUG
1164
    for (auto name : node->names) {
1165
        assert(!getSymVRegMap().count(name));
1166
    }
1167
#endif
Marius Wachtler's avatar
Marius Wachtler committed
1168 1169 1170 1171 1172 1173 1174 1175 1176
    return Value();
}

Value ASTInterpreter::visit_delete(AST_Delete* node) {
    for (AST_expr* target_ : node->targets) {
        switch (target_->type) {
            case AST_TYPE::Subscript: {
                AST_Subscript* sub = (AST_Subscript*)target_;
                Value value = visit_expr(sub->value);
1177
                Value slice = visit_slice(sub->slice);
1178 1179
                if (jit)
                    jit->emitDelItem(value, slice);
Marius Wachtler's avatar
Marius Wachtler committed
1180 1181 1182 1183 1184
                delitem(value.o, slice.o);
                break;
            }
            case AST_TYPE::Attribute: {
                AST_Attribute* attr = (AST_Attribute*)target_;
1185 1186 1187 1188 1189
                Value target = visit_expr(attr->value);
                BoxedString* str = attr->attr.getBox();
                if (jit)
                    jit->emitDelAttr(target, str);
                delattr(target.o, str);
Marius Wachtler's avatar
Marius Wachtler committed
1190 1191 1192 1193
                break;
            }
            case AST_TYPE::Name: {
                AST_Name* target = (AST_Name*)target_;
1194 1195 1196
                if (target->lookup_type == ScopeInfo::VarScopeType::UNKNOWN)
                    target->lookup_type = scope_info->getScopeTypeOfName(target->id);
                ScopeInfo::VarScopeType vst = target->lookup_type;
Travis Hance's avatar
exec  
Travis Hance committed
1197
                if (vst == ScopeInfo::VarScopeType::GLOBAL) {
1198 1199
                    if (jit)
                        jit->emitDelGlobal(target->id.getBox());
1200
                    delGlobal(globals, target->id.getBox());
Marius Wachtler's avatar
Marius Wachtler committed
1201
                    continue;
Travis Hance's avatar
exec  
Travis Hance committed
1202
                } else if (vst == ScopeInfo::VarScopeType::NAME) {
1203 1204 1205
                    if (jit)
                        jit->emitDelName(target->id);
                    ASTInterpreterJitInterface::delNameHelper(this, target->id);
Travis Hance's avatar
exec  
Travis Hance committed
1206
                } else {
1207
                    abortJITing();
Travis Hance's avatar
exec  
Travis Hance committed
1208
                    assert(vst == ScopeInfo::VarScopeType::FAST);
Marius Wachtler's avatar
Marius Wachtler committed
1209

1210 1211 1212
                    assert(getSymVRegMap().count(target->id));
                    assert(getSymVRegMap()[target->id] == target->vreg);
                    if (vregs[target->vreg] == 0) {
Travis Hance's avatar
exec  
Travis Hance committed
1213 1214 1215
                        assertNameDefined(0, target->id.c_str(), NameError, true /* local_var_msg */);
                        return Value();
                    }
Marius Wachtler's avatar
Marius Wachtler committed
1216

1217
                    vregs[target->vreg] = NULL;
Marius Wachtler's avatar
Marius Wachtler committed
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229
                }
                break;
            }
            default:
                ASSERT(0, "Unsupported del target: %d", target_->type);
                abort();
        }
    }
    return Value();
}

Value ASTInterpreter::visit_assign(AST_Assign* node) {
1230 1231
    assert(node->targets.size() == 1 && "cfg should have lowered it to a single target");

Marius Wachtler's avatar
Marius Wachtler committed
1232 1233 1234 1235 1236 1237 1238
    Value v = visit_expr(node->value);
    for (AST_expr* e : node->targets)
        doStore(e, v);
    return Value();
}

Value ASTInterpreter::visit_print(AST_Print* node) {
1239 1240 1241
    assert(node->values.size() <= 1 && "cfg should have lowered it to 0 or 1 values");
    Value dest = node->dest ? visit_expr(node->dest) : Value();
    Value var = node->values.size() ? visit_expr(node->values[0]) : Value();
1242

1243 1244 1245 1246 1247 1248 1249
    if (jit)
        jit->emitPrint(dest, var, node->nl);

    if (node->dest)
        printHelper(dest.o, var.o, node->nl);
    else
        printHelper(getSysStdout(), var.o, node->nl);
Marius Wachtler's avatar
Marius Wachtler committed
1250 1251 1252 1253

    return Value();
}

Travis Hance's avatar
exec  
Travis Hance committed
1254 1255
Value ASTInterpreter::visit_exec(AST_Exec* node) {
    // TODO implement the locals and globals arguments
1256 1257 1258
    Value code = visit_expr(node->body);
    Value globals = node->globals == NULL ? Value() : visit_expr(node->globals);
    Value locals = node->locals == NULL ? Value() : visit_expr(node->locals);
1259

1260 1261 1262
    if (jit)
        jit->emitExec(code, globals, locals, this->source_info->future_flags);
    exec(code.o, globals.o, locals.o, this->source_info->future_flags);
Travis Hance's avatar
exec  
Travis Hance committed
1263 1264 1265 1266

    return Value();
}

Marius Wachtler's avatar
Marius Wachtler committed
1267 1268
Value ASTInterpreter::visit_compare(AST_Compare* node) {
    RELEASE_ASSERT(node->comparators.size() == 1, "not implemented");
1269 1270 1271
    Value left = visit_expr(node->left);
    Value right = visit_expr(node->comparators[0]);
    return doBinOp(left, right, node->ops[0], BinExpType::Compare);
Marius Wachtler's avatar
Marius Wachtler committed
1272 1273
}

Kevin Modzelewski's avatar
Kevin Modzelewski committed
1274
Value ASTInterpreter::visit_expr(AST_expr* node) {
Marius Wachtler's avatar
Marius Wachtler committed
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315
    switch (node->type) {
        case AST_TYPE::Attribute:
            return visit_attribute((AST_Attribute*)node);
        case AST_TYPE::BinOp:
            return visit_binop((AST_BinOp*)node);
        case AST_TYPE::Call:
            return visit_call((AST_Call*)node);
        case AST_TYPE::Compare:
            return visit_compare((AST_Compare*)node);
        case AST_TYPE::Dict:
            return visit_dict((AST_Dict*)node);
        case AST_TYPE::Lambda:
            return visit_lambda((AST_Lambda*)node);
        case AST_TYPE::List:
            return visit_list((AST_List*)node);
        case AST_TYPE::Name:
            return visit_name((AST_Name*)node);
        case AST_TYPE::Num:
            return visit_num((AST_Num*)node);
        case AST_TYPE::Repr:
            return visit_repr((AST_Repr*)node);
        case AST_TYPE::Set:
            return visit_set((AST_Set*)node);
        case AST_TYPE::Str:
            return visit_str((AST_Str*)node);
        case AST_TYPE::Subscript:
            return visit_subscript((AST_Subscript*)node);
        case AST_TYPE::Tuple:
            return visit_tuple((AST_Tuple*)node);
        case AST_TYPE::UnaryOp:
            return visit_unaryop((AST_UnaryOp*)node);
        case AST_TYPE::Yield:
            return visit_yield((AST_Yield*)node);

        // pseudo
        case AST_TYPE::AugBinOp:
            return visit_augBinOp((AST_AugBinOp*)node);
        case AST_TYPE::ClsAttribute:
            return visit_clsAttribute((AST_ClsAttribute*)node);
        case AST_TYPE::LangPrimitive:
            return visit_langPrimitive((AST_LangPrimitive*)node);
1316 1317 1318 1319
        case AST_TYPE::MakeClass:
            return visit_makeClass((AST_MakeClass*)node);
        case AST_TYPE::MakeFunction:
            return visit_makeFunction((AST_MakeFunction*)node);
Marius Wachtler's avatar
Marius Wachtler committed
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330
        default:
            RELEASE_ASSERT(0, "");
    };
    return Value();
}


Value ASTInterpreter::visit_call(AST_Call* node) {
    Value v;
    Value func;

1331
    InternedString attr;
Marius Wachtler's avatar
Marius Wachtler committed
1332 1333 1334 1335 1336 1337 1338 1339

    bool is_callattr = false;
    bool callattr_clsonly = false;
    if (node->func->type == AST_TYPE::Attribute) {
        is_callattr = true;
        callattr_clsonly = false;
        AST_Attribute* attr_ast = ast_cast<AST_Attribute>(node->func);
        func = visit_expr(attr_ast->value);
1340
        attr = attr_ast->attr;
Marius Wachtler's avatar
Marius Wachtler committed
1341 1342 1343 1344 1345
    } else if (node->func->type == AST_TYPE::ClsAttribute) {
        is_callattr = true;
        callattr_clsonly = true;
        AST_ClsAttribute* attr_ast = ast_cast<AST_ClsAttribute>(node->func);
        func = visit_expr(attr_ast->value);
1346 1347
        attr = attr_ast->attr;
    } else {
Marius Wachtler's avatar
Marius Wachtler committed
1348
        func = visit_expr(node->func);
1349
    }
Marius Wachtler's avatar
Marius Wachtler committed
1350

1351
    std::vector<Box*, StlCompatAllocator<Box*>> args;
1352 1353 1354 1355 1356 1357 1358 1359 1360 1361
    llvm::SmallVector<RewriterVar*, 8> args_vars;
    for (AST_expr* e : node->args) {
        Value v = visit_expr(e);
        args.push_back(v.o);
        args_vars.push_back(v);
    }

    std::vector<BoxedString*>* keyword_names = NULL;
    if (node->keywords.size())
        keyword_names = getKeywordNameStorage(node);
Marius Wachtler's avatar
Marius Wachtler committed
1362 1363

    for (AST_keyword* k : node->keywords) {
1364 1365 1366
        Value v = visit_expr(k->value);
        args.push_back(v.o);
        args_vars.push_back(v);
Marius Wachtler's avatar
Marius Wachtler committed
1367 1368
    }

1369 1370 1371 1372 1373
    if (node->starargs) {
        Value v = visit_expr(node->starargs);
        args.push_back(v.o);
        args_vars.push_back(v);
    }
Marius Wachtler's avatar
Marius Wachtler committed
1374

1375 1376 1377 1378 1379
    if (node->kwargs) {
        Value v = visit_expr(node->kwargs);
        args.push_back(v.o);
        args_vars.push_back(v);
    }
Marius Wachtler's avatar
Marius Wachtler committed
1380 1381 1382 1383

    ArgPassSpec argspec(node->args.size(), node->keywords.size(), node->starargs, node->kwargs);

    if (is_callattr) {
1384
        CallattrFlags callattr_flags{.cls_only = callattr_clsonly, .null_on_nonexistent = false, .argspec = argspec };
1385 1386

        if (jit)
1387
            v.var = jit->emitCallattr(node, func, attr.getBox(), callattr_flags, args_vars, keyword_names);
1388 1389 1390 1391 1392

        v.o = callattr(func.o, attr.getBox(), callattr_flags, args.size() > 0 ? args[0] : 0,
                       args.size() > 1 ? args[1] : 0, args.size() > 2 ? args[2] : 0, args.size() > 3 ? &args[3] : 0,
                       keyword_names);
        return v;
Marius Wachtler's avatar
Marius Wachtler committed
1393
    } else {
1394 1395 1396
        Value v;

        if (jit)
1397
            v.var = jit->emitRuntimeCall(node, func, argspec, args_vars, keyword_names);
1398 1399 1400 1401

        v.o = runtimeCall(func.o, argspec, args.size() > 0 ? args[0] : 0, args.size() > 1 ? args[1] : 0,
                          args.size() > 2 ? args[2] : 0, args.size() > 3 ? &args[3] : 0, keyword_names);
        return v;
Marius Wachtler's avatar
Marius Wachtler committed
1402 1403 1404 1405 1406 1407 1408 1409 1410
    }
}


Value ASTInterpreter::visit_expr(AST_Expr* node) {
    return visit_expr(node->value);
}

Value ASTInterpreter::visit_num(AST_Num* node) {
1411 1412
    Box* o = NULL;
    if (node->num_type == AST_Num::INT) {
1413
        o = parent_module->getIntConstant(node->n_int);
1414
    } else if (node->num_type == AST_Num::FLOAT) {
1415
        o = parent_module->getFloatConstant(node->n_float);
1416
    } else if (node->num_type == AST_Num::LONG) {
1417
        o = parent_module->getLongConstant(node->n_long);
1418
    } else if (node->num_type == AST_Num::COMPLEX) {
1419
        o = parent_module->getPureImaginaryConstant(node->n_float);
1420 1421 1422
    } else
        RELEASE_ASSERT(0, "not implemented");
    return Value(o, jit ? jit->imm(o) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1423 1424 1425 1426 1427 1428 1429
}

Value ASTInterpreter::visit_index(AST_Index* node) {
    return visit_expr(node->value);
}

Value ASTInterpreter::visit_repr(AST_Repr* node) {
1430 1431
    Value v = visit_expr(node->value);
    return Value(repr(v.o), jit ? jit->emitRepr(v) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1432 1433 1434 1435 1436 1437 1438
}

Value ASTInterpreter::visit_lambda(AST_Lambda* node) {
    AST_Return* expr = new AST_Return();
    expr->value = node->body;

    std::vector<AST_stmt*> body = { expr };
1439
    return createFunction(node, node->args, body);
Marius Wachtler's avatar
Marius Wachtler committed
1440 1441 1442 1443
}

Value ASTInterpreter::visit_dict(AST_Dict* node) {
    RELEASE_ASSERT(node->keys.size() == node->values.size(), "not implemented");
1444 1445 1446 1447

    llvm::SmallVector<RewriterVar*, 8> keys;
    llvm::SmallVector<RewriterVar*, 8> values;

Marius Wachtler's avatar
Marius Wachtler committed
1448 1449
    BoxedDict* dict = new BoxedDict();
    for (size_t i = 0; i < node->keys.size(); ++i) {
1450 1451 1452 1453 1454 1455
        Value v = visit_expr(node->values[i]);
        Value k = visit_expr(node->keys[i]);
        dict->d[k.o] = v.o;

        values.push_back(v);
        keys.push_back(k);
Marius Wachtler's avatar
Marius Wachtler committed
1456 1457
    }

1458
    return Value(dict, jit ? jit->emitCreateDict(keys, values) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1459 1460 1461
}

Value ASTInterpreter::visit_set(AST_Set* node) {
1462 1463
    llvm::SmallVector<RewriterVar*, 8> items;

Marius Wachtler's avatar
Marius Wachtler committed
1464
    BoxedSet::Set set;
1465 1466 1467 1468 1469
    for (AST_expr* e : node->elts) {
        Value v = visit_expr(e);
        set.insert(v.o);
        items.push_back(v);
    }
Marius Wachtler's avatar
Marius Wachtler committed
1470

1471
    return Value(new BoxedSet(std::move(set)), jit ? jit->emitCreateSet(items) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1472 1473 1474
}

Value ASTInterpreter::visit_str(AST_Str* node) {
1475
    Box* o = NULL;
1476
    if (node->str_type == AST_Str::STR) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1477
        o = parent_module->getStringConstant(node->str_data, true);
1478
    } else if (node->str_type == AST_Str::UNICODE) {
1479
        o = parent_module->getUnicodeConstant(node->str_data);
1480 1481 1482
    } else {
        RELEASE_ASSERT(0, "%d", node->str_type);
    }
1483
    return Value(o, jit ? jit->imm(o) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1484 1485 1486
}

Value ASTInterpreter::visit_name(AST_Name* node) {
Travis Hance's avatar
exec  
Travis Hance committed
1487 1488 1489
    if (node->lookup_type == ScopeInfo::VarScopeType::UNKNOWN) {
        node->lookup_type = scope_info->getScopeTypeOfName(node->id);
    }
Marius Wachtler's avatar
Marius Wachtler committed
1490

Travis Hance's avatar
exec  
Travis Hance committed
1491
    switch (node->lookup_type) {
1492 1493 1494 1495 1496 1497 1498 1499
        case ScopeInfo::VarScopeType::GLOBAL: {
            Value v;
            if (jit)
                v.var = jit->emitGetGlobal(globals, node->id.getBox());

            v.o = getGlobal(globals, node->id.getBox());
            return v;
        }
Travis Hance's avatar
Travis Hance committed
1500
        case ScopeInfo::VarScopeType::DEREF: {
1501 1502
            return Value(ASTInterpreterJitInterface::derefHelper(this, node->id),
                         jit ? jit->emitDeref(node->id) : NULL);
Travis Hance's avatar
Travis Hance committed
1503
        }
Travis Hance's avatar
exec  
Travis Hance committed
1504 1505
        case ScopeInfo::VarScopeType::FAST:
        case ScopeInfo::VarScopeType::CLOSURE: {
1506 1507 1508 1509 1510 1511 1512
            Value v;
            if (jit) {
                bool is_live = false;
                if (node->lookup_type == ScopeInfo::VarScopeType::FAST)
                    is_live = source_info->getLiveness()->isLiveAtEnd(node->id, current_block);

                if (is_live)
1513
                    v.var = jit->emitGetLocal(node->id, node->vreg);
1514
                else
1515
                    v.var = jit->emitGetBlockLocal(node->id, node->vreg);
1516
            }
1517

1518 1519 1520 1521 1522
            assert(node->vreg >= 0);
            assert(getSymVRegMap().count(node->id));
            assert(getSymVRegMap()[node->id] == node->vreg);
            Box* val = vregs[node->vreg];
            if (val) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1523
                ASSERT(gc::isValidGCObject(val), "%s is %p", node->id.c_str(), val);
1524 1525 1526 1527 1528 1529
                v.o = val;
                return v;
            }

            assertNameDefined(0, node->id.c_str(), UnboundLocalError, true);
            RELEASE_ASSERT(0, "should be unreachable");
1530
        }
Travis Hance's avatar
exec  
Travis Hance committed
1531
        case ScopeInfo::VarScopeType::NAME: {
1532 1533 1534 1535
            Value v;
            if (jit)
                v.var = jit->emitGetBoxedLocal(node->id.getBox());
            v.o = boxedLocalsGet(frame_info.boxedLocals, node->id.getBox(), globals);
1536
            assert(gc::isValidGCObject(v.o));
1537
            return v;
1538 1539 1540
        }
        default:
            abort();
Marius Wachtler's avatar
Marius Wachtler committed
1541 1542 1543 1544 1545
    }
}

Value ASTInterpreter::visit_subscript(AST_Subscript* node) {
    Value value = visit_expr(node->value);
1546
    Value slice = visit_slice(node->slice);
1547 1548

    return Value(getitem(value.o, slice.o), jit ? jit->emitGetItem(value, slice) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1549 1550 1551
}

Value ASTInterpreter::visit_list(AST_List* node) {
1552 1553
    llvm::SmallVector<RewriterVar*, 8> items;

Marius Wachtler's avatar
Marius Wachtler committed
1554 1555
    BoxedList* list = new BoxedList;
    list->ensure(node->elts.size());
1556 1557 1558 1559 1560 1561 1562
    for (AST_expr* e : node->elts) {
        Value v = visit_expr(e);
        items.push_back(v);
        listAppendInternal(list, v.o);
    }

    return Value(list, jit ? jit->emitCreateList(items) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1563 1564 1565
}

Value ASTInterpreter::visit_tuple(AST_Tuple* node) {
1566 1567
    llvm::SmallVector<RewriterVar*, 8> items;

1568 1569
    BoxedTuple* rtn = BoxedTuple::create(node->elts.size());
    int rtn_idx = 0;
1570 1571 1572 1573 1574 1575 1576
    for (AST_expr* e : node->elts) {
        Value v = visit_expr(e);
        rtn->elts[rtn_idx++] = v.o;
        items.push_back(v);
    }

    return Value(rtn, jit ? jit->emitCreateTuple(items) : NULL);
Marius Wachtler's avatar
Marius Wachtler committed
1577 1578 1579
}

Value ASTInterpreter::visit_attribute(AST_Attribute* node) {
1580
    Value v = visit_expr(node->value);
1581 1582
    return Value(pyston::getattr(v.o, node->attr.getBox()),
                 jit ? jit->emitGetAttr(v, node->attr.getBox(), node) : NULL);
1583 1584 1585 1586
}
}


1587 1588 1589 1590
int ASTInterpreterJitInterface::getBoxedLocalsOffset() {
    return offsetof(ASTInterpreter, frame_info.boxedLocals);
}

1591 1592 1593 1594 1595 1596 1597 1598
int ASTInterpreterJitInterface::getCurrentBlockOffset() {
    return offsetof(ASTInterpreter, current_block);
}

int ASTInterpreterJitInterface::getCurrentInstOffset() {
    return offsetof(ASTInterpreter, current_inst);
}

1599 1600 1601 1602 1603 1604 1605 1606
int ASTInterpreterJitInterface::getGeneratorOffset() {
    return offsetof(ASTInterpreter, generator);
}

int ASTInterpreterJitInterface::getGlobalsOffset() {
    return offsetof(ASTInterpreter, globals);
}

1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624
void ASTInterpreterJitInterface::delNameHelper(void* _interpreter, InternedString name) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    Box* boxed_locals = interpreter->frame_info.boxedLocals;
    assert(boxed_locals != NULL);
    if (boxed_locals->cls == dict_cls) {
        auto& d = static_cast<BoxedDict*>(boxed_locals)->d;
        auto it = d.find(name.getBox());
        if (it == d.end()) {
            assertNameDefined(0, name.c_str(), NameError, false /* local_var_msg */);
        }
        d.erase(it);
    } else if (boxed_locals->cls == attrwrapper_cls) {
        attrwrapperDel(boxed_locals, name);
    } else {
        RELEASE_ASSERT(0, "%s", boxed_locals->cls->tp_name);
    }
}

1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649
Box* ASTInterpreterJitInterface::derefHelper(void* _interpreter, InternedString s) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    DerefInfo deref_info = interpreter->scope_info->getDerefInfo(s);
    assert(interpreter->passed_closure);
    BoxedClosure* closure = interpreter->passed_closure;
    for (int i = 0; i < deref_info.num_parents_from_passed_closure; i++) {
        closure = closure->parent;
    }
    Box* val = closure->elts[deref_info.offset];
    if (val == NULL) {
        raiseExcHelper(NameError, "free variable '%s' referenced before assignment in enclosing scope", s.c_str());
    }
    return val;
}

Box* ASTInterpreterJitInterface::doOSRHelper(void* _interpreter, AST_Jump* node) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    ++interpreter->edgecount;
    if (interpreter->edgecount >= OSR_THRESHOLD_BASELINE)
        return interpreter->doOSR(node);
    return NULL;
}

Box* ASTInterpreterJitInterface::landingpadHelper(void* _interpreter) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
1650
    ExcInfo& last_exception = interpreter->last_exception;
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664
    Box* type = last_exception.type;
    Box* value = last_exception.value ? last_exception.value : None;
    Box* traceback = last_exception.traceback ? last_exception.traceback : None;
    Box* rtn = BoxedTuple::create({ type, value, traceback });
    last_exception = ExcInfo(NULL, NULL, NULL);
    return rtn;
}

Box* ASTInterpreterJitInterface::setExcInfoHelper(void* _interpreter, Box* type, Box* value, Box* traceback) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    interpreter->getFrameInfo()->exc = ExcInfo(type, value, traceback);
    return None;
}

1665
void ASTInterpreterJitInterface::setLocalClosureHelper(void* _interpreter, long vreg, InternedString id, Box* v) {
1666 1667 1668
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;

    assert(gc::isValidGCObject(v));
1669 1670 1671
    assert(interpreter->getSymVRegMap().count(id));
    assert(interpreter->getSymVRegMap()[id] == vreg);
    interpreter->vregs[vreg] = v;
1672
    interpreter->created_closure->elts[interpreter->scope_info->getClosureOffset(id)] = v;
Marius Wachtler's avatar
Marius Wachtler committed
1673
}
1674

1675 1676 1677 1678 1679 1680
Box* ASTInterpreterJitInterface::uncacheExcInfoHelper(void* _interpreter) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    interpreter->getFrameInfo()->exc = ExcInfo(NULL, NULL, NULL);
    return None;
}

1681 1682 1683 1684 1685
void ASTInterpreterJitInterface::raise0Helper(void* _interpreter) {
    ASTInterpreter* interpreter = (ASTInterpreter*)_interpreter;
    raise0(&interpreter->getFrameInfo()->exc);
}

1686
const void* interpreter_instr_addr = (void*)&executeInnerAndSetupFrame;
1687

1688 1689 1690 1691
// small wrapper around executeInner because we can not directly call the member function from asm.
extern "C" Box* executeInnerFromASM(ASTInterpreter& interpreter, CFGBlock* start_block, AST_stmt* start_at) {
    return ASTInterpreter::executeInner(interpreter, start_block, start_at);
}
1692

1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710
static int calculateNumVRegs(CLFunction* clfunc) {
    ScopeInfo* scope_info = clfunc->source->getScopeInfo();
    SourceInfo* source_info = clfunc->source.get();

    // Note: due to some (avoidable) restrictions, this check is pretty constrained in where
    // it can go, due to the fact that it can throw an exception.
    // It can't go in the ASTInterpreter constructor, since that will cause the C++ runtime to
    // delete the partially-constructed memory which we don't currently handle.  It can't go into
    // executeInner since we want the SyntaxErrors to happen *before* the stack frame is entered.
    // (For instance, throwing the exception will try to fetch the current statement, but we determine
    // that by looking at the cfg.)
    if (!source_info->cfg)
        source_info->cfg = computeCFG(source_info, source_info->body);

    source_info->cfg->assignVRegs(clfunc->param_names, scope_info);
    return source_info->cfg->sym_vreg_map.size();
}

1711
Box* astInterpretFunction(CLFunction* clfunc, int nargs, Box* closure, Box* generator, Box* globals, Box* arg1,
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1712
                          Box* arg2, Box* arg3, Box** args) {
1713
    UNAVOIDABLE_STAT_TIMER(t0, "us_timer_in_interpreter");
1714

1715 1716 1717
    SourceInfo* source_info = clfunc->source.get();

    assert((!globals) == source_info->scoping->areGlobalsFromModule());
1718
    bool can_reopt = ENABLE_REOPT && !FORCE_INTERPRETER && (globals == NULL);
1719 1720 1721 1722 1723

    // If the cfg hasn't been computed yet, just conservatively say that it will be a big function.
    // It shouldn't matter, since the cfg should only be NULL if this is the first execution of this
    // function.
    int num_blocks = source_info->cfg ? source_info->cfg->blocks.size() : 10000;
1724
    int threshold = num_blocks <= 20 ? (REOPT_THRESHOLD_BASELINE / 3) : REOPT_THRESHOLD_BASELINE;
1725
    if (unlikely(can_reopt && (FORCE_OPTIMIZE || !ENABLE_INTERPRETER || clfunc->times_interpreted > threshold))) {
1726
        assert(!globals);
1727 1728 1729 1730 1731 1732 1733 1734 1735 1736

        clfunc->times_interpreted = 0;

        EffortLevel new_effort = EffortLevel::MODERATE;
        if (FORCE_OPTIMIZE)
            new_effort = EffortLevel::MAXIMAL;

        std::vector<ConcreteCompilerType*> arg_types;
        for (int i = 0; i < nargs; i++) {
            Box* arg = getArg(i, arg1, arg2, arg3, args);
1737 1738

            assert(arg || i == clfunc->param_names.kwargsIndex()); // only builtin functions can pass NULL args
1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750

            // TODO: reenable argument-type specialization
            arg_types.push_back(UNKNOWN);
            // arg_types.push_back(typeFromClass(arg->cls));
        }
        FunctionSpecialization* spec = new FunctionSpecialization(UNKNOWN, arg_types);

        // this also pushes the new CompiledVersion to the back of the version list:
        CompiledFunction* optimized = compileFunction(clfunc, spec, new_effort, NULL);

        clfunc->dependent_interp_callsites.invalidateAll();

1751
        UNAVOIDABLE_STAT_TIMER(t0, "us_timer_in_jitted_code");
1752
        Box* r;
1753
        if (closure && generator)
1754 1755
            r = optimized->closure_generator_call((BoxedClosure*)closure, (BoxedGenerator*)generator, arg1, arg2, arg3,
                                                  args);
1756
        else if (closure)
1757
            r = optimized->closure_call((BoxedClosure*)closure, arg1, arg2, arg3, args);
1758
        else if (generator)
1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769
            r = optimized->generator_call((BoxedGenerator*)generator, arg1, arg2, arg3, args);
        else
            r = optimized->call(arg1, arg2, arg3, args);

        if (optimized->exception_style == CXX)
            return r;
        else {
            if (!r)
                throwCAPIException();
            return r;
        }
1770 1771
    }

1772 1773 1774 1775 1776 1777 1778
    Box** vregs = NULL;
    int num_vregs = calculateNumVRegs(clfunc);
    if (num_vregs > 0) {
        vregs = (Box**)alloca(sizeof(Box*) * num_vregs);
        memset(vregs, 0, sizeof(Box*) * num_vregs);
    }

1779
    ++clfunc->times_interpreted;
1780
    ASTInterpreter interpreter(clfunc, vregs);
Travis Hance's avatar
Travis Hance committed
1781

1782
    ScopeInfo* scope_info = clfunc->source->getScopeInfo();
1783

Travis Hance's avatar
Travis Hance committed
1784
    if (unlikely(scope_info->usesNameLookup())) {
1785
        interpreter.setBoxedLocals(new BoxedDict());
Travis Hance's avatar
exec  
Travis Hance committed
1786
    }
1787

1788
    assert((!globals) == clfunc->source->scoping->areGlobalsFromModule());
1789
    if (globals) {
1790
        interpreter.setGlobals(globals);
1791
    } else {
1792
        interpreter.setGlobals(source_info->parent_module);
1793
    }
Travis Hance's avatar
Travis Hance committed
1794

1795 1796 1797
    interpreter.initArguments(nargs, (BoxedClosure*)closure, (BoxedGenerator*)generator, arg1, arg2, arg3, args);
    Box* v = ASTInterpreter::execute(interpreter);
    return v ? v : None;
1798 1799
}

1800 1801
Box* astInterpretFunctionEval(CLFunction* clfunc, Box* globals, Box* boxedLocals) {
    ++clfunc->times_interpreted;
1802

1803 1804 1805 1806 1807 1808 1809 1810
    Box** vregs = NULL;
    int num_vregs = calculateNumVRegs(clfunc);
    if (num_vregs > 0) {
        vregs = (Box**)alloca(sizeof(Box*) * num_vregs);
        memset(vregs, 0, sizeof(Box*) * num_vregs);
    }

    ASTInterpreter interpreter(clfunc, vregs);
1811 1812
    interpreter.initArguments(0, NULL, NULL, NULL, NULL, NULL, NULL);
    interpreter.setBoxedLocals(boxedLocals);
Travis Hance's avatar
Travis Hance committed
1813

1814
    assert(!clfunc->source->scoping->areGlobalsFromModule());
1815
    assert(globals);
1816
    interpreter.setGlobals(globals);
1817

1818 1819
    Box* v = ASTInterpreter::execute(interpreter);
    return v ? v : None;
1820
}
1821

1822 1823
Box* astInterpretDeopt(CLFunction* clfunc, AST_expr* after_expr, AST_stmt* enclosing_stmt, Box* expr_val,
                       FrameStackState frame_state) {
1824
    RELEASE_ASSERT(0, "didn't check if this still works");
1825
    assert(clfunc);
1826
    assert(enclosing_stmt);
Travis Hance's avatar
exec  
Travis Hance committed
1827
    assert(frame_state.locals);
1828 1829 1830
    assert(after_expr);
    assert(expr_val);

1831
    SourceInfo* source_info = clfunc->source.get();
1832 1833 1834 1835 1836 1837 1838 1839 1840 1841

    Box** vregs = NULL;
    int num_vregs = calculateNumVRegs(clfunc);
    if (num_vregs > 0) {
        vregs = (Box**)alloca(sizeof(Box*) * num_vregs);
        memset(vregs, 0, sizeof(Box*) * num_vregs);
    }

    ASTInterpreter interpreter(clfunc, vregs);

1842
    assert(clfunc->source->scoping->areGlobalsFromModule());
1843
    interpreter.setGlobals(source_info->parent_module);
Travis Hance's avatar
Travis Hance committed
1844

1845
    for (const auto& p : *frame_state.locals) {
1846
        assert(p.first->cls == str_cls);
1847
        auto name = static_cast<BoxedString*>(p.first)->s();
Travis Hance's avatar
exec  
Travis Hance committed
1848
        if (name == PASSED_GENERATOR_NAME) {
1849
            interpreter.setGenerator(p.second);
Travis Hance's avatar
exec  
Travis Hance committed
1850
        } else if (name == PASSED_CLOSURE_NAME) {
1851
            interpreter.setPassedClosure(p.second);
Travis Hance's avatar
exec  
Travis Hance committed
1852
        } else if (name == CREATED_CLOSURE_NAME) {
1853
            interpreter.setCreatedClosure(p.second);
Travis Hance's avatar
exec  
Travis Hance committed
1854
        } else {
1855
            InternedString interned = clfunc->source->getInternedStrings().get(name);
1856
            interpreter.addSymbol(interned, p.second, false);
Travis Hance's avatar
exec  
Travis Hance committed
1857
        }
1858 1859
    }

1860
    interpreter.setFrameInfo(frame_state.frame_info);
Travis Hance's avatar
exec  
Travis Hance committed
1861

1862 1863 1864 1865 1866 1867 1868 1869 1870
    CFGBlock* start_block = NULL;
    AST_stmt* starting_statement = NULL;
    while (true) {
        if (enclosing_stmt->type == AST_TYPE::Assign) {
            auto asgn = ast_cast<AST_Assign>(enclosing_stmt);
            assert(asgn->value == after_expr);
            assert(asgn->targets.size() == 1);
            assert(asgn->targets[0]->type == AST_TYPE::Name);
            auto name = ast_cast<AST_Name>(asgn->targets[0]);
1871
            assert(name->id.s()[0] == '#');
1872
            interpreter.addSymbol(name->id, expr_val, true);
1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890
            break;
        } else if (enclosing_stmt->type == AST_TYPE::Expr) {
            auto expr = ast_cast<AST_Expr>(enclosing_stmt);
            assert(expr->value == after_expr);
            break;
        } else if (enclosing_stmt->type == AST_TYPE::Invoke) {
            auto invoke = ast_cast<AST_Invoke>(enclosing_stmt);
            start_block = invoke->normal_dest;
            starting_statement = start_block->body[0];
            enclosing_stmt = invoke->stmt;
        } else {
            RELEASE_ASSERT(0, "should not be able to reach here with anything other than an Assign (got %d)",
                           enclosing_stmt->type);
        }
    }

    if (start_block == NULL) {
        // TODO innefficient
1891
        for (auto block : clfunc->source->cfg->blocks) {
1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909
            int n = block->body.size();
            for (int i = 0; i < n; i++) {
                if (block->body[i] == enclosing_stmt) {
                    ASSERT(i + 1 < n, "how could we deopt from a non-invoke terminator?");
                    start_block = block;
                    starting_statement = block->body[i + 1];
                    break;
                }
            }

            if (start_block)
                break;
        }

        ASSERT(start_block, "was unable to find the starting block??");
        assert(starting_statement);
    }

1910 1911 1912
    Box* v = ASTInterpreter::execute(interpreter, start_block, starting_statement);
    return v ? v : None;
}
1913

1914 1915 1916 1917 1918 1919 1920
extern "C" void printExprHelper(Box* obj) {
    Box* displayhook = PySys_GetObject("displayhook");
    if (!displayhook)
        raiseExcHelper(RuntimeError, "lost sys.displayhook");
    runtimeCall(displayhook, ArgPassSpec(1), obj, 0, 0, 0, 0);
}

1921 1922 1923 1924
static ASTInterpreter* getInterpreterFromFramePtr(void* frame_ptr) {
    // This offsets have to match the layout inside executeInnerAndSetupFrame
    ASTInterpreter** ptr = (ASTInterpreter**)(((uint8_t*)frame_ptr) - 8);
    return *ptr;
1925 1926 1927
}

AST_stmt* getCurrentStatementForInterpretedFrame(void* frame_ptr) {
1928
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1929 1930 1931 1932
    assert(interpreter);
    return interpreter->getCurrentStatement();
}

1933
Box* getGlobalsForInterpretedFrame(void* frame_ptr) {
1934
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1935 1936 1937 1938
    assert(interpreter);
    return interpreter->getGlobals();
}

1939
CLFunction* getCLForInterpretedFrame(void* frame_ptr) {
1940
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1941
    assert(interpreter);
1942
    return interpreter->getCL();
1943 1944 1945
}

FrameInfo* getFrameInfoForInterpretedFrame(void* frame_ptr) {
1946
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1947 1948 1949 1950 1951
    assert(interpreter);
    return interpreter->getFrameInfo();
}

BoxedDict* localsForInterpretedFrame(void* frame_ptr, bool only_user_visible) {
1952
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1953 1954
    assert(interpreter);
    BoxedDict* rtn = new BoxedDict();
1955
    for (auto& l : interpreter->getSymVRegMap()) {
1956
        if (only_user_visible && (l.first.s()[0] == '!' || l.first.s()[0] == '#'))
1957 1958
            continue;

1959 1960 1961 1962 1963
        Box* val = interpreter->getVRegs()[l.second];
        if (val) {
            assert(gc::isValidGCObject(val));
            rtn->d[l.first.getBox()] = val;
        }
1964
    }
1965

1966 1967 1968
    return rtn;
}

1969
BoxedClosure* passedClosureForInterpretedFrame(void* frame_ptr) {
1970
    ASTInterpreter* interpreter = getInterpreterFromFramePtr(frame_ptr);
1971 1972 1973
    assert(interpreter);
    return interpreter->getPassedClosure();
}
1974
}