Naive RC Insertion Principle

Reference Counting (RC) is a programming technique of storing the number of references to a resource, such as an object, a block of memory, disk space, and others, and releasing the resource when the number of references becomes 0. RC is used to achieve automatic resource management. RC also refers to a garbage collection algorithm that deallocates objects which are no longer referenced. Naive RC is a simplified RC.

Principle

• RC sources:

  • Heap reference (other objects or itself)

  • Stack-based reference (including registers)

  • Static variable and global variable

• RC Insertion rules (compiler and runtime):

  • If a value is assigned to a field, RC for the new object to which the field points is incremented and RC for the original object is decremented.

  • To read a local variable (including registers) on the stack, RC for the object to be read is incremented.

  • After last use, RC for the local variable is decremented.

  • If an object is returned, RC is incremented. After last use, RC for the compensated local variable is decremented.

• Example

  • Before insertion

  class A {
   static Object static_field;
   Object instance_field;
   A() {
     static_field = new Object();
   }
  }
  Object foo(){
   A a = new A();
   bar(a, new Object())
   return a.instance_field;
  }
  void bar(A a, Object o) {
   a.instance_field = o;
  }
  • After insertion

  class A {
    A() {
     local_var t = new Object(); // t is a temporary variable assigned to the static_field process.
     old = static_field;
     static_field = t;
     IncRef(t); DecRef(old); // RC is updated on the heap.
     The DecRef(t); // The function exits and RC on the stack is released.
    }
  }
  Object foo(){
    A a = new A();
    bar(a, new Object());
    locl_var t = a.instance_field;
    IncRef(t) // RC for the variable on the stack is incremented.
    The IncRef(t) // The function returns and RC for the returned value is incremented.
    The DecRef(a) // The function exits and RC on the stack is released.
    The DecRef(t) // The function exits and RC on the stack is released. 
    return t;
  }
  void bar(A a, Object o) {
    old = a.instance_field
    a.instance_field = o;
    IncRef(o); DecRef(old);
  }

• RC intrinsics:

  • Basic function Method: The basic function uses CreateIntrinsicCallMeStmt in IrMap to create the IntrinsiccallMeStmt statement and insert it to the position where RC needs increment or decrement.

    • INTRN_MCCIncRef

    • INTRN_MCCDecRef

  • Load/Write function Method: The Write function uses CreateIntrinsicCallMeStmt in IrMap to create the IntrinsiccallMeStmt statement and replace the iassign statement whose lvalue is static, global, or volatile. The Load function uses CreateIntrinsicCallAssignedMeStmt to create the IntrinsiccallMeStmt statement and replace the dassign statement whose rvalue is static, global, or volatile. The Load/Write function supports the IncRef operation.

    • INTRN_MCCLoadRef

    • INTRN_MCCLoadRefS

    • INTRN_MCCLoadRefVol

    • INTRN_MCCLoadRefSVol

    • INTRN_MCCWrite

    • INTRN_MCCWriteS

    • INTRN_MCCWriteVol

    • INTRN_MCCWriteSVol

RefVar IncRef Processing Rules:

• Assignment statement processing:

  • Process the statement based on the lvalue (variable value in the assignment statement) and rvalue (referenced value in the assignment statement) expressions.

  • First, process the rvalue. For example, select a load interface, or the rvalue (New, Call) that does not need RC increment.

    • Set Global to INTRN_MCCLoadRef.

    • Set Static to INTRN_MCCLoadRefS.

    • Set Volatile to INTRN_MCCLoadRefVol.

  • Then process the lvalue. For example, select a write interface, or save the old value or not.

    • Set Global to INTRN_MCCWriteRef.

    • Set Static to INTRN_MCCWriteRefS.

    • Set Volatile to INTRN_MCCWriteRefVol.

• Return value processing:

  • Increment RC for the return value.

• Local variable processing:

  • Decrement RC before the current function exits (normal or abnormal)

Rclowering Processing Procedure:

• Set the rclowering processing flag.

• Mark localrefvar.

• Rclowering pre-processing

  • Mark variables that need RC.

    • Mark the lvalue as DecRef, that is, variable value in the assignment statement.

      • Ref variable

  • Mark the rvalue as IncRef, that is, referenced or return value in the assignment statement.

    • Return value

    • Ref variable

    • hrow Value register

  • Clear stack variables.

• Rclowering processing

  • Process the assignment statement that contains the Ref variable.

    • DecRef original value

    • IncRef new value. For details, see RefVar IncRef processing rules.

• Rclowering post-processing

  • Perform the IncRef operation on the parameter at the function entry and mark the parameter as LocalRefVar.

  • Process the return value of the function. If the attribute is LocalRefVar, then the InRef operation is performed. If not, see RefVar IncRef processing rules.