1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/* ###
* IP: GHIDRA
*
* 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.
*/
#ifndef __CPUI_MERGE__
#define __CPUI_MERGE__
/// \file merge.hh
/// \brief Utilities for merging low-level Varnodes into high-level variables
#include "op.hh"
/// \brief A record for caching a Cover intersection test between two HighVariable objects
///
/// This is just a pair of HighVariable objects that can be used as a map key. The main
/// Merge class uses it to cache intersection test results between the two variables in
/// a map.
class HighEdge {
friend class Merge;
HighVariable *a; ///< First HighVariable of the pair
HighVariable *b; ///< Second HighVariable of the pair
public:
/// \brief Comparator
bool operator<(const HighEdge &op2) const { if (a==op2.a) return (b<op2.b); return (a<op2.a); }
HighEdge(HighVariable *c,HighVariable *d) { a=c; b=d; } ///< Constructor
};
/// \brief Helper class associating a Varnode with the block where it is defined
///
/// This class explicitly stores a Varnode with the index of the BlockBasic that defines it.
/// If a Varnode does not have a defining PcodeOp it is assigned an index of 0.
/// This facilitates quicker sorting of Varnodes based on their defining block.
class BlockVarnode {
int4 index; ///< Index of BlockBasic defining Varnode
Varnode *vn; ///< The Varnode itself
public:
void set(Varnode *v); ///< Set \b this as representing the given Varnode
bool operator<(const BlockVarnode &op2) const { return (index < op2.index); } ///< Comparator
Varnode *getVarnode(void) const { return vn; } ///< Get the Varnode represented by \b this
int4 getIndex(void) const { return index; } ///< Get the Varnode's defining block index
static int4 findFront(int4 blocknum,const vector<BlockVarnode> &list);
};
class Funcdata;
/// \brief Class for merging low-level Varnodes into high-level HighVariables
///
/// As a node in Single Static Assignment (SSA) form, a Varnode has at most one defining
/// operation. To get a suitable notion of a single high-level variable (HighVariable) that
/// may be reassigned at multiple places in a single function, individual Varnode objects
/// can be \e merged into a HighVariable object. Varnode objects may be merged in this way
/// if there is no pairwise intersection between each Varnode's Cover, the ranges of code
/// where the Varnode holds its value.
///
/// For a given function, this class attempts to merge Varnodes using various strategies
/// and keeps track of Cover intersections to facilitate the process. Merge strategies break up
/// into two general categories: \b forced merges, and \b speculative merges. Forced merges
/// \e must happen, and extra Varnodes may be added to split up problematic covers to enforce it.
/// Forced merges include:
/// - Merging inputs and outputs of MULTIEQUAL and INDIRECT operations
/// - Merging Varnodes at global (persistent) storage locations
/// - Merging Varnodes at mapped stack locations
///
/// Speculative merges are attempted to reduce the overall number of variables defined by a
/// function, but any given merge attempt is abandoned if there are Cover intersections. No
/// modification is made to the data-flow to force the merge. Speculative merges include:
/// - Merging an input and output Varnode of a single p-code op
/// - Merging Varnodes that hold the same data-type
class Merge {
Funcdata &data; ///< The function containing the Varnodes to be merged
map<HighEdge,bool> highedgemap; ///< A cache of intersection tests, sorted by HighVariable pair
vector<PcodeOp *> copyTrims; ///< COPY ops inserted to facilitate merges
bool updateHigh(HighVariable *a); ///< Make sure given HighVariable's Cover is up-to-date
void purgeHigh(HighVariable *high); ///< Remove cached intersection tests for a given HighVariable
bool blockIntersection(HighVariable *a,HighVariable *b,int4 blk);
static bool mergeTestRequired(HighVariable *high_out,HighVariable *high_in);
static bool mergeTestAdjacent(HighVariable *high_out,HighVariable *high_in);
static bool mergeTestSpeculative(HighVariable *high_out,HighVariable *high_in);
static bool mergeTestBasic(Varnode *vn);
static void findSingleCopy(HighVariable *high,vector<Varnode *> &singlelist);
static bool compareHighByBlock(const HighVariable *a,const HighVariable *b);
static bool compareCopyByInVarnode(PcodeOp *op1,PcodeOp *op2);
static bool shadowedVarnode(const Varnode *vn);
static void findAllIntoCopies(HighVariable *high,vector<PcodeOp *> ©Ins,bool filterTemps);
void collectCovering(vector<Varnode *> &vlist,HighVariable *high,PcodeOp *op);
bool collectCorrectable(const vector<Varnode *> &vlist,list<PcodeOp *> &oplist,vector<int4> &slotlist,
PcodeOp *op);
PcodeOp *allocateCopyTrim(Varnode *inVn,Datatype *ct,const Address &addr);
void snipReads(Varnode *vn,list<PcodeOp *> &markedop);
void snipIndirect(PcodeOp *indop);
void eliminateIntersect(Varnode *vn,const vector<BlockVarnode> &blocksort);
void unifyAddress(VarnodeLocSet::const_iterator startiter,VarnodeLocSet::const_iterator enditer);
void trimOpOutput(PcodeOp *op);
void trimOpInput(PcodeOp *op,int4 slot);
void mergeRangeMust(VarnodeLocSet::const_iterator startiter,VarnodeLocSet::const_iterator enditer);
void mergeOp(PcodeOp *op);
void mergeIndirect(PcodeOp *indop);
void mergeLinear(vector<HighVariable *> &highvec);
bool merge(HighVariable *high1,HighVariable *high2,bool isspeculative);
bool checkCopyPair(HighVariable *high,PcodeOp *domOp,PcodeOp *subOp);
void buildDominantCopy(HighVariable *high,vector<PcodeOp *> ©,int4 pos,int4 size);
void markRedundantCopies(HighVariable *high,vector<PcodeOp *> ©,int4 pos,int4 size);
void processHighDominantCopy(HighVariable *high);
void processHighRedundantCopy(HighVariable *high);
public:
Merge(Funcdata &fd) : data(fd) {} ///< Construct given a specific function
bool intersection(HighVariable *a,HighVariable *b);
bool inflateTest(Varnode *a,HighVariable *high);
void inflate(Varnode *a,HighVariable *high);
bool mergeTest(HighVariable *high,vector<HighVariable *> &tmplist);
void mergeOpcode(OpCode opc);
void mergeByDatatype(VarnodeLocSet::const_iterator startiter,VarnodeLocSet::const_iterator enditer);
void mergeAddrTied(void);
void mergeMarker(void);
void mergeAdjacent(void);
void mergeMultiEntry(void);
bool hideShadows(HighVariable *high);
void processCopyTrims(void);
void markInternalCopies(void);
#ifdef MERGEMULTI_DEBUG
void verifyHighCovers(void);
#endif
};
/// \brief Compare HighVariables by the blocks they cover
///
/// This comparator sorts, based on:
/// - Index of the first block containing cover for the HighVariable
/// - Address of the first instance
/// - Address of the defining p-code op
/// - Storage address
///
/// \param a is the first HighVariable to compare
/// \param b is the second HighVariable
/// \return \b true if the first HighVariable should be ordered before the second
inline bool Merge::compareHighByBlock(const HighVariable *a,const HighVariable *b)
{
int4 result = a->wholecover.compareTo(b->wholecover);
if ( result == 0 ) {
Varnode *v1 = a->getInstance( 0 );
Varnode *v2 = b->getInstance( 0 );
if ( v1->getAddr() == v2->getAddr() ) {
PcodeOp *def1 = v1->getDef();
PcodeOp *def2 = v2->getDef();
if ( def1 == (PcodeOp *) 0 ) {
return true;
}
else if ( def2 == (PcodeOp *) 0 ) {
return false;
}
return (def1->getAddr() < def2->getAddr());
}
return (v1->getAddr() < v2->getAddr());
}
return (result < 0);
}
#endif