<commit_before>/*
 *  Copyright 2014 <NAME>.
 *
 *  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.
 */
package org.teavm.model.util;

import com.carrotsearch.hppc.IntHashSet;
import com.carrotsearch.hppc.IntSet;
import java.util.ArrayDeque;
import java.util.BitSet;
import java.util.Deque;
import org.teavm.common.Graph;
import org.teavm.model.BasicBlock;
import org.teavm.model.Incoming;
import org.teavm.model.Instruction;
import org.teavm.model.Phi;
import org.teavm.model.Program;
import org.teavm.model.Variable;

public class LivenessAnalyzer {
    private BitSet[] liveVars;
    private BitSet[] liveOutVars;

    public boolean liveIn(int block, int var) {
        return liveVars[block].get(var);
    }

    public BitSet liveIn(int block) {
        return (BitSet) liveVars[block].clone();
    }

    public BitSet liveOut(int block) {
        return (BitSet) liveOutVars[block].clone();
    }

    public void analyze(Program program) {
        Graph cfg = ProgramUtils.buildControlFlowGraph(program);
        liveVars = new BitSet[cfg.size()];
        liveOutVars = new BitSet[cfg.size()];
        for (int i = 0; i < liveVars.length; ++i) {
            liveVars[i] = new BitSet(program.basicBlockCount());
            liveOutVars[i] = new BitSet(program.basicBlockCount());
        }

        UsageExtractor usageExtractor = new UsageExtractor();
        DefinitionExtractor defExtractor = new DefinitionExtractor();
        Deque<Task> stack = new ArrayDeque<>();
        int[] definitions = new int[program.variableCount()];
        for (int i = 0; i < program.basicBlockCount(); ++i) {
            BasicBlock block = program.basicBlockAt(i);

            if (block.getExceptionVariable() != null) {
                definitions[block.getExceptionVariable().getIndex()] = i;
            }

            for (Instruction insn : block) {
                insn.acceptVisitor(usageExtractor);
                IntSet usedVars = new IntHashSet();
                for (Variable var : usageExtractor.getUsedVariables()) {
                    Task task = new Task();
                    task.block = i;
                    task.var = var.getIndex();
                    stack.push(task);
                    usedVars.add(var.getIndex());
                }
                insn.acceptVisitor(defExtractor);
                for (Variable var : defExtractor.getDefinedVariables()) {
                    if (!usedVars.contains(var.getIndex())) {
                        definitions[var.getIndex()] = i;
                    }
                }
            }

            for (Phi phi : block.getPhis()) {
                definitions[phi.getReceiver().getIndex()] = i;
                for (Incoming incoming : phi.getIncomings()) {
                    Task task = new Task();
                    task.block = incoming.getSource().getIndex();
                    task.var = incoming.getValue().getIndex();
                    stack.push(task);
                }
            }
        }

        while (!stack.isEmpty()) {
            Task task = stack.pop();
            if (liveVars[task.block].get(task.var) || definitions[task.var] == task.block) {
                continue;
            }
            liveVars[task.block].set(task.var, true);
            for (int pred : cfg.incomingEdges(task.block)) {
                Task nextTask = new Task();
                nextTask.block = pred;
                nextTask.var = task.var;
                stack.push(nextTask);
            }
        }

        for (int i = 0; i < liveVars.length; ++i) {
            for (int j : cfg.incomingEdges(i)) {
                liveOutVars[j].or(liveVars[i]);
            }
            BasicBlock block = program.basicBlockAt(i);
            for (Phi phi : block.getPhis()) {
                for (Incoming incoming : phi.getIncomings()) {
                    liveOutVars[incoming.getSource().getIndex()].set(incoming.getValue().getIndex());
                }
            }
        }
    }

    private static class Task {
        int block;
        int var;
    }
}<commit_msg>Fix bug in liveness analysis<commit_after>/*
 *  Copyright 2014 <NAME>.
 *
 *  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.
 */
package org.teavm.model.util;

