irgen.cpp 44.4 KB
Newer Older
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1
// Copyright (c) 2014 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 "codegen/irgen.h"

Kevin Modzelewski's avatar
Kevin Modzelewski committed
17 18 19
#include <cstdio>
#include <iostream>
#include <sstream>
20
#include <stdint.h>
Kevin Modzelewski's avatar
Kevin Modzelewski committed
21 22

#include "llvm/Analysis/Passes.h"
23
#include "llvm/IR/DIBuilder.h"
24
#include "llvm/IR/Module.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
25
#include "llvm/IR/Verifier.h"
26
#include "llvm/PassManager.h"
27 28
#include "llvm/Support/FileSystem.h"
#include "llvm/Target/TargetMachine.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
29 30 31
#include "llvm/Transforms/Instrumentation.h"
#include "llvm/Transforms/Scalar.h"

32 33 34
#include "analysis/function_analysis.h"
#include "analysis/scoping_analysis.h"
#include "analysis/type_analysis.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
35 36
#include "codegen/codegen.h"
#include "codegen/compvars.h"
37
#include "codegen/gcbuilder.h"
38
#include "codegen/irgen/irgenerator.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
39 40 41 42
#include "codegen/irgen/util.h"
#include "codegen/opt/escape_analysis.h"
#include "codegen/opt/inliner.h"
#include "codegen/opt/passes.h"
43 44 45 46 47 48 49 50
#include "codegen/osrentry.h"
#include "codegen/patchpoints.h"
#include "codegen/stackmaps.h"
#include "core/ast.h"
#include "core/cfg.h"
#include "core/options.h"
#include "core/stats.h"
#include "core/util.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
51
#include "runtime/objmodel.h"
52
#include "runtime/types.h"
53

Kevin Modzelewski's avatar
Kevin Modzelewski committed
54 55 56 57 58 59
namespace pyston {

typedef std::unordered_set<CFGBlock*> BlockSet;

// This is where you can add a hook for any instruction added through the IRBuilder.
// It's currently not doing any hooking; hopefully there's not too much overhead from this.
60 61
void MyInserter::InsertHelper(llvm::Instruction* I, const llvm::Twine& Name, llvm::BasicBlock* BB,
                              llvm::BasicBlock::iterator InsertPt) const {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
62 63 64
    llvm::IRBuilderDefaultInserter<true>::InsertHelper(I, Name, BB, InsertPt);
}

65
static void addIRDebugSymbols(llvm::Function* f) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
66 67 68 69 70 71 72 73 74 75
    llvm::legacy::PassManager mpm;

    llvm::error_code code = llvm::sys::fs::create_directory(".debug_ir", true);
    assert(!code);

    mpm.add(llvm::createDebugIRPass(false, false, ".debug_ir", f->getName()));

    mpm.run(*g.cur_module);
}

76
static void optimizeIR(llvm::Function* f, EffortLevel::EffortLevel effort) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
77 78 79 80 81 82 83 84 85
    // TODO maybe should do some simple passes (ex: gvn?) if effort level isn't maximal?
    // In general, this function needs a lot of tuning.
    if (effort < EffortLevel::MAXIMAL)
        return;

    Timer _t("optimizing");

    llvm::FunctionPassManager fpm(g.cur_module);

86 87
    // TODO: using this as a pass is a legacy cludge that shouldn't be necessary any more; can it be updated?
    fpm.add(new llvm::DataLayoutPass(*g.tm->getDataLayout()));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
88

89 90
    if (ENABLE_INLINING && effort >= EffortLevel::MAXIMAL)
        fpm.add(makeFPInliner(275));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
91 92 93 94 95 96 97 98 99
    fpm.add(llvm::createCFGSimplificationPass());

    fpm.add(llvm::createBasicAliasAnalysisPass());
    fpm.add(llvm::createTypeBasedAliasAnalysisPass());
    if (ENABLE_PYSTON_PASSES) {
        fpm.add(new EscapeAnalysis());
        fpm.add(createPystonAAPass());
    }

