SSA Form build algorithm description

file.cpp

// вызывается для каждой переменой 
void SSAFormer::RenameVarToSSAForm(std::string varName) {
    counter = 0;
    stack.clear();
    TraverseBBWithVar(cfg->basicBlocks.front(), varName);
}

// метод для обхода всех использований переменой, на вход принимает энтри поинт CFG
void SSAFormer::TraverseBBWithVar(BasicBlock *bb, std::string varName) {
    // цикл по всем выражениям
    for (auto stmt : bb->statements) {
        // Renaming  vars in all rhs
        if (stmt->type != PHI) {
            // получаем все переменные использованные в RHS
            set<VariableExpession *> vars = varSearcher.AllVarsUsedInStatement(stmt);
            // цикл по всем переменным
            for (auto var : vars) {
                if (var->name == varName)
                    // проставляяем ССА индекс каждой переменой
                    // текущий индекс лежит последнем в стеке
                    var->SetSSAIndex(stack.back());
            }
        }
        
        // Renaming  vars in all lhs
        if (stmt->type == ASSIGN) {
            AssignStatement *assignStmt = static_cast<AssignStatement *>(stmt);
            if (assignStmt->var->name == varName) {
                 // проставляяем ССА индекс каждой переменой
                assignStmt->var->SetSSAIndex(counter);
                // поскольку это присваивание то мы должны увеличить индекс для следующих переменных
                stack.push_back(counter);
                counter += 1;
            }
        }
        
        if (stmt->type == PHI) {
            PhiNodeStatement *phiStmt = static_cast<PhiNodeStatement *>(stmt);
            if (phiStmt->var->name == varName) {
                // аналогичная ситуация как и для присваивания
                phiStmt->var->SetSSAIndex(counter);
                stack.push_back(counter);
                counter += 1;
            }
        }
    }
    
    // теперь мы должны поставить во всех фи функциях правильные индексы сса формы для каждого базового блока
    for (auto succBB : bb->succs) {
        for (auto stmt : succBB->statements) {
            if (stmt->type == PHI) {
                PhiNodeStatement *phiStmt = static_cast<PhiNodeStatement *>(stmt);
                if (phiStmt->bbToVarMap.count(bb) && phiStmt->bbToVarMap[bb]->name == varName) {
                    // собственно, что мы и делаем. Ставим для определенного базового блока - переменной нужный индекс
                    phiStmt->bbToVarMap[bb]->SetSSAIndex(stack.back());
                }
            }
        }
    }
    
    // рекурсивный вызов
    for (auto child : bb->domimatingBlocks) {
        TraverseBBWithVar(child, varName);
    }
    
    for (auto statement : bb->statements) {
        if (statement->type == ASSIGN) {
            AssignStatement *assignStmt = static_cast<AssignStatement *>(statement);
            if (assignStmt->var->name == varName) {
                // вытасикваем из стека, так как все нужные индексы (кот были в стеке) мы уже проставили
                // рекурсивными вызывами
                stack.pop_back();
            }
        }
    }
}