scan.h

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