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 "killed_locals.h"
  38
  39 using namespace std;
  40 using namespace clang;
  41
  42 /* Return the file offset of the expansion location of "Loc".
  43  */
  44 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
  45 {
  46         return SM.getFileOffset(SM.getExpansionLoc(Loc));
  47 }
  48
  49 /* Given a DeclRefExpr or an ArraySubscriptExpr, return a pointer
  50  * to the base DeclRefExpr.
  51  * If the expression is something other than a nested ArraySubscriptExpr
  52  * with a DeclRefExpr at the base, then return NULL.
  53  */
  54 static DeclRefExpr *extract_array_base(Expr *expr)
  55 {
  56         while (isa<ArraySubscriptExpr>(expr)) {
  57                 expr = (cast<ArraySubscriptExpr>(expr))->getBase();
  58                 expr = pet_clang_strip_casts(expr);
  59         }
  60         return dyn_cast<DeclRefExpr>(expr);
  61 }
  62
  63 /* Add "decl" to the set of local variables, provided it is a ValueDecl.
  64  */
  65 void pet_killed_locals::add_local(Decl *decl)
  66 {
  67         ValueDecl *vd;
  68
  69         vd = dyn_cast<ValueDecl>(decl);
  70         if (vd)
  71                 locals.insert(vd);
  72 }
  73
  74 /* Add all variables declared by "stmt" to the set of local variables.
  75  */
  76 void pet_killed_locals::add_locals(DeclStmt *stmt)
  77 {
  78         if (stmt->isSingleDecl()) {
  79                 add_local(stmt->getSingleDecl());
  80         } else {
  81                 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
  82                 unsigned n = group.size();
  83                 for (unsigned i = 0; i < n; ++i)
  84                         add_local(group[i]);
  85         }
  86 }
  87
  88 /* Set this->addr_end to the end of the address_of expression "expr".
  89  */
  90 void pet_killed_locals::set_addr_end(UnaryOperator *expr)
  91 {
  92         addr_end = getExpansionOffset(SM, expr->getLocEnd());
  93 }
  94
  95 /* Given an expression of type ArraySubscriptExpr or DeclRefExpr,
  96  * check two things
  97  * - is the variable used inside the scop?
  98  * - is the variable used after the scop or can a pointer be taken?
  99  * Return true if the traversal should continue.
 100  *
 101  * Reset the pointer to the end of the latest address-of expression
 102  * such that only the first array or scalar is considered to have
 103  * its address taken.  In particular, accesses inside the indices
 104  * of the array should not be considered to have their address taken.
 105  *
 106  * If the variable is not one of the local variables or
 107  * if the access appears inside an expression that was already handled,
 108  * then simply return.
 109  *
 110  * Otherwise, the expression is handled and "expr_end" is updated
 111  * to prevent subexpressions with the same base expression
 112  * from being handled as well.
 113  *
 114  * If a higher-dimensional slice of an array is accessed or
 115  * if the access appears inside an address-of expression,
 116  * then a pointer may leak, so the variable should not be killed.
 117  * Similarly, if the access appears after the end of the scop,
 118  * then the variable should not be killed.
 119  *
 120  * Otherwise, if the access appears inside the scop, then
 121  * keep track of the fact that the variable was accessed at least once
 122  * inside the scop.
 123  */
 124 bool pet_killed_locals::check_decl_in_expr(Expr *expr)
 125 {
 126         unsigned loc;
 127         int depth;
 128         DeclRefExpr *ref;
 129         ValueDecl *decl;
 130         unsigned old_addr_end;
 131
 132         ref = extract_array_base(expr);
 133         if (!ref)
 134                 return true;
 135
 136         old_addr_end = addr_end;
 137         addr_end = 0;
 138
 139         decl = ref->getDecl();
 140         if (locals.find(decl) == locals.end())
 141                 return true;
 142         loc = getExpansionOffset(SM, expr->getLocStart());
 143         if (loc <= expr_end)
 144                 return true;
 145
 146         expr_end = getExpansionOffset(SM, ref->getLocEnd());
 147         depth = pet_clang_array_depth(expr->getType());
 148         if (loc >= scop_end || loc <= old_addr_end || depth != 0)
 149                 locals.erase(decl);
 150         if (loc >= scop_start && loc <= scop_end)
 151                 accessed.insert(decl);
 152
 153         return locals.size() != 0;
 154 }
 155
 156 /* Remove the local variables that may be accessed inside "stmt" after
 157  * the scop starting at "start" and ending at "end", or that
 158  * are not accessed at all inside that scop.
 159  *
 160  * If there are no local variables that could potentially be killed,
 161  * then simply return.
 162  *
 163  * Otherwise, scan "stmt" for any potential use of the variables
 164  * after the scop.  This includes a possible pointer being taken
 165  * to (part of) the variable.  If there is any such use, then
 166  * the variable is removed from the set of local variables.
 167  *
 168  * At the same time, keep track of the variables that are
 169  * used anywhere inside the scop.  At the end, replace the local
 170  * variables with the intersection with these accessed variables.
 171  */
 172 void pet_killed_locals::remove_accessed_after(Stmt *stmt, unsigned start,
 173         unsigned end)
 174 {
 175         set<ValueDecl *> accessed_local;
 176
 177         if (locals.size() == 0)
 178                 return;
 179         scop_start = start;
 180         scop_end = end;
 181         addr_end = 0;
 182         expr_end = 0;
 183         TraverseStmt(stmt);
 184         set_intersection(locals.begin(), locals.end(),
 185                          accessed.begin(), accessed.end(),
 186                          inserter(accessed_local, accessed_local.begin()));
 187         locals = accessed_local;
 188 }