*/

#include "config.h"

#include <string.h>

#include <set>

#include <map>

#include <iostream>

#include <sstream>

#include <llvm/Support/raw_ostream.h>

#include <clang/AST/ASTContext.h>

#include <clang/AST/ASTDiagnostic.h>

#include <clang/AST/Attr.h>

#include <clang/AST/Expr.h>

#include <clang/AST/RecursiveASTVisitor.h>

#include <isl/id.h>

#include <isl/space.h>

#include <isl/aff.h>

#include <isl/set.h>

#include <isl/union_set.h>

#include "aff.h"

#include "array.h"

#include "clang.h"

#include "context.h"

#include "expr.h"

#include "expr_plus.h"

#include "id.h"

#include "inliner.h"

#include "inlined_calls.h"

#include "killed_locals.h"

#include "nest.h"

#include "options.h"

#include "scan.h"

#include "scop.h"

#include "scop_plus.h"

#include "substituter.h"

#include "tree.h"

#include "tree2scop.h"

using namespace std;

using namespace clang;

static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)

}

static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)

}

#ifdef GETTYPEINFORETURNSTYPEINFO

static int size_in_bytes(ASTContext &context, QualType type)

{

return context.getTypeInfo(type).Width / 8;

}

#else

static int size_in_bytes(ASTContext &context, QualType type)

{

return context.getTypeInfo(type).first / 8;

}

#endif

static bool const_base(QualType qt)

}

PetScan::~PetScan()

{

std::map<const Type *, pet_expr *>::iterator it;

std::map<FunctionDecl *, pet_function_summary *>::iterator it_s;

for (it = type_size.begin(); it != type_size.end(); ++it)

pet_expr_free(it->second);

for (it_s = summary_cache.begin(); it_s != summary_cache.end(); ++it_s)

pet_function_summary_free(it_s->second);

isl_id_to_pet_expr_free(id_size);

isl_union_map_free(value_bounds);

}

void PetScan::report(SourceRange range, unsigned id)

}

void PetScan::report(Stmt *stmt, unsigned id)

{

report(stmt->getSourceRange(), id);

}

void PetScan::report(Decl *decl, unsigned id)

{

report(decl->getSourceRange(), id);

}

void PetScan::unsupported(Stmt *stmt)

}

void PetScan::report_unsupported_unary_operator(Stmt *stmt)

}

void PetScan::report_unsupported_binary_operator(Stmt *stmt)

}

void PetScan::report_unsupported_statement_type(Stmt *stmt)

}

void PetScan::report_prototype_required(Stmt *stmt)

}

void PetScan::report_missing_increment(Stmt *stmt)

}

void PetScan::report_missing_summary_function(Stmt *stmt)

}

void PetScan::report_missing_summary_function_body(Stmt *stmt)

}

void PetScan::report_unsupported_inline_function_argument(Stmt *stmt)

}

void PetScan::report_unsupported_declaration(Decl *decl)

}

void PetScan::report_unbalanced_pragmas(SourceLocation scop,

}

void PetScan::report_unsupported_return(Stmt *stmt)

}

void PetScan::report_return_not_at_end_of_function(Stmt *stmt)

}

static __isl_give isl_val *extract_unsigned(isl_ctx *ctx,

const llvm::APInt &val)

{

unsigned n;

const uint64_t *data;

data = val.getRawData();

n = val.getNumWords();

return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);

}

static __isl_give isl_val *extract_int(isl_ctx *ctx, bool is_signed,

llvm::APInt val)

{

int is_negative = is_signed && val.isNegative();

isl_val *v;

if (is_negative)

val = -val;

v = extract_unsigned(ctx, val);

if (is_negative)

v = isl_val_neg(v);

return v;

}

__isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)

{

const Type *type = expr->getType().getTypePtr();

bool is_signed = type->hasSignedIntegerRepresentation();

return ::extract_int(ctx, is_signed, expr->getValue());

}

__isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)

{

return extract_int(expr->getSubExpr());

}

__isl_give isl_val *PetScan::extract_int(clang::Expr *expr)

{

if (expr->getStmtClass() == Stmt::IntegerLiteralClass)

return extract_int(ctx, cast<IntegerLiteral>(expr));

if (expr->getStmtClass() == Stmt::ParenExprClass)

return extract_int(cast<ParenExpr>(expr));

unsupported(expr);

return NULL;

}

__isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)

{

return pet_expr_new_int(extract_unsigned(ctx, val));

}

static int get_type_size(ValueDecl *decl)

{

return pet_clang_get_type_size(decl->getType(), decl->getASTContext());

}

static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,

unsigned pos, ValueDecl *decl)

