Re: [3/4] SMS: Record moves in the partial schedule
Ayal Zaks ayal.z...@gmail.com writes: On Wed, Sep 28, 2011 at 4:53 PM, Richard Sandiford richard.sandif...@linaro.org wrote: Ayal Zaks ayal.z...@gmail.com writes: Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. Ok then, very well. I was mostly referring to the following in prologue/epiloque code, which merely relies on assigning all regmoves of a node consecutive id's: FWIW, the 4/4 that I just posted did finally get rid of the first_reg_move nreg_moves fields. Here's a slightly updated patch in line with your 4/4 comments. The move-def is now always the id of the predecessor, rather than the id of the original ddg node producer. I've adapted the throw-away loop accordingly, but there are no other changes. This is ok. Thanks. Just to make sure I follow, the changes were (for this patch): 1. setting up a different move-def for each move + move-def = i_reg_move 0 ? first_move + i_reg_move - 1 : i; instead of the same original def for all + move-def = i; 2. inserting each move right before its own def, bottom-up: + FOR_EACH_VEC_ELT (ps_reg_move_info, ps-reg_moves, i, move) +add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); instead of inserting each move right before the original def, top-down: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); Yeah, those were the ones. Richard
Re: [3/4] SMS: Record moves in the partial schedule
On Wed, Sep 28, 2011 at 4:53 PM, Richard Sandiford richard.sandif...@linaro.org wrote: Ayal Zaks ayal.z...@gmail.com writes: Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. Ok then, very well. I was mostly referring to the following in prologue/epiloque code, which merely relies on assigning all regmoves of a node consecutive id's: FWIW, the 4/4 that I just posted did finally get rid of the first_reg_move nreg_moves fields. Here's a slightly updated patch in line with your 4/4 comments. The move-def is now always the id of the predecessor, rather than the id of the original ddg node producer. I've adapted the throw-away loop accordingly, but there are no other changes. This is ok. Just to make sure I follow, the changes were (for this patch): 1. setting up a different move-def for each move + move-def = i_reg_move 0 ? first_move + i_reg_move - 1 : i; instead of the same original def for all + move-def = i; 2. inserting each move right before its own def, bottom-up: + FOR_EACH_VEC_ELT (ps_reg_move_info, ps-reg_moves, i, move) +add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); instead of inserting each move right before the original def, top-down: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); Thanks, Ayal. Tested on powerpc64-linux-gnu and with ARM benchmarks. Richard gcc/ * modulo-sched.c (ps_insn): Adjust comment. (ps_reg_move_info): New structure. (partial_schedule): Add reg_moves field. (SCHED_PARAMS): Use node_sched_param_vec instead of node_sched_params. (node_sched_params): Turn first_reg_move into an identifier. (ps_reg_move): New function. (ps_rtl_insn): Cope with register moves. (ps_first_note): Adjust comment and assert that the instruction isn't a register move. (node_sched_params): Replace with... (node_sched_param_vec): ...this vector. (set_node_sched_params): Adjust accordingly. (print_node_sched_params): Take a partial schedule instead of a ddg. Use ps_rtl_insn and ps_reg_move. (generate_reg_moves): Rename to... (schedule_reg_moves): ...this. Remove rescan parameter. Record each move in the partial schedule, but don't emit it here. Don't perform register substitutions here either. (apply_reg_moves): New function. (duplicate_insns_of_cycles): Use register indices directly, rather than finding instructions using PREV_INSN. Use ps_reg_move. (sms_schedule): Call schedule_reg_moves before committing to a partial schedule. Try the next ii if the schedule fails. Use apply_reg_moves instead of generate_reg_moves. Adjust call to print_node_sched_params. Free node_sched_param_vec instead of node_sched_params. (create_partial_schedule): Initialize reg_moves. (free_partial_schedule): Free reg_moves. Index: gcc/modulo-sched.c === --- gcc/modulo-sched.c 2011-09-28 09:03:10.334301485 +0100 +++ gcc/modulo-sched.c 2011-09-28 11:24:26.530300781 +0100 @@ -124,7 +124,9 @@ #define PS_STAGE_COUNT(ps) (((partial_sc /* A single instruction in the partial schedule. */ struct ps_insn { - /* The number of the ddg node whose instruction is being scheduled. */ + /* Identifies the instruction to be scheduled. Values smaller than + the ddg's num_nodes refer directly to ddg nodes. A value of + X - num_nodes refers to register move X. */ int id; /* The (absolute) cycle in which the PS instruction is scheduled. @@ -137,6 +139,30 @@ struct ps_insn }; +/* Information about a register move that has been added to a partial + schedule. */ +struct ps_reg_move_info +{ + /* The source of the move is defined by the ps_insn with id DEF. + The destination is used by the ps_insns with the ids in USES. */ + int def; + sbitmap uses; + + /* The original form of USES' instructions used OLD_REG, but they + should now use NEW_REG. */ + rtx old_reg; + rtx new_reg; + + /* An instruction that sets NEW_REG to the correct value. The first + move associated with DEF will have an rhs of OLD_REG; later moves + use the result of the previous move. */ + rtx insn; +}; + +typedef struct ps_reg_move_info ps_reg_move_info; +DEF_VEC_O (ps_reg_move_info); +DEF_VEC_ALLOC_O (ps_reg_move_info,
Re: [3/4] SMS: Record moves in the partial schedule
Ayal Zaks ayal.z...@gmail.com writes: Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. Ok then, very well. I was mostly referring to the following in prologue/epiloque code, which merely relies on assigning all regmoves of a node consecutive id's: FWIW, the 4/4 that I just posted did finally get rid of the first_reg_move nreg_moves fields. Here's a slightly updated patch in line with your 4/4 comments. The move-def is now always the id of the predecessor, rather than the id of the original ddg node producer. I've adapted the throw-away loop accordingly, but there are no other changes. Tested on powerpc64-linux-gnu and with ARM benchmarks. Richard gcc/ * modulo-sched.c (ps_insn): Adjust comment. (ps_reg_move_info): New structure. (partial_schedule): Add reg_moves field. (SCHED_PARAMS): Use node_sched_param_vec instead of node_sched_params. (node_sched_params): Turn first_reg_move into an identifier. (ps_reg_move): New function. (ps_rtl_insn): Cope with register moves. (ps_first_note): Adjust comment and assert that the instruction isn't a register move. (node_sched_params): Replace with... (node_sched_param_vec): ...this vector. (set_node_sched_params): Adjust accordingly. (print_node_sched_params): Take a partial schedule instead of a ddg. Use ps_rtl_insn and ps_reg_move. (generate_reg_moves): Rename to... (schedule_reg_moves): ...this. Remove rescan parameter. Record each move in the partial schedule, but don't emit it here. Don't perform register substitutions here either. (apply_reg_moves): New function. (duplicate_insns_of_cycles): Use register indices directly, rather than finding instructions using PREV_INSN. Use ps_reg_move. (sms_schedule): Call schedule_reg_moves before committing to a partial schedule. Try the next ii if the schedule fails. Use apply_reg_moves instead of generate_reg_moves. Adjust call to print_node_sched_params. Free node_sched_param_vec instead of node_sched_params. (create_partial_schedule): Initialize reg_moves. (free_partial_schedule): Free reg_moves. Index: gcc/modulo-sched.c === --- gcc/modulo-sched.c 2011-09-28 09:03:10.334301485 +0100 +++ gcc/modulo-sched.c 2011-09-28 11:24:26.530300781 +0100 @@ -124,7 +124,9 @@ #define PS_STAGE_COUNT(ps) (((partial_sc /* A single instruction in the partial schedule. */ struct ps_insn { - /* The number of the ddg node whose instruction is being scheduled. */ + /* Identifies the instruction to be scheduled. Values smaller than + the ddg's num_nodes refer directly to ddg nodes. A value of + X - num_nodes refers to register move X. */ int id; /* The (absolute) cycle in which the PS instruction is scheduled. @@ -137,6 +139,30 @@ struct ps_insn }; +/* Information about a register move that has been added to a partial + schedule. */ +struct ps_reg_move_info +{ + /* The source of the move is defined by the ps_insn with id DEF. + The destination is used by the ps_insns with the ids in USES. */ + int def; + sbitmap uses; + + /* The original form of USES' instructions used OLD_REG, but they + should now use NEW_REG. */ + rtx old_reg; + rtx new_reg; + + /* An instruction that sets NEW_REG to the correct value. The first + move associated with DEF will have an rhs of OLD_REG; later moves + use the result of the previous move. */ + rtx insn; +}; + +typedef struct ps_reg_move_info ps_reg_move_info; +DEF_VEC_O (ps_reg_move_info); +DEF_VEC_ALLOC_O (ps_reg_move_info, heap); + /* Holds the partial schedule as an array of II rows. Each entry of the array points to a linked list of PS_INSNs, which represents the instructions that are scheduled for that row. */ @@ -148,6 +174,10 @@ struct partial_schedule /* rows[i] points to linked list of insns scheduled in row i (0=iii). */ ps_insn_ptr *rows; + /* All the moves added for this partial schedule. Index X has + a ps_insn id of X + g-num_nodes. */ + VEC (ps_reg_move_info, heap) *reg_moves; + /* rows_length[i] holds the number of instructions in the row. It is used only (as an optimization) to back off quickly from trying to schedule a node in a full row; that is, to avoid running @@ -201,7 +231,7 @@ static void remove_node_from_ps (partial #define NODE_ASAP(node)
Re: [3/4] SMS: Record moves in the partial schedule
Ayal Zaks ayal.z...@gmail.com writes: Richard Sandiford richard.sandif...@linaro.org wrote on 30/08/2011 03:10:50 PM: From: Richard Sandiford richard.sandif...@linaro.org To: gcc-patches@gcc.gnu.org Cc: Ayal Zaks/Haifa/IBM@IBMIL Date: 30/08/2011 03:10 PM Subject: [3/4] SMS: Record moves in the partial schedule This patch adds infrastructure that will be used by the final patch. Specifically: - it splits the generation of register moves into two: schedule_reg_moves records moves in the partial schedule, while apply_reg_moves makes the register substitutions. This patch doesn't actually schedule the moves. Instead, there's some throw-away code in apply_reg_moves to emit the moves in the same as we do now. That's throw-away code that will be removed in the final patch. - schedule_reg_moves is allowed to fail. We then try again with the next ii (subject to the usual ii limits). In this patch, schedule_reg_moves always returns true. - The partial schedule uses ids to represent register moves. The first register move has id g-num_nodes. Richard This is fine. Thanks. Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. I'd rather the code didn't rely on any ordering here. If any future code is added that needs to know more about the moves, I think it should use the move structure instead of the ids. (There's already a fair bit of info in the structure, but we could add more later if we need it.) Functionality-wise it results in identical code as current version, right? Yeah, that's right. Only patch 4 does anything useful to the output. Richard
Re: [3/4] SMS: Record moves in the partial schedule
Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. Ok then, very well. I was mostly referring to the following in prologue/epiloque code, which merely relies on assigning all regmoves of a node consecutive id's: i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u)); /* The reg_moves start from the *first* reg_move backwards. */ ! i_reg_move = SCHED_FIRST_REG_MOVE (u) + (i_reg_moves - 1); Ayal. 2011/9/22 Richard Sandiford richard.sandif...@linaro.org Ayal Zaks ayal.z...@gmail.com writes: Richard Sandiford richard.sandif...@linaro.org wrote on 30/08/2011 03:10:50 PM: From: Richard Sandiford richard.sandif...@linaro.org To: gcc-patches@gcc.gnu.org Cc: Ayal Zaks/Haifa/IBM@IBMIL Date: 30/08/2011 03:10 PM Subject: [3/4] SMS: Record moves in the partial schedule This patch adds infrastructure that will be used by the final patch. Specifically: - it splits the generation of register moves into two: schedule_reg_moves records moves in the partial schedule, while apply_reg_moves makes the register substitutions. This patch doesn't actually schedule the moves. Instead, there's some throw-away code in apply_reg_moves to emit the moves in the same as we do now. That's throw-away code that will be removed in the final patch. - schedule_reg_moves is allowed to fail. We then try again with the next ii (subject to the usual ii limits). In this patch, schedule_reg_moves always returns true. - The partial schedule uses ids to represent register moves. The first register move has id g-num_nodes. Richard This is fine. Thanks. Only request is to document that the register moves are placed/assigned-id's in a specific order. I suppose this is the downside of splitting the patches up, sorry, but the ids are only ordered for the throw-away loop: FOR_EACH_VEC_ELT_REVERSE (ps_reg_move_info, ps-reg_moves, i, move) add_insn_before (move-insn, ps_first_note (ps, move-def), NULL); and for the prologue/epilogue code. Both are replaced in patch 4 with code that doesn't rely on the ordering of ids. I'd rather the code didn't rely on any ordering here. If any future code is added that needs to know more about the moves, I think it should use the move structure instead of the ids. (There's already a fair bit of info in the structure, but we could add more later if we need it.) Functionality-wise it results in identical code as current version, right? Yeah, that's right. Only patch 4 does anything useful to the output. Richard
Re: [3/4] SMS: Record moves in the partial schedule
Richard Sandiford richard.sandif...@linaro.org wrote on 30/08/2011 03:10:50 PM: From: Richard Sandiford richard.sandif...@linaro.org To: gcc-patches@gcc.gnu.org Cc: Ayal Zaks/Haifa/IBM@IBMIL Date: 30/08/2011 03:10 PM Subject: [3/4] SMS: Record moves in the partial schedule This patch adds infrastructure that will be used by the final patch. Specifically: - it splits the generation of register moves into two: schedule_reg_moves records moves in the partial schedule, while apply_reg_moves makes the register substitutions. This patch doesn't actually schedule the moves. Instead, there's some throw-away code in apply_reg_moves to emit the moves in the same as we do now. That's throw-away code that will be removed in the final patch. - schedule_reg_moves is allowed to fail. We then try again with the next ii (subject to the usual ii limits). In this patch, schedule_reg_moves always returns true. - The partial schedule uses ids to represent register moves. The first register move has id g-num_nodes. Richard This is fine. Only request is to document that the register moves are placed/assigned-id's in a specific order. Functionality-wise it results in identical code as current version, right? Thanks, Ayal.