parameters: (
          block, ops, target_block, no_grad_dict, grad_to_var, checkpoints)
return_statement: return program_stat, checkpoints_name, vars_should_be_hold, recompute_segments
docstring: Create grad ops with forward ops, and insert them into given block
  
      Args:
          block(Block): the block where forward ops are
          ops(Op): the forward operators whose forward recomputation backward ops need to be added
          target_block(Block): the block which is going to hold new generated grad ops
          no_grad_dict(dict):
              key(int) block index
              val(str): corresponding forward variable name
          checkpoints: variables that a user defined as checkpoint for forward recomputation
  
      Algorithms:
          0) deal with forward recomputing program descs
          1) find ops between checkpoints, i.e. recompute_segments
          2) go through all forward ops and induct all variables that will be hold in memory
              a. variables that are used across segments will be held in memory
              b. output of dropout op will be held in memory
              c. input variables will be held in memory
          3) go through each recompute_segments, add backward ops with forward recomputation
              a. add ops in current recompute_segment as forward recomputation ops
              b. rename all non-checkpoint variables in recomputation ops
              c. add backward ops of current recomputation ops
              d. add sum op for repetitive_outputs
          4) remove no grad branch as it is in _remove_no_grad_branch_
          5) Note1: all appended ops' OpRole are Backward
          6) Note2: all variables with new name should be returned so that _append_backward_vars_ can be called
          7) Note3: current forward recomputation backpropagation does not handle programs with subblock
