Last active
June 7, 2017 18:54
-
-
Save filletofish/cd7ea39d67333ef8ee85eb3b196b78fd to your computer and use it in GitHub Desktop.
SSA Form build algorithm description
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // вызывается для каждой переменой | |
| 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(); | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment