restrict 한정자(qualifier) in C

Programming/C language

restrict 한정자(qualifier) in C

choimosi 2010. 9. 7. 00:47

Type Qualifiers
C언어에서 C89 표준에서는 한정자가 contst, volatile 이 두가지가 있었다. C99에서는 세 번째 타임으로 restrict가 추가 되었다.
이 한정자들은 lvalue를 통해 객체를 접근할 때 컴파일러가 전제 조건을 결정한다.

Const 예약어는 문법은 C++에도 이미 적용되어 있다. 이 개념은 다른 언어에도 나타나있다. volatile과 restrict는
C언어에서 발견되었다. 그리고 이 둘 다 const 와 같은 문장 구성법을 같는다.

한정자의 형(type)은 최적화를 통해 더 많은 제어적 요소를 제공하기 위해 소개 되었다. 몇몇 중요 최적화 기술들은 cacheing을 토대로 한다.
특정 상황에서 컴파일러는 그 지역으로 부터 가장 마지막에 엑세스된 값을 기억하고 그 지역에서 다음에 사용될 값을 보존한다.
(memory, cache, hardware register). 만약 메모리가 machine register라면, 코드는 외부메모리에 접근하는 것보다 레지스터를 이용하면
더 작고 더 빨라 질 수 잇다.

한정자의 형은 엑세스와 캐싱하는데 이용되고 다음과 같은 제반 사항을 가지고 있다.

const

lvalue에 쓸수 없다. 이 한정자가 없으면 사용할 수 있다.

volatile

이 lvalue 값은 캐슁 되지 않는다. 기호로 의미 있는 특정 작업이 무조겅 형성 되어 있어야 한다.(캐쉬에 적재하지 않는 다는 것은
아마도 그 위치에 다음 전달될 값이 무엇인지 보장되지 않는 다는 것을 말한다.) 이 한정자가 없으면, 지시된 장소의 컨텐츠 들이
적중 가능성이 큰 앨리어싱을 제외 하고는 값이 변화되지 않게 된다.
volatile을 통해 포트 값을 읽으면 메모리에 있는 대상체에 직접적인 접근이 이루어지고 그 때마다 변화하는 새로운 값을
읽어와 계산에 사용 된다.

restrict

restrict-qualified pointer를 통해 참조된 객체는 그 포인터에 특수한 조직을 가진다. 객체에 모든 참조들은 반드시 직간접적으로 이
포인터의 값을 사용 해야 한다. 이 한정자가 없으면, 다른 포인터들은 이 객체에 앨리어스 할 수 있다. 제한 한정자 포인터를 가리키는 객체의 값을
캐슁하는 것은 그 포인터가 선언된 블럭을 시작할 때 안전하다. 왜냐하면 앞서 존재한 앨리어스 되지 않은 것들이 저 객채를 참조했을 것이기 때문이다.
캐쉬된 값은 블락의 끝(즉 앞서 존재한 앨리어스들이 유효하게 되는 곳)에서 복귀되어야 한다. 새로운 앨리어스들은 아마 블럭내에서 형성되지만,
이 것들은 한정용법의 restrict의 값에 의존해야만 한다. 그렇게 해야 그 캐쉬 값에서 확인 되거나 적용되어질 수 있다. 파일의 영역에서 본 restrict
한정자는 그 블럭의 파일에서 각 함수의 몸체이다.

The restrict Qualifier and Aliasing

restrict 한정자는 잠정적으로 에일리어징에 의한 최적화를 금지시킬 수 있는 것을 뜻 한다. 특히 컴파일러가 다른 객체로 참조되어 사용 되는 두 가지 다른 포인터들을 결정할 수 없을때, 그 때 이 값들을 load나 store로 재주문하거나, 메모리보다 레지스터에 있는 객채의 값을 유지하는 것은 최적화를
적용할 수가 없다.

The restrict qualifier was designed to express and extend two types of aliasing information already specified in the language.

First, if a single pointer is directly assigned the return value from an invocation of malloc, then that pointer is the sole initial means of access to the allocated object (that is, another pointer can gain access to that object only by being assigned a value that is based on the value of the first pointer). Declaring the pointer to be restrict-qualified expresses this information to the compiler. Furthermore, the qualifier can be used to extend a compiler’s special treatment of such a pointer to more general situations. For example, an invocation of malloc might be hidden from the compiler in another function, or a single invocation of malloc might be used to allocate several objects, each referenced through its own pointer.
Second, the library specifies two versions of an object copying function, because on many systems a faster copy is possible if it is known that the source and target arrays do not overlap. The restrict qualifier can be used to express the restriction on overlap in a new prototype that is compatible with the original version:
```
  void *memcpy(void * restrict s1, const void * restrict s2, size_t n);
  void *memmove(void * s1, const void * s2, size_t n);
```
With the restriction visible to the compiler, a straightforward implementation of memcpy in C now gives a level of performance that previously required assembly language or other non-standard means. Thus the restrict qualifier provides a standard means with which to make, in the definition of any function, an aliasing assertion of a type that could previously be made only for library functions.

