Implemented DeclarationCopyPropagation pass #3082

AleksaSyrmia · 2022-02-11T01:07:36Z

Implemented DeclarationCopyPropagation pass as a fix for case 2 of issue #2844.
It propagates variables declared with a constant in the locals part of controls.

The goal is to propagate variables that are declared with a constant value so that they can be used
in places where compile time values are necessary. It also optimizes the code by making the variables
unneeded if they are completely propagated.

For example:
before propagation

control C1(inout bit<16> x) {
     bit<32> counter_size = 1024;
     counter(counter_size, CounterType.packets) stats;
}

after propagation:

control C1(inout bit<16> x) {
     bit<32> counter_size = 1024;
     counter(1024, CounterType.packets) stats;
}

Before propagation this example wouldn't work because counter_size cannot evaluate to a compile time constant.
After propagation the value of counter_size will be placed directly where it is needed, and it will compile without an error.

It works only in control locals because the declared values cannot be changed until the apply block,
and minimal copy propagation that is needed to fix the issue is done, so we are sure that it doesn't make things
worse and more complicated.
Also, because of the same reason it is currently disabled in actions and tables.

The pass is called two times in the frontend, first before the first TypeInference, with checkOnly flag set to true.
When this flag is true the pass checks declarations for used variables and if they have an initializer, sets them as compile time constant, even if they aren't. No propagation is done during this run. It is implemented like this to postpone the first compile time check, and wait for TypeInference to insert casts and convert structures from ListExpression to StructExpression, to make it possible to properly find values of struct members.

Second call of the pass is in the form of PassRepeated, in combination with ConstantFolding. In this case checkOnly flag is set to false, and propagation is done until convergence.

Edit:
There was a problem with infinite iterations of PassRepeated with ConstantFolding when there is a Declaration_Constant with a cast. Because the cast is detected, the initializer is cloned, and in every iteration has a different pointer, which resulted in an infinite loop. The initializers are still exactly the same, but with different pointers, so changing the check from shallow to deep equivalence fixed the issue.

mihaibudiu · 2022-02-11T21:45:34Z

frontends/p4/decl_copyprop.cpp

