[M3devel] gcc 4.5.0?

[Jay K]

Thanks for the reference!
 
search for "Good Ideas, Through the Looking Glass"
finds it right away: "http://www.cs.inf.ethz.ch/~wirth/Articles/GoodIdeas_origFig.pdf"
(I don't need to provide the link really.)
 
 - Jay

----------------------------------------
> To: jay.krell at cornell.edu
> Date: Thu, 20 May 2010 22:37:56 -0700
> From: mika at async.async.caltech.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] gcc 4.5.0?
>
>
> As I recall it the "Dragon Book" has a whole section on this topic of
> nested functions in Pascal. Including Dijkstra's "display". I'm not
> an expert, just remember reading it. Wirth also talks about it in his
> "Good Ideas, Through the Looking Glass" (where he says the display
> might be a pessimization).
>
> Mika
>
> Jay K writes:
>>
>>Maybe we can/should transform into one of the forms I show and dispense wit=
>>h any gcc support?
>>At the cost of losing some "easy" optimization..of nested functions?
>> "easy" as in=2C occurs even without -O2=2C but might occur with -O2?
>>=20
>>=20
>>I know what you mean -- NT386 passes the static link in ecx.
>>This is "ok" because in C++ the "this" pointer is passed in ecx.
>>=20
>>=20
>>Passing it as "just" another parameter might be less efficient=2C but ok?
>> And really=2C it'd only be less efficient on one architecture -- 32bit x8=
>>6.
>> And maybe not all x86s -- depending on if some ABIs have a register based=
>> calling convention.
>>=20
>>=20
>>We don't need any actual ABI-compatibility with anything here=2C do we?
>>=20
>>=20
>> - Jay
>>
>>
>>----------------------------------------
>>> From: hosking at cs.purdue.edu
>>> Date: Thu=2C 20 May 2010 22:22:46 -0400
>>> To: jay.krell at cornell.edu
>>> CC: m3devel at elegosoft.com
>>> Subject: Re: [M3devel] gcc 4.5.0?
>>>
>>> That is the standard formulation=2C but different architectures have diff=
>>erent optimised forms (passing static link in a register=2C etc.). In any c=
>>ase=2C gcc has its own weird way of doing things=2C which we mostly use=2C =
>>but from which we need a little extra support (hence the small amount of sp=
>>ecial tailoring).
>>>
>>> On 20 May 2010=2C at 21:43=2C Jay K wrote:
>>>
>>>>
>>>> Wierd. To me the model to follow is almost obvious. It should be obvious=
>> to everyone and implemented the way I have in mind. :)
>>>>
>>>>
>>>> The static link is an extra parameter.
>>>> And=2C as such=2C also an extra local variable.
>>>> You only need one.
>>>> Each nesting level would follow another chain.
>>>> Or you can pass each nesting level as an extra parameter.
>>>> Or you can optimize and pass locals/parameters separately.
>>>> But there is an obvious straightforward non-optimized form. ?
>>>>
>>>>
>>>> Here=2C I worked it through:
>>>>
>>>>
>>>>
>>>> Why doesn't it just look something like this:
>>>>
>>>>
>>>> nested:
>>>>
>>>> void F1(int a=2C int b)
>>>> {
>>>> int c =3D a + b=3B
>>>>
>>>> int f2()
>>>> {
>>>> int d =3D a + b=3B
>>>>
>>>> int f3()
>>>> {
>>>> return d + a + c=3B
>>>> }
>>>>
>>>> return a + c + f3()=3B
>>>> }
>>>>
>>>> return f2()=3B
>>>> }
>>>>
>>>> not nested:
>>>>
>>>>
>>>> typedef struct {
>>>> /* locals */
>>>> int d=3B
>>>> void* x86_frame_pointer=3B
>>>> void* x86_return_address=3B
>>>> /* parameters */
>>>> f1_frame_t* f1=3B
>>>> } f2_frame_t=3B
>>>>
>>>>
>>>> typedef struct {
>>>> /* locals */
>>>> int c=3B
>>>> void* x86_frame_pointer=3B
>>>> void* x86_return_address=3B
>>>> /* parameters */
>>>> int a=3B
>>>> int b=3B
>>>> } f1_frame_t=3B
>>>>
>>>>
>>>> int f3(f2_frame_t* f2)
>>>> {
>>>> return f2->d + f2->f1->a + f2->f1->c=3B
>>>> }
>>>>
>>>>
>>>> int f2(f1_frame_t* f1)
>>>> {
>>>> int d =3D f1->a + f1->b=3B
>>>> return f1->a + f1->c + f3((f2_frame_t*)&d)=3B
>>>> }
>>>>
>>>>
>>>> int F1(int a=2C int b)
>>>> {
>>>> int c =3D a + b=3B
>>>> return f2((f1_frame_t*)&c)=3B
>>>> }
>>>>
>>>>
>>>> or=2C alernatively=2C almost the same=2C pass each chain as another para=
>>meter:
>>>>
>>>>
>>>> typedef struct {
>>>> /* locals */
>>>> int d=3B
>>>> void* x86_frame_pointer=3B
>>>> void* x86_return_address=3B
>>>> /* parameters */
>>>> } f2_frame_t=3B
>>>>
>>>>
>>>> typedef struct {
>>>> /* locals */
>>>> int c=3B
>>>> void* x86_frame_pointer=3B
>>>> void* x86_return_address=3B
>>>> /* parameters */
>>>> int a=3B
>>>> int b=3B
>>>> } f1_frame_t=3B
>>>>
>>>>
>>>> int f3(f2_frame_t* f2=2C f1_frame_t* f1)
>>>> {
>>>> return f2->d + f1->a + f1->c=3B
>>>> }
>>>>
>>>>
>>>>
>>>> int f2(f1_frame_t* f1)
>>>> {
>>>> int d =3D f1->a + f1->b=3B
>>>> return f1->a + f1->c + f3((f2_frame_t*)&d=2C f1)=3B
>>>> }
>>>>
>>>>
>>>> int F1(int a=2C int b)
>>>> {
>>>> int c =3D a + b=3B
>>>> return f2((f1_frame_t*)&c)=3B
>>>> }
>>>>
>>>>
>>>> This should be easily adapted to any function call convention/sequence.
>>>> e.g. even if parameters are passed in registers.
>>>>
>>>>
>>>> And for that matter=2C why don't we just transform it to be like this?
>>>> With the goal of reducing/eliminating gcc patches?
>>>>
>>>>
>>>> Am I missing something?
>>>>
>>>>
>>>> This form doesn't work?
>>>>
>>>>
>>>> Isn't reasonably simple?
>>>>
>>>>
>>>> Granted it might not be optimal. But it depends.
>>>> You know=2C you can copy in the local/parameter values=2C but then you h=
>>ave
>>>> to copy them out too. You can do analysis to show they aren't changed=2C
>>>> in which case no need to copy them out.
>>>> Similarly you can pass the parameters as separate parameters=2C by addre=
>>ss
>>>> if they are ever changed.
>>>>
>>>>
>>>> A portable transform couldn't depend on adjacency of locals and paramete=
>>rs.
>>>> It would have to either copy the parameters into the frame_t=2C or their=
>> addresses.
>>>>
>>>>
>>>> A portable form couldn't get the frame by taking the address of a "indiv=
>>idual" local.
>>>>
>>>>
>>>> Here is portable form:
>>>>
>>>>
>>>> typedef struct {
>>>> int d=3B
>>>> f1_frame_t* f1=3B
>>>> } f2_frame_t=3B
>>>>
>>>> typedef struct {
>>>> int a=3B
>>>> int b=3B
>>>> int c=3B
>>>> } f1_frame_t=3B
>>>>
>>>>
>>>> int f3(f2_frame_t* f2)
>>>> {
>>>> return f2->d + f2->f1->a + f2->f1->c=3B
>>>> }
>>>>
>>>> int f2(f1_frame_t* f1)
>>>> {
>>>> f2_frame_t f=3B
>>>> f.f1 =3D f1=3B
>>>> f.d =3D f1->a + f1->b=3B
>>>> return f1->a + f1->c + f3(&f)=3B
>>>> }
>>>>
>>>>
>>>> int F1(int a=2C int b)
>>>> {
>>>> f1_frame_t f=3B
>>>> f.a =3D a=3B
>>>> f.b =3D b=3B
>>>> f.c =3D a + b=3B
>>>> return f2(&f)=3B
>>>> }
>>>>
>>>>
>>>> or:
>>>>
>>>>
>>>> typedef struct {
>>>> int d=3B
>>>> } f2_frame_t=3B
>>>>
>>>>
>>>> typedef struct {
>>>> int a=3B
>>>> int b=3B
>>>> int c=3B
>>>> } f1_frame_t=3B
>>>>
>>>>
>>>> int f3(f2_frame_t* f2=2C f1_frame_t* f1)
>>>> {
>>>> return f2->d + f1->a + f1->c=3B
>>>> }
>>>>
>>>>
>>>> int f2(f1_frame_t* f1)
>>>> {
>>>> f2_frame_t f=3B
>>>> f.d =3D f1->a + f1->b=3B
>>>> return f1->a + f1->c + f3(&f=2C f1)=3B
>>>> }
>>>>
>>>>
>>>> int F1(int a=2C int b)
>>>> {
>>>> f1_frame_t f=3B
>>>> f.a =3D a=3B
>>>> f.b =3D b=3B
>>>> f.c =3D a + b=3B
>>>> return f2(&f)=3B
>>>> }
>>>>
>>>>
>>>>
>>>>
>>>> - Jay
>>>>
>>>>
>>>>
>>>> ----------------------------------------
>>>>> Date: Thu=2C 20 May 2010 12:12:00 -0500
>>>>> From: rodney_bates at lcwb.coop
>>>>> To: m3devel at elegosoft.com
>>>>> Subject: Re: [M3devel] gcc 4.5.0?
>>>>>
>>>>> gcc even extends C with nested functions=2C and the support is there fo=
>>r that. We use it too.
>>>>>
>>>>> Beware: The runtime model is=2C IMO=2C bizarre. Definitely counterintui=
>>tive and unlike anything
>>>>> you will ever see elsewhere. There are two static links. One is used fo=
>>r the first step
>>>>> in following a static chain and points to the expected place in the tar=
>>get frame. The other
>>>>> is used of subsequent steps in chain-following=2C and points to somewhe=
>>re inside the target
>>>>> frame that is dependent on the target procedure. It's the beginning of =
>>a subrecord where
>>>>> all the nonlocally-referenced variables are collected. The second stati=
>>c link is also
>>>>> located in there. All the nonlocally-referenced variables and parameter=
>>s are duplicated
>>>>> in there too.
>>>>>
>>>>> I'm not sure I remembered these details exactly right. Maybe both links=
>> point to the
>>>>> subrecord=2C but one is located at a traditional procedure-independent=
>>=2C fixed location
>>>>> in the frame=2C while the second is located in the subrecord. Also=2C s=
>>ometimes the first
>>>>> static link value is kept in a register and never stored.
>>>>>
>>>>> What this all apparently accomplishes is simplifying an "insanely compl=
>>icated" _compile-time_
>>>>> scheme that=2C I believe came from interaction between nested procedure=
>>s and inlining them.
>>>>>
>>>>> But it's at the cost of what I would call an insanely complicated _runt=
>>ime_ scheme.
>>>>>
>>>>> It undermined m3gdb's handling of static links=2C and I don't think it'=
>>s possible to fix
>>>>> with the current design of emitting debug info very early. The location=
>>s and target
>>>>> offsets of these things aren't know until later=2C and m3gdb really nee=
>>ds to know them.
>>>>>
>>>>>
>>>>> Jay K wrote:
>>>>>> What I meant regarding "static chain" was more like "does gcc already =
>>have support that we can use".
>>>>>> Don't any of the other languages need it already?
>>>>>> Ada? Pascal? Maybe the nested C function support?
>>>>>>
>>>>>> - Jay
>>>>>>
>>> =