docstring_summary: Create grad ops with forward ops, and insert them into given block
docstring_tokens: Create grad ops with forward ops and insert them into given block
function: def _append_backward_ops_with_checkpoints_(
          block, ops, target_block, no_grad_dict, grad_to_var, checkpoints):
      """
      Create grad ops with forward ops, and insert them into given block
  
      Args:
          block(Block): the block where forward ops are
          ops(Op): the forward operators whose forward recomputation backward ops need to be added
          target_block(Block): the block which is going to hold new generated grad ops
          no_grad_dict(dict):
              key(int) block index
              val(str): corresponding forward variable name
          checkpoints: variables that a user defined as checkpoint for forward recomputation
  
      Algorithms:
          0) deal with forward recomputing program descs
          1) find ops between checkpoints, i.e. recompute_segments
          2) go through all forward ops and induct all variables that will be hold in memory
              a. variables that are used across segments will be held in memory
              b. output of dropout op will be held in memory
              c. input variables will be held in memory
          3) go through each recompute_segments, add backward ops with forward recomputation
              a. add ops in current recompute_segment as forward recomputation ops
              b. rename all non-checkpoint variables in recomputation ops
              c. add backward ops of current recomputation ops
              d. add sum op for repetitive_outputs
          4) remove no grad branch as it is in _remove_no_grad_branch_
          5) Note1: all appended ops' OpRole are Backward
          6) Note2: all variables with new name should be returned so that _append_backward_vars_ can be called
          7) Note3: current forward recomputation backpropagation does not handle programs with subblock
      """
  
      checkpoints_name = [x.name for x in checkpoints]
      checkpoints_name = list(set(checkpoints_name))
      local_block = block.program._create_block()
      buffer_block = block.program._create_block()
      # 0) deal with forward recomputing program descs
      program_stat = ProgramStats(block, ops)
      program_stat.modify_forward_desc_for_recompute()
      program_stat.build_stats()
  
      # 1) find ops between checkpoints, i.e. recompute_segments
      checkpoints_name = program_stat.sort_checkpoints(checkpoints_name)
      segments = []
  
      if len(checkpoints_name) == 1:
          # only one checkpoint
          max_op_idx = -1
          var_group = [checkpoints_name[0]]
          for name in var_group:
              if name not in program_stat.var_op_deps:
                  break
              op_idx = program_stat.var_op_deps[name]["var_as_output_ops"]
              # only count the last generate op
              for idx in op_idx:
                  max_op_idx = max(max_op_idx, idx)
          if max_op_idx > 0:
              segments.append([0, max_op_idx + 1])
      else:
          start_idx = 0
          pre_segment_end_idx = -1
          while True:
              if start_idx >= len(checkpoints_name) - 1:
                  break
              # min_idx: checkpoint_1' s input op
              # max_idx: checkpoint_2' s output op
              flag, min_idx, max_idx = program_stat.is_subgraph(
                  [checkpoints_name[start_idx]],
                  [checkpoints_name[start_idx + 1]])
              if flag:
                  # max_idx + 1 since the exact and used segment end idx is max_idx
                  min_idx = program_stat._update_segment_start(
                      min_idx, pre_segment_end_idx)
                  segments.append([min_idx, max_idx + 1])
              else:
                  _logger.info("Could not recompute op range [{}] - [{}] ".format(
                      min_idx, max_idx + 1))
  
              start_idx += 1
  
      if segments != [] and segments[0][0] != 0:
          recompute_segments = [[0, segments[0][0]]] + segments
      else:
          recompute_segments = segments
  
      for i, (idx1, idx2) in enumerate(recompute_segments):
          _logger.info("recompute segment[{}]".format(i))
          _logger.info("segment start op: [{}]: [{}]".format(ops[idx1].desc.type(
          ), ops[idx1].desc.input_arg_names()))
          _logger.info("segment end op: [{}]: [{}]".format(ops[
              idx2 - 1].desc.type(), ops[idx2 - 1].desc.input_arg_names()))
          _logger.info("recompute segment[{}]".format(i))
          _logger.info("segment start op: [{}]: [{}]".format(ops[idx1].desc.type(
          ), ops[idx1].desc.input_arg_names()))
          _logger.info("segment end op: [{}]: [{}]".format(ops[
              idx2 - 1].desc.type(), ops[idx2 - 1].desc.input_arg_names()))
  
      # 2) go through all forward ops and induct all variables that will be hold in memory
      vars_should_be_hold = []
      # a. variables that are used across segments will be held in memory
      for segment in recompute_segments:
          vars_should_be_hold.extend(
              program_stat.get_out_of_subgraph_vars(segment[0], segment[1]))
  
      cross_vars = set(vars_should_be_hold) - set(checkpoints_name)
      _logger.info("found [{}] vars which cross recompute segment: [{}], better checkpoints might be set to reduce those vars".format( \
      len(cross_vars), cross_vars))
  
      # b. output of seed op should be kept in memory
      vars_should_be_hold.extend(program_stat.get_reserved_vars())
      # c. input variables are checkpoints
      vars_should_be_hold.extend(program_stat.get_input_nodes())
      vars_should_be_hold = list(set(vars_should_be_hold))
  
      # 3) go through each recompute_segments, add backward ops with forward recomputation
      grad_op_descs = []
      var_name_dict = {}
  
      vars_in_memory = vars_should_be_hold + checkpoints_name
  
      max_calculated_op_position = len(ops)
      device_attr_name = core.op_proto_and_checker_maker.kOpDeviceAttrName()
      if recompute_segments == []:
          gap_ops = ops[0:max_calculated_op_position]
          for op in reversed(gap_ops):
              if op.has_attr("sub_block"):
                  raise Exception("Recompute don't support ops with sub_block"
                                  "invoke op: %s" %
                                  _pretty_op_desc_(op.desc, "with_sub_block"))
              grad_op_desc, op_grad_to_var = core.get_grad_op_desc(
                  op.desc, cpt.to_text(no_grad_dict[block.idx]), [])
              # Set device for grad_op according to forward Op
              if op.desc.has_attr(device_attr_name):
                  op_device = op.desc.attr(device_attr_name)
                  for op_desc in grad_op_desc:
                      op_desc._set_attr(device_attr_name, op_device)
              added_descs = _add_descs_to_block(grad_op_desc, local_block)
              grad_op_descs.extend(added_descs)
              grad_to_var.update(op_grad_to_var)
  
      for i, segment in enumerate(recompute_segments[::-1]):
          gap_ops = ops[segment[1]:max_calculated_op_position]
          max_calculated_op_position = segment[0]
          for op in reversed(gap_ops):
              if op.has_attr("sub_block"):
                  raise Exception("Recompute don't support ops with sub_block"
                                  "invoke op: %s" %
                                  _pretty_op_desc_(op.desc, "with_sub_block"))
              grad_op_desc, op_grad_to_var = core.get_grad_op_desc(
                  op.desc, cpt.to_text(no_grad_dict[block.idx]), [])
              # Set device for grad_op according to forward Op
              if op.desc.has_attr(device_attr_name):
                  op_device = op.desc.attr(device_attr_name)
                  for op_desc in grad_op_desc:
                      op_desc._set_attr(device_attr_name, op_device)
              added_descs = _add_descs_to_block(grad_op_desc, local_block)
              grad_op_descs.extend(added_descs)
              grad_to_var.update(op_grad_to_var)
  
          ff_ops = ops[segment[0]:segment[1]]
          var_suffix = ".subprog_%d" % i
  
          for op in ff_ops:
              if op.has_attr("sub_block"):
                  raise Exception("Recompute don't support ops with sub_block"
                                  "invoke op: %s" %
                                  _pretty_op_desc_(op.desc, "with_sub_block"))
              input_and_output_names = []
              input_and_output_names.extend(op.desc.input_arg_names())
              input_and_output_names.extend(op.desc.output_arg_names())
              for name in input_and_output_names:
                  if block.var(name).persistable or name in checkpoints_name:
                      continue
                  if name in vars_should_be_hold:
                      continue
                  if name not in var_name_dict:
                      var_name_dict[name] = name + var_suffix
  
                      # we should create the rename var in subprog, otherwise its VarType will be BOOL
                      ref_var = block.program.global_block().var(name)
                      block.create_var(
                          name=var_name_dict[name],
                          shape=ref_var.shape,
                          dtype=ref_var.dtype,
                          type=ref_var.type,
                          persistable=ref_var.persistable,
                          stop_gradient=ref_var.stop_gradient)
  
          # 3.a. add ops in current recompute_segment as forward recomputation ops
          buffer_descs = _add_needed_descs_to_block(ff_ops, buffer_block, block,
                                                    vars_in_memory)
          added_descs = _add_descs_to_block(ff_ops, local_block)
  
          # 3.b. rename all non-checkpoint variables in recomputation ops
          for key in var_name_dict:
              _rename_arg_(buffer_descs, key, var_name_dict[key])
  
          # added_descs should be in grad_op_descs because it is backward op desc
          grad_op_descs.extend(buffer_descs)
  
          # 3.c. add backward ops for all ops in current segment
          for op_desc in reversed(added_descs):
              grad_op_desc, op_grad_to_var = core.get_grad_op_desc(
                  op_desc, cpt.to_text(no_grad_dict[block.idx]), [])
  
              # Set device for grad_op according to forward Op
              if op_desc.has_attr(device_attr_name):
                  op_device = op_desc.attr(device_attr_name)
                  for g_op_desc in grad_op_desc:
                      g_op_desc._set_attr(device_attr_name, op_device)
  
              for key in var_name_dict:
                  _rename_arg_(grad_op_desc, key, var_name_dict[key])
              grad_op_descs.extend(grad_op_desc)
              grad_to_var.update(op_grad_to_var)
  
      # 3.d. add sum op for repetitive_outputs
      grad_op_descs = _addup_repetitive_outputs_(grad_op_descs, block.idx)
      # 4) remove no grad branch as it is in _remove_no_grad_branch_
      grad_op_descs = _remove_no_grad_branch_(grad_op_descs,
                                              no_grad_dict[block.idx])
      added_descs = _add_descs_to_block(grad_op_descs, target_block)
      return program_stat, checkpoints_name, vars_should_be_hold, recompute_segments