Some Typical Uses of the `restrict` Qualifier

The complexity of the specification of the restrict qualifier reflects the fact that C has a rich set of types and a dynamic notion of the type of an object. For example, an object does not have a fixed type, but acquires a type when referenced. Similarly, in some of the library functions, the extent of an array object referenced through a pointer parameter is dynamically determined, either by another parameter or by the contents of the array. The full specification is necessary to determine the precise meaning of a qualifier in any context, and so must be understood by the compiler. Fortunately, C programmers only need to understand a few simple patterns of usage explained in the following examples.

A compiler can assume that a file-scope restrict-qualified pointer is the sole initial means of access to an object, much as if it were the declared name of an array. This is useful for a dynamically allocated array whose size is not known until run time. Note in the following example how a single block of storage is effectively subdivided into two disjoint objects.
```
  float * restrict a1, * restrict a2;
  void init(int n)
  {
    float * t = malloc(2 * n * sizeof(float));
    a1 = t; // a1 refers to 1st half
    a2 = t + n; // a2 refers to 2nd half
  } // 이 코드 우분투에서 선언이 안된다 -_-;
```

A compiler can assume that a restrict-qualified pointer that is a function parameter is, at the beginning of each execution of the function, the sole means of access to an object. Note that this assumption expires with the end of each execution. In the following example, parameters a1 and a2 can be assumed to refer to disjoint array objects because both are restrict-qualified. This implies that each iteration of the loop is independent of the others, and so the loop can be aggressively optimized.
```
  void f1(int n, float * restrict a1, const float * restrict a2)
  {
    int i;
    for ( i = 0; i < n; i++ )
    a1[i] += a2[i];
  }
```
A compiler can assume that a restrict-qualified pointer declared with block scope is, during each execution of the block, the sole initial means of access to an object. An invocation of the macro shown in the following example is equivalent to an inline version of a call to the function f1 above.
```
  # define f2(N,A1,A2) \
  { int n = (N); \
   float * restrict a1 = (A1); \
   float * restrict a2 = (A2); \
   int i; \
   for ( i = 0; i < n; i++ ) \
    a1[i] += a2[i]; \
  }
```
The restrict qualifier can be used in the declaration of a structure member. A compiler can assume, when an identifier is declared that provides a means of access to an object of that structure type, that the member provides the sole initial means of access to an object of the type specified in the member declaration. The duration of the assumption depends on the scope of the identifier, not on the scope of the declaration of the structure. Thus a compiler can assume that s1.a1 and s1.a2 below are used to refer to disjoint objects for the duration of the whole program, but that s2.a1 and s2.a2 are used to refer to disjoint objects only for the duration of each invocation of the f3 function.
```
  struct t {
    int n;
    float * restrict a1, * restrict a2;
  };
  
  struct t s1;
  
  void f3(struct t s2) { /* ... */ }
```

Unions and Typedefs

The meaning of the restrict qualifier for a union member or in a type definition is analogous. Just as an object with a declared name can be aliased by an unqualified pointer, so can the object associated with a restrict-qualified pointer.

This allows the restrict qualifier to be introduced more easily into existing programs, and also allows restrict to be used in new programs that call functions from libraries that do not use the qualifier. In particular, a restrict-qualified pointer can be the actual argument for a function parameter that is unqualified. On the other hand, it is easier for a translator to find opportunities for optimization if as many as possible of the pointers in a program are restrict-qualified.

용어: cacheing - 요리사가 요리를 하기 전에 냉장고에서 미리 요리 재료를 꺼내서 도마위에 올려두는 것과 같은것.
aliase - In computing, aliasing describes a situation in which a data location in memory can be accessed through different symbolic names in the program. Thus, modifying the data through one name implicitly modifies the values associated to all aliased names, which may not be expected by the programmer. As a result, aliasing makes it particularly difficult to understand, analyze and optimize programs. Aliasing analyses intend to make and compute useful information for understanding aliasing in programs.
C 언어에서 에일리어징(aliasing)이란 메모리에 존재하는 하나의 대상체(object)에 접근할 수 있는 경로가 다양함을 의미한다. 이는 보통 공용체와 포인터를 통해 일어난다. 예를 들어 다음과 같은 프로그램에서는 대상체에 접근할 수 있는 2가지 방법(object를 통한 방법, 이를 가리키는 포인터 pi를 통한 방법)이 존재한다.

[출처] C 언어도 진화한다「C99」|작성자 맥스

출처: 위키피디아, http://snowall.tistory.com/1647, http://developers.sun.com/solaris/articles/cc_restrict.html
http://blog.naver.com/xtreme21?Redirect=Log&logNo=5972397