100 101
    if (ENABLE_PYSTON_PASSES)
        fpm.add(createMallocsNonNullPass());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117

    // TODO Find the right place for this pass (and ideally not duplicate it)
    if (ENABLE_PYSTON_PASSES) {
        fpm.add(llvm::createGVNPass());
        fpm.add(createConstClassesPass());
    }

    // TODO: find the right set of passes
    if (0) {
        // My original set of passes, that seem to get about 90% of the benefit:
        fpm.add(llvm::createInstructionCombiningPass());
        fpm.add(llvm::createReassociatePass());
        fpm.add(llvm::createGVNPass());
        fpm.add(llvm::createCFGSimplificationPass());
    } else {
        // copied + slightly modified from llvm/lib/Transforms/IPO/PassManagerBuilder.cpp::populateModulePassManager
118 119
        fpm.add(llvm::createEarlyCSEPass());                   // Catch trivial redundancies
        fpm.add(llvm::createJumpThreadingPass());              // Thread jumps.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
120
        fpm.add(llvm::createCorrelatedValuePropagationPass()); // Propagate conditionals
121 122 123 124 125 126 127 128
        fpm.add(llvm::createCFGSimplificationPass());          // Merge & remove BBs
        fpm.add(llvm::createInstructionCombiningPass());       // Combine silly seq's

        fpm.add(llvm::createTailCallEliminationPass()); // Eliminate tail calls
        fpm.add(llvm::createCFGSimplificationPass());   // Merge & remove BBs
        fpm.add(llvm::createReassociatePass());         // Reassociate expressions
        fpm.add(llvm::createLoopRotatePass());          // Rotate Loop
        fpm.add(llvm::createLICMPass());                // Hoist loop invariants
Kevin Modzelewski's avatar
Kevin Modzelewski committed
129 130
        fpm.add(llvm::createLoopUnswitchPass(true /*optimize_for_size*/));
        fpm.add(llvm::createInstructionCombiningPass());
131 132 133
        fpm.add(llvm::createIndVarSimplifyPass()); // Canonicalize indvars
        fpm.add(llvm::createLoopIdiomPass());      // Recognize idioms like memset.
        fpm.add(llvm::createLoopDeletionPass());   // Delete dead loops
Kevin Modzelewski's avatar
Kevin Modzelewski committed
134

135
        fpm.add(llvm::createLoopUnrollPass()); // Unroll small loops
Kevin Modzelewski's avatar
Kevin Modzelewski committed
136

137 138 139
        fpm.add(llvm::createGVNPass());       // Remove redundancies
        fpm.add(llvm::createMemCpyOptPass()); // Remove memcpy / form memset
        fpm.add(llvm::createSCCPPass());      // Constant prop with SCCP
Kevin Modzelewski's avatar
Kevin Modzelewski committed
140 141 142 143

        // Run instcombine after redundancy elimination to exploit opportunities
        // opened up by them.
        fpm.add(llvm::createInstructionCombiningPass());
144
        fpm.add(llvm::createJumpThreadingPass()); // Thread jumps
Kevin Modzelewski's avatar
Kevin Modzelewski committed
145
        fpm.add(llvm::createCorrelatedValuePropagationPass());
146
        fpm.add(llvm::createDeadStoreEliminationPass()); // Delete dead stores
Kevin Modzelewski's avatar
Kevin Modzelewski committed
147 148

        fpm.add(llvm::createLoopRerollPass());
149
        // fpm.add(llvm::createSLPVectorizerPass());   // Vectorize parallel scalar chains.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
150 151


152 153 154
        fpm.add(llvm::createAggressiveDCEPass());        // Delete dead instructions
        fpm.add(llvm::createCFGSimplificationPass());    // Merge & remove BBs
        fpm.add(llvm::createInstructionCombiningPass()); // Clean up after everything.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
155

156 157
        // fpm.add(llvm::createBarrierNoopPass());
        // fpm.add(llvm::createLoopVectorizePass(DisableUnrollLoops, LoopVectorize));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
158 159 160 161 162 163 164 165 166 167 168
        fpm.add(llvm::createInstructionCombiningPass());
        fpm.add(llvm::createCFGSimplificationPass());
    }

    // TODO Find the right place for this pass (and ideally not duplicate it)
    if (ENABLE_PYSTON_PASSES) {
        fpm.add(createConstClassesPass());
        fpm.add(llvm::createInstructionCombiningPass());
        fpm.add(llvm::createCFGSimplificationPass());
        fpm.add(createConstClassesPass());
        fpm.add(createDeadAllocsPass());
169 170 171 172
        // fpm.add(llvm::createSCCPPass());                  // Constant prop with SCCP
        // fpm.add(llvm::createEarlyCSEPass());              // Catch trivial redundancies
        // fpm.add(llvm::createInstructionCombiningPass());
        // fpm.add(llvm::createCFGSimplificationPass());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
173 174 175 176 177 178 179 180
    }

    fpm.doInitialization();

    for (int i = 0; i < MAX_OPT_ITERATIONS; i++) {
        bool changed = fpm.run(*f);

        if (!changed) {
181 182
            if (VERBOSITY("irgen"))
                printf("done after %d optimization iterations\n", i - 1);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
183 184 185 186 187 188 189 190
            break;
        }

        if (VERBOSITY("irgen") >= 1) {
            fprintf(stderr, "after optimization %d:\n", i);
            printf("\033[36m");
            fflush(stdout);
            dumpPrettyIR(f);
191 192
            // f->dump();
            // g.cur_module->dump();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
193 194 195 196 197 198 199 200 201 202
            printf("\033[0m");
            fflush(stdout);
        }
    }

    long us = _t.end();
    static StatCounter us_optimizing("us_compiling_optimizing");
    us_optimizing.log(us);
}

203
static bool compareBlockPairs(const std::pair<CFGBlock*, CFGBlock*>& p1, const std::pair<CFGBlock*, CFGBlock*>& p2) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
204 205 206
    return p1.first->idx < p2.first->idx;
}

207 208
static std::vector<std::pair<CFGBlock*, CFGBlock*> >
computeBlockTraversalOrder(const BlockSet& full_blocks, const BlockSet& partial_blocks, CFGBlock* start) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
209 210 211 212 213 214 215 216 217 218

    std::vector<std::pair<CFGBlock*, CFGBlock*> > rtn;
    std::unordered_set<CFGBlock*> in_queue;

    if (start) {
        assert(full_blocks.count(start));
        in_queue.insert(start);
        rtn.push_back(std::make_pair(start, (CFGBlock*)NULL));
    }

Kevin Modzelewski's avatar
Kevin Modzelewski committed
219 220 221
    for (CFGBlock* b : partial_blocks) {
        in_queue.insert(b);
        rtn.push_back(std::make_pair(b, (CFGBlock*)NULL));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
222 223 224 225 226 227 228 229 230 231 232 233 234
    }

    // It's important for debugging purposes that the order is deterministic, but the iteration
    // over the BlockSet is not:
    std::sort(rtn.begin(), rtn.end(), compareBlockPairs);

    int idx = 0;
    while (rtn.size() < full_blocks.size() + partial_blocks.size()) {
        // TODO: come up with an alternative algorithm that outputs
        // the blocks in "as close to in-order as possible".
        // Do this by iterating over all blocks and picking the smallest one
        // that has a predecessor in the list already.
        while (idx < rtn.size()) {
235
            CFGBlock* cur = rtn[idx].first;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
236 237

            for (int i = 0; i < cur->successors.size(); i++) {
238
                CFGBlock* b = cur->successors[i];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
239 240 241 242 243 244 245 246 247 248 249 250 251 252
                assert(full_blocks.count(b) || partial_blocks.count(b));
                if (in_queue.count(b))
                    continue;

                rtn.push_back(std::make_pair(b, cur));
                in_queue.insert(b);
            }

            idx++;
        }

        if (rtn.size() == full_blocks.size() + partial_blocks.size())
            break;

253
        CFGBlock* best = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
254
        for (CFGBlock* b : full_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
255 256 257 258 259 260 261 262 263 264 265 266
            if (in_queue.count(b))
                continue;

            // Avoid picking any blocks where we can't add an epilogue to the predecessors
            if (b->predecessors.size() == 1 && b->predecessors[0]->successors.size() > 1)
                continue;

            if (best == NULL || b->idx < best->idx)
                best = b;
        }
        assert(best != NULL);

267 268
        if (VERBOSITY("irgen") >= 1)
            printf("Giving up and adding block %d to the order\n", best->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
269 270 271 272 273 274 275 276
        in_queue.insert(best);
        rtn.push_back(std::make_pair(best, (CFGBlock*)NULL));
    }

    ASSERT(rtn.size() == full_blocks.size() + partial_blocks.size(), "%ld\n", rtn.size());
    return rtn;
}

