7 #ifndef RETDEC_LLVMIR2HLL_LLVM_LLVMIR2BIR_CONVERTER_STRUCTURE_CONVERTER_H
8 #define RETDEC_LLVMIR2HLL_LLVM_LLVMIR2BIR_CONVERTER_STRUCTURE_CONVERTER_H
13 #include <unordered_map>
14 #include <unordered_set>
30 class ScalarEvolution;
39 class LLVMValueConverter;
61 using BBSet = std::unordered_set<llvm::BasicBlock *>;
65 using LoopSet = std::unordered_set<llvm::Loop *>;
68 using MapBBToBBSet = std::unordered_map<llvm::BasicBlock *, BBSet>;
69 using MapBBToCFGNode = std::unordered_map<llvm::BasicBlock *, ShPtr<CFGNode>>;
74 using MapTargetToGoto = std::unordered_map<ShPtr<CFGNode>, std::vector<ShPtr<GotoStmt>>>;
75 using MapStmtToClones = std::unordered_map<ShPtr<Statement>, std::vector<ShPtr<Statement>>>;
94 llvm::Loop *loop)
const;
113 std::size_t succ)
const;
115 std::size_t succ)
const;
117 std::size_t succ)
const;
119 std::size_t succ)
const;
121 std::size_t succ)
const;
126 std::size_t succ)
const;
182 bool hasDefault =
true)
const;
190 bool hasDefault)
const;
204 bool hasDefault)
const;
218 llvm::BasicBlock *succ);
A converter of LLVM basic blocks.
A representation of a control-flow graph node.
A converter of LLVM basic blocks.
Definition: basic_block_converter.h:42
std::unordered_set< ShPtr< CFGNode > > CFGNodeSet
Definition: cfg_node.h:58
A converter of the LLVM function structure.
Definition: structure_converter.h:51
void reduceToIfStatementClone(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement without else c...
Definition: structure_converter.cpp:1147
void reduceToSequence(ShPtr< CFGNode > node)
Reduces node node and its only successor into a single node which contains merged bodies of both node...
Definition: structure_converter.cpp:1059
std::unordered_set< llvm::Loop * > LoopSet
Definition: structure_converter.h:65
void reduceToNestedWhileTrueLoopWithContinueInHeader(ShPtr< CFGNode > node, std::size_t succ)
Reduces the given node node is into a while(true) statement, when on the index succ is the body of th...
Definition: structure_converter.cpp:1394
std::stack< ShPtr< CFGNode > > CFGNodeStack
Definition: structure_converter.h:63
std::unordered_map< llvm::BasicBlock *, BBSet > MapBBToBBSet
Definition: structure_converter.h:68
void reduceToIfStatement(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement without else c...
Definition: structure_converter.cpp:1118
BasicBlockConverter bbConverter
A converter of the LLVM basic block.
Definition: structure_converter.h:269
void replaceGoto(CFGNodeVector &targets)
Replaces goto with code if there is only one reference to it.
Definition: structure_converter.cpp:165
ShPtr< Statement > getPHICopiesForSuccessor(llvm::BasicBlock *currBB, llvm::BasicBlock *succ)
Returns PHI copies for the given basic block currBB and its successor succ.
Definition: structure_converter.cpp:2213
unsigned getStatementCount(ShPtr< Statement > statement)
Returns number of statements in parent statement (body of if/while etc.)
Definition: structure_converter.cpp:240
std::unordered_map< llvm::Loop *, ShPtr< CFGNode > > MapLoopToCFGNode
Definition: structure_converter.h:72
llvm::LoopInfo * loopInfo
Information about loops.
Definition: structure_converter.h:260
bool isNodeAfterSwitchClause(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clauseNode) const
Determines whether the given node node is after the given switch clause clauseNode.
Definition: structure_converter.cpp:1698
bool isIfStatementWithBreakByGotoInLoop(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:828
std::unordered_map< ShPtr< CFGNode >, DFSNodeState > MapCFGNodeToDFSNodeState
Definition: structure_converter.h:71
std::unordered_map< ShPtr< CFGNode >, ShPtr< SwitchClause > > MapCFGNodeToSwitchClause
Definition: structure_converter.h:70
std::queue< ShPtr< CFGNode > > CFGNodeQueue
Definition: structure_converter.h:62
bool isNestedWhileTrueLoopWithContinueInHeader(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is a while(true) statement, when on the index succ is the body...
Definition: structure_converter.cpp:960
ShPtr< Statement > getIfClauseBody(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor)
Creates a new body of the given if clause clause.
Definition: structure_converter.cpp:1505
void reduceToForLoop(ShPtr< CFGNode > node)
Reduces node node into a node with for loop.
Definition: structure_converter.cpp:1329
ShPtr< Statement > getGotoForSuccessor(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &target)
Creates a goto statement which jumps from the given node node to the given target node target.
Definition: structure_converter.cpp:2173
bool isSequenceWithTerminatingBranchToClone(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be reduced with following node as a sequence,...
Definition: structure_converter.cpp:684
ShPtr< Statement > getAssignsToPHINodes(const ShPtr< CFGNode > &from, const ShPtr< CFGNode > &to)
Returns assignments to the PHI nodes from the given node from and to the given node to.
Definition: structure_converter.cpp:2198
bool isIfStatementWithBreakInLoop(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:795
DFSNodeState
Information about state of node during DFS traversal.
Definition: structure_converter.h:54
@ Closed
Visited, but not closed node.
ShPtr< IfStmt > getIfStmt(const ShPtr< Expression > &cond, const ShPtr< Statement > &trueBody, const ShPtr< Statement > &falseBody=nullptr) const
Returns new if statement with the given condition cond and true body trueBody and false body (else cl...
Definition: structure_converter.cpp:1556
void correctUndefinedLabels()
If goto target label is not used in code, it is replaced with its clone (that is used)
Definition: structure_converter.cpp:267
void reduceToIfElseStatementWithBreakInLoop(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with break sta...
Definition: structure_converter.cpp:1176
BBSet reducedSwitches
Definition: structure_converter.h:297
void initialiazeLLVMAnalyses(llvm::Function &func)
Initializes required LLVM analyses for converted function func.
Definition: structure_converter.cpp:2258
LoopSet reducedLoops
Definition: structure_converter.h:294
ShPtr< CFGNode > getSwitchSuccessor(const ShPtr< CFGNode > &switchNode) const
Returns successor of the given switch node switchNode.
Definition: structure_converter.cpp:1657
ShPtr< CFGNode > popFromQueue(CFGNodeQueue &queue) const
Pop and return node from the given queue queue.
Definition: structure_converter.cpp:498
bool hasDefaultClause(const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor) const
Determines whether the given switch node switchNode has a default clause.
Definition: structure_converter.cpp:1724
void fixClonedGotos(ShPtr< Statement > statement)
Definition: structure_converter.cpp:130
llvm::Pass * basePass
Pass that have instantiated the converter.
Definition: structure_converter.h:257
std::vector< ShPtr< Statement > > findContinueOrBreakStatements(ShPtr< Statement > parent, SwitchParent sp)
Finds break and continue statements in cloned statements.
Definition: structure_converter.cpp:2138
MapLoopToCFGNode loopHeaders
Definition: structure_converter.h:276
void addGotoTargetIfNotExists(const ShPtr< CFGNode > &node)
Adds node node to the vector of the goto targets if it isn't already there.
Definition: structure_converter.cpp:2393
bool isIfElseStatementWithContinue(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:860
bool isIfStatement(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and if body is in the s...
Definition: structure_converter.cpp:721
void reduceToContinueStatement(ShPtr< CFGNode > node)
Reduces node node into a node which is terminated by switch statement.
Definition: structure_converter.cpp:1297
bool isInParentLoopOf(const ShPtr< CFGNode > &node, llvm::Loop *loop) const
Determines whether the given node node is in the parent loop of the given loop loop.
Definition: structure_converter.cpp:2338
std::unordered_map< ShPtr< Statement >, std::vector< ShPtr< Statement > >> MapStmtToClones
Definition: structure_converter.h:75
bool hasOnlySwitchOrClausesInPreds(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Determines whether the given switch clause clauseNode has only switch node or other clauses in predec...
Definition: structure_converter.cpp:1782
ShPtr< Statement > replaceBreakOrContinueOutsideLoop(ShPtr< Statement > statement, SwitchParent sp)
Replaces break/continue statements that are outside of loop with goto statements.
Definition: structure_converter.cpp:284
bool isNodeAfterAllSwitchClauses(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &switchNode) const
Determines whether the given node node is after all clauses of the given switch switchNode.
Definition: structure_converter.cpp:1673
CFGNode::CFGNodeSet statementsOnStack
Definition: structure_converter.h:303
void reduceToWhileTrueLoop(ShPtr< CFGNode > node)
Reduces node node into a node with while(true) loop.
Definition: structure_converter.cpp:1364
llvm::Loop * getLoopFor(const ShPtr< CFGNode > &node) const
Returns the innermost loop for the given node node. If node is not inside loop, returns nulptr.
Definition: structure_converter.cpp:2270
bool isIfElseStatement(const ShPtr< CFGNode > &node) const
Determines whether the given the given node node is an if statement with else clause.
Definition: structure_converter.cpp:704
std::vector< ShPtr< CFGNode > > CFGNodeVector
Definition: structure_converter.h:64
void completelyReduceLoop(ShPtr< CFGNode > loopNode)
Completely reduces the given loop node loopNode.
Definition: structure_converter.cpp:1608
MapTargetToGoto targetReferences
A map of references for goto targets.
Definition: structure_converter.h:288
std::unordered_set< llvm::BasicBlock * > BBSet
Definition: structure_converter.h:61
std::string getLabel(const ShPtr< CFGNode > &node) const
Returns a label of the given node node.
Definition: structure_converter.cpp:2423
std::vector< ShPtr< SwitchClause > > SwitchClauseVector
Definition: structure_converter.h:66
ShPtr< Statement > getIfClauseBodyClone(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor)
Creates a new body of the given if clause clause. The body of the clause is cloned.
Definition: structure_converter.cpp:1528
CFGNode::CFGNodeSet gotoTargetsSet
Definition: structure_converter.h:309
unsigned getTripCount(llvm::Loop *loop) const
Returns number of iterations for the given for loop loop. If loop is not a for loop,...
Definition: structure_converter.cpp:2362
std::unordered_map< llvm::BasicBlock *, ShPtr< CFGNode > > MapBBToCFGNode
Definition: structure_converter.h:69
ShPtr< LabelsHandler > labelsHandler
A handler of labels.
Definition: structure_converter.h:266
CFGNodeStack statementsStack
Definition: structure_converter.h:300
bool existsPathWithoutLoopsBetween(const ShPtr< CFGNode > &node1, const ShPtr< CFGNode > &node2) const
Determines whether exists direct path (without loops) between two given nodes node1 and node2.
Definition: structure_converter.cpp:650
MapBBToBBSet generatedPHINodes
A map of already generated phi nodes from specific basic blocks.
Definition: structure_converter.h:279
void detectBackEdges(ShPtr< CFGNode > cfg) const
Traverses the given control-flow graph cfg and detects all back edges.
Definition: structure_converter.cpp:364
void addClausesWithTheSameCond(ShPtr< SwitchStmt > switchStmt, const ExprVector &conds, const ShPtr< Statement > &clauseBody) const
Adds case clauses with different conditions, but with the same clause body to the given switch statem...
Definition: structure_converter.cpp:2042
bool reduceCFG(ShPtr< CFGNode > cfg)
Traverses the given control-flow graph cfg and tries to reduce some nodes to control-flow statements.
Definition: structure_converter.cpp:400
bool isClauseTerminatedByBreak(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchSuccessor) const
Determines whether the given switch clause clauseNode is terminated by a break statement.
Definition: structure_converter.cpp:2023
ShPtr< SwitchStmt > getSwitchStmt(const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, bool hasDefault)
Returns new switch statement which is created from the given switch node switchNode.
Definition: structure_converter.cpp:1841
CFGNode::CFGNodeSet generatedNodes
Definition: structure_converter.h:312
MapStmtToClones stmtClones
A map of clones of statement.
Definition: structure_converter.h:291
ShPtr< CFGNode > BFSFindFirst(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> pred) const
Traverses the given control-flow graph cfg using breadth-first search and returns first node which sa...
Definition: structure_converter.cpp:625
bool isReducibleClause(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, bool hasDefault=true) const
Determines whether the given switch clause clauseNode is a clause ready to be reduced.
Definition: structure_converter.cpp:1748
bool isNodeOutsideLoop(const ShPtr< CFGNode > &node, llvm::Loop *loop) const
Determines whether the given node node is outside of the given loop loop.
Definition: structure_converter.cpp:2320
bool canBeCloned(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be cloned.
Definition: structure_converter.cpp:1031
llvm::ScalarEvolution * scalarEvolution
Definition: structure_converter.h:263
bool fallsThroughToAnotherCase(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Determines whether the given switch clause clauseNode falls through to the another case clause or to ...
Definition: structure_converter.cpp:1813
bool canBeForLoop(llvm::Loop *loop) const
Determines whether the given loop loop can be a for loop.
Definition: structure_converter.cpp:2377
SwitchClauseVector getSwitchClauses(const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Returns a vector of clauses of the given switch node switchNode.
Definition: structure_converter.cpp:1871
ShPtr< SwitchClause > findFirstClauseWithSinglePred(const SwitchClauseVector &clauses) const
Returns first switch clause from the vector of clauses clauses which has only single predecessor.
Definition: structure_converter.cpp:1955
bool isIfStatementWithTerminatingBranch(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement and successor on the index succ is terminat...
Definition: structure_converter.cpp:741
void removeReducedSuccsOfSwitch(const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Removes reduced successors of the given switch node switchNode.
Definition: structure_converter.cpp:2064
bool isContinueStatement(const ShPtr< CFGNode > &node) const
Determines whether the given node node is terminated by continue statement.
Definition: structure_converter.cpp:895
bool isSwitchStatement(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a switch statement.
Definition: structure_converter.cpp:991
std::unordered_map< ShPtr< CFGNode >, std::vector< ShPtr< GotoStmt > >> MapTargetToGoto
Definition: structure_converter.h:74
bool isWhileTrueLoop(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a while(true) loop.
Definition: structure_converter.cpp:945
bool inspectCFGNode(ShPtr< CFGNode > node)
Inspects the given CFG node node and tries to reduce this and neighboring nodes to any control-flow s...
Definition: structure_converter.cpp:417
ShPtr< Statement > convertFuncBody(llvm::Function &func)
Converts body of the given LLVM function func into a sequence of statements in BIR which include cond...
Definition: structure_converter.cpp:87
bool isIfStatementWithTerminatingBranchToClone(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement and successor on the index succ is terminat...
Definition: structure_converter.cpp:774
bool isForLoop(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a reducible for loop.
Definition: structure_converter.cpp:927
bool isSequence(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be reduced with following node as a sequence.
Definition: structure_converter.cpp:669
ShPtr< Statement > getSuccessorsBodyClone(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &succ)
Creates a new body of the given node node successor succ. The body of the successor is cloned.
Definition: structure_converter.cpp:2105
bool BFSTraverse(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> inspectFunc) const
Traverses the given control-flow graph cfg using breadth-first search and inspect every node by funct...
Definition: structure_converter.cpp:570
CFGNodeVector gotoTargets
Definition: structure_converter.h:306
SwitchClauseVector sortSwitchClauses(const SwitchClauseVector &clauses, const ShPtr< CFGNode > &switchSuccessor) const
Returns sorted vector of switch clauses clauses.
Definition: structure_converter.cpp:1916
ShPtr< CFGNode > getLoopSuccessor(const ShPtr< CFGNode > &loopNode) const
Returns successor of the given loop node loopNode.
Definition: structure_converter.cpp:1590
void reduceToIfElseStatementWithBreakByGotoInLoop(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with goto stat...
Definition: structure_converter.cpp:1221
void addBranchMetadataToEndOfBodyIfNeeded(ShPtr< Statement > &body, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor) const
Adds metadata of the form "branch -> xxx" to the body of the given if statement (if needed).
Definition: structure_converter.cpp:2407
void cleanUp()
Cleans up the helper containers.
Definition: structure_converter.cpp:2432
ShPtr< Statement > getClauseBody(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, const CFGNode::CFGNodeSet &generated)
Returns new case clause of the switch statement which is created from the given switch node clauseNod...
Definition: structure_converter.cpp:1979
MapStmtToTargetNode gotoTargetsToCfgNodes
A map of goto target statements to cfg nodes.
Definition: structure_converter.h:285
ShPtr< Statement > getSuccessorsBody(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &succ)
Creates a new body of the given node node successor succ.
Definition: structure_converter.cpp:2089
void reduceToIfElseStatement(ShPtr< CFGNode > node)
Reduces node node and both its successors into a single node with if statement with else clause.
Definition: structure_converter.cpp:1094
std::unordered_map< ShPtr< Statement >, ShPtr< CFGNode > > MapStmtToTargetNode
Definition: structure_converter.h:73
ShPtr< LLVMValueConverter > converter
A converter from LLVM values to values in BIR.
Definition: structure_converter.h:272
MapStmtToTargetNode loopTargets
A map of targets for break and continue statements.
Definition: structure_converter.h:282
void addUnvisitedSuccessorsToQueueInLoop(const ShPtr< CFGNode > &node, CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited, llvm::Loop *loop) const
Adds all unvisited successors inside loop loop of the given node node to the queue toBeVisited and al...
Definition: structure_converter.cpp:543
ShPtr< Module > resModule
The resulting module in BIR.
Definition: structure_converter.h:315
void reduceSwitchStatement(ShPtr< CFGNode > node)
Reduces node node into a node with the switch statement.
Definition: structure_converter.cpp:1633
ShPtr< CFGNode > createCFG(llvm::BasicBlock &root)
Creates control-flow graph of the function from the given root basic block root.
Definition: structure_converter.cpp:325
void addUnvisitedSuccessorsToQueue(const ShPtr< CFGNode > &node, CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited) const
Adds all unvisited successors of the given node node to the queue toBeVisited and also to the set of ...
Definition: structure_converter.cpp:513
void structureByGotos(ShPtr< CFGNode > cfg)
Completely structures given CFG cfg using goto statements.
Definition: structure_converter.cpp:1439
bool isLoopHeader(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a loop header.
Definition: structure_converter.cpp:2287
std::pair< ExprVector, ShPtr< CFGNode > > SwitchClause
Definition: structure_converter.h:59
void insertClonedLoopTargets(ShPtr< Statement > origParent, ShPtr< Statement > newParent)
Inserts cloned break/continue stmts in case they need replacing.
Definition: structure_converter.cpp:2122
StructureConverter(llvm::Pass *basePass, ShPtr< LLVMValueConverter > conv, ShPtr< Module > module)
Constructs a new structure converter.
Definition: structure_converter.cpp:72
bool BFSTraverseLoop(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> inspectFunc) const
Traverses the given control-flow graph cfg of a loop using breadth-first search and inspect every nod...
Definition: structure_converter.cpp:598
void reduceToSequenceClone(ShPtr< CFGNode > node)
Reduces node node and its only successor into a single node which contains merged bodies of both node...
Definition: structure_converter.cpp:1077
void reduceToIfElseStatementWithContinue(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with continue ...
Definition: structure_converter.cpp:1257
A mixin to make classes non-copyable.
Definition: non_copyable.h:27
ShPtr< Module > module
The current module.
Definition: hll_writer.cpp:100
Definition: itanium_ast_ctypes_parser.h:12
A library providing API for working with back-end IR.
std::shared_ptr< T > ShPtr
An alias for a shared pointer.
Definition: smart_ptr.h:18
std::vector< ShPtr< Expression > > ExprVector
Vector of expressions.
Definition: types.h:99
SwitchParent
Enum class to distinguish when parent of statement is switch or not.
Definition: structure_converter.h:46
Definition: archive_wrapper.h:19
A mixin to make classes non-copyable.
Declarations, aliases, macros, etc. for the use of smart pointers.
Aliases for several useful types.