1 /*
2 * Copyright 2015 Sven Verdoolaege. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials provided
14 * with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY SVEN VERDOOLAEGE ''AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SVEN VERDOOLAEGE OR
20 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
23 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * The views and conclusions contained in the software and documentation
29 * are those of the authors and should not be interpreted as
30 * representing official policies, either expressed or implied, of
31 * Sven Verdoolaege.
32 */
33
34 #include "config.h"
35
36 #include "clang.h"
37 #include "clang_compatibility.h"
38 #include "killed_locals.h"
39
40 using namespace std;
41 using namespace clang;
42
43 /* Return the file offset of the expansion location of "Loc".
44 */
getExpansionOffset(SourceManager & SM,SourceLocation Loc)45 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
46 {
47 return SM.getFileOffset(SM.getExpansionLoc(Loc));
48 }
49
50 /* Given a DeclRefExpr or an ArraySubscriptExpr, return a pointer
51 * to the base DeclRefExpr.
52 * If the expression is something other than a nested ArraySubscriptExpr
53 * with a DeclRefExpr at the base, then return NULL.
54 */
extract_array_base(Expr * expr)55 static DeclRefExpr *extract_array_base(Expr *expr)
56 {
57 while (isa<ArraySubscriptExpr>(expr)) {
58 expr = (cast<ArraySubscriptExpr>(expr))->getBase();
59 expr = pet_clang_strip_casts(expr);
60 }
61 return dyn_cast<DeclRefExpr>(expr);
62 }
63
64 /* Add "decl" to the set of local variables, provided it is a ValueDecl.
65 */
add_local(Decl * decl)66 void pet_killed_locals::add_local(Decl *decl)
67 {
68 ValueDecl *vd;
69
70 vd = dyn_cast<ValueDecl>(decl);
71 if (vd)
72 locals.insert(vd);
73 }
74
75 /* Add all variables declared by "stmt" to the set of local variables.
76 */
add_locals(DeclStmt * stmt)77 void pet_killed_locals::add_locals(DeclStmt *stmt)
78 {
79 if (stmt->isSingleDecl()) {
80 add_local(stmt->getSingleDecl());
81 } else {
82 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
83 unsigned n = group.size();
84 for (unsigned i = 0; i < n; ++i)
85 add_local(group[i]);
86 }
87 }
88
89 /* Set this->addr_end to the end of the address_of expression "expr".
90 */
set_addr_end(UnaryOperator * expr)91 void pet_killed_locals::set_addr_end(UnaryOperator *expr)
92 {
93 addr_end = getExpansionOffset(SM, end_loc(expr));
94 }
95
96 /* Given an expression of type ArraySubscriptExpr or DeclRefExpr,
97 * check two things
98 * - is the variable used inside the scop?
99 * - is the variable used after the scop or can a pointer be taken?
100 * Return true if the traversal should continue.
101 *
102 * Reset the pointer to the end of the latest address-of expression
103 * such that only the first array or scalar is considered to have
104 * its address taken. In particular, accesses inside the indices
105 * of the array should not be considered to have their address taken.
106 *
107 * If the variable is not one of the local variables or
108 * if the access appears inside an expression that was already handled,
109 * then simply return.
110 *
111 * Otherwise, the expression is handled and "expr_end" is updated
112 * to prevent subexpressions with the same base expression
113 * from being handled as well.
114 *
115 * If a higher-dimensional slice of an array is accessed or
116 * if the access appears inside an address-of expression,
117 * then a pointer may leak, so the variable should not be killed.
118 * Similarly, if the access appears after the end of the scop,
119 * then the variable should not be killed.
120 *
121 * Otherwise, if the access appears inside the scop, then
122 * keep track of the fact that the variable was accessed at least once
123 * inside the scop.
124 */
check_decl_in_expr(Expr * expr)125 bool pet_killed_locals::check_decl_in_expr(Expr *expr)
126 {
127 unsigned loc;
128 int depth;
129 DeclRefExpr *ref;
130 ValueDecl *decl;
131 unsigned old_addr_end;
132
133 ref = extract_array_base(expr);
134 if (!ref)
135 return true;
136
137 old_addr_end = addr_end;
138 addr_end = 0;
139
140 decl = ref->getDecl();
141 if (locals.find(decl) == locals.end())
142 return true;
143 loc = getExpansionOffset(SM, begin_loc(expr));
144 if (loc <= expr_end)
145 return true;
146
147 expr_end = getExpansionOffset(SM, end_loc(ref));
148 depth = pet_clang_array_depth(expr->getType());
149 if (loc >= scop_end || loc <= old_addr_end || depth != 0)
150 locals.erase(decl);
151 if (loc >= scop_start && loc <= scop_end)
152 accessed.insert(decl);
153
154 return locals.size() != 0;
155 }
156
157 /* Remove the local variables that may be accessed inside "stmt" after
158 * the scop starting at "start" and ending at "end", or that
159 * are not accessed at all inside that scop.
160 *
161 * If there are no local variables that could potentially be killed,
162 * then simply return.
163 *
164 * Otherwise, scan "stmt" for any potential use of the variables
165 * after the scop. This includes a possible pointer being taken
166 * to (part of) the variable. If there is any such use, then
167 * the variable is removed from the set of local variables.
168 *
169 * At the same time, keep track of the variables that are
170 * used anywhere inside the scop. At the end, replace the local
171 * variables with the intersection with these accessed variables.
172 */
remove_accessed_after(Stmt * stmt,unsigned start,unsigned end)173 void pet_killed_locals::remove_accessed_after(Stmt *stmt, unsigned start,
174 unsigned end)
175 {
176 set<ValueDecl *> accessed_local;
177
178 if (locals.size() == 0)
179 return;
180 scop_start = start;
181 scop_end = end;
182 addr_end = 0;
183 expr_end = 0;
184 TraverseStmt(stmt);
185 set_intersection(locals.begin(), locals.end(),
186 accessed.begin(), accessed.end(),
187 inserter(accessed_local, accessed_local.begin()));
188 locals = accessed_local;
189 }
190