--- tree.h 2005-03-16 15:36:28.000000000 -0500 +++ tree-modified.h 2005-07-27 13:28:49.000000000 -0400 @@ -259,7 +259,7 @@ tree chain; tree type; union tree_ann_d *ann; - + int refid; ENUM_BITFIELD(tree_code) code : 8; unsigned side_effects_flag : 1; --- tree-loop-linear.c 2005-02-17 11:29:56.000000000 -0500 +++ tree-loop-linear.c-modified 2005-07-27 13:21:18.000000000 -0400 @@ -45,6 +45,12 @@ #include "varray.h" #include "lambda.h" +// ADDED_SK +#include "dynprof.h" + +int* iterations_estimate; +extern int timestamp_flag; + /* Linear loop transforms include any composition of interchange, scaling, skewing, and reversal. They are used to change the iteration order of loop nests in order to optimize data locality of @@ -237,6 +243,98 @@ return trans; } + + +void find_data_references(struct loop *loop_nest, varray_type* datarefs) +{ + + + // printf(" No of loops is %d \n",loops->num); + unsigned int i; + unsigned int j; + int N; + + + struct data_reference *a, *b; + + + bblock_info **basic_block_list; + // struct loop *loop_nest = loops->parray[0]; + basic_block_list=(bblock_info**)xmalloc(sizeof(bblock_info*)*loop_nest->num_nodes); + // printf(" No of loops is %d basic_blocks %d\n",loops->num,loop_nest->num_nodes); + printf(" basic_blocks %d\n",loop_nest->num_nodes); + + for(i=0; i < loop_nest->num_nodes;i++) + { + basic_block_list[i]=(bblock_info*)xmalloc(sizeof(bblock_info)); + + // basic_block_list[i]->depth =0; + + } + for(i=0; i < loop_nest->num_nodes;i++) + { + basic_block_list[i]->depth =0; + VARRAY_GENERIC_PTR_INIT (basic_block_list[i]->myrefs, 10, "myrefs"); + } + + + + printf(" Some info on this loop with id %d\n",loop_nest->num); + printf(" No of blocks in this %d \n",loop_nest->num_nodes); + printf(" The level of this loop %d \n",loop_nest->level); + printf(" The Depth of this loop %d \n",loop_nest->depth); + + unsigned int depth = 0; + examine_data_references_in_loop(loop_nest,basic_block_list); + + + VARRAY_GENERIC_PTR_INIT (*datarefs, 10, "datarefs"); + // loop_nest = loops->parray[1]; + // printf(" The Depth of this loop %d \n",loop_nest->depth); + + + for(j=0; j < loop_nest->num_nodes;j++) + { + + + N = VARRAY_ACTIVE_SIZE (basic_block_list[j]->myrefs); + + + for (i = 0; i < N; i++) + { + + printf(" Examining contents \n"); + + + a = VARRAY_GENERIC_PTR (basic_block_list[j]->myrefs, i); + a->refid=0; + a->groupid=0; + a->ug_overlap=0; + a->non_ug_overlap=0; + a->depth=basic_block_list[j]->depth; + a->num=basic_block_list[j]->num; + a->size=(int*)xmalloc(sizeof(int)*(a->depth+1)); + dump_data_reference(stdout,a); + VARRAY_PUSH_GENERIC_PTR (*datarefs,a); + + + } + + } + + + + + + + // dumping data references per loop + + printf(" Finished looking at references \n"); + // dump_data_references(stdout,datarefs); + + } + + /* Perform a set of linear transforms on LOOPS. */ void @@ -244,7 +342,54 @@ { unsigned int i; + varray_type refsinloops; + compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL); + analyze_all_data_dependences (loops); + + + if(timestamp_flag) + { + + VARRAY_GENERIC_PTR_INIT (refsinloops, 10, "refsinloops"); + + + printf(" Number of loops in this program is %d \n",loops->num); + + estimate_numbers_of_iterations (loops); + + iterations_estimate= (int*) xmalloc(sizeof(int)*(loops->num +1)); + + for (i = 1; i < loops->num; i++) + { + struct loop* l_nest = loops->parray[i]; + printf(" Estimate for %d with depth %d ",i,l_nest->depth); + + if(l_nest->estimated_nb_iterations != NULL) + { +// && (TREE_CODE(l_nest->estimated_nb_iterations)== INTEGER_CST)) + + printf("%d \n",TREE_INT_CST_LOW(l_nest->estimated_nb_iterations)); + iterations_estimate[i]=TREE_INT_CST_LOW(l_nest->estimated_nb_iterations); + } + else + iterations_estimate[i]=-1; + + + + } + + } + + // VARRAY_GENERIC_PTR_INIT (dependence_relations, 10, +// "dependence_relations"); + + + // compute_data_dependences_for_loop (depth, loop_nest, +// &datarefs, &dependence_relations); + + + for (i = 1; i < loops->num; i++) { unsigned int depth = 0; @@ -274,6 +419,8 @@ } */ if (!loop_nest->inner) continue; + + printf(" Processing loop for %d \n",i); depth = 1; for (temp = loop_nest->inner; temp; temp = temp->inner) { @@ -291,24 +438,170 @@ /* Analyze data references and dependence relations using scev. */ + VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs"); VARRAY_GENERIC_PTR_INIT (dependence_relations, 10, "dependence_relations"); - + + + printf(" Inside loop_nest->num %d %d\n",loop_nest->num,loop_nest->depth); - compute_data_dependences_for_loop (depth, loop_nest, - &datarefs, &dependence_relations); - if (dump_file && (dump_flags & TDF_DETAILS)) + // compute_data_dependences_for_loop (depth, loop_nest, &datarefs, &dependence_relations); + + // ADDED_SK + + + if(timestamp_flag) + { + + find_data_references(loop_nest,&refsinloops); + dump_data_references (stdout,refsinloops); + + printf("*****************\n"); + printf(" UG set information \n"); + compute_UG_sets(refsinloops); + // + + printf("*****************\n"); + printf("Data dependency information \n"); + + compute_data_dependences_for_loop_SK (depth, loop_nest,&refsinloops, &dependence_relations); + + + printf("*****************\n"); + printf("Processing for overlap\n"); + process_for_overlap(&dependence_relations); + + + +// dump_updated_data_references (stdout,refsinloops); + + printf("*****************\n"); + printf(" Computing sizes \n"); + compute_sizes(loop_nest,refsinloops); + + printf("*****************\n"); + printf(" Size information \n"); + dump_size_information(loop_nest,refsinloops); + printf("*****************\n"); + printf(" Inserting annotations \n"); + + insert_annotations(loop_nest); + + + + } + + + +/* dump_file=stdout; + dump_flags=TDF_DETAILS; + + + if (dump_file && (dump_flags & TDF_DETAILS)) { unsigned int j; + printf("Hello\n"); for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++) { struct data_dependence_relation *ddr = (struct data_dependence_relation *) VARRAY_GENERIC_PTR (dependence_relations, j); + if(DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + ddr->a->overlap=1; + ddr->b->overlap=1; + + } + + if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) ) + { + printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid); + dump_data_reference(dump_file,ddr->a); + printf("\n"); + dump_data_reference(dump_file,ddr->b); + printf("\n"); + // is -1 present + + // if b is write and a is read + lambda_vector vector; + int vect_len=DDR_SIZE_VECT (ddr); + for (i = 0; i a->isread == 0) && (ddr->b->isread ==1)) + { + ddr->a->overlap=0; // overlap can be ignored + ddr->b->overlap=0; + + + } + else + { + ddr->a->overlap=i+1; + ddr->b->overlap=i+1; + break; + } + } + + + else if(vector[i] == 1) + { + if((ddr->a->isread == 1) && (ddr->b->isread ==0)) + { + ddr->a->overlap=0; // overlap can be ignored + ddr->b->overlap=0; + + + } + else + { + ddr->a->overlap=i+1; + ddr->b->overlap=i+1; + break; + } + + } + + } + fprintf (dump_file, "DISTANCE_V ("); + print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), + DDR_SIZE_VECT (ddr)); + fprintf (dump_file, ")\n"); + fprintf (dump_file, "DIRECTION_V ("); + print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), + DDR_SIZE_VECT (ddr)); + fprintf (dump_file, ")\n"); + } + } + fprintf (dump_file, "\n\n"); + } + + /* - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + unsigned int j; + printf("Hello\n"); + for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++) + { + struct data_dependence_relation *ddr = + (struct data_dependence_relation *) + VARRAY_GENERIC_PTR (dependence_relations, j); + + if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) ) { + printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid); + dump_data_reference(dump_file,ddr->a); + + + printf("\n"); + dump_data_reference(dump_file,ddr->b); + printf("\n"); + + fprintf (dump_file, "DISTANCE_V ("); print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); @@ -321,8 +614,11 @@ } fprintf (dump_file, "\n\n"); } - /* Build the transformation matrix. */ - trans = lambda_trans_matrix_new (depth, depth); + + dump_file=NULL; + dump_flags=0; + + trans = lambda_trans_matrix_new (depth, depth); lambda_matrix_id (LTM_MATRIX (trans), depth); trans = try_interchange_loops (trans, depth, dependence_relations, @@ -335,7 +631,7 @@ continue; } - /* Check whether the transformation is legal. */ + if (!lambda_transform_legal_p (trans, depth, dependence_relations)) { if (dump_file) @@ -369,6 +665,7 @@ fprintf (dump_file, "Successfully transformed loop.\n"); oldivs = NULL; invariants = NULL; + */ free_dependence_relations (dependence_relations); free_data_refs (datarefs); } --- tree-data-ref.c 2005-02-17 07:58:01.000000000 -0500 +++ tree-data-ref.c-modified 2005-07-27 13:21:09.000000000 -0400 @@ -95,6 +95,19 @@ #include "tree-scalar-evolution.h" #include "tree-pass.h" + +// ADDED_SK + + +#include "dynprof.h" +int groupid=1; +int refid=1; + +extern int* iterations_estimate; +extern FILE* refFile; +extern FILE* refinfo; +extern int timestamp_flag; + /* This is the simplest data dependence test: determines whether the data references A and B access the same array/region. Returns false when the property is not computable at compile time. @@ -264,6 +277,7 @@ fprintf (outf, "(Data Ref: \n stmt: "); print_generic_stmt (outf, DR_STMT (dr), 0); + // fprintf(outf," Statement line number %d \n",dr->stmt->exp.common.refid); fprintf (outf, " ref: "); print_generic_stmt (outf, DR_REF (dr), 0); fprintf (outf, " base_name: "); @@ -274,7 +288,10 @@ fprintf (outf, " Access function %d: ", i); print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); } - fprintf (outf, ")\n"); + + fprintf (outf, ")\n"); + fprintf (outf, "the loop where this was found %d\n",dr->num); + } /* Dump function for a SUBSCRIPT structure. */ @@ -1708,6 +1725,15 @@ print_generic_expr (dump_file, *overlap_iterations_b, 0); fprintf (dump_file, ")\n"); } + /* + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (stdout, " (overlap_iterations_a = "); + print_generic_expr (stdout, *overlap_iterations_a, 0); + fprintf (stdout, ")\n (overlap_iterations_b = "); + print_generic_expr (stdout, *overlap_iterations_b, 0); + fprintf (stdout, ")\n"); + }*/ } @@ -2281,6 +2307,8 @@ if (bb->loop_father->estimated_nb_iterations == NULL_TREE) compute_estimated_nb_iterations (bb->loop_father); } + + // dump_data_references(stdout,datarefs); free (bbs); @@ -2303,7 +2331,8 @@ { unsigned int i; varray_type allrelations; - + + /* If one of the data references is not computable, give up without spending time to compute other dependences. */ if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) @@ -2318,7 +2347,174 @@ build_classic_dir_vector (ddr, nb_loops, loop->depth); return; } + + + + VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations"); + compute_all_dependences (*datarefs, &allrelations); + + for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++) + { + struct data_dependence_relation *ddr; + ddr = VARRAY_GENERIC_PTR (allrelations, i); + if (build_classic_dist_vector (ddr, nb_loops, loop->depth)) + { + VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); + build_classic_dir_vector (ddr, nb_loops, loop->depth); + } + } + + // dump_data_references(stdout,datarefs); + +} + +// ADDED_SK following functions are for partial variable analysiz. + +/* For a data reference REF contained in the statement STMT, initialize + a DATA_REFERENCE structure, and return it. IS_READ flag has to be + set to true when REF is in the right hand side of an + assignment. */ + +struct data_reference * +analyze_array_SK (tree stmt, tree ref, bool is_read,int depth,int num) +{ + struct data_reference *res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_array \n"); + fprintf (dump_file, " (ref = "); + print_generic_stmt (dump_file, ref, 0); + fprintf (dump_file, ")\n"); + } + + res = xmalloc (sizeof (struct data_reference)); + + DR_STMT (res) = stmt; + DR_REF (res) = ref; + VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns"); + DR_BASE_NAME (res) = analyze_array_indexes + (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt); + DR_IS_READ (res) = is_read; + res->size=(int*)xmalloc(sizeof(int)*depth); + res->depth=depth; + res->num=num; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); + + return res; +} + + +tree +find_data_references_in_loop_SK (struct loop *loop, varray_type *datarefs) +{ + bool dont_know_node_not_inserted = true; + basic_block bb, *bbs; + unsigned int i; + block_stmt_iterator bsi; + + bbs = get_loop_body (loop); + + for (i = 0; i < loop->num_nodes; i++) + { + + printf(" Examining loop %d %d \n",loop->depth,loop->level); + bb = bbs[i]; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + stmt_ann_t ann = stmt_ann (stmt); + if (TREE_CODE (stmt) != MODIFY_EXPR) + continue; + + if (!VUSE_OPS (ann) + && !V_MUST_DEF_OPS (ann) + && !V_MAY_DEF_OPS (ann)) + continue; + + /* In the GIMPLE representation, a modify expression + contains a single load or store to memory. */ + printf(" Reference found at depth %d \n",loop->depth); + if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) + VARRAY_PUSH_GENERIC_PTR + (*datarefs, analyze_array_SK (stmt, TREE_OPERAND (stmt, 0), + false,loop->depth,loop->num)); + + else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF) + VARRAY_PUSH_GENERIC_PTR + (*datarefs, analyze_array_SK (stmt, TREE_OPERAND (stmt, 1), + true,loop->depth,loop->num)); + else + { + if (dont_know_node_not_inserted) + { + struct data_reference *res; + res = xmalloc (sizeof (struct data_reference)); + DR_STMT (res) = NULL_TREE; + DR_REF (res) = NULL_TREE; + DR_ACCESS_FNS (res) = NULL; + DR_BASE_NAME (res) = NULL; + DR_IS_READ (res) = false; + res->depth=loop->depth; + res->num=loop->num; + VARRAY_PUSH_GENERIC_PTR (*datarefs, res); + dont_know_node_not_inserted = false; + printf(" Dont know node inserted \n"); + exit(-1); + } + } + + /* When there are no defs in the loop, the loop is parallel. */ + if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0 + || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0) + bb->loop_father->parallel_p = false; + } + + if (bb->loop_father->estimated_nb_iterations == NULL_TREE) + compute_estimated_nb_iterations (bb->loop_father); + } + + // dump_data_references(stdout,datarefs); + + free (bbs); + + return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know; +} + + + +void +compute_data_dependences_for_loop_SK (unsigned nb_loops, + struct loop *loop, + varray_type *datarefs, + varray_type *dependence_relations) +{ + unsigned int i; + varray_type allrelations; + varray_type dummyrefs; + VARRAY_GENERIC_PTR_INIT (dummyrefs, 10, "dummyrefs"); + + + /* If one of the data references is not computable, give up without + spending time to compute other dependences. */ + /* + if (find_data_references_in_loop_SK (loop, &dummyrefs) == chrec_dont_know) + { + struct data_dependence_relation *ddr; + + ddr = initialize_data_dependence_relation (NULL, NULL); + VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); + build_classic_dist_vector (ddr, nb_loops, loop->depth); + build_classic_dir_vector (ddr, nb_loops, loop->depth); + return; + } + */ + + VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations"); compute_all_dependences (*datarefs, &allrelations); @@ -2332,8 +2528,1059 @@ build_classic_dir_vector (ddr, nb_loops, loop->depth); } } + + // dump_data_references(stdout,datarefs); + +} + + + +void process_for_overlap(varray_type *dependence_relations) +{ + unsigned int j,i; + printf("Hello\n"); + int temp_overlapa,temp_overlapb; + + for (j = 0; j < VARRAY_ACTIVE_SIZE (*dependence_relations); j++) + { + + + struct data_dependence_relation *ddr = + (struct data_dependence_relation *) + VARRAY_GENERIC_PTR (*dependence_relations, j); + + printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid); + + + if(DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + ddr->a->non_ug_overlap=1; + ddr->b->non_ug_overlap=1; + + + } + +// if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) && (ddr->a->groupid != ddr->b->groupid)) + if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE)) + { + + printf(" Null tree with %d %d \n", ddr->a->groupid,ddr->b->groupid); + + if(ddr->a->groupid =ddr->b->groupid) + + dump_data_reference(stdout,ddr->a); + printf("\n"); + dump_data_reference(stdout,ddr->b); + printf("\n"); + lambda_vector vector; + int vect_len=DDR_SIZE_VECT (ddr); + vector =DDR_DIST_VECT (ddr); + for (i = vect_len -1; i >= 0 ; i--) + { + printf(" the vector %d %d \n",i,vector[i]); + if(vector[i] < 0)//b is the source , a is sink + { + if((ddr->a->is_read == 0) && (ddr->b->is_read ==1)) + { + temp_overlapa=0; // overlap can be ignored + temp_overlapb=0; + + + } + else + { + temp_overlapa=i+1; + temp_overlapb=i+1; + break; + } + } + + + else if(vector[i] > 0) + { + if((ddr->a->is_read == 1) && (ddr->b->is_read ==0)) + { + temp_overlapa=0; // overlap can be ignored + temp_overlapb=0; + + + } + else + { + temp_overlapa=i+1; + temp_overlapb=i+1; + break; + } + + } + + + // Verify - a 0 might indicate a loop independent dependence only if there are no loop carried dependences. + + + } + + printf(" No loop carried dependence \n"); + if(temp_overlapa ==0 ) + { + if((ddr->a->is_read == 1) && (ddr->b->is_read ==0)) + { + printf(" Overlap can be ignored \n"); + temp_overlapa=0; // overlap can be ignored + temp_overlapb=0; + + + } + + + else + { + printf(" Overlap cant be ignored \n"); + temp_overlapa=i+1; + + temp_overlapb=i+1; + //printf(" the reference of b is %d %d\n",ddr->b->refid,ddr->b->overlap); + break; + } + } + + if(temp_overlapa != 0) + { + + if(ddr->a->groupid == ddr->b->groupid) + { + if(temp_overlapa < ddr->a->ug_overlap) + ddr->a->ug_overlap =temp_overlapa; + + } + else + { + if(temp_overlapa < ddr->a->non_ug_overlap) + ddr->a->non_ug_overlap =temp_overlapa; + + + + } + + } + if(temp_overlapb != 0) + { + + if(ddr->a->groupid == ddr->b->groupid) + { + + if(temp_overlapb < ddr->b->ug_overlap) + ddr->b->ug_overlap =temp_overlapb; + + } + else + { + if(temp_overlapb < ddr->b->non_ug_overlap) + ddr->b->non_ug_overlap =temp_overlapb; + } + } + + + + fprintf (stdout, "DISTANCE_V ("); + print_lambda_vector (stdout, DDR_DIST_VECT (ddr), + DDR_SIZE_VECT (ddr)); + fprintf (stdout, ")\n"); + fprintf (stdout, "DIRECTION_V ("); + print_lambda_vector (stdout, DDR_DIR_VECT (ddr), + DDR_SIZE_VECT (ddr)); + fprintf (stdout, ")\n"); + } + } + fprintf (stdout, "\n\n"); + +} + + + + +void +dump_updated_data_references (FILE *file, + varray_type datarefs) +{ + unsigned int i; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + dump_updated_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); +} + +void +dump_updated_data_reference (FILE *outf, + struct data_reference *dr) +{ + unsigned int i; + + fprintf (outf, "(Data Ref: \n stmt: "); + print_generic_stmt (outf, DR_STMT (dr), 0); + fprintf (outf, " ref: "); + print_generic_stmt (outf, DR_REF (dr), 0); + fprintf (outf, " base_name: "); + print_generic_stmt (outf, DR_BASE_NAME (dr), 0); + + for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) + { + fprintf (outf, " Access function %d: ", i); + print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); + + } + fprintf (outf, " Overlap information \n"); + fprintf (outf, " Groupid %d reference %d Overlap %d %d\n",dr->groupid,dr->refid,dr->ug_overlap,dr->non_ug_overlap); + + fprintf (outf, ")\n"); +} + + +tree +examine_data_references_in_loop (struct loop *loop, bblock_info** basic_block_list) +//examine_data_references_in_loop (struct loop *loop, varray_type *datarefs) +{ + bool dont_know_node_not_inserted = true; + basic_block bb, *bbs; + unsigned int i; + block_stmt_iterator bsi; + + + bbs = get_loop_body (loop); + int index; + + + //varray_type myrefs; + + printf(" Some info on this loop with id %d\n",loop->num); + printf(" No of blocks in this %d \n",loop->num_nodes); + printf(" The level of this loop %d \n",loop->level); + printf(" The Depth of this loop %d \n",loop->depth); + // printf(" The outer of this loop %d \n",loop->outer->num); + // printf(" The Depth of this loop %d \n",loop->depth); + //printf(" The index of loop latch %d \n",loop->latch->index); + // printf(" The header of loop %d \n",loop->header->index); +// printf(" The first block in loop %d \n",loop->first->index); +// printf(" The last block in loop %d \n",loop->last->index); + +// printf(" The starting basic block %d \n",loop->first->index); + // printf(" The last basic block %d \n",loop->last->index); + + for (i = 0; i < loop->num_nodes; i++) + { + + + + bb = bbs[i]; + printf("Basic block %d with index %d with depth %d belonging to loop %d\n",i,bb->index,bb->loop_depth,bb->loop_father->num); +// printf(" This basic belongs to %d with depth %d\n",bb->loop_father->num,loop->depth); + index=bb->index; + + + // if( basic_block_list[index]->depth > loop->depth) + { + printf(" Node %d already present \n",i); + // basic_block_list[index]->loop_num =loop->num; + // basic_block_list[index]->depth = loop->depth; + basic_block_list[i]->depth = bb->loop_depth; + basic_block_list[i]->num=bb->loop_father->num; + + + + //printf(" Node %d already present done\n",i); + + } + +// else + { + + printf(" Collecting references \n"); + // varray_clear(basic_block_list[i]->myrefs); + + printf(" Traversing basic block lists \n"); + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + stmt_ann_t ann = stmt_ann (stmt); + + if (TREE_CODE (stmt) != MODIFY_EXPR) + continue; + + if (!VUSE_OPS (ann) + && !V_MUST_DEF_OPS (ann) + && !V_MAY_DEF_OPS (ann)) + continue; + + if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) + { + + VARRAY_PUSH_GENERIC_PTR + (basic_block_list[i]->myrefs, analyze_array (stmt, TREE_OPERAND (stmt, 0), + false)); + + } + + else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF) + VARRAY_PUSH_GENERIC_PTR + (basic_block_list[i]->myrefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), + true)); + else + { + if (dont_know_node_not_inserted) + { + + printf(" Inside dont know node not inserted \n"); + struct data_reference *res; + res = xmalloc (sizeof (struct data_reference)); + DR_STMT (res) = NULL_TREE; + DR_REF (res) = NULL_TREE; + DR_ACCESS_FNS (res) = NULL; + DR_BASE_NAME (res) = NULL; + DR_IS_READ (res) = false; + VARRAY_PUSH_GENERIC_PTR (basic_block_list[i]->myrefs, res); + dont_know_node_not_inserted = false; + } + } + + + } + } + + // printf(" Dumping data references \n"); + //examine_data_references(*datarefs); + + dump_data_references(stdout,basic_block_list[i]->myrefs); + // printf("\n"); + + + } + + + free (bbs); + + return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know; +} + +tree +insert_annotations (struct loop *loop) +//examine_data_references_in_loop (struct loop *loop, varray_type *datarefs) +{ + bool dont_know_node_not_inserted = true; + basic_block bb, *bbs; + unsigned int i; + block_stmt_iterator bsi,new_bsi; + + + bbs = get_loop_body (loop); + int index; + + + for (i = 0; i < loop->num_nodes; i++) + { + + + + bb = bbs[i]; + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + if(stmt->exp.common.refid != 0) + { + stmt->exp.common.refid=0; + printf(" The refid is %d ",stmt->exp.common.refid); + print_generic_stmt(stdout,stmt,0); + + //tree new_tree=build_empty_stmt(); + tree id = get_identifier ("foo"); + printf(" call node created \n"); + + tree t = build_function_type_list (void_type_node,NULL_TREE); + printf(" call node created \n"); + + + tree decl = build_decl (FUNCTION_DECL, id, t); + printf(" call node created \n"); + + + tree call = build_function_call_expr (decl, NULL); + printf(" call node created \n"); + + + // TREE_SET_CODE(new_tree,CALL_EXPR); + bsi_insert_before(&bsi,call,BSI_CHAIN_END); + printf(" call node inserted \n"); + + print_generic_stmt(stdout,call,0); + printf("\n"); + stmt->exp.common.refid=0; + + } + + } + } + + + free (bbs); + + return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know; +} + +int compute_UG_sets(varray_type datarefs) +{ + + unsigned int i, j, N,ret,k; + struct data_reference *a, *b; + + + + N = VARRAY_ACTIVE_SIZE (datarefs); + + groupid=1; + + + /*for (i = 0; i < N; i++) + { + + + a = VARRAY_GENERIC_PTR (datarefs, i); + a->refid=0; + a->groupid=0; + a->overlap=0; + + }*/ + + + + + for (i = 0; i < N; i++) + { + + printf("Comparing %d\n",i); + a = VARRAY_GENERIC_PTR (datarefs, i); + a->refid=refid++; + if(timestamp_flag) + { + fprintf(refFile,"#Promote %d ",a->refid); + fprintf(refFile," %d ",a->depth); + print_generic_stmt (refFile, DR_BASE_NAME (a), 0); + fprintf(refFile,"\n"); + + printf(" Assigned refid %d to ",a->refid); + + print_generic_stmt (stdout,a->stmt, 0); + printf("\n"); + + + + + } + + a->stmt->exp.common.refid=a->refid; + + dump_data_reference(stdout,a); + if(a->groupid !=0) + continue; + a->groupid = groupid ++; + + + for (j = 0; j < N; j++) + { + + if(j==i) + continue; + +// struct data_dependence_relation *ddr; + + b = VARRAY_GENERIC_PTR (datarefs, j); + + printf("\n"); + printf("with****************%d\n",j); + dump_data_reference(stdout,b); + + tree base_a=DR_BASE_NAME(a); + + tree base_b=DR_BASE_NAME(b); + + if(base_a != base_b) + { + printf("Not equal \n"); + continue; + } + + if(DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS(b)) + printf("Not equal \n"); + + + else + { + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + fprintf (stdout, " Comparing Access function %d: ", k); + print_generic_stmt (stdout, DR_ACCESS_FN (a, k), 0); + print_generic_stmt (stdout, DR_ACCESS_FN (b, k), 0); + printf("\n"); + ret=1; + + ret=simple_chrec_equal(DR_ACCESS_FN (a, k),DR_ACCESS_FN (b, k)); + if(ret == -1) + break; + + } + } + if(ret==-1) + printf("Not Equal"); + else + { + b->groupid =a->groupid; + printf(" equal\n"); + } + printf("\n********************\n"); + + + } + } + + + + + return(1); + + +} + + +int +simple_chrec_equal (tree t1, tree t2) +{ + enum tree_code code1, code2; + int cmp; + int i; + int ret; + + + + + + code1 = TREE_CODE (t1); + code2 = TREE_CODE (t2); + + printf(" Checking high level\n"); + + if(code1 != code2) + return(-1); + + + + if(code1==POLYNOMIAL_CHREC) + { + printf(" Polynomial \n"); + printf("Checking left tree\n"); + + tree tree_left_t1=CHREC_LEFT (t1); + tree tree_left_t2=CHREC_LEFT (t2); + code1=TREE_CODE(tree_left_t1); + code2=TREE_CODE(tree_left_t2); + if(code1 == code2) + { + if(code1== POLYNOMIAL_CHREC) + { + ret=simple_chrec_equal(tree_left_t1,tree_left_t2); + if(ret == -1) + return(ret); + + } + + } + + + else + return(-1); + + printf(" Checking right tree \n"); + tree tree_right_t1=CHREC_RIGHT(t1); + tree tree_right_t2=CHREC_RIGHT(t2); + + code1=TREE_CODE(tree_right_t1); + code2=TREE_CODE(tree_right_t2); + if(code1 == code2) + { + + /*if(TREE_CODE (tree_right_t2) == INTEGER_CST) + { + printf("low part %d \n", TREE_INT_CST_LOW(tree_right_t1)); + printf(" high part%d \n", TREE_INT_CST_HIGH(tree_right_t1)); + printf("low part-2 %d \n", TREE_INT_CST_LOW(tree_right_t2)); + printf(" high part-2 %d \n", TREE_INT_CST_HIGH(tree_right_t2)); + + } + */ + + if(code1== POLYNOMIAL_CHREC) + { + ret=simple_chrec_equal(tree_right_t1,tree_right_t2); + if(ret == -1) + return(ret); + + } + + + else if ( (TREE_CODE (tree_right_t1) == INTEGER_CST) + && ((TREE_INT_CST_LOW (tree_right_t1) != TREE_INT_CST_LOW (tree_right_t2)) + || (TREE_INT_CST_HIGH (tree_right_t1) != TREE_INT_CST_HIGH (tree_right_t2)))) + { + return(-1); + } + + } + + + else + return(-1); + + + printf(" Checking index variable \n"); + + tree tree_var_t1=CHREC_VAR(t1); + tree tree_var_t2=CHREC_VAR(t2); + code1=TREE_CODE(tree_var_t1); + code2=TREE_CODE(tree_var_t2); + if(TREE_CODE (tree_var_t2) == INTEGER_CST) + { + printf("low part %d \n", TREE_INT_CST_LOW(tree_var_t1)); + printf(" high part%d \n", TREE_INT_CST_HIGH(tree_var_t1)); + printf("low part-2 %d \n", TREE_INT_CST_LOW(tree_var_t2)); + printf(" high part-2 %d \n", TREE_INT_CST_HIGH(tree_var_t2)); + + } + + if (TREE_CODE (tree_var_t1) == INTEGER_CST + && TREE_CODE (tree_var_t2) == INTEGER_CST + && TREE_INT_CST_LOW (tree_var_t1) == TREE_INT_CST_LOW (tree_var_t2) + && TREE_INT_CST_HIGH (tree_var_t1) == TREE_INT_CST_HIGH (tree_var_t2)) + return(1); + + + else + { + printf(" Not equal \n"); + return(-1); + } + + + } + + + + } + + + + void compute_sizes(struct loop* loop, varray_type datarefs) + { + unsigned int i, j, N,ret,k; + struct data_reference *a, *b; + int subscript_spanned=0; + int temp_domain_size; + int subscript_spanned_at_current_depth; + int plane_flag=0; // Indicates of two dimensions are adjacent imen + + int union_flag; + int size_of_element; + + N = VARRAY_ACTIVE_SIZE (datarefs); + + for (i = 0; i < N; i++) + { + + + a = VARRAY_GENERIC_PTR (datarefs, i); + + printf(" Number of dimensions %d\n",DR_NUM_DIMENSIONS(a)); + int* dimension_sizes; + dimension_sizes=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a)); + tree t= array_ref_element_size(DR_REF(a)); + + size_of_element= TREE_INT_CST_LOW(t); + a->size_of_element=size_of_element; + + + get_dimension_size(DR_BASE_NAME (a),DR_NUM_DIMENSIONS(a),dimension_sizes); + + int depth=a->depth; + + printf(" Reference found at depth %d \n",depth); + + + int* subscript; + subscript=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a)); + int* subscript_at_current_depth; + subscript_at_current_depth=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a)); + + + + int size; + int domain_size=-1; + + while(depth > 0) + { + + + subscript_spanned = 0; + subscript_spanned_at_current_depth=0; + plane_flag=0; + + if(a->non_ug_overlap >= depth) + { + a->size[depth]=0; + depth --; + continue ; + + } + + union_flag=0; + + if(a->ug_overlap >= depth) + { + union_flag=1; // indicates ug's overlap - so the size calculated is good enough for the whole ug set + + } + + + + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + + // for a loop depth, if there is an index variable affecting belonging to the same loop depth + // in the polynomial estimate size as size of that subscript // this is conservative else + // estimate size as 1 + int ret=check_if_depth_occurs_in_subscript(k,depth,a); + if(ret ==1) + { + subscript_at_current_depth[k]=1; + printf(" Subscript %d being evaluated for depth %d set \n",k,depth); + subscript_spanned_at_current_depth ++; + /* + if(k != 0) + { + if(subscript_at_current_depth[k-1]==1) + plane_flag=1; + } + */ + // printf(" Subscript %d being evaluated for depth %d set \n",k,depth); + } + // else + // printf(" Subscript %d being evaluated for depth %d not set \n",k,depth); + + } + + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + if(subscript[k] ==1) + subscript_spanned ++; + } + + printf("subscript spanned %d current subscript_spanned %d \n",subscript_spanned,subscript_spanned_at_current_depth); + + if(subscript_spanned_at_current_depth> 0) + { + + if(subscript_spanned_at_current_depth == 2) + { + printf(" Special case diagonal \n"); + printf(" The id of loop where this reference wasfound %d \n",a->num); + // diagonal // size of smallest dimension + domain_size=iterations_estimate[a->num]; // Induction variable estimate + + } + + else + { + domain_size=1; + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + if(subscript_at_current_depth[k] ==1) + domain_size=dimension_sizes[k]*domain_size; + } + + } + } + + else + domain_size=1; + + + printf(" The size just from this level is %d \n",domain_size); + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + if(subscript[k] ==1) + domain_size=dimension_sizes[k]*domain_size; + } + a->size[depth]=domain_size; + + if(union_flag) + a->size[depth] - a->size[depth]*-1; // Consider the whole partition instead of individual reference + + + // Merge + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + if(subscript_at_current_depth[k] ==1) + subscript[k] =1; + + } + + for (k = 0; k < DR_NUM_DIMENSIONS (a); k++) + { + subscript_at_current_depth[k] =0; + + } + + + subscript_spanned_at_current_depth=0; + printf(" Size at depth %d found as %d \n",depth,domain_size); + + depth --; + if(depth == 0) + break; + + } // end of while + + + + + } + + } + + + void dump_size_information(struct loop* loop, varray_type datarefs) + { + + int N, i,j; + + + + struct data_reference *a,*b; + int depth,level; + + + N = VARRAY_ACTIVE_SIZE (datarefs); + /* + printf("#Group info \n"); + + for(i=1; i < groupid; i++) + { + + printf("#%d ",i); + + for (i = 0; i < N; i++) + { + + + a = VARRAY_GENERIC_PTR (datarefs, i); + if(a->groupid == i) + printf(" %d ",a->refid); + } + printf("\n"); + + } + + */ + + + + + + + int varid=1; + + + for(level=loop->level;level > 0;level--) + { + depth=loop->level-level +1; + + fprintf(refinfo,"#Depth %d \n",depth); + fprintf(refinfo,"\n"); + + for (i = 0; i < N; i++) + { + + a = VARRAY_GENERIC_PTR (datarefs, i); + if(depth > a->depth) + continue; + + if(a->size[depth] == 0) + continue; + + fprintf(refinfo,"#Varid %d \n",varid++); + int count =1; + + fprintf(refinfo,"#Members %d ",a->refid); + + + for (j = 0; j < N; j++) + { + + if(j==i) + continue; + + b = VARRAY_GENERIC_PTR (datarefs, j); + + if(a->groupid != b->groupid) + continue; + + if((depth < a->ug_overlap) || (depth < b->ug_overlap)) + continue; + + + count++; + fprintf(refinfo,"%d ",b->refid); + + b->size[depth]=0; + + + + } + + fprintf(refinfo,"\n"); + fprintf(refinfo,"#Count %d \n",count); + fprintf(refinfo,"#Size %d \n",a->size[depth]*a->size_of_element); + fprintf(refinfo,"\n"); + a->size[depth]=0; + + } + + } + + } + + + + + +int check_if_depth_occurs_in_subscript(int k, int depth, struct data_reference* dr) + + { + + + enum tree_code code1, code2; + + code1 = TREE_CODE (DR_ACCESS_FN (dr, k)); + + printf(" Checking- high level\n"); + + + + if(code1==POLYNOMIAL_CHREC) + { + + + int index =get_loop_index(DR_ACCESS_FN(dr,k)); + printf(" The index of subscript %d is %d and depth %d\n",k,index,depth); + + if(index == depth) + return(1); + + if(index < 1) + { + + printf(" Non separable indices \n"); + + tree tree_left_t1=CHREC_LEFT (DR_ACCESS_FN (dr, k)); + code1=TREE_CODE(tree_left_t1); + if(code1== POLYNOMIAL_CHREC) + { + + if(check_if_depth_occurs_in_subscript(k,depth,tree_left_t1)) + return(1); + else + return(-1); + + } + + } + + + + } + + return(-1); + + } + + + +int get_loop_index(tree node) +{ + + if(TREE_CODE (node) == POLYNOMIAL_CHREC) + { + + return(TREE_INT_CST_LOW(CHREC_VAR (node))); + + + } + else + { + printf(" Node is not affine \n"); + return(-1); + + } + + + + } + + +int get_dimension_size(tree node,int k, int* dimension_sizes) +{ + tree tmp; + int i =0; + + /* Print the innermost component type. */ + + /* Print the dimensions. */ + tmp = TREE_TYPE (node); + while (TREE_CODE (tmp) == ARRAY_TYPE) + { + int size = get_array_domain ( TYPE_DOMAIN (tmp)); + tmp = TREE_TYPE (tmp); + dimension_sizes[k-i-1]=size; + printf("size is - %d \n",size); + i ++; + } + + + +} + +int get_array_domain(tree domain) +{ + if (domain) + { + tree min = TYPE_MIN_VALUE (domain); + tree max = TYPE_MAX_VALUE (domain); + + if (min && max + && integer_zerop (min) + && host_integerp (max, 0)) + { + + return(TREE_INT_CST_LOW (max)+1); + } + + } + return(0); } + + /* Entry point (for testing only). Analyze all the data references and the dependence relations. @@ -2373,6 +3620,7 @@ compute_data_dependences_for_loop (loops->num, loops->parray[0], &datarefs, &dependence_relations); + if (dump_file) { dump_data_dependence_relations (dump_file, dependence_relations);