C++ aliasing, restrict (was: Re: C as a Subset of C++ (or C++ as
a superset of C))
On 2012-08-29 21:33, Bo Persson wrote:
David Brown wrote 2012-08-29 09:51:
But it will be a long time before compiler technology can figure out all
cases of "restrict" by itself - that requires insight between different
compile units, and hefty analysis on the way the functions are used.
The argument from the C++ camp, for not implementing it, is that it is a
lot less useful in C++. Most functions don't take pointers to basic
types as parameters, because C++ is largely class based.
Type based alias analysis will show that function parameters cannot
alias, because they are of different class types. Adding restrict will
not help.
If you have
void f(std::vector<int>& v1, std::vector<int>& v2)
{
// Here v1[1] can never, ever alias v2[2]
// because vectors don't work that way, and the compiler can tell
}
on the other hand, with C style code
void f(int* v1, int* v2)
{
// Here any v1[i] might alias any v2[j]
// because the function just COULD have been called
// with f(p, p + 7)
}
Of course, you are dead wrong. The two vectors can potentially alias
(the compiler will have a really hard time proving otherwise, it would
have to be able to track the underlying storage over the entire
lifetime; neither Visual C++ nor GCC get it right, even in trivial cases).
Let's see:
#include <vector>
void test1(std::vector<int>& v1, std::vector<int>& v2) {
v1[7] += 7;
v2[3] = 10;
v1[7] += 42;
}
void test2(int* v1, int* v2) {
v1[7] += 7;
v2[3] = 10;
v1[7] += 42;
}
void test3(int* __restrict v1, int* __restrict v2) {
v1[7] += 7;
v2[3] = 10;
v1[7] += 42;
}
The conclusion from the disassembly below: GCC and Visual C++ think that:
- test1(): the vectors can alias
- test2(): the pointers can alias
- test3(): the pointers can't alias
---- Visual C++ 2012 --------------------------------------------------
?test1@@YAXAAV?$vector@HV?$allocator@H@std@@@std@@0@Z (void __cdecl
test1(class std::vector<int,class std::allocator<int> > &,class
std::vector<int,class std::allocator<int> > &)):
00000000: 8B 4C 24 04 mov ecx,dword ptr [esp+4]
00000004: 8B 01 mov eax,dword ptr [ecx]
00000006: 83 40 1C 07 add dword ptr [eax+1Ch],7
0000000A: 8B 44 24 08 mov eax,dword ptr [esp+8]
0000000E: 8B 00 mov eax,dword ptr [eax]
00000010: C7 40 0C 0A 00 00 mov dword ptr [eax+0Ch],0Ah
00
00000017: 8B 01 mov eax,dword ptr [ecx]
00000019: 83 40 1C 2A add dword ptr [eax+1Ch],2Ah
0000001D: C3 ret
?test2@@YAXPAH0@Z (void __cdecl test2(int *,int *)):
00000000: 8B 4C 24 04 mov ecx,dword ptr [esp+4]
00000004: 8B 44 24 08 mov eax,dword ptr [esp+8]
00000008: 83 41 1C 07 add dword ptr [ecx+1Ch],7
0000000C: C7 40 0C 0A 00 00 mov dword ptr [eax+0Ch],0Ah
00
00000013: 83 41 1C 2A add dword ptr [ecx+1Ch],2Ah
00000017: C3 ret
?test3@@YAXPIAH0@Z (void __cdecl test3(int * __restrict,int * __restrict)):
00000000: 8B 4C 24 04 mov ecx,dword ptr [esp+4]
00000004: 8B 44 24 08 mov eax,dword ptr [esp+8]
00000008: 83 41 1C 31 add dword ptr [ecx+1Ch],31h
0000000C: C7 40 0C 0A 00 00 mov dword ptr [eax+0Ch],0Ah
00
00000013: C3 ret
---- GCC 4.7 -----------------------------------------------------
00000160 <test1(std::vector<int, std::allocator<int> >&,
std::vector<int, std::allocator<int> >&)>:
160: 8b 44 24 04 mov eax,DWORD PTR [esp+0x4]
164: 8b 54 24 08 mov edx,DWORD PTR [esp+0x8]
168: 8b 00 mov eax,DWORD PTR [eax]
16a: 8b 12 mov edx,DWORD PTR [edx]
16c: 83 40 1c 07 add DWORD PTR [eax+0x1c],0x7
170: c7 42 0c 0a 00 00 00 mov DWORD PTR [edx+0xc],0xa
177: 83 40 1c 2a add DWORD PTR [eax+0x1c],0x2a
17b: c3 ret
00000180 <test2(int*, int*)>:
180: 8b 44 24 04 mov eax,DWORD PTR [esp+0x4]
184: 8b 54 24 08 mov edx,DWORD PTR [esp+0x8]
188: 83 40 1c 07 add DWORD PTR [eax+0x1c],0x7
18c: c7 42 0c 0a 00 00 00 mov DWORD PTR [edx+0xc],0xa
193: 83 40 1c 2a add DWORD PTR [eax+0x1c],0x2a
197: c3 ret
000001a0 <test3(int*, int*)>:
1a0: 8b 44 24 04 mov eax,DWORD PTR [esp+0x4]
1a4: 8b 54 24 08 mov edx,DWORD PTR [esp+0x8]
1a8: c7 42 0c 0a 00 00 00 mov DWORD PTR [edx+0xc],0xa
1af: 8b 50 1c mov edx,DWORD PTR [eax+0x1c]
1b2: 83 c2 31 add edx,0x31
1b5: 89 50 1c mov DWORD PTR [eax+0x1c],edx
1b8: c3 ret
---- End GCC 4.7 -----------------------------------------------
For some more fun:
int test4() {
int* v1 = (int*) malloc(10*sizeof(int));
int* v2 = (int*) malloc(10*sizeof(int));
v1[1] += 0x77;
v2[2] += 0x42;
v1[1] -= 0x77;
return v1[1];
}
int test5() {
std::vector<int> v1(10);
std::vector<int> v2(10);
v1[1] += 0x77;
v2[2] += 0x42;
v1[1] -= 0x77;
return v1[1];
}
template<class T> class simple_vector {
public:
simple_vector(size_t size) : elems((int*)malloc(size*sizeof(T))),
size(size), capacity(size) {}
~simple_vector() { free(elems); }
T& operator[](size_t idx) { return elems[idx]; }
private:
T* elems; size_t size; size_t capacity;
};
int test6() {
simple_vector<int> v1(10);
simple_vector<int> v2(10);
v1[1] += 0x77;
v2[2] += 0x42;
v1[1] -= 0x77;
return v1[1];
}
For test4(), both Visual C++ and GCC can figure out that there is no
aliasing. For test5() both can't. For test6(), Visual C++ thinks there
can be aliasing, GCC gets it right. (Disassembly not posted, it's way
too big.)