Add support for generic arrays and applyonall/forall

[apinski-cavium]

I decided to write up something based on @albertgran 's proposal to the mailing list.

We should add generic arrays. They need to have constant size at compile time. Accessing them can only be via constant access or via a new forall statement. Generic arrays cannot be used as a return value (though this restriction can be removed in the future if wanted). They can be used as function arguments; an implementation can expand them into N elements if need to (using the same direction as the original argument).

A example of all of this together is:

struct s
{
  bit<32>[3] a;
}

void f(in s i, inout s io)
{
  forall(indx : i.a) {
    io.a[indx] = io.a[indx] + i.a[indx];
  }
}

The indx would be expanded as 0, 1, and 2. and the compiler can be bounds checking just in case io and i had different types originally etc. here indx is considered a compile time known constant.

I am not never good at writing up this formally really but I thought filing this would be useful to have others add their thoughts on how the syntax should be for forall and even the generic arrays.

[mihaibudiu]

The main question to answer is what happens when the bounds checking fails.

[apinski-cavium]

Since all sizes/indexes are known at compile time, the front-end should reject the code if there is an out of bounds. There will never be an access which is NOT known at compile time because we will reject those cases too. Now Implementing this inside p4c might be easy as you just unroll the forall loops and error out if there was out of bounds access. we can also say the max size of a generic array is implementation/target depedent and having a real low size for p4c, say max 8 or 16. that should cover most cases which Albert's o4 took care of (I think he had a 4x4 array in the end).

[vgurevich]

The proposed construct makes little sense to me. You use forall construct to iterate over an array, but the loop variable is assigned the indexes of the array elements rather than elements themselves. This is very counter-intuitive, not to mention that it is absolutely not clear what the type of that variable (indx) will be. At the very minimum it should be something like