{

int type_size;

isl_ctx *ctx;

isl_val *bound;

ctx = isl_set_get_ctx(set);

type_size = get_type_size(decl);

if (type_size == 0)

isl_die(ctx, isl_error_invalid, "not an integer type",

return isl_set_free(set));

if (type_size > 0) {

set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);

bound = isl_val_int_from_ui(ctx, type_size);

bound = isl_val_2exp(bound);

bound = isl_val_sub_ui(bound, 1);

set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);

} else {

bound = isl_val_int_from_ui(ctx, -type_size - 1);

bound = isl_val_2exp(bound);

bound = isl_val_sub_ui(bound, 1);

set = isl_set_upper_bound_val(set, isl_dim_param, pos,

isl_val_copy(bound));

bound = isl_val_neg(bound);

bound = isl_val_sub_ui(bound, 1);

set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);

}

return set;

}

__isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)

{

return extract_index_expr(expr->getSubExpr());

}

__isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)

{

return extract_index_expr(expr->getDecl());

}

__isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)

{

isl_id *id;

if (isa<EnumConstantDecl>(decl))

return extract_expr(cast<EnumConstantDecl>(decl));

id = pet_id_from_decl(ctx, decl);

return pet_id_create_index_expr(id);

}

__isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)

{

switch (expr->getStmtClass()) {

case Stmt::ImplicitCastExprClass:

return extract_index_expr(cast<ImplicitCastExpr>(expr));

case Stmt::DeclRefExprClass:

return extract_index_expr(cast<DeclRefExpr>(expr));

case Stmt::ArraySubscriptExprClass:

return extract_index_expr(cast<ArraySubscriptExpr>(expr));

case Stmt::IntegerLiteralClass:

return extract_expr(cast<IntegerLiteral>(expr));

case Stmt::MemberExprClass:

return extract_index_expr(cast<MemberExpr>(expr));

default:

unsupported(expr);

}

return NULL;

}

__isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)

{

Expr *base = expr->getBase();

Expr *idx = expr->getIdx();

pet_expr *index;

pet_expr *base_expr;

base_expr = extract_index_expr(base);

index = extract_expr(idx);

base_expr = pet_expr_access_subscript(base_expr, index);

return base_expr;

}

__isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)

{

Expr *base = expr->getBase();

FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());

pet_expr *base_index;

isl_id *id;

base_index = extract_index_expr(base);

if (expr->isArrow()) {

pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));

base_index = pet_expr_access_subscript(base_index, index);

}

if (field->isAnonymousStructOrUnion())

return base_index;

id = pet_id_from_decl(ctx, field);

return pet_expr_access_member(base_index, id);

}

static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)

{

access = pet_expr_access_set_write(access, 1);

access = pet_expr_access_set_read(access, 0);

return access;

}

static __isl_give pet_expr *mark_may_write(__isl_take pet_expr *expr)

{

isl_union_map *access;

isl_union_map *empty;

access = pet_expr_access_get_dependent_access(expr,

pet_expr_access_may_read);

empty = isl_union_map_empty(isl_union_map_get_space(access));

expr = pet_expr_access_set_access(expr, pet_expr_access_may_write,

access);

expr = pet_expr_access_set_access(expr, pet_expr_access_must_write,

empty);

return expr;

}

__isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)

{

int type_size;

pet_expr *arg;

enum pet_op_type op;

op = UnaryOperatorKind2pet_op_type(expr->getOpcode());

if (op == pet_op_last) {

report_unsupported_unary_operator(expr);

return NULL;

}

arg = extract_expr(expr->getSubExpr());

if (expr->isIncrementDecrementOp() &&

pet_expr_get_type(arg) == pet_expr_access) {

arg = mark_write(arg);

arg = pet_expr_access_set_read(arg, 1);

}

type_size = pet_clang_get_type_size(expr->getType(), ast_context);

return pet_expr_new_unary(type_size, op, arg);

}

__isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)

{

int type_size;

pet_expr *lhs, *rhs;

enum pet_op_type op;

op = BinaryOperatorKind2pet_op_type(expr->getOpcode());

if (op == pet_op_last) {

report_unsupported_binary_operator(expr);

return NULL;

}

lhs = extract_expr(expr->getLHS());

rhs = extract_expr(expr->getRHS());

if (expr->isAssignmentOp() &&

pet_expr_get_type(lhs) == pet_expr_access) {

lhs = mark_write(lhs);

if (expr->isCompoundAssignmentOp())

lhs = pet_expr_access_set_read(lhs, 1);

}

type_size = pet_clang_get_type_size(expr->getType(), ast_context);

return pet_expr_new_binary(type_size, op, lhs, rhs);

}

__isl_give pet_tree *PetScan::extract(Decl *decl)

{

VarDecl *vd;

pet_expr *lhs, *rhs;

pet_tree *tree;

if (!isa<VarDecl>(decl)) {

report_unsupported_declaration(decl);

return NULL;

}

vd = cast<VarDecl>(decl);

declarations.push_back(vd);

lhs = extract_access_expr(vd);

lhs = mark_write(lhs);

if (!vd->getInit())

tree = pet_tree_new_decl(lhs);

else {

rhs = extract_expr(vd->getInit());

tree = pet_tree_new_decl_init(lhs, rhs);

}

return tree;

}

