On Thu, Jun 17, 2010 at 12:22 AM, Eli Friedman <eli.friedman at gmail.com> wrote:> On Wed, Jun 16, 2010 at 11:14 PM, Pierre C <lists at peufeu.com> wrote: >>> There are essentially two ways to "solve" this issue: one is >>> type-based alias analysis, i.e. assuming "double" and "int" don't >>> alias; LLVM doesn't implement this at the moment. The other is to >>> attempt to analyze the loop and prove that %indvar.i is never >>> negative; LLVM doesn't implement anything like this at the moment >>> either. >>> >>> -Eli >> >> Actually I think it's much simpler than that... >> >> http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa >> >> it says says "Different fields of a structure do not alias." >> >> This is the case here : we have two different fields of a struct however it >> mistakenly thinks they alias. > > Consider a case like the following: > struct X { int a; int b[10]; }; > int f(struct X* a) { a->b[-1] = 1; return a->a; } > > This is technically illegal code, but various programs depend on > constructs like this working.I don't know if it's illegal, but this is how libstdc++'s string implementation finds its header data. std::string stores a pointer directly to the character data (making subscripting slightly faster), and then subtracts the size of the header when it needs to do any bookkeeping. Do you have a reference to the standard that makes it undefined?
> Do you have a reference to the standard that makes it undefined?I'm second this question. I tried to find anything banning calculating address of one field from address of another in the standard some time ago, but could not find it. On Thu, Jun 17, 2010 at 6:19 PM, Jeffrey Yasskin <jyasskin at google.com> wrote:> On Thu, Jun 17, 2010 at 12:22 AM, Eli Friedman <eli.friedman at gmail.com> wrote: >> On Wed, Jun 16, 2010 at 11:14 PM, Pierre C <lists at peufeu.com> wrote: >>>> There are essentially two ways to "solve" this issue: one is >>>> type-based alias analysis, i.e. assuming "double" and "int" don't >>>> alias; LLVM doesn't implement this at the moment. The other is to >>>> attempt to analyze the loop and prove that %indvar.i is never >>>> negative; LLVM doesn't implement anything like this at the moment >>>> either. >>>> >>>> -Eli >>> >>> Actually I think it's much simpler than that... >>> >>> http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa >>> >>> it says says "Different fields of a structure do not alias." >>> >>> This is the case here : we have two different fields of a struct however it >>> mistakenly thinks they alias. >> >> Consider a case like the following: >> struct X { int a; int b[10]; }; >> int f(struct X* a) { a->b[-1] = 1; return a->a; } >> >> This is technically illegal code, but various programs depend on >> constructs like this working. > > I don't know if it's illegal, but this is how libstdc++'s string > implementation finds its header data. std::string stores a pointer > directly to the character data (making subscripting slightly faster), > and then subtracts the size of the header when it needs to do any > bookkeeping. > > Do you have a reference to the standard that makes it undefined? > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On 06/17/2010 06:19 PM, Jeffrey Yasskin wrote:> On Thu, Jun 17, 2010 at 12:22 AM, Eli Friedman <eli.friedman at gmail.com> wrote: >> On Wed, Jun 16, 2010 at 11:14 PM, Pierre C <lists at peufeu.com> wrote: >>>> There are essentially two ways to "solve" this issue: one is >>>> type-based alias analysis, i.e. assuming "double" and "int" don't >>>> alias; LLVM doesn't implement this at the moment. The other is to >>>> attempt to analyze the loop and prove that %indvar.i is never >>>> negative; LLVM doesn't implement anything like this at the moment >>>> either. >>>> >>>> -Eli >>> >>> Actually I think it's much simpler than that... >>> >>> http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa >>> >>> it says says "Different fields of a structure do not alias." >>> >>> This is the case here : we have two different fields of a struct however it >>> mistakenly thinks they alias. >> >> Consider a case like the following: >> struct X { int a; int b[10]; }; >> int f(struct X* a) { a->b[-1] = 1; return a->a; } >> >> This is technically illegal code, but various programs depend on >> constructs like this working. > > I don't know if it's illegal, but this is how libstdc++'s string > implementation finds its header data. std::string stores a pointer > directly to the character data (making subscripting slightly faster), > and then subtracts the size of the header when it needs to do any > bookkeeping.Character types are special: they can alias everything. if this weren't the case you couldn't write malloc().> Do you have a reference to the standard that makes it undefined?Several places, but 6.3.2.3 of C99 is the most important: it lists all the legal pointer conversions. Andrew.
On Jun 17, 2010, at 1:34 PM, Eugene Toder wrote:>> Do you have a reference to the standard that makes it undefined? > > I'm second this question. I tried to find anything banning calculating > address of one field from address of another in the standard some time > ago, but could not find it.In the currect C++0x FCD, 5.7/5: "When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined." (Note in particular the last phrase, and recall that subscripting is defined in terms of pointer arithmetic.) Daveed> > On Thu, Jun 17, 2010 at 6:19 PM, Jeffrey Yasskin <jyasskin at google.com> wrote: >> On Thu, Jun 17, 2010 at 12:22 AM, Eli Friedman <eli.friedman at gmail.com> wrote: >>> On Wed, Jun 16, 2010 at 11:14 PM, Pierre C <lists at peufeu.com> wrote: >>>>> There are essentially two ways to "solve" this issue: one is >>>>> type-based alias analysis, i.e. assuming "double" and "int" don't >>>>> alias; LLVM doesn't implement this at the moment. The other is to >>>>> attempt to analyze the loop and prove that %indvar.i is never >>>>> negative; LLVM doesn't implement anything like this at the moment >>>>> either. >>>>> >>>>> -Eli >>>> >>>> Actually I think it's much simpler than that... >>>> >>>> http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa >>>> >>>> it says says "Different fields of a structure do not alias." >>>> >>>> This is the case here : we have two different fields of a struct however it >>>> mistakenly thinks they alias. >>> >>> Consider a case like the following: >>> struct X { int a; int b[10]; }; >>> int f(struct X* a) { a->b[-1] = 1; return a->a; } >>> >>> This is technically illegal code, but various programs depend on >>> constructs like this working. >> >> I don't know if it's illegal, but this is how libstdc++'s string >> implementation finds its header data. std::string stores a pointer >> directly to the character data (making subscripting slightly faster), >> and then subtracts the size of the header when it needs to do any >> bookkeeping. >> >> Do you have a reference to the standard that makes it undefined? >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Jun 17, 2010, at 10:42 AM, Andrew Haley wrote:> On 06/17/2010 06:19 PM, Jeffrey Yasskin wrote: >> On Thu, Jun 17, 2010 at 12:22 AM, Eli Friedman <eli.friedman at gmail.com> wrote: >>> On Wed, Jun 16, 2010 at 11:14 PM, Pierre C <lists at peufeu.com> wrote: >>>>> There are essentially two ways to "solve" this issue: one is >>>>> type-based alias analysis, i.e. assuming "double" and "int" don't >>>>> alias; LLVM doesn't implement this at the moment. The other is to >>>>> attempt to analyze the loop and prove that %indvar.i is never >>>>> negative; LLVM doesn't implement anything like this at the moment >>>>> either. >>>>> >>>>> -Eli >>>> >>>> Actually I think it's much simpler than that... >>>> >>>> http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa >>>> >>>> it says says "Different fields of a structure do not alias." >>>> >>>> This is the case here : we have two different fields of a struct however it >>>> mistakenly thinks they alias. >>> >>> Consider a case like the following: >>> struct X { int a; int b[10]; }; >>> int f(struct X* a) { a->b[-1] = 1; return a->a; } >>> >>> This is technically illegal code, but various programs depend on >>> constructs like this working. >> >> I don't know if it's illegal, but this is how libstdc++'s string >> implementation finds its header data. std::string stores a pointer >> directly to the character data (making subscripting slightly faster), >> and then subtracts the size of the header when it needs to do any >> bookkeeping. > > Character types are special: they can alias everything. if this weren't > the case you couldn't write malloc(). > >> Do you have a reference to the standard that makes it undefined? > > Several places, but 6.3.2.3 of C99 is the most important: it lists all > the legal pointer conversions.The better reference is 6.5.6p7-8, about pointer addition: For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. John. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100617/c9f94469/attachment.html>