277
static void emitBBs(IRGenState* irstate, const char* bb_type, GuardList& out_guards, const GuardList& in_guards,
278
                    TypeAnalysis* types, const OSREntryDescriptor* entry_descriptor, const BlockSet& full_blocks,
279 280
                    const BlockSet& partial_blocks) {
    SourceInfo* source = irstate->getSourceInfo();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
281
    EffortLevel::EffortLevel effort = irstate->getEffortLevel();
282 283 284
    CompiledFunction* cf = irstate->getCurFunction();
    ConcreteCompilerType* rtn_type = irstate->getReturnType();
    // llvm::MDNode* func_info = irstate->getFuncDbgInfo();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
285 286

    if (entry_descriptor != NULL)
287
        assert(full_blocks.count(source->cfg->getStartingBlock()) == 0);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
288 289

    // We need the entry blocks pre-allocated so that we can jump forward to them.
290 291
    std::unordered_map<CFGBlock*, llvm::BasicBlock*> llvm_entry_blocks;
    for (CFGBlock* block : source->cfg->blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
292
        if (partial_blocks.count(block) == 0 && full_blocks.count(block) == 0) {
293
            llvm_entry_blocks[block] = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
294 295 296 297
            continue;
        }

        char buf[40];
298 299
        snprintf(buf, 40, "%s_block%d", bb_type, block->idx);
        llvm_entry_blocks[block] = llvm::BasicBlock::Create(g.context, buf, irstate->getLLVMFunction());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
300 301
    }

302 303 304
    llvm::BasicBlock* osr_entry_block = NULL; // the function entry block, where we add the type guards
    llvm::BasicBlock* osr_unbox_block = NULL; // the block after type guards where we up/down-convert things
    ConcreteSymbolTable* osr_syms = NULL;     // syms after conversion
Kevin Modzelewski's avatar
Kevin Modzelewski committed
305
    if (entry_descriptor != NULL) {
306 307 308 309
        osr_unbox_block = llvm::BasicBlock::Create(g.context, "osr_unbox", irstate->getLLVMFunction(),
                                                   &irstate->getLLVMFunction()->getEntryBlock());
        osr_entry_block = llvm::BasicBlock::Create(g.context, "osr_entry", irstate->getLLVMFunction(),
                                                   &irstate->getLLVMFunction()->getEntryBlock());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
310 311 312
        assert(&irstate->getLLVMFunction()->getEntryBlock() == osr_entry_block);

        osr_syms = new ConcreteSymbolTable();
313 314
        SymbolTable* initial_syms = new SymbolTable();
        // llvm::BranchInst::Create(llvm_entry_blocks[entry_descriptor->backedge->target->idx], entry_block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
315

316 317 318 319
        llvm::BasicBlock* osr_entry_block_end = osr_entry_block;
        llvm::BasicBlock* osr_unbox_block_end = osr_unbox_block;
        std::unique_ptr<IREmitter> entry_emitter(createIREmitter(irstate, osr_entry_block_end));
        std::unique_ptr<IREmitter> unbox_emitter(createIREmitter(irstate, osr_unbox_block_end));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
320

321
        CFGBlock* target_block = entry_descriptor->backedge->target;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
322 323 324

        // Currently we AND all the type guards together and then do just a single jump;
        // guard_val is the current AND'd value, or NULL if there weren't any guards
325
        llvm::Value* guard_val = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
326 327

        std::vector<llvm::Value*> func_args;
328 329
        for (llvm::Function::arg_iterator AI = irstate->getLLVMFunction()->arg_begin();
             AI != irstate->getLLVMFunction()->arg_end(); AI++) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
330 331 332 333
            func_args.push_back(AI);
        }

        // Handle loading symbols from the passed osr arguments:
Kevin Modzelewski's avatar
Kevin Modzelewski committed
334
        int arg_num = -1;
335
        for (const auto& p : entry_descriptor->args) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
336
            llvm::Value* from_arg;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
337 338 339
            arg_num++;
            if (arg_num < 3) {
                from_arg = func_args[arg_num];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
340 341
            } else {
                ASSERT(func_args.size() == 4, "%ld", func_args.size());
342
                llvm::Value* ptr = entry_emitter->getBuilder()->CreateConstGEP1_32(func_args[3], arg_num - 3);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
343
                if (p.second == INT) {
344
                    ptr = entry_emitter->getBuilder()->CreateBitCast(ptr, g.i64->getPointerTo());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
345
                } else if (p.second == FLOAT) {
346
                    ptr = entry_emitter->getBuilder()->CreateBitCast(ptr, g.double_->getPointerTo());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
347
                }
348
                from_arg = entry_emitter->getBuilder()->CreateLoad(ptr);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
349
                assert(from_arg->getType() == p.second->llvmType());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
350 351
            }

352
            ConcreteCompilerType* phi_type;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
353
            if (startswith(p.first, "!is_defined"))
354 355
                phi_type = BOOL;
            else
Kevin Modzelewski's avatar
Kevin Modzelewski committed
356
                phi_type = types->getTypeAtBlockStart(p.first, target_block);
357 358
            // ConcreteCompilerType *analyzed_type = types->getTypeAtBlockStart(p.first, block);
            // ConcreteCompilerType *phi_type = (*phis)[p.first].first;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
359

360
            ConcreteCompilerVariable* var = new ConcreteCompilerVariable(p.second, from_arg, true);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
361
            (*initial_syms)[p.first] = var;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
362 363 364 365 366

            // It's possible to OSR into a version of the function with a higher speculation level;
            // this means that the types of the OSR variables are potentially higher (more unspecialized)
            // than what the optimized code expects.
            // So, we have to re-check the speculations and potentially deopt.
367
            llvm::Value* v = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
368
            if (p.second == phi_type) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
369 370
                // good to go
                v = from_arg;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
371
            } else if (p.second->canConvertTo(phi_type)) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
372 373
                // not sure if/when this happens, but if there's a type mismatch but one we know
                // can be handled (such as casting from a subclass to a superclass), handle it:
374
                ConcreteCompilerVariable* converted = var->makeConverted(*unbox_emitter, phi_type);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