forall(int indx: range(0, i.a.nElements()) {
        io.a[indx] = io.a[indx] + i.a[indx];
}

[vgurevich]

Here are some other thoughts on this and similar features.

1. Let us clearly separate metaprogramming features from the "real" ones.
2. It has to be really clear when the computation will occur -- at compile or at runtime. This should be achievable my making metaprogramming features syntactically distinct
3. Metaprogramming features work on the program text, so they should be allowed to appear anywhere. Here is an example: We have preprocessor #if and we have if() statements. The latter can work as the former if the condition can be evaluated at the compile time. However, in reality it is better to stick to #if, because they can be used anywhere. For example can be used to conditionally compile/remove variable definitions, extern instantiations, table definitions, parser states, etc -- and if() statements can't do it -- they can appear only in very few limited contexts.
4. If we were to build metaprogramming features into the language, I'd first make sure that they will allow us to get rid of C preprocessor -- it would make very little sense to have two frameworks
5. C preprocessor is pretty capable (see for example https://www.boost.org/doc/libs/master/libs/preprocessor/doc/AppendixA-AnIntroductiontoPreprocessorMetaprogramming.html) and there are tons of much more powerful tools. The main reason to introduce P4-specific framework is if it can be guaranteed to be natively supported by various P4 tools. As an example, CPP is not natively supported by GDB and related tools. Anyone who tried to debug a program that uses CPP macros extensively knows how painful it is. I'd like us not to make things worse than they are
6. My extensive experience helping people to debug P4 code does show that P4 code that heavily relies on any metaprogramming feature gets very difficult to both fit and debug. In fact, this is true even when we are talking about the code that extensively uses common P4 facilities, such as nested actions, parsers and controls (note that these are, indeed, metaprogramming facilities). Ultimately one has to preprocess the code, then use the compiler frontend to flatten it and only after that it is possible to do anything reasonable with it.
7. Speaking of the motivational article, please note that it is very short on the examples and that's for a reason. In fact, the only interesting example it has (Figure 2 on page 1) is not even correct, since it describes a shortcoming of TNA rather than the fundamental property of the language. Just my 2 cents.

[apinski-cavium]

P4 defines the preprocessor not having to support macro functions so unless that changes ...

Also gdb and gcc do support macros with -g3, just it bloats the debug info which is why it is not enabled by default. Generics is already a form of meta programming just a limited form.

---

From: Vladimir Gurevich @.> Sent: Tuesday, December 13, 2022 10:22 PM To: p4lang/p4-spec @.> Cc: Andrew Pinski @.>; Author @.> Subject: [EXT] Re: [p4lang/p4-spec] Add support for generic arrays and applyonall/forall (Issue #1206)

External Email

---

Here are some other thoughts on this and similar features.

1. Let us clearly separate metaprogramming features from the "real" ones.
2. It has to be really clear when the computation will occur -- at compile or at runtime. This should be achievable my making metaprogramming features syntactically distinct
3. Metaprogramming features work on the program text, so they should be allowed to appear anywhere. Here is an example: We have preprocessor #if and we have if() statements. The latter can work as the former if the condition can be evaluated at the compile time. However, in reality it is better to stick to #if, because they can be used anywhere. For example can be used to conditionally compile/remove variable definitions, extern instantiations, table definitions, parser states, etc -- and if() statements can't do it -- they can appear only in very few limited contexts.
4. If we were to build metaprogramming features into the language, I'd first make sure that they will allow us to get rid of C preprocessor -- it would make very little sense to have two frameworks
5. C preprocessor is pretty capable (see for example https://www.boost.org/doc/libs/master/libs/preprocessor/doc/AppendixA-AnIntroductiontoPreprocessorMetaprogramming.htmlhttps://urldefense.proofpoint.com/v2/url?u=https-3A__www.boost.org_doc_libs_master_libs_preprocessor_doc_AppendixA-2DAnIntroductiontoPreprocessorMetaprogramming.html&d=DwMCaQ&c=nKjWec2b6R0mOyPaz7xtfQ&r=FBRTwJHR2ue2f_Dw7bS-z_SQVqQRdREKl_Pq8gRr44E&m=bsZ2HvRATxg1EmTSX6BTXy3CM-MoNfTS_IWjefssRTHRKt4omQ7xmdiJ1jbqqrQf&s=wKskwSRxLabh0HzEnfqToAae6cVyUhMddtRtGz4BjDE&e=) and there are tons of much more powerful tools. The main reason to introduce P4-specific framework is if it can be guaranteed to be natively supported by various P4 tools. As an example, CPP is not natively supported by GDB and related tools. Anyone who tried to debug a program that uses CPP macros extensively knows how painful it is. I'd like us not to make things worse than they are
6. My extensive experience helping people to debug P4 code does show that P4 code that heavily relies on any metaprogramming feature gets very difficult to both fit and debug. In fact, this is true even when we are talking about the code that extensively uses common P4 facilities, such as nested actions, parsers and controls (note that these are, indeed, metaprogramming facilities). Ultimately one has to preprocess the code, then use the compiler frontend to flatten it and only after that it is possible to do anything reasonable with it.
7. Speaking of the motivational article, please note that it is very short on the examples and that's for a reason. In fact, the only interesting example it has (Figure 2 on page 1) is not even correct, since it describes a shortcoming of TNA rather than the fundamental property of the language. Just my 2 cents.

— Reply to this email directly, view it on GitHubhttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_p4lang_p4-2Dspec_issues_1206-23issuecomment-2D1350467630&d=DwMCaQ&c=nKjWec2b6R0mOyPaz7xtfQ&r=FBRTwJHR2ue2f_Dw7bS-z_SQVqQRdREKl_Pq8gRr44E&m=bsZ2HvRATxg1EmTSX6BTXy3CM-MoNfTS_IWjefssRTHRKt4omQ7xmdiJ1jbqqrQf&s=miQZKEVBuPLQdv9TSGEtCU-mQ3C51utjMlxeksJQq3Y&e=, or unsubscribehttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_notifications_unsubscribe-2Dauth_ABQKWU6DMDF2H46KPFPTMP3WNFRS7ANCNFSM6AAAAAAS54C25A&d=DwMCaQ&c=nKjWec2b6R0mOyPaz7xtfQ&r=FBRTwJHR2ue2f_Dw7bS-z_SQVqQRdREKl_Pq8gRr44E&m=bsZ2HvRATxg1EmTSX6BTXy3CM-MoNfTS_IWjefssRTHRKt4omQ7xmdiJ1jbqqrQf&s=EkyCG6eQJHeoKsCaaxzcHKuP3E2LVmqW2MNJfDXKlEU&e=. You are receiving this because you authored the thread.Message ID: @.***>

[vgurevich]

@apinski-cavium -- you are correct.

1. P4 spec requires only restricted preprocessor semantics. Having said that, I believe that the current practice is to simply use the CPP. Nobody checks if the program uses any extended CPP facilities that are present there, but not defined by P4 spec. Also, in practice tons of people do rely on that functionality today. yes, we can take it away, but that will only mean that they will have to run CPP manually before feeding the compiler with the already preprocessed code.
2. You are also correct, that latest versions of the tool provide CPP support. I would encourage you to check how many years passed between CPP introduction and those facilities appearing in GCC/GDB. That will provide a useful perspective in addition to your own comment about the "debug info bloat"
3. Yes, generics are a form of meta programming.

I do want to point out that P4 differs in one important aspect from other programming languages. With most other languages, once the program is written the user of that program can be totally oblivious to its source code. You can restructure the program, rename identifiers, replace libraries, etc -- it would not matter to the end user (esp. if the libraries are statically linked or distributed along the program). Not so in P4: almost any change in the source code propagates to the control plane and is very visible. In addition to that, the amount of low-level optimization (that requires full visibility into the actual source), currently required to fit any non-trivial P4 program on any high-speed target target is way outside of what is considered "normal" in most other programming languages. While we easily operate with C programs with call stack 20 or 80 levels deep (and rarely think of it), try to mentally create a dependency graph of a P4 program that uses 5-6 levels of controls plus CPP. That's what people deal with every day today.

[apinski-cavium]

The reason why I pointed out not requiring function like macros is that my front-end does not relay on the system preprocessor to do the preprocessing instead has its own integrated preprocessor and it does NOT currently supports function-like macros due to the complexities involved due to token forming; plus I suspect the use of the C preprocessor does not always do the right thing when it comes to tokens differences between C and P4; especially when it comes to token pasting.

[mihaibudiu]

The main question is about the scope of for loops. If you just want to iterate over arrays this proposal is sufficient. But if you want to be able to generate one parser state for each element in an array - that's different. That's real metaprogramming. We have debated in the past the use of a metaprogramming loop: https://github.com/p4lang/p4-spec/issues/907

[jnfoster]

In the interest of tidying up the set of active issues on the P4 specification repository, I'm marking this as "stalled" and closing it. Of course, we can always re-open it in the future if there is interest in resurrecting it.

[ChrisDodd]

We've added looping constructs (in particular for (T elem in vec)... loops), so perhaps it makes sense to to revisit this.

Issues I see with this

1. Interactions with existing header stacks -- could treat header stacks as a special case of arrays, when the array element type is a header or header_union. Additional functionality of header stacks (next/last/push/pop) would only be available in that case,
2. Effect of out-of-range accesses. Undefined behavior?
3. Should we allow C-style declarators rather than requiring the current java style
4. Call out non-constant indexes as being architecture specific, possibly varying between different parts of an architecture (parser vs control -- this is likely the case for header stacks currently in reality)