import com.carrotsearch.hppc.IntHashSet;
import com.carrotsearch.hppc.IntSet;
import com.carrotsearch.hppc.IntStack;
import java.util.BitSet;
import org.teavm.common.DominatorTree;
import org.teavm.common.Graph;
import org.teavm.common.GraphUtils;
import org.teavm.model.BasicBlock;
import org.teavm.model.Incoming;
import org.teavm.model.Instruction;
import org.teavm.model.Phi;
import org.teavm.model.Program;
import org.teavm.model.Variable;

public class LivenessAnalyzer {
    private BitSet[] liveVars;
    private BitSet[] liveOutVars;

    public boolean liveIn(int block, int var) {
        return liveVars[block].get(var);
    }

    public BitSet liveIn(int block) {
        return (BitSet) liveVars[block].clone();
    }

    public BitSet liveOut(int block) {
        return (BitSet) liveOutVars[block].clone();
    }

    public void analyze(Program program) {
        Graph cfg = ProgramUtils.buildControlFlowGraph(program);
        DominatorTree dominatorTree = GraphUtils.buildDominatorTree(cfg);
        liveVars = new BitSet[cfg.size()];
        liveOutVars = new BitSet[cfg.size()];
        for (int i = 0; i < liveVars.length; ++i) {
            liveVars[i] = new BitSet(program.basicBlockCount());
            liveOutVars[i] = new BitSet(program.basicBlockCount());
        }

        UsageExtractor usageExtractor = new UsageExtractor();
        DefinitionExtractor defExtractor = new DefinitionExtractor();
        IntStack stack = new IntStack();
        int[] definitions = new int[program.variableCount()];
        for (int i = 0; i < program.basicBlockCount(); ++i) {
            BasicBlock block = program.basicBlockAt(i);

            if (block.getExceptionVariable() != null) {
                definitions[block.getExceptionVariable().getIndex()] = i;
            }

            for (Instruction insn : block) {
                insn.acceptVisitor(usageExtractor);
                IntSet usedVars = new IntHashSet();
                for (Variable var : usageExtractor.getUsedVariables()) {
                    stack.push(i);
                    stack.push(var.getIndex());
                    usedVars.add(var.getIndex());
                }
                insn.acceptVisitor(defExtractor);
                for (Variable var : defExtractor.getDefinedVariables()) {
                    if (!usedVars.contains(var.getIndex())) {
                        definitions[var.getIndex()] = i;
                    }
                }
            }

            for (Phi phi : block.getPhis()) {
                definitions[phi.getReceiver().getIndex()] = i;
                for (Incoming incoming : phi.getIncomings()) {
                    stack.push(incoming.getSource().getIndex());
                    stack.push(incoming.getValue().getIndex());
                }
            }
        }

        while (!stack.isEmpty()) {
            int variable = stack.pop();
            int block = stack.pop();
            BitSet blockLiveVars = liveVars[block];
            if (blockLiveVars.get(variable) || definitions[variable] == block
                    || !dominatorTree.dominates(definitions[variable], block)) {
                continue;
            }
            liveVars[block].set(variable, true);
            for (int pred : cfg.incomingEdges(block)) {
                stack.push(pred);
                stack.push(variable);
            }
        }

        for (int i = 0; i < liveVars.length; ++i) {
            for (int j : cfg.incomingEdges(i)) {
                liveOutVars[j].or(liveVars[i]);
            }
            BasicBlock block = program.basicBlockAt(i);
            for (Phi phi : block.getPhis()) {
                for (Incoming incoming : phi.getIncomings()) {
                    liveOutVars[incoming.getSource().getIndex()].set(incoming.getValue().getIndex());
                }
            }
        }
    }
}
{'fraction_non_alphanumeric': 0.11261261261261261, 'fraction_numerical': 0.0024170511975390024, 'mean_word_length': 1.9826343381389253, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1370839', 'n_tokens_mistral': 2559, 'n_tokens_neox': 2514, 'n_words': 596}