+/// It checks both cases because it needs to retain the casts.
+/// @return true if a constant is found.
+bool DoDeclarationCopyPropagation::checkConst(const IR::Expression* expr) {
+ if (expr->is<IR::Constant>()) {


This will only discover integer constants, but there are many other types of constants.

The typechecker has a very compreshensive constant detection algorithm.

Yes, sorry. I have now added support for other types of constants.

mihaibudiu · 2022-02-11T21:54:59Z

frontends/p4/decl_copyprop.h

+ bool working = false;
+
+ /// If set to true limits the pass to only check if the used
+ /// variables are initialized. It assumes that all of them are


I don't understand the comment. Please clarify.
Variables can be initialized also from expressions depending on parameters and by calling functions.

When checkOnly is true the pass checks if used variables have declarations, and if they have an initializer sets them as compile time constant, even if they aren't. This is done to postpone compile time constant check and wait for TypeInference to insert casts and convert structures from ListExpression to StructExpression. When this flag is true no propagation is done.
Propagating variables initialized by calling functions is currently disabled because I think that it is too early in the frontend to find the return values and propagate them without complicating things further.

mihaibudiu · 2022-02-11T21:58:06Z

frontends/p4/frontend.cpp

@@ -172,11 173,17 @@ const IR::P4Program *FrontEnd::run(const CompilerOptions &options, const IR::P4P
 new ResolveReferences(&refMap), // check shadowing
 new Deprecated(&refMap),
 new CheckNamedArgs(),
+ new DeclarationCopyPropagation(&refMap, &typeMap, true),


This makes me think that we have to separate the typeMap into two pieces - one for constants and one for types.
The one for types can just subclass the one for constants. Also, you are not passing information through the typeMap between passes, so it probably can be allocated locally in the DeclarationCopyPropagation and not passed as an argument.

Yes, I think that separating the maps will be useful too, but it is not crucial for my solution.
TypeMap is needed to postpone the compile time constant check in TypeInference, by adding declarations with initializers in the constants set. After that all variables that are initialized with constants will be propagated, and TypeInference will do it's work, so passing the information further is not needed.

Indeed, it is not, but since you are the first user of the reduced functionality it is a logical place to do it here.
It won't be too much work: just create a class that contains the constants HashMap and the APIs to insert and lookup. Then make typeMap inherit from that class.

Can you please explain it a bit further?
I can create a class that contains the constants and will be the parent of the TypeMap class, but I would still need to use the typeMap in DeclarationCopyPropagation so that TypeInference could see them.

Are you assuming that the TypeInference pass from line 180 will reuse that information?
My guess is that it won't - it will recompute it from scratch using its own rules.
If you have propagated the constants it should not need the information anyway.

The information will be used in that TypeInference when checking if variables are compile time constant. This is needed only here because the DeclarationCopyPropagation on line 176 won't propagate any constants. The propagation is done in the PassRepeated DeclarationCopyPropagation, after the first TypeInference has passed.

I see. That could be a problem is additional passes are inserted in between that information could be lost.
I wonder whether a separate data structure should be used for that purpose (but that's not easy).
A second problem is that any changes in the IR between these two passes may invalidate this information: if a child of any of the nodes you analyze will change, the nodes will be replaced by clones, so they won't be found in the TypeMap.
Ideally you should propagate the constants right away, immediately after you detect them. But I assume you need type information. Can't you put the analysis and propagation next to each other?

I intended that the passes in between, including DeclarationCopyPropagation, would be viewed as a group and not changed, but you are right, additional passes could be inserted.
Yes, first it was the plan to do everything right away, but I needed TypeInference to check types and do other work, and only then propagate. The problem was with compile time constant errors, so I needed to split the pass calls to solve this.

Now that I think of it, maybe a good solution would be to add a skipCompileTimeConstantsCheck flag in TypeInference. That way I could postpone the compile time constant check, and DeclarationCopyPropagation on line 176 wouldn't be needed anymore, everything could be done in PassRepeated afterwards. Also, in that case, the use of TypeMap could be completely avoided.

Type checking uses the constant property to check that some expressions are compile-time constants, e.g., constructor parameters. It may be possible to split this functionality in a separate pass, but it may not be easy.

Your proposal to avoid giving errors in the first type-checking pass is a possibility. The type-checking pass is accumulating a few such boolean flags, which will make the code harder to understand, but they are relatively local.
If you make this change we should move from having boolean arguments in the constructor, that is completely unreadable, please define some enums with the options for typechecking.

enum class TypeCheckingOptions { SkipConstantCheck, ReadOnly, }

We could put these in the typeMap - in fact, this is what setStrictStruct does.

Thank you for your advice! I will try to do that and reply when I'm done.

mihaibudiu · 2022-02-11T21:58:53Z

testdata/p4_16_samples/decl-copy-prop.p4

@@ -0,0 1,120 @@
+
+/*


do you need to modify this copyright header?

Yes, sorry about that.

mihaibudiu · 2022-02-11T21:59:52Z

testdata/p4_16_samples/decl-copy-prop.p4

+
+control C1(inout bit<16> x)
+{
+ test2 tst2 = {1, {2, {3, 4}}, {5, {6, {7, 8}}, {{9, {10, 11}}, true}}};


this is not even a structexpression, it is a listexpression, but it will be turned into a structexpression after type checking.

Yes, I know. It was easier for me to initialize the struct in this form. I have now added a variable initialized with a StructExpression in the example.

It propagates declared variables in the locals part of controls. Implemented as a fix for p4lang#2844.

mihaibudiu · 2022-02-17T17:32:28Z

testdata/p4_16_samples_outputs/decl-copy-prop-first.p4

+ bit<32> h = 32w2;
+ bit<32> z = 32w12;
+ bit<32> all = 32w20;
+ bit<32> fun = f(h, 32w12);


in this test please add one more initializer after fun. I expect that one will not be optimized.

I've added it. You are right, it won't be optimized.

mihaibudiu · 2022-02-17T17:38:33Z

frontends/p4/frontend.cpp

@@ -172,11 173,17 @@ const IR::P4Program *FrontEnd::run(const CompilerOptions &options, const IR::P4P
 new ResolveReferences(&refMap), // check shadowing
 new Deprecated(&refMap),
 new CheckNamedArgs(),
+ new DeclarationCopyPropagation(&refMap, &typeMap, true),


Indeed, it is not, but since you are the first user of the reduced functionality it is a logical place to do it here.
It won't be too much work: just create a class that contains the constants HashMap and the APIs to insert and lookup. Then make typeMap inherit from that class.

AleksaSyrmia force-pushed the decl-copyprop branch from 51f0175 to 72065b4 Compare February 11, 2022 15:01

mihaibudiu requested changes Feb 11, 2022

View reviewed changes

Added DeclarationCopyPropagation pass.

2be7f1e

It propagates declared variables in the locals part of controls. Implemented as a fix for p4lang#2844.

AleksaSyrmia force-pushed the decl-copyprop branch from 72065b4 to 2be7f1e Compare February 17, 2022 16:09

mihaibudiu requested changes Feb 17, 2022

View reviewed changes

Test example changes

e16ef74

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implemented DeclarationCopyPropagation pass #3082

Implemented DeclarationCopyPropagation pass #3082

AleksaSyrmia commented Feb 11, 2022 •

edited

Loading

mihaibudiu Feb 11, 2022

mihaibudiu Feb 11, 2022

AleksaSyrmia Feb 17, 2022

mihaibudiu Feb 11, 2022

AleksaSyrmia Feb 17, 2022

mihaibudiu Feb 11, 2022

AleksaSyrmia Feb 17, 2022

mihaibudiu Feb 17, 2022

AleksaSyrmia Feb 21, 2022

mihaibudiu Feb 22, 2022

AleksaSyrmia Feb 22, 2022

mihaibudiu Feb 22, 2022

AleksaSyrmia Feb 22, 2022

mihaibudiu Feb 22, 2022

AleksaSyrmia Feb 22, 2022

mihaibudiu Feb 11, 2022

AleksaSyrmia Feb 17, 2022

mihaibudiu Feb 11, 2022

AleksaSyrmia Feb 17, 2022

mihaibudiu Feb 17, 2022

AleksaSyrmia Feb 21, 2022

mihaibudiu Feb 17, 2022

Implemented DeclarationCopyPropagation pass #3082

Are you sure you want to change the base?

Implemented DeclarationCopyPropagation pass #3082

Conversation

AleksaSyrmia commented Feb 11, 2022 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

AleksaSyrmia commented Feb 11, 2022 •

edited

Loading