This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][1/n] Vectorizer TLC: re-organize data dependence checking


On Wed, Feb 27, 2013 at 4:49 PM, Richard Biener <rguenther@suse.de> wrote:
>
> This splits data reference group analysis away from data dependence
> checking and splits the latter into loop and a BB vectorization
> functions.  This allows us to perform the now no longer quadratic
> but O(n * log (n)) data reference group analysis right after
> data reference gathering, pushing the quadratic data dependence
> testing down the vectorization analysis pipeline.
>
> Bootstrap and regtest running on x86_64-unknown-linux-gnu, queued for 4.9.

Committed as r196775.

Richard.

> Richard.
>
> 2013-02-27  Richard Biener  <rguenther@suse.de>
>
>         * tree-vect-data-refs.c (vect_update_interleaving_chain): Remove.
>         (vect_insert_into_interleaving_chain): Likewise.
>         (vect_drs_dependent_in_basic_block): Inline ...
>         (vect_slp_analyze_data_ref_dependence): ... here.  New function,
>         split out from ...
>         (vect_analyze_data_ref_dependence): ... here.  Simplify.
>         (vect_check_interleaving): Simplify.
>         (vect_analyze_data_ref_dependences): Likewise.  Split out ...
>         (vect_slp_analyze_data_ref_dependences): ... this new function.
>         (dr_group_sort_cmp): New function.
>         (vect_analyze_data_ref_accesses): Compute data-reference groups
>         here instead of in vect_analyze_data_ref_dependence.  Use
>         a more efficient algorithm.
>         * tree-vect-slp.c (vect_slp_analyze_bb_1): Use
>         vect_slp_analyze_data_ref_dependences.  Call
>         vect_analyze_data_ref_accesses earlier.
>         * tree-vect-loop.c (vect_analyze_loop_2): Likewise.
>         * tree-vectorizer.h (vect_analyze_data_ref_dependences): Adjust.
>         (vect_slp_analyze_data_ref_dependences): New prototype.
>
> Index: trunk/gcc/tree-vect-data-refs.c
> ===================================================================
> *** trunk.orig/gcc/tree-vect-data-refs.c        2013-02-27 14:53:36.000000000 +0100
> --- trunk/gcc/tree-vect-data-refs.c     2013-02-27 16:45:58.969861004 +0100
> *************** vect_get_place_in_interleaving_chain (gi
> *** 154,394 ****
>   }
>
>
> - /* Function vect_insert_into_interleaving_chain.
> -
> -    Insert DRA into the interleaving chain of DRB according to DRA's INIT.  */
> -
> - static void
> - vect_insert_into_interleaving_chain (struct data_reference *dra,
> -                                    struct data_reference *drb)
> - {
> -   gimple prev, next;
> -   tree next_init;
> -   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
> -   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
> -
> -   prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
> -   next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
> -   while (next)
> -     {
> -       next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
> -       if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
> -       {
> -         /* Insert here.  */
> -         GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
> -         GROUP_NEXT_ELEMENT (stmtinfo_a) = next;
> -         return;
> -       }
> -       prev = next;
> -       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
> -     }
> -
> -   /* We got to the end of the list. Insert here.  */
> -   GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
> -   GROUP_NEXT_ELEMENT (stmtinfo_a) = NULL;
> - }
> -
> -
> - /* Function vect_update_interleaving_chain.
> -
> -    For two data-refs DRA and DRB that are a part of a chain interleaved data
> -    accesses, update the interleaving chain.  DRB's INIT is smaller than DRA's.
> -
> -    There are four possible cases:
> -    1. New stmts - both DRA and DRB are not a part of any chain:
> -       FIRST_DR = DRB
> -       NEXT_DR (DRB) = DRA
> -    2. DRB is a part of a chain and DRA is not:
> -       no need to update FIRST_DR
> -       no need to insert DRB
> -       insert DRA according to init
> -    3. DRA is a part of a chain and DRB is not:
> -       if (init of FIRST_DR > init of DRB)
> -           FIRST_DR = DRB
> -         NEXT(FIRST_DR) = previous FIRST_DR
> -       else
> -           insert DRB according to its init
> -    4. both DRA and DRB are in some interleaving chains:
> -       choose the chain with the smallest init of FIRST_DR
> -       insert the nodes of the second chain into the first one.  */
> -
> - static void
> - vect_update_interleaving_chain (struct data_reference *drb,
> -                               struct data_reference *dra)
> - {
> -   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
> -   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
> -   tree next_init, init_dra_chain, init_drb_chain;
> -   gimple first_a, first_b;
> -   tree node_init;
> -   gimple node, prev, next, first_stmt;
> -
> -   /* 1. New stmts - both DRA and DRB are not a part of any chain.   */
> -   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
> -     {
> -       GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (drb);
> -       GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
> -       GROUP_NEXT_ELEMENT (stmtinfo_b) = DR_STMT (dra);
> -       return;
> -     }
> -
> -   /* 2. DRB is a part of a chain and DRA is not.  */
> -   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && GROUP_FIRST_ELEMENT (stmtinfo_b))
> -     {
> -       GROUP_FIRST_ELEMENT (stmtinfo_a) = GROUP_FIRST_ELEMENT (stmtinfo_b);
> -       /* Insert DRA into the chain of DRB.  */
> -       vect_insert_into_interleaving_chain (dra, drb);
> -       return;
> -     }
> -
> -   /* 3. DRA is a part of a chain and DRB is not.  */
> -   if (GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
> -     {
> -       gimple old_first_stmt = GROUP_FIRST_ELEMENT (stmtinfo_a);
> -       tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
> -                                                             old_first_stmt)));
> -       gimple tmp;
> -
> -       if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
> -       {
> -         /* DRB's init is smaller than the init of the stmt previously marked
> -            as the first stmt of the interleaving chain of DRA.  Therefore, we
> -            update FIRST_STMT and put DRB in the head of the list.  */
> -         GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
> -         GROUP_NEXT_ELEMENT (stmtinfo_b) = old_first_stmt;
> -
> -         /* Update all the stmts in the list to point to the new FIRST_STMT.  */
> -         tmp = old_first_stmt;
> -         while (tmp)
> -           {
> -             GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) = DR_STMT (drb);
> -             tmp = GROUP_NEXT_ELEMENT (vinfo_for_stmt (tmp));
> -           }
> -       }
> -       else
> -       {
> -         /* Insert DRB in the list of DRA.  */
> -         vect_insert_into_interleaving_chain (drb, dra);
> -         GROUP_FIRST_ELEMENT (stmtinfo_b) = GROUP_FIRST_ELEMENT (stmtinfo_a);
> -       }
> -       return;
> -     }
> -
> -   /* 4. both DRA and DRB are in some interleaving chains.  */
> -   first_a = GROUP_FIRST_ELEMENT (stmtinfo_a);
> -   first_b = GROUP_FIRST_ELEMENT (stmtinfo_b);
> -   if (first_a == first_b)
> -     return;
> -   init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
> -   init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
> -
> -   if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
> -     {
> -       /* Insert the nodes of DRA chain into the DRB chain.
> -        After inserting a node, continue from this node of the DRB chain (don't
> -          start from the beginning.  */
> -       node = GROUP_FIRST_ELEMENT (stmtinfo_a);
> -       prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
> -       first_stmt = first_b;
> -     }
> -   else
> -     {
> -       /* Insert the nodes of DRB chain into the DRA chain.
> -        After inserting a node, continue from this node of the DRA chain (don't
> -          start from the beginning.  */
> -       node = GROUP_FIRST_ELEMENT (stmtinfo_b);
> -       prev = GROUP_FIRST_ELEMENT (stmtinfo_a);
> -       first_stmt = first_a;
> -     }
> -
> -   while (node)
> -     {
> -       node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
> -       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
> -       while (next)
> -       {
> -         next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
> -         if (tree_int_cst_compare (next_init, node_init) > 0)
> -           {
> -             /* Insert here.  */
> -             GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
> -             GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = next;
> -             prev = node;
> -             break;
> -           }
> -         prev = next;
> -         next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
> -       }
> -       if (!next)
> -       {
> -         /* We got to the end of the list. Insert here.  */
> -         GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
> -         GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = NULL;
> -         prev = node;
> -       }
> -       GROUP_FIRST_ELEMENT (vinfo_for_stmt (node)) = first_stmt;
> -       node = GROUP_NEXT_ELEMENT (vinfo_for_stmt (node));
> -     }
> - }
> -
> - /* Check dependence between DRA and DRB for basic block vectorization.
> -    If the accesses share same bases and offsets, we can compare their initial
> -    constant offsets to decide whether they differ or not.  In case of a read-
> -    write dependence we check that the load is before the store to ensure that
> -    vectorization will not change the order of the accesses.  */
> -
> - static bool
> - vect_drs_dependent_in_basic_block (struct data_reference *dra,
> -                                    struct data_reference *drb)
> - {
> -   HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
> -   gimple earlier_stmt;
> -
> -   /* We only call this function for pairs of loads and stores, but we verify
> -      it here.  */
> -   if (DR_IS_READ (dra) == DR_IS_READ (drb))
> -     {
> -       if (DR_IS_READ (dra))
> -         return false;
> -       else
> -         return true;
> -     }
> -
> -   /* Check that the data-refs have same bases and offsets.  If not, we can't
> -      determine if they are dependent.  */
> -   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
> -       || !dr_equal_offsets_p (dra, drb))
> -     return true;
> -
> -   /* Check the types.  */
> -   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
> -   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> -
> -   if (type_size_a != type_size_b
> -       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
> -                               TREE_TYPE (DR_REF (drb))))
> -     return true;
> -
> -   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
> -   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
> -
> -   /* Two different locations - no dependence.  */
> -   if (init_a != init_b)
> -     return false;
> -
> -   /* We have a read-write dependence.  Check that the load is before the store.
> -      When we vectorize basic blocks, vector load can be only before
> -      corresponding scalar load, and vector store can be only after its
> -      corresponding scalar store.  So the order of the acceses is preserved in
> -      case the load is before the store.  */
> -   earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
> -   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
> -     return false;
> -
> -   return true;
> - }
> -
> -
>   /* Function vect_check_interleaving.
>
>      Check if DRA and DRB are a part of interleaving.  In case they are, insert
> --- 154,159 ----
> *************** static bool
> *** 398,479 ****
>   vect_check_interleaving (struct data_reference *dra,
>                          struct data_reference *drb)
>   {
> !   HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
>
> !   /* Check that the data-refs have same first location (except init) and they
> !      are both either store or load (not load and store).  */
>     if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
>         || !dr_equal_offsets_p (dra, drb)
> -       || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
>         || DR_IS_READ (dra) != DR_IS_READ (drb))
> !     return false;
>
> !   /* Check:
> !      1. data-refs are of the same type
> !      2. their steps are equal
> !      3. the step (if greater than zero) is greater than the difference between
> !         data-refs' inits.  */
>     type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
>     type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> -
>     if (type_size_a != type_size_b
> !       || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
> !       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
> !                               TREE_TYPE (DR_REF (drb))))
>       return false;
>
>     init_a = TREE_INT_CST_LOW (DR_INIT (dra));
>     init_b = TREE_INT_CST_LOW (DR_INIT (drb));
>     step = TREE_INT_CST_LOW (DR_STEP (dra));
>
> !   if (init_a > init_b)
> !     {
> !       /* If init_a == init_b + the size of the type * k, we have an interleaving,
> !        and DRB is accessed before DRA.  */
> !       diff_mod_size = (init_a - init_b) % type_size_a;
> !
> !       if (step && (init_a - init_b) > step)
> !          return false;
>
> !       if (diff_mod_size == 0)
> !       {
> !         vect_update_interleaving_chain (drb, dra);
> !         if (dump_enabled_p ())
> !           {
> !             dump_printf_loc (MSG_NOTE, vect_location,
> !                                "Detected interleaving ");
> !             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
> !             dump_printf (MSG_NOTE,  " and ");
> !             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
> !           }
> !         return true;
> !       }
> !     }
> !   else
> !     {
> !       /* If init_b == init_a + the size of the type * k, we have an
> !        interleaving, and DRA is accessed before DRB.  */
> !       diff_mod_size = (init_b - init_a) % type_size_a;
>
> !       if (step && (init_b - init_a) > step)
> !          return false;
>
> !       if (diff_mod_size == 0)
> !       {
> !         vect_update_interleaving_chain (dra, drb);
> !         if (dump_enabled_p ())
> !           {
> !             dump_printf_loc (MSG_NOTE, vect_location,
> !                                "Detected interleaving ");
> !             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
> !             dump_printf (MSG_NOTE,  " and ");
> !             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
> !           }
> !         return true;
> !       }
>       }
>
> !   return false;
>   }
>
>   /* Check if data references pointed by DR_I and DR_J are same or
> --- 163,220 ----
>   vect_check_interleaving (struct data_reference *dra,
>                          struct data_reference *drb)
>   {
> !   HOST_WIDE_INT type_size_a, type_size_b, step, init_a, init_b;
>
> !   /* The caller has ensured that the data-refs have same first location
> !      (except init) and they are both either store or load.  */
>     if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
>         || !dr_equal_offsets_p (dra, drb)
>         || DR_IS_READ (dra) != DR_IS_READ (drb))
> !     gcc_unreachable ();
>
> !   /* The caller has ensured type sizes and steps are equal.  */
>     type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
>     type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
>     if (type_size_a != type_size_b
> !       || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)) != 0)
> !     gcc_unreachable ();
> !
> !   /* Do not place the same access in the interleaving chain twice.  */
> !   if (tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb)) == 0)
> !     return false;
> !
> !   /* Check the types are compatible.  */
> !   if (!types_compatible_p (TREE_TYPE (DR_REF (dra)),
> !                          TREE_TYPE (DR_REF (drb))))
>       return false;
>
>     init_a = TREE_INT_CST_LOW (DR_INIT (dra));
>     init_b = TREE_INT_CST_LOW (DR_INIT (drb));
>     step = TREE_INT_CST_LOW (DR_STEP (dra));
>
> !   /* The caller has ensured that DR_INIT (dra) <= DR_INIT (drb).  */
> !   gcc_assert (init_a < init_b);
>
> !   /* If init_b == init_a + the size of the type * k, we have an
> !      interleaving, and DRA is accessed before DRB.  */
> !   if ((init_b - init_a) % type_size_a != 0)
> !     return false;
>
> !   /* The step (if not zero) is greater than the difference between
> !      data-refs' inits.  This splits groups into suitable sizes.  */
> !   if (step != 0 && step <= (init_b - init_a))
> !     return false;
>
> !   if (dump_enabled_p ())
> !     {
> !       dump_printf_loc (MSG_NOTE, vect_location,
> !                      "Detected interleaving ");
> !       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
> !       dump_printf (MSG_NOTE,  " and ");
> !       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
>       }
>
> !   return true;
>   }
>
>   /* Check if data references pointed by DR_I and DR_J are same or
> *************** vect_analyze_data_ref_dependence (struct
> *** 578,584 ****
>                                     loop_vec_info loop_vinfo, int *max_vf)
>   {
>     unsigned int i;
> !   struct loop *loop = NULL;
>     struct data_reference *dra = DDR_A (ddr);
>     struct data_reference *drb = DDR_B (ddr);
>     stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
> --- 319,325 ----
>                                     loop_vec_info loop_vinfo, int *max_vf)
>   {
>     unsigned int i;
> !   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
>     struct data_reference *dra = DDR_A (ddr);
>     struct data_reference *drb = DDR_B (ddr);
>     stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
> *************** vect_analyze_data_ref_dependence (struct
> *** 586,688 ****
>     lambda_vector dist_v;
>     unsigned int loop_depth;
>
> !   /* Don't bother to analyze statements marked as unvectorizable.  */
>     if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
>         || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
> !     return false;
>
>     if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
> !     {
> !       /* Independent data accesses.  */
> !       vect_check_interleaving (dra, drb);
> !       return false;
> !     }
> !
> !   if (loop_vinfo)
> !     loop = LOOP_VINFO_LOOP (loop_vinfo);
>
> !   if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
>       return false;
>
>     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
>       {
> -       gimple earlier_stmt;
> -
> -       if (loop_vinfo)
> -         {
> -           if (dump_enabled_p ())
> -             {
> -               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> -                                "versioning for alias required: "
> -                                "can't determine dependence between ");
> -               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
> -                                  DR_REF (dra));
> -               dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
> -               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
> -                                  DR_REF (drb));
> -             }
> -
> -           /* Add to list of ddrs that need to be tested at run-time.  */
> -           return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
> -         }
> -
> -       /* When vectorizing a basic block unknown depnedence can still mean
> -        grouped access.  */
> -       if (vect_check_interleaving (dra, drb))
> -          return false;
> -
> -       /* Read-read is OK (we need this check here, after checking for
> -          interleaving).  */
> -       if (DR_IS_READ (dra) && DR_IS_READ (drb))
> -         return false;
> -
> -       if (dump_enabled_p ())
> -         {
> -           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> -                            "can't determine dependence between ");
> -           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
> -           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
> -           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
> -         }
> -
> -       /* We do not vectorize basic blocks with write-write dependencies.  */
> -       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
> -         return true;
> -
> -       /* Check that it's not a load-after-store dependence.  */
> -       earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
> -       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
> -         return true;
> -
> -       return false;
> -     }
> -
> -   /* Versioning for alias is not yet supported for basic block SLP, and
> -      dependence distance is unapplicable, hence, in case of known data
> -      dependence, basic block vectorization is impossible for now.  */
> -   if (!loop_vinfo)
> -     {
> -       if (dra != drb && vect_check_interleaving (dra, drb))
> -         return false;
> -
>         if (dump_enabled_p ())
> !         {
> !           dump_printf_loc (MSG_NOTE, vect_location,
> !                            "determined dependence between ");
> !           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
> !           dump_printf (MSG_NOTE, " and ");
> !           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
> !         }
> !
> !       /* Do not vectorize basic blcoks with write-write dependences.  */
> !       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
> !         return true;
>
> !       /* Check if this dependence is allowed in basic block vectorization.  */
> !       return vect_drs_dependent_in_basic_block (dra, drb);
>       }
>
> !   /* Loop-based vectorization and known data dependence.  */
>     if (DDR_NUM_DIST_VECTS (ddr) == 0)
>       {
>         if (dump_enabled_p ())
> --- 327,365 ----
>     lambda_vector dist_v;
>     unsigned int loop_depth;
>
> !   /* In loop analysis all data references should be vectorizable.  */
>     if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
>         || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
> !     gcc_unreachable ();
>
> +   /* Independent data accesses.  */
>     if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
> !     return false;
>
> !   if (dra == drb
> !       || (DR_IS_READ (dra) && DR_IS_READ (drb)))
>       return false;
>
> +   /* Unknown data dependence.  */
>     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
>       {
>         if (dump_enabled_p ())
> !       {
> !         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> !                          "versioning for alias required: "
> !                          "can't determine dependence between ");
> !         dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
> !                            DR_REF (dra));
> !         dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
> !         dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
> !                            DR_REF (drb));
> !       }
>
> !       /* Add to list of ddrs that need to be tested at run-time.  */
> !       return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
>       }
>
> !   /* Known data dependence.  */
>     if (DDR_NUM_DIST_VECTS (ddr) == 0)
>       {
>         if (dump_enabled_p ())
> *************** vect_analyze_data_ref_dependence (struct
> *** 719,725 ****
>             }
>
>             /* For interleaving, mark that there is a read-write dependency if
> !              necessary. We check before that one of the data-refs is store.  */
>             if (DR_IS_READ (dra))
>               GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
>           else
> --- 396,402 ----
>             }
>
>             /* For interleaving, mark that there is a read-write dependency if
> !              necessary.  We check before that one of the data-refs is store.  */
>             if (DR_IS_READ (dra))
>               GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
>           else
> *************** vect_analyze_data_ref_dependence (struct
> *** 787,821 ****
>      the maximum vectorization factor the data dependences allow.  */
>
>   bool
> ! vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
> !                                    bb_vec_info bb_vinfo, int *max_vf)
>   {
>     unsigned int i;
> -   vec<ddr_p> ddrs = vNULL;
>     struct data_dependence_relation *ddr;
>
>     if (dump_enabled_p ())
>       dump_printf_loc (MSG_NOTE, vect_location,
> !                      "=== vect_analyze_dependences ===");
> !   if (loop_vinfo)
>       {
> !       if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo),
> !                                   &LOOP_VINFO_DDRS (loop_vinfo),
> !                                   LOOP_VINFO_LOOP_NEST (loop_vinfo), true))
> !       return false;
> !       ddrs = LOOP_VINFO_DDRS (loop_vinfo);
>       }
> !   else
>       {
> !       if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
> !                                   &BB_VINFO_DDRS (bb_vinfo),
> !                                   vNULL, true))
> !       return false;
> !       ddrs = BB_VINFO_DDRS (bb_vinfo);
>       }
>
> !   FOR_EACH_VEC_ELT (ddrs, i, ddr)
> !     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
>         return false;
>
>     return true;
> --- 464,624 ----
>      the maximum vectorization factor the data dependences allow.  */
>
>   bool
> ! vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo, int *max_vf)
>   {
>     unsigned int i;
>     struct data_dependence_relation *ddr;
>
>     if (dump_enabled_p ())
>       dump_printf_loc (MSG_NOTE, vect_location,
> !                      "=== vect_analyze_data_ref_dependences ===");
> !
> !   if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo),
> !                               &LOOP_VINFO_DDRS (loop_vinfo),
> !                               LOOP_VINFO_LOOP_NEST (loop_vinfo), true))
> !     return false;
> !
> !   FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo), i, ddr)
> !     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
> !       return false;
> !
> !   return true;
> ! }
> !
> !
> ! /* Function vect_slp_analyze_data_ref_dependence.
> !
> !    Return TRUE if there (might) exist a dependence between a memory-reference
> !    DRA and a memory-reference DRB.  When versioning for alias may check a
> !    dependence at run-time, return FALSE.  Adjust *MAX_VF according to
> !    the data dependence.  */
> !
> ! static bool
> ! vect_slp_analyze_data_ref_dependence (struct data_dependence_relation *ddr)
> ! {
> !   struct data_reference *dra = DDR_A (ddr);
> !   struct data_reference *drb = DDR_B (ddr);
> !
> !   /* We need to check dependences of statements marked as unvectorizable
> !      as well, they still can prohibit vectorization.  */
> !
> !   /* Independent data accesses.  */
> !   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
> !     return false;
> !
> !   if (dra == drb)
> !     return false;
> !
> !   /* Read-read is OK.  */
> !   if (DR_IS_READ (dra) && DR_IS_READ (drb))
> !     return false;
> !
> !   /* Unknown data dependence.  */
> !   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
>       {
> !       gimple earlier_stmt;
> !
> !       if (dump_enabled_p ())
> !         {
> !           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> !                            "can't determine dependence between ");
> !           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
> !           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
> !           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
> !         }
> !
> !       /* We do not vectorize basic blocks with write-write dependencies.  */
> !       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
> !         return true;
> !
> !       /* Check that it's not a load-after-store dependence.  */
> !       earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
> !       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
> !         return true;
> !
> !       return false;
>       }
> !
> !   if (dump_enabled_p ())
>       {
> !       dump_printf_loc (MSG_NOTE, vect_location,
> !                      "determined dependence between ");
> !       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
> !       dump_printf (MSG_NOTE, " and ");
> !       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
>       }
>
> !   /* Do not vectorize basic blocks with write-write dependences.  */
> !   if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
> !     return true;
> !
> !   /* Check dependence between DRA and DRB for basic block vectorization.
> !      If the accesses share same bases and offsets, we can compare their initial
> !      constant offsets to decide whether they differ or not.  In case of a read-
> !      write dependence we check that the load is before the store to ensure that
> !      vectorization will not change the order of the accesses.  */
> !
> !   HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
> !   gimple earlier_stmt;
> !
> !   /* Check that the data-refs have same bases and offsets.  If not, we can't
> !      determine if they are dependent.  */
> !   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
> !       || !dr_equal_offsets_p (dra, drb))
> !     return true;
> !
> !   /* Check the types.  */
> !   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
> !   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> !
> !   if (type_size_a != type_size_b
> !       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
> !                               TREE_TYPE (DR_REF (drb))))
> !     return true;
> !
> !   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
> !   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
> !
> !   /* Two different locations - no dependence.  */
> !   if (init_a != init_b)
> !     return false;
> !
> !   /* We have a read-write dependence.  Check that the load is before the store.
> !      When we vectorize basic blocks, vector load can be only before
> !      corresponding scalar load, and vector store can be only after its
> !      corresponding scalar store.  So the order of the acceses is preserved in
> !      case the load is before the store.  */
> !   earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
> !   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
> !     return false;
> !
> !   return true;
> ! }
> !
> !
> ! /* Function vect_analyze_data_ref_dependences.
> !
> !    Examine all the data references in the basic-block, and make sure there
> !    do not exist any data dependences between them.  Set *MAX_VF according to
> !    the maximum vectorization factor the data dependences allow.  */
> !
> ! bool
> ! vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo)
> ! {
> !   struct data_dependence_relation *ddr;
> !   unsigned int i;
> !
> !   if (dump_enabled_p ())
> !     dump_printf_loc (MSG_NOTE, vect_location,
> !                      "=== vect_slp_analyze_data_ref_dependences ===");
> !
> !   if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
> !                               &BB_VINFO_DDRS (bb_vinfo),
> !                               vNULL, true))
> !     return false;
> !
> !   FOR_EACH_VEC_ELT (BB_VINFO_DDRS (bb_vinfo), i, ddr)
> !     if (vect_slp_analyze_data_ref_dependence (ddr))
>         return false;
>
>     return true;
> *************** vect_analyze_data_ref_access (struct dat
> *** 2567,2572 ****
> --- 2370,2425 ----
>     return vect_analyze_group_access (dr);
>   }
>
> + /* Compare two data-references DRA and DRB to group them into chunks
> +    suitable for grouping.  */
> +
> + static int
> + dr_group_sort_cmp (const void *dra_, const void *drb_)
> + {
> +   data_reference_p dra = *(data_reference_p *)const_cast<void *>(dra_);
> +   data_reference_p drb = *(data_reference_p *)const_cast<void *>(drb_);
> +   int cmp;
> +
> +   /* Stabilize sort.  */
> +   if (dra == drb)
> +     return 0;
> +
> +   /* Ordering of DRs with unequal base or offset according to a hash.  */
> +   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
> +       || !dr_equal_offsets_p (dra, drb))
> +     {
> +       hashval_t h1
> +       = iterative_hash_expr (DR_BASE_ADDRESS (dra),
> +                              iterative_hash_expr (DR_OFFSET (dra), 0));
> +       hashval_t h2
> +       = iterative_hash_expr (DR_BASE_ADDRESS (drb),
> +                              iterative_hash_expr (DR_OFFSET (drb), 0));
> +       if (h1 == h2)
> +       gcc_unreachable ();
> +       return h1 < h2 ? -1 : 1;
> +     }
> +
> +   /* Else put reads first.  */
> +   if (DR_IS_READ (dra) != DR_IS_READ (drb))
> +     return DR_IS_READ (dra) ? -1 : 1;
> +
> +   /* Then sort after access size.  */
> +   cmp = tree_int_cst_compare (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
> +                             TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> +   if (cmp != 0)
> +     return cmp;
> +
> +   /* And after step.  */
> +   cmp = tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb));
> +   if (cmp != 0)
> +     return cmp;
> +
> +   /* Then sort after DR_INIT.  In case of identical DRs sort after stmt UID.  */
> +   cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
> +   if (cmp == 0)
> +     return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1;
> +   return cmp;
> + }
>
>   /* Function vect_analyze_data_ref_accesses.
>
> *************** vect_analyze_data_ref_accesses (loop_vec
> *** 2593,2598 ****
> --- 2446,2497 ----
>     else
>       datarefs = BB_VINFO_DATAREFS (bb_vinfo);
>
> +   if (datarefs.is_empty ())
> +     return true;
> +
> +   /* Sort the array of datarefs to make building the interleaving chains
> +      linear.  */
> +   qsort (datarefs.address(), datarefs.length (),
> +        sizeof (data_reference_p), dr_group_sort_cmp);
> +
> +   /* Build the interleaving chains.  */
> +   for (i = 0; i < datarefs.length () - 1;)
> +     {
> +       data_reference_p dra = datarefs[i];
> +       stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
> +       stmt_vec_info lastinfo = NULL;
> +       for (i = i + 1; i < datarefs.length (); ++i)
> +       {
> +         data_reference_p drb = datarefs[i];
> +         stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
> +         /* Check that the data-refs have same first location (except init)
> +            and they are both either store or load (not load and store).
> +            Check that the data-refs have the same size and step.  */
> +         if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
> +             || !dr_equal_offsets_p (dra, drb)
> +             || DR_IS_READ (dra) != DR_IS_READ (drb)
> +             || tree_int_cst_compare (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
> +                                      TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))))
> +             || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)))
> +           break;
> +         /* ???  Imperfect sorting (non-compatible types, non-modulo
> +            accesses, same accesses) can lead to a group to be artificially
> +            split here as we don't just skip over those.  If it really
> +            matters we can push those to a worklist and re-iterate
> +            over them.  The we can just skip ahead to the next DR here.  */
> +         if (!vect_check_interleaving (dra, drb))
> +           break;
> +         if (!GROUP_FIRST_ELEMENT (stmtinfo_a))
> +           {
> +             GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (dra);
> +             lastinfo = stmtinfo_a;
> +           }
> +         GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (dra);
> +         GROUP_NEXT_ELEMENT (lastinfo) = DR_STMT (drb);
> +         lastinfo = stmtinfo_b;
> +       }
> +     }
> +
>     FOR_EACH_VEC_ELT (datarefs, i, dr)
>       if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
>           && !vect_analyze_data_ref_access (dr))
> Index: trunk/gcc/tree-vect-slp.c
> ===================================================================
> *** trunk.orig/gcc/tree-vect-slp.c      2013-02-27 14:53:36.000000000 +0100
> --- trunk/gcc/tree-vect-slp.c   2013-02-27 14:57:30.977783197 +0100
> *************** vect_slp_analyze_bb_1 (basic_block bb)
> *** 2089,2095 ****
>     slp_instance instance;
>     int i;
>     int min_vf = 2;
> -   int max_vf = MAX_VECTORIZATION_FACTOR;
>
>     bb_vinfo = new_bb_vec_info (bb);
>     if (!bb_vinfo)
> --- 2089,2094 ----
> *************** vect_slp_analyze_bb_1 (basic_block bb)
> *** 2117,2126 ****
>         return NULL;
>       }
>
>     vect_pattern_recog (NULL, bb_vinfo);
>
> !   if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo, &max_vf)
> !        || min_vf > max_vf)
>        {
>          if (dump_enabled_p ())
>          dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> --- 2116,2135 ----
>         return NULL;
>       }
>
> +   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
> +     {
> +      if (dump_enabled_p ())
> +        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                       "not vectorized: unhandled data access in "
> +                       "basic block.\n");
> +
> +       destroy_bb_vec_info (bb_vinfo);
> +       return NULL;
> +     }
> +
>     vect_pattern_recog (NULL, bb_vinfo);
>
> !   if (!vect_slp_analyze_data_ref_dependences (bb_vinfo))
>        {
>          if (dump_enabled_p ())
>          dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> *************** vect_slp_analyze_bb_1 (basic_block bb)
> *** 2140,2156 ****
>
>         destroy_bb_vec_info (bb_vinfo);
>         return NULL;
> -     }
> -
> -   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
> -     {
> -      if (dump_enabled_p ())
> -        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> -                       "not vectorized: unhandled data access in "
> -                       "basic block.\n");
> -
> -       destroy_bb_vec_info (bb_vinfo);
> -       return NULL;
>       }
>
>     /* Check the SLP opportunities in the basic block, analyze and build SLP
> --- 2149,2154 ----
> Index: trunk/gcc/tree-vect-loop.c
> ===================================================================
> *** trunk.orig/gcc/tree-vect-loop.c     2013-02-27 14:53:36.000000000 +0100
> --- trunk/gcc/tree-vect-loop.c  2013-02-27 14:57:30.978783208 +0100
> *************** vect_analyze_loop_2 (loop_vec_info loop_
> *** 1603,1608 ****
> --- 1603,1620 ----
>         return false;
>       }
>
> +   /* Analyze the access patterns of the data-refs in the loop (consecutive,
> +      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
> +
> +   ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
> +   if (!ok)
> +     {
> +       if (dump_enabled_p ())
> +       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                        "bad data access.");
> +       return false;
> +     }
> +
>     /* Classify all cross-iteration scalar data-flow cycles.
>        Cross-iteration cycles caused by virtual phis are analyzed separately.  */
>
> *************** vect_analyze_loop_2 (loop_vec_info loop_
> *** 1626,1632 ****
>        the dependences.
>        FORNOW: fail at the first data dependence that we encounter.  */
>
> !   ok = vect_analyze_data_ref_dependences (loop_vinfo, NULL, &max_vf);
>     if (!ok
>         || max_vf < min_vf)
>       {
> --- 1638,1644 ----
>        the dependences.
>        FORNOW: fail at the first data dependence that we encounter.  */
>
> !   ok = vect_analyze_data_ref_dependences (loop_vinfo, &max_vf);
>     if (!ok
>         || max_vf < min_vf)
>       {
> *************** vect_analyze_loop_2 (loop_vec_info loop_
> *** 1664,1681 ****
>         return false;
>       }
>
> -   /* Analyze the access patterns of the data-refs in the loop (consecutive,
> -      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
> -
> -   ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
> -   if (!ok)
> -     {
> -       if (dump_enabled_p ())
> -       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> -                        "bad data access.");
> -       return false;
> -     }
> -
>     /* Prune the list of ddrs to be tested at run-time by versioning for alias.
>        It is important to call pruning after vect_analyze_data_ref_accesses,
>        since we use grouping information gathered by interleaving analysis.  */
> --- 1676,1681 ----
> Index: trunk/gcc/tree-vectorizer.h
> ===================================================================
> *** trunk.orig/gcc/tree-vectorizer.h    2013-02-27 14:53:36.000000000 +0100
> --- trunk/gcc/tree-vectorizer.h 2013-02-27 14:57:30.978783208 +0100
> *************** extern enum dr_alignment_support vect_su
> *** 914,921 ****
>                                              (struct data_reference *, bool);
>   extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
>                                              HOST_WIDE_INT *);
> ! extern bool vect_analyze_data_ref_dependences (loop_vec_info, bb_vec_info,
> !                                              int *);
>   extern bool vect_enhance_data_refs_alignment (loop_vec_info);
>   extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info);
>   extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);
> --- 914,921 ----
>                                              (struct data_reference *, bool);
>   extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
>                                              HOST_WIDE_INT *);
> ! extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *);
> ! extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info);
>   extern bool vect_enhance_data_refs_alignment (loop_vec_info);
>   extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info);
>   extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]