killed_locals.cc

   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  */
  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  */
  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  */
  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  */
  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  */
  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  */
 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  */
 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 }