375 376 377
                v = converted->getValue();
                delete converted;
            } else {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
378
                ASSERT(p.second == UNKNOWN, "%s", p.second->debugName().c_str());
379
                BoxedClass* speculated_class = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
380 381 382 383 384 385 386 387 388
                if (phi_type == INT) {
                    speculated_class = int_cls;
                } else if (phi_type == FLOAT) {
                    speculated_class = float_cls;
                } else {
                    speculated_class = phi_type->guaranteedClass();
                }
                ASSERT(speculated_class, "%s", phi_type->debugName().c_str());

389 390
                llvm::Value* type_check = ConcreteCompilerVariable(p.second, from_arg, true)
                                              .makeClassCheck(*entry_emitter, speculated_class);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
391
                if (guard_val) {
392
                    guard_val = entry_emitter->getBuilder()->CreateAnd(guard_val, type_check);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
393 394 395
                } else {
                    guard_val = type_check;
                }
396
                // entry_emitter->getBuilder()->CreateCall(g.funcs.my_assert, type_check);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
397 398

                if (speculated_class == int_cls) {
399 400
                    v = unbox_emitter->getBuilder()->CreateCall(g.funcs.unboxInt, from_arg);
                    (new ConcreteCompilerVariable(BOXED_INT, from_arg, true))->decvref(*unbox_emitter);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
401
                } else if (speculated_class == float_cls) {
402 403
                    v = unbox_emitter->getBuilder()->CreateCall(g.funcs.unboxFloat, from_arg);
                    (new ConcreteCompilerVariable(BOXED_FLOAT, from_arg, true))->decvref(*unbox_emitter);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
404 405 406 407 408 409
                } else {
                    assert(phi_type == typeFromClass(speculated_class));
                    v = from_arg;
                }
            }

410 411
            if (VERBOSITY("irgen"))
                v->setName("prev_" + p.first);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
412

Kevin Modzelewski's avatar
Kevin Modzelewski committed
413
            (*osr_syms)[p.first] = new ConcreteCompilerVariable(phi_type, v, true);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