function_tokens: def _append_backward_ops_with_checkpoints_ ( block , ops , target_block , no_grad_dict , grad_to_var , checkpoints ) : checkpoints_name = [ x . name for x in checkpoints ] checkpoints_name = list ( set ( checkpoints_name ) ) local_block = block . program . _create_block ( ) buffer_block = block . program . _create_block ( ) # 0) deal with forward recomputing program descs program_stat = ProgramStats ( block , ops ) program_stat . modify_forward_desc_for_recompute ( ) program_stat . build_stats ( ) # 1) find ops between checkpoints, i.e. recompute_segments checkpoints_name = program_stat . sort_checkpoints ( checkpoints_name ) segments = [ ] if len ( checkpoints_name ) == 1 : # only one checkpoint max_op_idx = - 1 var_group = [ checkpoints_name [ 0 ] ] for name in var_group : if name not in program_stat . var_op_deps : break op_idx = program_stat . var_op_deps [ name ] [ "var_as_output_ops" ] # only count the last generate op for idx in op_idx : max_op_idx = max ( max_op_idx , idx ) if max_op_idx > 0 : segments . append ( [ 0 , max_op_idx + 1 ] ) else : start_idx = 0 pre_segment_end_idx = - 1 while True : if start_idx >= len ( checkpoints_name ) - 1 : break # min_idx: checkpoint_1' s input op # max_idx: checkpoint_2' s output op flag , min_idx , max_idx = program_stat . is_subgraph ( [ checkpoints_name [ start_idx ] ] , [ checkpoints_name [ start_idx + 1 ] ] ) if flag : # max_idx + 1 since the exact and used segment end idx is max_idx min_idx = program_stat . _update_segment_start ( min_idx , pre_segment_end_idx ) segments . append ( [ min_idx , max_idx + 1 ] ) else : _logger . info ( "Could not recompute op range [{}] - [{}] " . format ( min_idx , max_idx + 1 ) ) start_idx += 1 if segments != [ ] and segments [ 0 ] [ 0 ] != 0 : recompute_segments = [ [ 0 , segments [ 0 ] [ 0 ] ] ] + segments else : recompute_segments = segments for i , ( idx1 , idx2 ) in enumerate ( recompute_segments ) : _logger . info ( "recompute segment[{}]" . format ( i ) ) _logger . info ( "segment start op: [{}]: [{}]" . format ( ops [ idx1 ] . desc . type ( ) , ops [ idx1 ] . desc . input_arg_names ( ) ) ) _logger . info ( "segment end op: [{}]: [{}]" . format ( ops [ idx2 - 1 ] . desc . type ( ) , ops [ idx2 - 1 ] . desc . input_arg_names ( ) ) ) _logger . info ( "recompute segment[{}]" . format ( i ) ) _logger . info ( "segment start op: [{}]: [{}]" . format ( ops [ idx1 ] . desc . type ( ) , ops [ idx1 ] . desc . input_arg_names ( ) ) ) _logger . info ( "segment end op: [{}]: [{}]" . format ( ops [ idx2 - 1 ] . desc . type ( ) , ops [ idx2 - 1 ] . desc . input_arg_names ( ) ) ) # 2) go through all forward ops and induct all variables that will be hold in memory vars_should_be_hold = [ ] # a. variables that are used across segments will be held in memory for segment in recompute_segments : vars_should_be_hold . extend ( program_stat . get_out_of_subgraph_vars ( segment [ 0 ] , segment [ 1 ] ) ) cross_vars = set ( vars_should_be_hold ) - set ( checkpoints_name ) _logger . info ( "found [{}] vars which cross recompute segment: [{}], better checkpoints might be set to reduce those vars" . format ( len ( cross_vars ) , cross_vars ) ) # b. output of seed op should be kept in memory vars_should_be_hold . extend ( program_stat . get_reserved_vars ( ) ) # c. input variables are checkpoints vars_should_be_hold . extend ( program_stat . get_input_nodes ( ) ) vars_should_be_hold = list ( set ( vars_should_be_hold ) ) # 3) go through each recompute_segments, add backward ops with forward recomputation grad_op_descs = [ ] var_name_dict = { } vars_in_memory = vars_should_be_hold + checkpoints_name max_calculated_op_position = len ( ops ) device_attr_name = core . op_proto_and_checker_maker . kOpDeviceAttrName ( ) if recompute_segments == [ ] : gap_ops = ops [ 0 : max_calculated_op_position ] for op in reversed ( gap_ops ) : if op . has_attr ( "sub_block" ) : raise Exception ( "Recompute don't support ops with sub_block" "invoke op: %s" % _pretty_op_desc_ ( op . desc , "with_sub_block" ) ) grad_op_desc , op_grad_to_var = core . get_grad_op_desc ( op . desc , cpt . to_text ( no_grad_dict [ block . idx ] ) , [ ] ) # Set device for grad_op according to forward Op if op . desc . has_attr ( device_attr_name ) : op_device = op . desc . attr ( device_attr_name ) for op_desc in grad_op_desc : op_desc . _set_attr ( device_attr_name , op_device ) added_descs = _add_descs_to_block ( grad_op_desc , local_block ) grad_op_descs . extend ( added_descs ) grad_to_var . update ( op_grad_to_var ) for i , segment in enumerate ( recompute_segments [ : : - 1 ] ) : gap_ops = ops [ segment [ 1 ] : max_calculated_op_position ] max_calculated_op_position = segment [ 0 ] for op in reversed ( gap_ops ) : if op . has_attr ( "sub_block" ) : raise Exception ( "Recompute don't support ops with sub_block" "invoke op: %s" % _pretty_op_desc_ ( op . desc , "with_sub_block" ) ) grad_op_desc , op_grad_to_var = core . get_grad_op_desc ( op . desc , cpt . to_text ( no_grad_dict [ block . idx ] ) , [ ] ) # Set device for grad_op according to forward Op if op . desc . has_attr ( device_attr_name ) : op_device = op . desc . attr ( device_attr_name ) for op_desc in grad_op_desc : op_desc . _set_attr ( device_attr_name , op_device ) added_descs = _add_descs_to_block ( grad_op_desc , local_block ) grad_op_descs . extend ( added_descs ) grad_to_var . update ( op_grad_to_var ) ff_ops = ops [ segment [ 0 ] : segment [ 1 ] ] var_suffix = ".subprog_%d" % i for op in ff_ops : if op . has_attr ( "sub_block" ) : raise Exception ( "Recompute don't support ops with sub_block" "invoke op: %s" % _pretty_op_desc_ ( op . desc , "with_sub_block" ) ) input_and_output_names = [ ] input_and_output_names . extend ( op . desc . input_arg_names ( ) ) input_and_output_names . extend ( op . desc . output_arg_names ( ) ) for name in input_and_output_names : if block . var ( name ) . persistable or name in checkpoints_name : continue if name in vars_should_be_hold : continue if name not in var_name_dict : var_name_dict [ name ] = name + var_suffix # we should create the rename var in subprog, otherwise its VarType will be BOOL ref_var = block . program . global_block ( ) . var ( name ) block . create_var ( name = var_name_dict [ name ] , shape = ref_var . shape , dtype = ref_var . dtype , type = ref_var . type , persistable = ref_var . persistable , stop_gradient = ref_var . stop_gradient ) # 3.a. add ops in current recompute_segment as forward recomputation ops buffer_descs = _add_needed_descs_to_block ( ff_ops , buffer_block , block , vars_in_memory ) added_descs = _add_descs_to_block ( ff_ops , local_block ) # 3.b. rename all non-checkpoint variables in recomputation ops for key in var_name_dict : _rename_arg_ ( buffer_descs , key , var_name_dict [ key ] ) # added_descs should be in grad_op_descs because it is backward op desc grad_op_descs . extend ( buffer_descs ) # 3.c. add backward ops for all ops in current segment for op_desc in reversed ( added_descs ) : grad_op_desc , op_grad_to_var = core . get_grad_op_desc ( op_desc , cpt . to_text ( no_grad_dict [ block . idx ] ) , [ ] ) # Set device for grad_op according to forward Op if op_desc . has_attr ( device_attr_name ) : op_device = op_desc . attr ( device_attr_name ) for g_op_desc in grad_op_desc : g_op_desc . _set_attr ( device_attr_name , op_device ) for key in var_name_dict : _rename_arg_ ( grad_op_desc , key , var_name_dict [ key ] ) grad_op_descs . extend ( grad_op_desc ) grad_to_var . update ( op_grad_to_var ) # 3.d. add sum op for repetitive_outputs grad_op_descs = _addup_repetitive_outputs_ ( grad_op_descs , block . idx ) # 4) remove no grad branch as it is in _remove_no_grad_branch_ grad_op_descs = _remove_no_grad_branch_ ( grad_op_descs , no_grad_dict [ block . idx ] ) added_descs = _add_descs_to_block ( grad_op_descs , target_block ) return program_stat , checkpoints_name , vars_should_be_hold , recompute_segments