scan.h

   1 #include <map>
   2
   3 #include <clang/Basic/SourceManager.h>
   4 #include <clang/AST/Decl.h>
   5 #include <clang/AST/Stmt.h>
   6 #include <clang/Lex/Preprocessor.h>
   7
   8 #include <isl/ctx.h>
   9 #include <isl/map.h>
  10 #include <isl/val.h>
  11
  12 #include "context.h"
  13 #include "inliner.h"
  14 #include "loc.h"
  15 #include "scop.h"
  16 #include "summary.h"
  17 #include "tree.h"
  18
  19 namespace clang {
  20
  21 #ifndef HAVE_STMTRANGE
  22 /* StmtRange was replaced by iterator_range in more recent versions of clang.
  23  * Implement a StmtRange in terms of this iterator_range if StmtRange
  24  * is not available.
  25  */
  26 struct StmtRange : std::pair<StmtIterator,StmtIterator> {
  27         StmtRange(const StmtIterator &begin, const StmtIterator &end) :
  28                 std::pair<StmtIterator,StmtIterator>(begin, end) {}
  29         StmtRange(Stmt::child_range range) :
  30                 std::pair<StmtIterator,StmtIterator>(range.begin(),
  31                                                         range.end()) {}
  32 };
  33 #endif
  34
  35 };
  36
  37 /* The location of the scop, as delimited by scop and endscop
  38  * pragmas by the user.
  39  * "start_line" is the line number of the start position.
  40  */
  41 struct ScopLoc {
  42         ScopLoc() : end(0) {}
  43
  44         unsigned start_line;
  45         unsigned start;
  46         unsigned end;
  47 };
  48
  49 /* The information extracted from a pragma pencil independent.
  50  * We currently only keep track of the line number where
  51  * the pragma appears.
  52  */
  53 struct Independent {
  54         Independent(unsigned line) : line(line) {}
  55
  56         unsigned line;
  57 };
  58
  59 /* Compare two TypeDecl pointers based on their names.
  60  */
  61 struct less_name {
  62         bool operator()(const clang::TypeDecl *x,
  63                         const clang::TypeDecl *y) {
  64                 return x->getNameAsString().compare(y->getNameAsString()) < 0;
  65         }
  66 };
  67
  68 /* The PetTypes structure collects a set of RecordDecl and
  69  * TypedefNameDecl pointers.
  70  * The pointers are sorted using a fixed order.  The actual order
  71  * is not important, only that it is consistent across platforms.
  72  */
  73 struct PetTypes {
  74         std::set<clang::RecordDecl *, less_name> records;
  75         std::set<clang::TypedefNameDecl *, less_name> typedefs;
  76
  77         void insert(clang::RecordDecl *decl) {
  78                 records.insert(decl);
  79         }
  80         void insert(clang::TypedefNameDecl *decl) {
  81                 typedefs.insert(decl);
  82         }
  83 };
  84
  85 struct PetScan {
  86         clang::Preprocessor &PP;
  87         clang::ASTContext &ast_context;
  88         /* The DeclContext of the function containing the scop.
  89          */
  90         clang::DeclContext *decl_context;
  91         /* If autodetect is false, then loc contains the location
  92          * of the scop to be extracted.
  93          */
  94         ScopLoc &loc;
  95         isl_ctx *ctx;
  96         pet_options *options;
  97         /* Set if the pet_scop returned by an extract method only
  98          * represents part of the input tree.
  99          */
 100         bool partial;
 101
 102         /* A cache of size expressions for array types as computed
 103          * by PetScan::get_array_size.
 104          */
 105         std::map<const clang::Type *, pet_expr *> type_size;
 106
 107         /* A cache of funtion summaries for function declarations
 108          * as extracted by PetScan::get_summary.
 109          */
 110         std::map<clang::FunctionDecl *, pet_function_summary *> summary_cache;
 111
 112         /* A union of mappings of the form
 113          *      { identifier[] -> [i] : lower_bound <= i <= upper_bound }
 114          */
 115         isl_union_map *value_bounds;
 116
 117         /* The line number of the previously considered Stmt. */
 118         unsigned last_line;
 119         /* The line number of the Stmt currently being considered. */
 120         unsigned current_line;
 121         /* Information about the independent pragmas in the source code. */
 122         std::vector<Independent> &independent;
 123
 124         /* All variables that have already been declared
 125          * in the current compound statement.
 126          */
 127         std::vector<clang::VarDecl *> declarations;
 128         /* Sequence number of the next rename. */
 129         int n_rename;
 130         /* Have the declared names been collected? */
 131         bool declared_names_collected;
 132         /* The names of the variables declared in decl_context,
 133          * if declared_names_collected is set.
 134          */
 135         std::set<std::string> declared_names;
 136         /* A set of names known to be in use. */
 137         std::set<std::string> used_names;
 138
 139         /* Sequence number of the next temporary inlined argument variable. */
 140         int n_arg;
 141
 142         PetScan(clang::Preprocessor &PP, clang::ASTContext &ast_context,
 143                 clang::DeclContext *decl_context, ScopLoc &loc,
 144                 pet_options *options, __isl_take isl_union_map *value_bounds,
 145                 std::vector<Independent> &independent) :
 146                 PP(PP),
 147                 ast_context(ast_context), decl_context(decl_context), loc(loc),
 148                 ctx(isl_union_map_get_ctx(value_bounds)),
 149                 options(options), partial(false), value_bounds(value_bounds),
 150                 last_line(0), current_line(0),
 151                 independent(independent), n_rename(0),
 152                 declared_names_collected(false), n_arg(0) { }
 153
 154         ~PetScan();
 155
 156         struct pet_scop *scan(clang::FunctionDecl *fd);
 157
 158         static __isl_give isl_val *extract_int(isl_ctx *ctx,
 159                 clang::IntegerLiteral *expr);
 160         __isl_give pet_expr *get_array_size(const clang::Type *type);
 161         struct pet_array *extract_array(__isl_keep isl_id *id,
 162                 PetTypes *types, __isl_keep pet_context *pc);
 163 private:
 164         void set_current_stmt(clang::Stmt *stmt);
 165         bool is_current_stmt_marked_independent();
 166
 167         void collect_declared_names();
 168         void add_new_used_names(const std::set<std::string> &used_names);
 169         bool name_in_use(const std::string &name, clang::Decl *decl);
 170         std::string generate_new_name(const std::string &name);
 171
 172         __isl_give pet_tree *add_kills(__isl_take pet_tree *tree,
 173                 std::set<clang::ValueDecl *> locals);
 174
 175         struct pet_scop *scan(clang::Stmt *stmt);
 176
 177         struct pet_scop *scan_arrays(struct pet_scop *scop,
 178                 __isl_keep pet_context *pc);
 179         struct pet_array *extract_array(clang::ValueDecl *decl,
 180                 PetTypes *types, __isl_keep pet_context *pc);
 181         struct pet_array *extract_array(__isl_keep isl_id_list *delcs,
 182                 PetTypes *types, __isl_keep pet_context *pc);
 183         __isl_give pet_expr *set_upper_bounds(__isl_take pet_expr *expr,
 184                 const clang::Type *type, int pos);
 185         struct pet_array *set_upper_bounds(struct pet_array *array,
 186                 const clang::Type *type, __isl_keep pet_context *pc);
 187
 188         __isl_give pet_tree *insert_initial_declarations(
 189                 __isl_take pet_tree *tree, int n_decl,
 190                 clang::StmtRange stmt_range);
 191         __isl_give pet_tree *extract(clang::Stmt *stmt,
 192                 bool skip_declarations = false);
 193         __isl_give pet_tree *extract(clang::StmtRange stmt_range, bool block,
 194                 bool skip_declarations);
 195         __isl_give pet_tree *extract(clang::IfStmt *stmt);
 196         __isl_give pet_tree *extract(clang::WhileStmt *stmt);
 197         __isl_give pet_tree *extract(clang::CompoundStmt *stmt,
 198                 bool skip_declarations = false);
 199         __isl_give pet_tree *extract(clang::LabelStmt *stmt);
 200         __isl_give pet_tree *extract(clang::Decl *decl);
 201         __isl_give pet_tree *extract(clang::DeclStmt *expr);
 202
 203         __isl_give pet_loc *construct_pet_loc(clang::SourceRange range,
 204                 bool skip_semi);
 205         __isl_give pet_tree *extract(__isl_take pet_expr *expr,
 206                 clang::SourceRange range, bool skip_semi);
 207         __isl_give pet_tree *update_loc(__isl_take pet_tree *tree,
 208                 clang::Stmt *stmt);
 209
 210         struct pet_scop *extract_scop(__isl_take pet_tree *tree);
 211
 212         clang::BinaryOperator *initialization_assignment(clang::Stmt *init);
 213         clang::Decl *initialization_declaration(clang::Stmt *init);
 214         clang::ValueDecl *extract_induction_variable(clang::BinaryOperator *stmt);
 215         clang::VarDecl *extract_induction_variable(clang::Stmt *init,
 216                                 clang::Decl *stmt);
 217         __isl_give pet_expr *extract_unary_increment(clang::UnaryOperator *op,
 218                                 clang::ValueDecl *iv);
 219         __isl_give pet_expr *extract_binary_increment(
 220                                 clang::BinaryOperator *op,
 221                                 clang::ValueDecl *iv);
 222         __isl_give pet_expr *extract_compound_increment(
 223                                 clang::CompoundAssignOperator *op,
 224                                 clang::ValueDecl *iv);
 225         __isl_give pet_expr *extract_increment(clang::ForStmt *stmt,
 226                                 clang::ValueDecl *iv);
 227         __isl_give pet_tree *extract_for(clang::ForStmt *stmt);
 228         __isl_give pet_tree *extract_expr_stmt(clang::Stmt *stmt);
 229         __isl_give pet_tree *extract_inlined_call(clang::CallExpr *call,
 230                 clang::FunctionDecl *fd);
 231         int set_inliner_arguments(pet_inliner &inliner, clang::CallExpr *call,
 232                 clang::FunctionDecl *fd);
 233
 234         __isl_give pet_expr *extract_assume(clang::Expr *expr);
 235         __isl_give pet_function_summary *get_summary(clang::FunctionDecl *fd);
 236         __isl_give pet_expr *set_summary(__isl_take pet_expr *expr,
 237                 clang::FunctionDecl *fd);
 238         __isl_give pet_expr *extract_argument(clang::FunctionDecl *fd, int pos,
 239                 clang::Expr *expr, bool detect_writes);
 240         __isl_give pet_expr *extract_expr(const llvm::APInt &val);
 241         __isl_give pet_expr *extract_expr(clang::Expr *expr);
 242         __isl_give pet_expr *extract_expr(clang::UnaryOperator *expr);
 243         __isl_give pet_expr *extract_expr(clang::BinaryOperator *expr);
 244         __isl_give pet_expr *extract_expr(clang::ImplicitCastExpr *expr);
 245         __isl_give pet_expr *extract_expr(clang::IntegerLiteral *expr);
 246         __isl_give pet_expr *extract_expr(clang::EnumConstantDecl *expr);
 247         __isl_give pet_expr *extract_expr(clang::FloatingLiteral *expr);
 248         __isl_give pet_expr *extract_expr(clang::ParenExpr *expr);
 249         __isl_give pet_expr *extract_expr(clang::ConditionalOperator *expr);
 250         __isl_give pet_expr *extract_expr(clang::CallExpr *expr);
 251         __isl_give pet_expr *extract_expr(clang::CStyleCastExpr *expr);
 252
 253         __isl_give pet_expr *extract_access_expr(clang::QualType qt,
 254                 __isl_take pet_expr *index);
 255         __isl_give pet_expr *extract_access_expr(clang::Expr *expr);
 256         __isl_give pet_expr *extract_access_expr(clang::ValueDecl *decl);
 257
 258         __isl_give pet_expr *extract_index_expr(
 259                 clang::ArraySubscriptExpr *expr);
 260         __isl_give pet_expr *extract_index_expr(clang::Expr *expr);
 261         __isl_give pet_expr *extract_index_expr(clang::ImplicitCastExpr *expr);
 262         __isl_give pet_expr *extract_index_expr(clang::DeclRefExpr *expr);
 263         __isl_give pet_expr *extract_index_expr(clang::ValueDecl *decl);
 264         __isl_give pet_expr *extract_index_expr(clang::MemberExpr *expr);
 265
 266         __isl_give isl_val *extract_int(clang::Expr *expr);
 267         __isl_give isl_val *extract_int(clang::ParenExpr *expr);
 268
 269         clang::FunctionDecl *find_decl_from_name(clang::CallExpr *call,
 270                 std::string name);
 271         clang::FunctionDecl *get_summary_function(clang::CallExpr *call);
 272
 273         void report(clang::SourceRange range, unsigned id);
 274         void report(clang::Stmt *stmt, unsigned id);
 275         void report(clang::Decl *decl, unsigned id);
 276         void unsupported(clang::Stmt *stmt);
 277         void report_unsupported_unary_operator(clang::Stmt *stmt);
 278         void report_unsupported_statement_type(clang::Stmt *stmt);
 279         void report_prototype_required(clang::Stmt *stmt);
 280         void report_missing_increment(clang::Stmt *stmt);
 281         void report_missing_summary_function(clang::Stmt *stmt);
 282         void report_missing_summary_function_body(clang::Stmt *stmt);
 283         void report_unsupported_inline_function_argument(clang::Stmt *stmt);
 284         void report_unsupported_declaration(clang::Decl *decl);
 285 };