414 415 416
        }

        if (guard_val) {
417 418 419 420 421
            // Create the guard with both branches leading to the success_bb,
            // and let the deopt path change the failure case to point to the
            // as-yet-unknown deopt block.
            // TODO Not the best approach since if we fail to do that patching,
            // the guard will just silently be ignored.
422 423
            llvm::BranchInst* br
                = entry_emitter->getBuilder()->CreateCondBr(guard_val, osr_unbox_block, osr_unbox_block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
424 425
            out_guards.registerGuardForBlockEntry(target_block, br, *initial_syms);
        } else {
426
            entry_emitter->getBuilder()->CreateBr(osr_unbox_block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
427
        }
428
        unbox_emitter->getBuilder()->CreateBr(llvm_entry_blocks[entry_descriptor->backedge->target]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
429

430
        for (const auto& p : *initial_syms) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
431
            delete p.second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
432 433 434 435 436 437 438 439
        }
        delete initial_syms;
    }

    // In a similar vein, we need to keep track of the exit blocks for each cfg block,
    // so that we can construct phi nodes later.
    // Originally I preallocated these blocks as well, but we can construct the phi's
    // after the fact, so we can just record the exit blocks as we go along.
440
    std::unordered_map<CFGBlock*, llvm::BasicBlock*> llvm_exit_blocks;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
441 442 443 444

    ////
    // Main ir generation: go through each basic block in the CFG and emit the code

445 446
    std::unordered_map<CFGBlock*, SymbolTable*> ending_symbol_tables;
    std::unordered_map<CFGBlock*, ConcreteSymbolTable*> phi_ending_symbol_tables;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
447
    typedef std::unordered_map<std::string, std::pair<ConcreteCompilerType*, llvm::PHINode*> > PHITable;
448
    std::unordered_map<CFGBlock*, PHITable*> created_phis;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
449 450 451 452

    CFGBlock* initial_block = NULL;
    if (entry_descriptor) {
        initial_block = entry_descriptor->backedge->target;
453 454
    } else if (full_blocks.count(source->cfg->getStartingBlock())) {
        initial_block = source->cfg->getStartingBlock();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
455 456 457 458 459 460 461 462 463
    }

    // The rest of this code assumes that for each non-entry block that gets evaluated,
    // at least one of its predecessors has been evaluated already (from which it will
    // get type information).
    // The cfg generation code will generate a cfg such that each block has a predecessor
    // with a lower index value, so if the entry block is 0 then we can iterate in index
    // order.
    // The entry block doesn't have to be zero, so we have to calculate an allowable order here:
464 465
    std::vector<std::pair<CFGBlock*, CFGBlock*> > traversal_order
        = computeBlockTraversalOrder(full_blocks, partial_blocks, initial_block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
466 467 468

    std::unordered_set<CFGBlock*> into_hax;
    for (int _i = 0; _i < traversal_order.size(); _i++) {
469 470
        CFGBlock* block = traversal_order[_i].first;
        CFGBlock* pred = traversal_order[_i].second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
471

472 473
        if (VERBOSITY("irgen") >= 1)
            printf("processing %s block %d\n", bb_type, block->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
474 475 476

        bool is_partial = false;
        if (partial_blocks.count(block)) {
477 478
            if (VERBOSITY("irgen") >= 1)
                printf("is partial block\n");
Kevin Modzelewski's avatar
Kevin Modzelewski committed
479 480
            is_partial = true;
        } else if (!full_blocks.count(block)) {
481 482 483 484 485 486
            if (VERBOSITY("irgen") >= 1)
                printf("Skipping this block\n");
            // created_phis[block] = NULL;
            // ending_symbol_tables[block] = NULL;
            // phi_ending_symbol_tables[block] = NULL;
            // llvm_exit_blocks[block] = NULL;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
487 488 489
            continue;
        }

490 491
        std::unique_ptr<IRGenerator> generator(
            createIRGenerator(irstate, llvm_entry_blocks, block, types, out_guards, in_guards, is_partial));
492 493
        llvm::BasicBlock* entry_block_end = llvm_entry_blocks[block];
        std::unique_ptr<IREmitter> emitter(createIREmitter(irstate, entry_block_end));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
494 495 496 497

        PHITable* phis = NULL;
        if (!is_partial) {
            phis = new PHITable();
498
            created_phis[block] = phis;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
499 500 501 502 503
        }

        // Set initial symbol table:
        if (is_partial) {
            // pass
504
        } else if (block == source->cfg->getStartingBlock()) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
505 506
            assert(entry_descriptor == NULL);
            // number of times a function needs to be called to be reoptimized:
Kevin Modzelewski's avatar
Kevin Modzelewski committed
507 508 509 510
            static const int REOPT_THRESHOLDS[] = {
                10,    // INTERPRETED->MINIMAL
                250,   // MINIMAL->MODERATE
                10000, // MODERATE->MAXIMAL
Kevin Modzelewski's avatar
Kevin Modzelewski committed
511 512 513 514
            };

            assert(strcmp("opt", bb_type) == 0);

Kevin Modzelewski's avatar
Kevin Modzelewski committed
515 516
            if (ENABLE_REOPT && effort < EffortLevel::MAXIMAL && source->ast != NULL
                && source->ast->type != AST_TYPE::Module) {
517 518 519
                llvm::BasicBlock* preentry_bb
                    = llvm::BasicBlock::Create(g.context, "pre_entry", irstate->getLLVMFunction(),
                                               llvm_entry_blocks[source->cfg->getStartingBlock()]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
520
                llvm::BasicBlock* reopt_bb = llvm::BasicBlock::Create(g.context, "reopt", irstate->getLLVMFunction());
521
                emitter->getBuilder()->SetInsertPoint(preentry_bb);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
522

523 524 525 526
                llvm::Value* call_count_ptr = embedConstantPtr(&cf->times_called, g.i64->getPointerTo());
                llvm::Value* cur_call_count = emitter->getBuilder()->CreateLoad(call_count_ptr);
                llvm::Value* new_call_count
                    = emitter->getBuilder()->CreateAdd(cur_call_count, getConstantInt(1, g.i64));
527
                emitter->getBuilder()->CreateStore(new_call_count, call_count_ptr);
528 529
                llvm::Value* reopt_test = emitter->getBuilder()->CreateICmpSGT(
                    new_call_count, getConstantInt(REOPT_THRESHOLDS[effort], g.i64));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
530

531 532
                llvm::Value* md_vals[]
                    = { llvm::MDString::get(g.context, "branch_weights"), getConstantInt(1), getConstantInt(1000) };
Kevin Modzelewski's avatar
Kevin Modzelewski committed
533 534
                llvm::MDNode* branch_weights = llvm::MDNode::get(g.context, llvm::ArrayRef<llvm::Value*>(md_vals));

535 536
                llvm::BranchInst* guard = emitter->getBuilder()->CreateCondBr(
                    reopt_test, reopt_bb, llvm_entry_blocks[source->cfg->getStartingBlock()], branch_weights);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
537

538
                emitter->getBuilder()->SetInsertPoint(reopt_bb);
539 540 541
                // emitter->getBuilder()->CreateCall(g.funcs.my_assert, getConstantInt(0, g.i1));
                llvm::Value* r = emitter->getBuilder()->CreateCall(g.funcs.reoptCompiledFunc,
                                                                   embedConstantPtr(cf, g.i8->getPointerTo()));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
542 543 544
                assert(r);
                assert(r->getType() == g.i8->getPointerTo());

545
                llvm::Value* bitcast_r = emitter->getBuilder()->CreateBitCast(r, irstate->getLLVMFunction()->getType());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
546 547

                std::vector<llvm::Value*> args;
548 549 550 551
                // bitcast_r->dump();
                for (llvm::Function::arg_iterator AI = irstate->getLLVMFunction()->arg_begin();
                     AI != irstate->getLLVMFunction()->arg_end(); AI++) {
                    // AI->dump();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
552 553
                    args.push_back(&(*AI));
                }
554 555
                // printf("%ld\n", args.size());
                llvm::CallInst* postcall = emitter->getBuilder()->CreateCall(bitcast_r, args);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
556 557
                postcall->setTailCall(true);
                if (rtn_type == VOID) {
558
                    emitter->getBuilder()->CreateRetVoid();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
559
                } else {
560
                    emitter->getBuilder()->CreateRet(postcall);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
561 562
                }

563
                emitter->getBuilder()->SetInsertPoint(llvm_entry_blocks[source->cfg->getStartingBlock()]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
564
            }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
565

566
            generator->doFunctionEntry(source->arg_names, cf->spec->arg_types);
567 568 569 570

            // Function-entry safepoint:
            // TODO might be more efficient to do post-call safepoints?
            generator->doSafePoint();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
571 572 573 574 575
        } else if (entry_descriptor && block == entry_descriptor->backedge->target) {
            assert(block->predecessors.size() > 1);
            assert(osr_entry_block);
            assert(phis);

576 577
            for (const auto& p : entry_descriptor->args) {
                ConcreteCompilerType* analyzed_type;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
578
                if (startswith(p.first, "!is_defined"))
579 580
                    analyzed_type = BOOL;
                else
Kevin Modzelewski's avatar
Kevin Modzelewski committed
581
                    analyzed_type = types->getTypeAtBlockStart(p.first, block);
582

583 584
                // printf("For %s, given %s, analyzed for %s\n", p.first.c_str(), p.second->debugName().c_str(),
                // analyzed_type->debugName().c_str());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
585

586 587 588
                llvm::PHINode* phi = emitter->getBuilder()->CreatePHI(analyzed_type->llvmType(),
                                                                      block->predecessors.size() + 1, p.first);
                ConcreteCompilerVariable* var = new ConcreteCompilerVariable(analyzed_type, phi, true);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
589 590
                generator->giveLocalSymbol(p.first, var);
                (*phis)[p.first] = std::make_pair(analyzed_type, phi);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
591 592 593 594 595 596
            }
        } else if (pred == NULL) {
            assert(traversal_order.size() < source->cfg->blocks.size());
            assert(phis);
            assert(block->predecessors.size());
            for (int i = 0; i < block->predecessors.size(); i++) {
597
                CFGBlock* b2 = block->predecessors[i];
598
                assert(ending_symbol_tables.count(b2) == 0);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
599 600 601
                into_hax.insert(b2);
            }

602 603
            const PhiAnalysis::RequiredSet& names = source->phis->getAllDefinedAt(block);
            for (const auto& s : names) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
604
                // TODO the list from getAllDefinedAt should come filtered:
Kevin Modzelewski's avatar
Kevin Modzelewski committed
605
                if (!source->liveness->isLiveAtEnd(s, block->predecessors[0]))
Kevin Modzelewski's avatar
Kevin Modzelewski committed
606 607
                    continue;

608 609 610 611
                // printf("adding guessed phi for %s\n", s.c_str());
                ConcreteCompilerType* type = types->getTypeAtBlockStart(s, block);
                llvm::PHINode* phi = emitter->getBuilder()->CreatePHI(type->llvmType(), block->predecessors.size(), s);
                ConcreteCompilerVariable* var = new ConcreteCompilerVariable(type, phi, true);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
612
                generator->giveLocalSymbol(s, var);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
613

Kevin Modzelewski's avatar
Kevin Modzelewski committed
614
                (*phis)[s] = std::make_pair(type, phi);
615

Kevin Modzelewski's avatar
Kevin Modzelewski committed
616 617
                if (source->phis->isPotentiallyUndefinedAfter(s, block->predecessors[0])) {
                    std::string is_defined_name = "!is_defined_" + s;
618 619 620
                    llvm::PHINode* phi
                        = emitter->getBuilder()->CreatePHI(g.i1, block->predecessors.size(), is_defined_name);
                    ConcreteCompilerVariable* var = new ConcreteCompilerVariable(BOOL, phi, true);
621 622 623 624
                    generator->giveLocalSymbol(is_defined_name, var);

                    (*phis)[is_defined_name] = std::make_pair(BOOL, phi);
                }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
625 626 627 628 629
            }
        } else {
            assert(pred);
            assert(full_blocks.count(pred) || partial_blocks.count(pred));

630
            if (block->predecessors.size() == 1) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
631 632
                // If this block has only one predecessor, it by definition doesn't need any phi nodes.
                // Assert that the phi_st is empty, and just create the symbol table from the non-phi st:
633 634 635
                ASSERT(phi_ending_symbol_tables[pred]->size() == 0, "%d %d", block->idx, pred->idx);
                assert(ending_symbol_tables.count(pred));
                generator->copySymbolsFrom(ending_symbol_tables[pred]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
636
            } else {
637 638
                // With multiple predecessors, the symbol tables at the end of each predecessor should be *exactly* the
                // same.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
639 640 641 642
                // (this should be satisfied by the post-run() code in this function)

                // With multiple predecessors, we have to combine the non-phi and phi symbol tables.
                // Start off with the non-phi ones:
643
                generator->copySymbolsFrom(ending_symbol_tables[pred]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
644 645

                // And go through and add phi nodes:
646
                ConcreteSymbolTable* pred_st = phi_ending_symbol_tables[pred];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
647
                for (ConcreteSymbolTable::iterator it = pred_st->begin(); it != pred_st->end(); it++) {
648 649 650 651 652
                    // printf("adding phi for %s\n", it->first.c_str());
                    llvm::PHINode* phi = emitter->getBuilder()->CreatePHI(it->second->getType()->llvmType(),
                                                                          block->predecessors.size(), it->first);
                    // emitter->getBuilder()->CreateCall(g.funcs.dump, phi);
                    ConcreteCompilerVariable* var = new ConcreteCompilerVariable(it->second->getType(), phi, true);
653
                    generator->giveLocalSymbol(it->first, var);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
654 655 656 657 658 659

                    (*phis)[it->first] = std::make_pair(it->second->getType(), phi);
                }
            }
        }

660 661 662 663 664 665 666 667 668
        for (CFGBlock* predecessor : block->predecessors) {
            if (predecessor->idx > block->idx) {
                // Loop safepoint:
                // TODO does it matter which side of the backedge these are on?
                generator->doSafePoint();
                break;
            }
        }

669
        generator->run(block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
670

671
        const IRGenerator::EndingState& ending_st = generator->getEndingSymbolTable();
672 673 674
        ending_symbol_tables[block] = ending_st.symbol_table;
        phi_ending_symbol_tables[block] = ending_st.phi_symbol_table;
        llvm_exit_blocks[block] = ending_st.ending_block;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
675 676 677 678 679 680 681 682 683 684

        if (into_hax.count(block))
            ASSERT(ending_st.symbol_table->size() == 0, "%d", block->idx);
    }

    ////
    // Phi generation.
    // We don't know the exact ssa values to back-propagate to the phi nodes until we've generated
    // the relevant IR, so after we have done all of it, go back through and populate the phi nodes.
    // Also, do some checking to make sure that the phi analysis stuff worked out, and that all blocks
685
    // agreed on what symbols + types they should be propagating for the phis.
686 687
    for (CFGBlock* b : source->cfg->blocks) {
        PHITable* phis = created_phis[b];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
688 689 690
        if (phis == NULL)
            continue;

691
        bool this_is_osr_entry = (entry_descriptor && b == entry_descriptor->backedge->target);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
692

693 694
        const std::vector<GuardList::BlockEntryGuard*>& block_guards = in_guards.getGuardsForBlock(b);
        // printf("Found %ld guards for block %p, for %p\n", block_guards.size(), b, &in_guards);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
695 696

        for (int j = 0; j < b->predecessors.size(); j++) {
697
            CFGBlock* b2 = b->predecessors[j];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
698 699 700
            if (full_blocks.count(b2) == 0 && partial_blocks.count(b2) == 0)
                continue;

701
            // printf("%d %d %ld %ld\n", i, b2->idx, phi_ending_symbol_tables[b2]->size(), phis->size());
702 703
            compareKeyset(phi_ending_symbol_tables[b2], phis);
            assert(phi_ending_symbol_tables[b2]->size() == phis->size());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
704 705 706 707 708 709
        }

        if (this_is_osr_entry) {
            compareKeyset(osr_syms, phis);
        }

710
        std::vector<IREmitter*> emitters;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
711 712 713 714 715 716
        std::vector<llvm::BasicBlock*> offramps;
        for (int i = 0; i < block_guards.size(); i++) {
            compareKeyset(&block_guards[i]->symbol_table, phis);

            llvm::BasicBlock* off_ramp = llvm::BasicBlock::Create(g.context, "deopt_ramp", irstate->getLLVMFunction());
            offramps.push_back(off_ramp);
717 718
            llvm::BasicBlock* off_ramp_end = off_ramp;
            IREmitter* emitter = createIREmitter(irstate, off_ramp_end);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
719 720 721 722 723 724 725 726
            emitters.push_back(emitter);

            block_guards[i]->branch->setSuccessor(1, off_ramp);
        }

        for (PHITable::iterator it = phis->begin(); it != phis->end(); it++) {
            llvm::PHINode* llvm_phi = it->second.second;
            for (int j = 0; j < b->predecessors.size(); j++) {
727
                CFGBlock* b2 = b->predecessors[j];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
728 729 730
                if (full_blocks.count(b2) == 0 && partial_blocks.count(b2) == 0)
                    continue;

731
                ConcreteCompilerVariable* v = (*phi_ending_symbol_tables[b2])[it->first];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
732 733 734 735
                assert(v);
                assert(v->isGrabbed());

                // Make sure they all prepared for the same type:
736 737
                ASSERT(it->second.first == v->getType(), "%d %d: %s %s %s", b->idx, b2->idx, it->first.c_str(),
                       it->second.first->debugName().c_str(), v->getType()->debugName().c_str());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
738

739
                llvm_phi->addIncoming(v->getValue(), llvm_exit_blocks[b->predecessors[j]]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
740 741 742
            }

            if (this_is_osr_entry) {
743
                ConcreteCompilerVariable* v = (*osr_syms)[it->first];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
744 745 746 747 748 749 750 751
                assert(v);
                assert(v->isGrabbed());

                ASSERT(it->second.first == v->getType(), "");
                llvm_phi->addIncoming(v->getValue(), osr_unbox_block);
            }

            for (int i = 0; i < block_guards.size(); i++) {
752 753
                GuardList::BlockEntryGuard* g = block_guards[i];
                IREmitter* emitter = emitters[i];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
754

755 756
                CompilerVariable* unconverted = g->symbol_table[it->first];
                ConcreteCompilerVariable* v = unconverted->makeConverted(*emitter, it->second.first);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
757 758 759 760 761 762 763 764 765 766 767 768 769 770
                assert(v);
                assert(v->isGrabbed());


                ASSERT(it->second.first == v->getType(), "");
                llvm_phi->addIncoming(v->getValue(), offramps[i]);

                // TODO not sure if this is right:
                unconverted->decvref(*emitter);
                delete v;
            }
        }

        for (int i = 0; i < block_guards.size(); i++) {
771
            emitters[i]->getBuilder()->CreateBr(llvm_entry_blocks[b]);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
772 773 774 775
            delete emitters[i];
        }
    }

776
    for (CFGBlock* b : source->cfg->blocks) {
777
        if (ending_symbol_tables[b] == NULL)
Kevin Modzelewski's avatar
Kevin Modzelewski committed
778 779
            continue;

780
        for (SymbolTable::iterator it = ending_symbol_tables[b]->begin(); it != ending_symbol_tables[b]->end(); it++) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
781 782
            it->second->decvrefNodrop();
        }
783 784
        for (ConcreteSymbolTable::iterator it = phi_ending_symbol_tables[b]->begin();
             it != phi_ending_symbol_tables[b]->end(); it++) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
785 786
            it->second->decvrefNodrop();
        }
787 788 789
        delete phi_ending_symbol_tables[b];
        delete ending_symbol_tables[b];
        delete created_phis[b];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
790 791 792
    }

    if (entry_descriptor) {
793
        for (const auto& p : *osr_syms) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
794
            delete p.second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
795 796 797 798 799
        }
        delete osr_syms;
    }
}

800
static void computeBlockSetClosure(BlockSet& full_blocks, BlockSet& partial_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
801 802
    if (VERBOSITY("irgen") >= 1) {
        printf("Initial full:");
803
        for (CFGBlock* b : full_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
804
            printf(" %d", b->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
805 806 807
        }
        printf("\n");
        printf("Initial partial:");
808
        for (CFGBlock* b : partial_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
809
            printf(" %d", b->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
810 811 812 813 814 815 816 817 818
        }
        printf("\n");
    }
    std::vector<CFGBlock*> q;
    BlockSet expanded;
    q.insert(q.end(), full_blocks.begin(), full_blocks.end());
    q.insert(q.end(), partial_blocks.begin(), partial_blocks.end());

    while (q.size()) {
819
        CFGBlock* b = q.back();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
820 821 822 823 824 825 826
        q.pop_back();

        if (expanded.count(b))
            continue;
        expanded.insert(b);

        for (int i = 0; i < b->successors.size(); i++) {
827
            CFGBlock* b2 = b->successors[i];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
828 829 830 831 832 833 834 835
            partial_blocks.erase(b2);
            full_blocks.insert(b2);
            q.push_back(b2);
        }
    }

    if (VERBOSITY("irgen") >= 1) {
        printf("Ending full:");
836
        for (CFGBlock* b : full_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
837
            printf(" %d", b->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
838 839 840
        }
        printf("\n");
        printf("Ending partial:");
841
        for (CFGBlock* b : partial_blocks) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
842
            printf(" %d", b->idx);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
843 844 845 846 847
        }
        printf("\n");
    }
}
// returns a pointer to the function-info mdnode
848
static llvm::MDNode* setupDebugInfo(SourceInfo* source, llvm::Function* f, std::string origname) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
849 850 851 852 853 854 855
    int lineno = 0;
    if (source->ast)
        lineno = source->ast->lineno;

    llvm::DIBuilder builder(*g.cur_module);

    std::string fn = source->parent_module->fn;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
856
    std::string dir = "";
Kevin Modzelewski's avatar
Kevin Modzelewski committed
857 858 859 860 861
    std::string producer = "pyston; git rev " STRINGIFY(GITREV);

    llvm::DIFile file = builder.createFile(fn, dir);
    llvm::DIArray param_types = builder.getOrCreateArray(llvm::None);
    llvm::DICompositeType func_type = builder.createSubroutineType(file, param_types);
862 863
    llvm::DISubprogram func_info = builder.createFunction(file, f->getName(), f->getName(), file, lineno, func_type,
                                                          false, true, lineno + 1, 0, true, f);
864 865 866 867 868

    // The 'variables' field gets initialized with a tag-prefixed array, but
    // a later verifier asserts that there is no tag.  Replace it with an empty array:
    func_info.getVariables()->replaceAllUsesWith(builder.getOrCreateArray(llvm::ArrayRef<llvm::Value*>()));

869 870
    llvm::DICompileUnit compile_unit
        = builder.createCompileUnit(llvm::dwarf::DW_LANG_Python, fn, dir, producer, true, "", 0);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
871 872 873 874 875 876 877 878 879 880 881

    llvm::DIArray subprograms = builder.getOrCreateArray(&*func_info);
    compile_unit.getSubprograms()->replaceAllUsesWith(subprograms);

    compile_unit.getEnumTypes()->replaceAllUsesWith(builder.getOrCreateArray(llvm::ArrayRef<llvm::Value*>()));
    compile_unit.getRetainedTypes()->replaceAllUsesWith(builder.getOrCreateArray(llvm::ArrayRef<llvm::Value*>()));
    compile_unit.getGlobalVariables()->replaceAllUsesWith(builder.getOrCreateArray(llvm::ArrayRef<llvm::Value*>()));
    compile_unit.getImportedEntities()->replaceAllUsesWith(builder.getOrCreateArray(llvm::ArrayRef<llvm::Value*>()));
    return func_info;
}

882 883
static std::string getUniqueFunctionName(std::string nameprefix, EffortLevel::EffortLevel effort,
                                         const OSREntryDescriptor* entry) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
884 885 886 887 888 889 890 891 892 893 894 895 896
    static int num_functions = 0;

    std::ostringstream os;
    os << nameprefix;
    os << "_e" << effort;
    if (entry) {
        os << "_osr" << entry->backedge->target->idx << "_from_" << entry->cf->func->getName().data();
    }
    os << '_' << num_functions;
    num_functions++;
    return os.str();
}

897
CompiledFunction* doCompile(SourceInfo* source, const OSREntryDescriptor* entry_descriptor,
898
                            EffortLevel::EffortLevel effort, FunctionSpecialization* spec, std::string nameprefix) {
899
    Timer _t("in doCompile");
Kevin Modzelewski's avatar
Kevin Modzelewski committed
900

901 902
    if (VERBOSITY("irgen") >= 1)
        source->cfg->print();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
903 904 905 906 907

    assert(g.cur_module == NULL);
    std::string name = getUniqueFunctionName(nameprefix, effort, entry_descriptor);
    g.cur_module = new llvm::Module(name, g.context);
    g.cur_module->setDataLayout(g.tm->getDataLayout()->getStringRepresentation());
908
    // g.engine->addModule(g.cur_module);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
909 910 911 912

    ////
    // Initializing the llvm-level structures:

913
    int nargs = source->arg_names.totalParameters();
914
    ASSERT(nargs == spec->arg_types.size(), "%d %ld", nargs, spec->arg_types.size());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
915 916

    std::vector<llvm::Type*> llvm_arg_types;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
917 918 919
    if (source->scoping->getScopeInfoForNode(source->ast)->takesClosure())
        llvm_arg_types.push_back(g.llvm_closure_type_ptr);

Kevin Modzelewski's avatar
Kevin Modzelewski committed
920 921 922 923 924 925
    if (entry_descriptor == NULL) {
        for (int i = 0; i < nargs; i++) {
            if (i == 3) {
                llvm_arg_types.push_back(g.llvm_value_type_ptr->getPointerTo());
                break;
            }
926
            llvm_arg_types.push_back(spec->arg_types[i]->llvmType());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
927 928
        }
    } else {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
929
        int arg_num = -1;
930
        for (const auto& p : entry_descriptor->args) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
931
            arg_num++;
932
            // printf("Loading %s: %s\n", p.first.c_str(), p.second->debugName().c_str());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
933 934
            if (arg_num < 3)
                llvm_arg_types.push_back(p.second->llvmType());
Kevin Modzelewski's avatar
Kevin Modzelewski committed
935 936 937 938 939 940 941
            else {
                llvm_arg_types.push_back(g.llvm_value_type_ptr->getPointerTo());
                break;
            }
        }
    }

942
    llvm::FunctionType* ft = llvm::FunctionType::get(spec->rtn_type->llvmType(), llvm_arg_types, false /*vararg*/);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
943

944 945
    llvm::Function* f = llvm::Function::Create(ft, llvm::Function::ExternalLinkage, name, g.cur_module);
    // g.func_registry.registerFunction(f, g.cur_module);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
946

947
    CompiledFunction* cf
948
        = new CompiledFunction(f, spec, (effort == EffortLevel::INTERPRETED), NULL, NULL, effort, entry_descriptor);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
949 950 951 952 953 954

    llvm::MDNode* dbg_funcinfo = setupDebugInfo(source, f, nameprefix);

    TypeAnalysis::SpeculationLevel speculation_level = TypeAnalysis::NONE;
    if (ENABLE_SPECULATION && effort >= EffortLevel::MODERATE)
        speculation_level = TypeAnalysis::SOME;
955
    TypeAnalysis* types = doTypeAnalysis(source->cfg, source->arg_names, spec->arg_types, speculation_level,
956
                                         source->scoping->getScopeInfoForNode(source->ast));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
957 958 959 960 961

    GuardList guards;

    BlockSet full_blocks, partial_blocks;
    if (entry_descriptor == NULL) {
962
        for (CFGBlock* b : source->cfg->blocks) {
963
            full_blocks.insert(b);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
964 965 966 967 968 969 970 971
        }
    } else {
        full_blocks.insert(entry_descriptor->backedge->target);
        computeBlockSetClosure(full_blocks, partial_blocks);
    }

    IRGenState irstate(cf, source, getGCBuilder(), dbg_funcinfo);

972
    emitBBs(&irstate, "opt", guards, GuardList(), types, entry_descriptor, full_blocks, partial_blocks);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
973 974 975 976 977 978

    // De-opt handling:

    if (!guards.isEmpty()) {
        BlockSet deopt_full_blocks, deopt_partial_blocks;
        GuardList deopt_guards;
979 980
        // typedef std::unordered_map<CFGBlock*, std::unordered_map<AST_expr*, GuardList::ExprTypeGuard*> > Worklist;
        // Worklist guard_worklist;
981 982

        guards.getBlocksWithGuards(deopt_full_blocks);
983
        for (const auto& p : guards.exprGuards()) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
984
            deopt_partial_blocks.insert(p.second->cfg_block);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
985 986 987 988
        }

        computeBlockSetClosure(deopt_full_blocks, deopt_partial_blocks);

989 990
        assert(deopt_full_blocks.size() || deopt_partial_blocks.size());

991
        TypeAnalysis* deopt_types = doTypeAnalysis(source->cfg, source->arg_names, spec->arg_types, TypeAnalysis::NONE,
992
                                                   source->scoping->getScopeInfoForNode(source->ast));
993
        emitBBs(&irstate, "deopt", deopt_guards, guards, deopt_types, NULL, deopt_full_blocks, deopt_partial_blocks);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
994
        assert(deopt_guards.isEmpty());
995
        deopt_guards.assertGotPatched();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
996 997 998

        delete deopt_types;
    }
999
    guards.assertGotPatched();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1000

1001
    for (const auto& p : guards.exprGuards()) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1002
        delete p.second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1003 1004 1005 1006 1007 1008 1009 1010 1011
    }

    delete types;

    if (VERBOSITY("irgen") >= 1) {
        printf("generated IR:\n");
        printf("\033[33m");
        fflush(stdout);
        dumpPrettyIR(f);
1012 1013 1014
        // f->dump();
        // g.cur_module->dump();
        // g.cur_module->print(llvm::outs(), NULL);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1015 1016 1017 1018
        printf("\033[0m");
        fflush(stdout);
    } else {
        // Somehow, running this code makes it faster...?????
1019 1020
        // printf("\033[0m");
        // fflush(stdout);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
    }

#ifndef NDEBUG
    if (!BENCH) {
        // Calling verifyFunction() confuses the profiler, which will end up attributing
        // a large amount of runtime to it since the call stack looks very similar to
        // the (expensive) case of compiling the function.
        llvm::verifyFunction(*f);
    }
#endif

    long us = _t.end();
    static StatCounter us_irgen("us_compiling_irgen");
    us_irgen.log(us);

    if (ENABLE_LLVMOPTS)
        optimizeIR(f, effort);

    bool ENABLE_IR_DEBUG = false;
    if (ENABLE_IR_DEBUG) {
        addIRDebugSymbols(f);
1042
        // dumpPrettyIR(f);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
    }

    g.cur_module = NULL;

    return cf;
}



} // namespace pyston