From efa3a367885c9510bb6280788241dae6f48a42bb Mon Sep 17 00:00:00 2001 From: Rusty Wagner Date: Mon, 24 Feb 2020 19:42:56 -0500 Subject: Adding SSA support for HLIL --- highlevelilinstruction.cpp | 196 +++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 181 insertions(+), 15 deletions(-) (limited to 'highlevelilinstruction.cpp') diff --git a/highlevelilinstruction.cpp b/highlevelilinstruction.cpp index 609b7f77..610c9e63 100644 --- a/highlevelilinstruction.cpp +++ b/highlevelilinstruction.cpp @@ -46,6 +46,7 @@ unordered_map {CarryExprHighLevelOperandUsage, ExprHighLevelOperand}, {IndexExprHighLevelOperandUsage, ExprHighLevelOperand}, {ConditionExprHighLevelOperandUsage, ExprHighLevelOperand}, + {ConditionPhiExprHighLevelOperandUsage, ExprHighLevelOperand}, {TrueExprHighLevelOperandUsage, ExprHighLevelOperand}, {FalseExprHighLevelOperandUsage, ExprHighLevelOperand}, {LoopExprHighLevelOperandUsage, ExprHighLevelOperand}, @@ -86,9 +87,16 @@ unordered_map> {HLIL_IF, {ConditionExprHighLevelOperandUsage, TrueExprHighLevelOperandUsage, FalseExprHighLevelOperandUsage}}, {HLIL_WHILE, {ConditionExprHighLevelOperandUsage, LoopExprHighLevelOperandUsage}}, + {HLIL_WHILE_SSA, {ConditionPhiExprHighLevelOperandUsage, + ConditionExprHighLevelOperandUsage, LoopExprHighLevelOperandUsage}}, {HLIL_DO_WHILE, {LoopExprHighLevelOperandUsage, ConditionExprHighLevelOperandUsage}}, + {HLIL_DO_WHILE_SSA, {LoopExprHighLevelOperandUsage, ConditionPhiExprHighLevelOperandUsage, + ConditionExprHighLevelOperandUsage}}, {HLIL_FOR, {InitExprHighLevelOperandUsage, ConditionExprHighLevelOperandUsage, UpdateExprHighLevelOperandUsage, LoopExprHighLevelOperandUsage}}, + {HLIL_FOR_SSA, {InitExprHighLevelOperandUsage, ConditionPhiExprHighLevelOperandUsage, + ConditionExprHighLevelOperandUsage, UpdateExprHighLevelOperandUsage, + LoopExprHighLevelOperandUsage}}, {HLIL_SWITCH, {ConditionExprHighLevelOperandUsage, DefaultExprHighLevelOperandUsage, CasesHighLevelOperandUsage}}, {HLIL_CASE, {ValueExprsHighLevelOperandUsage, TrueExprHighLevelOperandUsage}}, @@ -394,12 +402,20 @@ HighLevelILIndexList::operator vector() const const HighLevelILInstruction HighLevelILInstructionList::ListIterator::operator*() { - return HighLevelILInstruction(pos.GetFunction(), pos.GetFunction()->GetRawExpr((size_t)*pos), (size_t)*pos); + if (ast) + { + return HighLevelILInstruction(pos.GetFunction(), pos.GetFunction()->GetRawExpr((size_t)*pos), + (size_t)*pos, true, instructionIndex); + } + return HighLevelILInstruction(pos.GetFunction(), pos.GetFunction()->GetRawNonASTExpr((size_t)*pos), + (size_t)*pos, false, instructionIndex); } HighLevelILInstructionList::HighLevelILInstructionList(HighLevelILFunction* func, - const BNHighLevelILInstruction& instr, size_t count): m_list(func, instr, count) + const BNHighLevelILInstruction& instr, size_t count, bool asFullAst, + size_t instructionIndex): m_list(func, instr, count), m_ast(asFullAst), + m_instructionIndex(instructionIndex) { } @@ -408,6 +424,8 @@ HighLevelILInstructionList::const_iterator HighLevelILInstructionList::begin() c { const_iterator result; result.pos = m_list.begin(); + result.ast = m_ast; + result.instructionIndex = m_instructionIndex; return result; } @@ -416,6 +434,8 @@ HighLevelILInstructionList::const_iterator HighLevelILInstructionList::end() con { const_iterator result; result.pos = m_list.end(); + result.ast = m_ast; + result.instructionIndex = m_instructionIndex; return result; } @@ -661,7 +681,7 @@ HighLevelILInstruction::HighLevelILInstruction() HighLevelILInstruction::HighLevelILInstruction(HighLevelILFunction* func, - const BNHighLevelILInstruction& instr, size_t expr) + const BNHighLevelILInstruction& instr, size_t expr, bool asFullAst, size_t instrIdx) { operation = instr.operation; sourceOperand = instr.sourceOperand; @@ -675,6 +695,8 @@ HighLevelILInstruction::HighLevelILInstruction(HighLevelILFunction* func, parent = instr.parent; function = func; exprIndex = expr; + instructionIndex = instrIdx; + ast = asFullAst; } @@ -691,6 +713,8 @@ HighLevelILInstruction::HighLevelILInstruction(const HighLevelILInstructionBase& address = instr.address; function = instr.function; exprIndex = instr.exprIndex; + instructionIndex = instr.instructionIndex; + ast = instr.ast; parent = instr.parent; } @@ -721,7 +745,13 @@ size_t HighLevelILInstructionBase::GetRawOperandAsIndex(size_t operand) const HighLevelILInstruction HighLevelILInstructionBase::GetRawOperandAsExpr(size_t operand) const { - return HighLevelILInstruction(function, function->GetRawExpr(operands[operand]), operands[operand]); + if (ast) + { + return HighLevelILInstruction(function, function->GetRawExpr(operands[operand]), + operands[operand], true, instructionIndex); + } + return HighLevelILInstruction(function, function->GetRawNonASTExpr(operands[operand]), + operands[operand], false, instructionIndex); } @@ -739,7 +769,8 @@ SSAVariable HighLevelILInstructionBase::GetRawOperandAsSSAVariable(size_t operan HighLevelILInstructionList HighLevelILInstructionBase::GetRawOperandAsExprList(size_t operand) const { - return HighLevelILInstructionList(function, function->GetRawExpr(operands[operand + 1]), operands[operand]); + return HighLevelILInstructionList(function, function->GetRawExpr(operands[operand + 1]), + operands[operand], ast, instructionIndex); } @@ -865,6 +896,30 @@ HighLevelILInstruction HighLevelILInstructionBase::GetInstruction() const } +HighLevelILInstruction HighLevelILInstructionBase::AsAST() const +{ + return function->GetExpr(exprIndex, true); +} + + +HighLevelILInstruction HighLevelILInstructionBase::AsNonAST() const +{ + return function->GetExpr(exprIndex, false); +} + + +bool HighLevelILInstructionBase::HasParent() const +{ + return parent != BN_INVALID_EXPR; +} + + +HighLevelILInstruction HighLevelILInstructionBase::GetParent() const +{ + return function->GetExpr(parent, true); +} + + void HighLevelILInstruction::VisitExprs(const std::function& func) const { stack toProcess; @@ -873,7 +928,7 @@ void HighLevelILInstruction::VisitExprs(const std::functionGetExpr(toProcess.top()); + HighLevelILInstruction cur = function->GetExpr(toProcess.top(), ast); toProcess.pop(); if (!func(cur)) continue; @@ -885,29 +940,58 @@ void HighLevelILInstruction::VisitExprs(const std::functionexprIndex); break; case HLIL_IF: - toProcess.push(cur.GetFalseExpr().exprIndex); - toProcess.push(cur.GetTrueExpr().exprIndex); + if (ast) + { + toProcess.push(cur.GetFalseExpr().exprIndex); + toProcess.push(cur.GetTrueExpr().exprIndex); + } toProcess.push(cur.GetConditionExpr().exprIndex); break; case HLIL_WHILE: - toProcess.push(cur.GetLoopExpr().exprIndex); + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); toProcess.push(cur.GetConditionExpr().exprIndex); break; + case HLIL_WHILE_SSA: + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); + toProcess.push(cur.GetConditionExpr().exprIndex); + toProcess.push(cur.GetConditionPhiExpr().exprIndex); + break; case HLIL_DO_WHILE: toProcess.push(cur.GetConditionExpr().exprIndex); - toProcess.push(cur.GetLoopExpr().exprIndex); + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); + break; + case HLIL_DO_WHILE_SSA: + toProcess.push(cur.GetConditionExpr().exprIndex); + toProcess.push(cur.GetConditionPhiExpr().exprIndex); + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); break; case HLIL_FOR: - toProcess.push(cur.GetLoopExpr().exprIndex); + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); toProcess.push(cur.GetUpdateExpr().exprIndex); toProcess.push(cur.GetConditionExpr().exprIndex); toProcess.push(cur.GetInitExpr().exprIndex); break; + case HLIL_FOR_SSA: + if (ast) + toProcess.push(cur.GetLoopExpr().exprIndex); + toProcess.push(cur.GetUpdateExpr().exprIndex); + toProcess.push(cur.GetConditionExpr().exprIndex); + toProcess.push(cur.GetConditionPhiExpr().exprIndex); + toProcess.push(cur.GetInitExpr().exprIndex); + break; case HLIL_SWITCH: - exprs = cur.GetCases(); - for (auto i = exprs.rbegin(); i != exprs.rend(); ++i) - toProcess.push(i->exprIndex); - toProcess.push(cur.GetDefaultExpr().exprIndex); + if (ast) + { + exprs = cur.GetCases(); + for (auto i = exprs.rbegin(); i != exprs.rend(); ++i) + toProcess.push(i->exprIndex); + toProcess.push(cur.GetDefaultExpr().exprIndex); + } toProcess.push(cur.GetConditionExpr().exprIndex); break; case HLIL_CASE: @@ -1120,13 +1204,27 @@ ExprId HighLevelILInstruction::CopyTo(HighLevelILFunction* dest, case HLIL_WHILE: return dest->While(subExprHandler(GetConditionExpr()), subExprHandler(GetLoopExpr()), *this); + case HLIL_WHILE_SSA: + return dest->WhileSSA(subExprHandler(GetConditionPhiExpr()), + subExprHandler(GetConditionExpr()), + subExprHandler(GetLoopExpr()), *this); case HLIL_DO_WHILE: return dest->DoWhile(subExprHandler(GetLoopExpr()), subExprHandler(GetConditionExpr()), *this); + case HLIL_DO_WHILE_SSA: + return dest->DoWhileSSA(subExprHandler(GetLoopExpr()), + subExprHandler(GetConditionPhiExpr()), + subExprHandler(GetConditionExpr()), *this); case HLIL_FOR: return dest->For(subExprHandler(GetInitExpr()), subExprHandler(GetConditionExpr()), subExprHandler(GetUpdateExpr()), subExprHandler(GetLoopExpr()), *this); + case HLIL_FOR_SSA: + return dest->ForSSA(subExprHandler(GetInitExpr()), + subExprHandler(GetConditionPhiExpr()), + subExprHandler(GetConditionExpr()), + subExprHandler(GetUpdateExpr()), + subExprHandler(GetLoopExpr()), *this); case HLIL_SWITCH: for (auto& i : GetCases()) params.push_back(subExprHandler(i)); @@ -1387,12 +1485,32 @@ bool HighLevelILInstruction::operator<(const HighLevelILInstruction& other) cons if (other.GetConditionExpr() < GetConditionExpr()) return false; return GetLoopExpr() < other.GetLoopExpr(); + case HLIL_WHILE_SSA: + if (GetConditionPhiExpr() < other.GetConditionPhiExpr()) + return true; + if (other.GetConditionPhiExpr() < GetConditionPhiExpr()) + return false; + if (GetConditionExpr() < other.GetConditionExpr()) + return true; + if (other.GetConditionExpr() < GetConditionExpr()) + return false; + return GetLoopExpr() < other.GetLoopExpr(); case HLIL_DO_WHILE: if (GetLoopExpr() < other.GetLoopExpr()) return true; if (other.GetLoopExpr() < GetLoopExpr()) return false; return GetConditionExpr() < other.GetConditionExpr(); + case HLIL_DO_WHILE_SSA: + if (GetLoopExpr() < other.GetLoopExpr()) + return true; + if (other.GetLoopExpr() < GetLoopExpr()) + return false; + if (GetConditionPhiExpr() < other.GetConditionPhiExpr()) + return true; + if (other.GetConditionPhiExpr() < GetConditionPhiExpr()) + return false; + return GetConditionExpr() < other.GetConditionExpr(); case HLIL_FOR: if (GetInitExpr() < other.GetInitExpr()) return true; @@ -1407,6 +1525,24 @@ bool HighLevelILInstruction::operator<(const HighLevelILInstruction& other) cons if (other.GetUpdateExpr() < GetUpdateExpr()) return false; return GetLoopExpr() < other.GetLoopExpr(); + case HLIL_FOR_SSA: + if (GetInitExpr() < other.GetInitExpr()) + return true; + if (other.GetInitExpr() < GetInitExpr()) + return false; + if (GetConditionPhiExpr() < other.GetConditionPhiExpr()) + return true; + if (other.GetConditionPhiExpr() < GetConditionPhiExpr()) + return false; + if (GetConditionExpr() < other.GetConditionExpr()) + return true; + if (other.GetConditionExpr() < GetConditionExpr()) + return false; + if (GetUpdateExpr() < other.GetUpdateExpr()) + return true; + if (other.GetUpdateExpr() < GetUpdateExpr()) + return false; + return GetLoopExpr() < other.GetLoopExpr(); case HLIL_SWITCH: if (GetConditionExpr() < other.GetConditionExpr()) return true; @@ -1946,6 +2082,15 @@ HighLevelILInstruction HighLevelILInstruction::GetConditionExpr() const } +HighLevelILInstruction HighLevelILInstruction::GetConditionPhiExpr() const +{ + size_t operandIndex; + if (GetOperandIndexForUsage(ConditionPhiExprHighLevelOperandUsage, operandIndex)) + return GetRawOperandAsExpr(operandIndex); + throw HighLevelILInstructionAccessException(); +} + + HighLevelILInstruction HighLevelILInstruction::GetTrueExpr() const { size_t operandIndex; @@ -2187,12 +2332,26 @@ ExprId HighLevelILFunction::While(ExprId condition, ExprId loopExpr, const ILSou } +ExprId HighLevelILFunction::WhileSSA(ExprId conditionPhi, ExprId condition, ExprId loopExpr, + const ILSourceLocation& loc) +{ + return AddExprWithLocation(HLIL_WHILE_SSA, loc, 0, conditionPhi, condition, loopExpr); +} + + ExprId HighLevelILFunction::DoWhile(ExprId loopExpr, ExprId condition, const ILSourceLocation& loc) { return AddExprWithLocation(HLIL_DO_WHILE, loc, 0, loopExpr, condition); } +ExprId HighLevelILFunction::DoWhileSSA(ExprId loopExpr, ExprId conditionPhi, ExprId condition, + const ILSourceLocation& loc) +{ + return AddExprWithLocation(HLIL_DO_WHILE_SSA, loc, 0, loopExpr, conditionPhi, condition); +} + + ExprId HighLevelILFunction::For(ExprId initExpr, ExprId condition, ExprId updateExpr, ExprId loopExpr, const ILSourceLocation& loc) { @@ -2200,6 +2359,13 @@ ExprId HighLevelILFunction::For(ExprId initExpr, ExprId condition, ExprId update } +ExprId HighLevelILFunction::ForSSA(ExprId initExpr, ExprId conditionPhi, ExprId condition, + ExprId updateExpr, ExprId loopExpr, const ILSourceLocation& loc) +{ + return AddExprWithLocation(HLIL_FOR_SSA, loc, 0, initExpr, conditionPhi, condition, updateExpr, loopExpr); +} + + ExprId HighLevelILFunction::Switch(ExprId condition, ExprId defaultExpr, const std::vector& cases, const ILSourceLocation& loc) { -- cgit v1.3.1