__isl_give pet_tree *PetScan::extract(DeclStmt *stmt)

{

pet_tree *tree;

unsigned n;

if (!stmt->isSingleDecl()) {

const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();

n = group.size();

tree = pet_tree_new_block(ctx, 0, n);

for (unsigned i = 0; i < n; ++i) {

pet_tree *tree_i;

pet_loc *loc;

tree_i = extract(group[i]);

loc = construct_pet_loc(group[i]->getSourceRange(),

false);

tree_i = pet_tree_set_loc(tree_i, loc);

tree = pet_tree_block_add_child(tree, tree_i);

}

return tree;

}

return extract(stmt->getSingleDecl());

}

__isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)

{

pet_expr *cond, *lhs, *rhs;

cond = extract_expr(expr->getCond());

lhs = extract_expr(expr->getTrueExpr());

rhs = extract_expr(expr->getFalseExpr());

return pet_expr_new_ternary(cond, lhs, rhs);

}

__isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)

{

return extract_expr(expr->getSubExpr());

}

__isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)

{

double d;

string s;

const LangOptions &LO = PP.getLangOpts();

SourceLocation loc = expr->getLocation();

if (!loc.isMacroID()) {

SourceManager &SM = PP.getSourceManager();

unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);

s = string(SM.getCharacterData(loc), len);

} else {

llvm::raw_string_ostream S(s);

expr->printPretty(S, 0, PrintingPolicy(LO));

S.str();

}

d = expr->getValueAsApproximateDouble();

return pet_expr_new_double(ctx, d, s.c_str());

}

__isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)

{

pet_expr *index;

index = extract_index_expr(expr);

if (pet_expr_get_type(index) == pet_expr_int)

return index;

return pet_expr_access_from_index(expr->getType(), index, ast_context);

}

__isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)

{

return pet_expr_access_from_index(decl->getType(),

extract_index_expr(decl), ast_context);

}

__isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)

{

return extract_expr(expr->getSubExpr());

}

__isl_give pet_expr *PetScan::extract_assume(Expr *expr)

{

return pet_expr_new_unary(0, pet_op_assume, extract_expr(expr));

}

static Expr *extract_addr_of_arg(Expr *expr)

{

UnaryOperator *op;

if (expr->getStmtClass() != Stmt::UnaryOperatorClass)

return NULL;

op = cast<UnaryOperator>(expr);

if (op->getOpcode() != UO_AddrOf)

return NULL;

return op->getSubExpr();

}

__isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,

Expr *expr, bool detect_writes)

{

Expr *arg;

pet_expr *res;

int is_addr = 0, is_partial = 0;

expr = pet_clang_strip_casts(expr);

arg = extract_addr_of_arg(expr);

if (arg) {

is_addr = 1;

expr = arg;

}

res = extract_expr(expr);

if (!res)

return NULL;

if (pet_clang_array_depth(expr->getType()) > 0)

is_partial = 1;

if (detect_writes && (is_addr || is_partial) &&

pet_expr_get_type(res) == pet_expr_access) {

ParmVarDecl *parm;

if (!fd->hasPrototype()) {

report_prototype_required(expr);

return pet_expr_free(res);

}

parm = fd->getParamDecl(pos);

if (!const_base(parm->getType()))

res = mark_may_write(res);

}

if (is_addr)

res = pet_expr_new_unary(0, pet_op_address_of, res);

return res;

}

FunctionDecl *PetScan::find_decl_from_name(CallExpr *call, string name)

{

TranslationUnitDecl *tu = ast_context.getTranslationUnitDecl();

DeclContext::decl_iterator begin = tu->decls_begin();

DeclContext::decl_iterator end = tu->decls_end();

for (DeclContext::decl_iterator i = begin; i != end; ++i) {

FunctionDecl *fd = dyn_cast<FunctionDecl>(*i);

if (!fd)

continue;

if (fd->getName().str().compare(name) != 0)

continue;

if (fd->hasBody())

return fd;

report_missing_summary_function_body(call);

return NULL;

}

report_missing_summary_function(call);

return NULL;

}

FunctionDecl *PetScan::get_summary_function(CallExpr *call)

{

FunctionDecl *decl = call->getDirectCallee();

if (!decl)

return NULL;

if (!options->pencil)

return decl;

specific_attr_iterator<AnnotateAttr> begin, end, i;

begin = decl->specific_attr_begin<AnnotateAttr>();

end = decl->specific_attr_end<AnnotateAttr>();

for (i = begin; i != end; ++i) {

string attr = (*i)->getAnnotation().str();

const char prefix[] = "pencil_access(";

size_t start = attr.find(prefix);

if (start == string::npos)

continue;

start += strlen(prefix);

string name = attr.substr(start, attr.find(')') - start);

return find_decl_from_name(call, name);

}

return decl;

}

static bool is_assume(int pencil, const string &name)

}