[gen] Unify the macro unfold, edge wildcard unfold, and edge-annotation merge

[ShaleXIONG]

Assume an input relaxation $R$, the current unfold processes are:

• A choice between unfold a macro or parse as an edge.
  • if $R$ is an individual relax, it triggers relax macro unfold, while if it is a composite relax, it will NOT.
  • If unfolding macro fails or is not triggered, it falls back to the default parsing as edge. The input $R$ will be parsed, via a lookup table, to an internal data structure type edge in edge.ml, that is, {atom_1, edge, atom_2}. For example input [PodWR A] yields a list ERS ([{None, PodWR, None}; {A, Id, A}]). Note that individual annotations are NOT merged with edges nor type check here, e.g. {A, Id, A}, where Id edge indicating annotation. Such list is wrapped in a contractor ERS. This process happens in expand_relax_macros in relax.ml.
• Given the result above under type relax, the wildcard edge in the ERS(...) will be unfolded further. For example PodW* will be unfold to PodWR and PodWW. Separately, there is a legacy const contractor PPO that are serves as special wildcard based on different architectures. PPO will be unfolded to ERS(...). This happens in expand_relaxs in relax.ml.
• Last, for a candidate cycle of the form ERS(...), from (1) direct input of diyone7, (2) cartesian product from input of diycross7 and (3) output of the searching algorithms in diy7:
  • annotations will be type checked and merged into adjacent edges,
  • adjacent edges will be type checked for example a edge ending with read should match with next edge starting from a read. The two processes are in resolve_edges in edge.ml.

The possible improvement:

• Fix the problem where a composite relax will not go through macro unfold process.
• Unify architecture-agnostic macro unfold and architecture-specific edge wildcard unfold. A better solution is an architecture-specific lookup table to unfold wildcard edges. This means macro and wildcard can be unfold all together.
• Resolve and type check earlier in the process. This means less searching space for diy7 where the input can be immediate resolved and type checked to filter out invalid inputs prior the searching algorithm.

@fsestini
ref: discussion in #1745

[fsestini]

Thanks for this @ShaleXIONG

I think another aspect worth mentioning is that currently diy7 -show edges will not include macros like allRW in the list it prints. I think there should be a way to print the list of macros, especially if we plan to unify the logic for macro and wildcard expansion. I am not sure if these macros/wildcards should be printed via a new -show macros flag or included in -show edges, though.

Moreover, if we decide to unify macro expansion and wildcard unfolding, we will need to think about how to deal with input relaxations like allR* (i.e., combinations of macros and wildcards). I think in this cases we should expand * first, then expand any macro that results.

Do you have thoughts about these two points?

[ShaleXIONG]

Thanks for this @ShaleXIONG

I think another aspect worth mentioning is that currently diy7 -show edges will not include macros like allRW in the list it prints. I think there should be a way to print the list of macros, especially if we plan to unify the logic for macro and wildcard expansion. I am not sure if these macros/wildcards should be printed via a new -show macros flag or included in -show edges, though.

Moreover, if we decide to unify macro expansion and wildcard unfolding, we will need to think about how to deal with input relaxations like allR* (i.e., combinations of macros and wildcards). I think in this cases we should expand * first, then expand any macro that results.

Do you have thoughts about these two points?

Yes that is a good question. I forget to document the -show edge/-list and thanks to bring it here.

We can always expand or unfold the new unified macro lookup table (or via other mechanism), which includes all the old macros and wildcard, uniformly and immediately after parsing or during the parsing. For example an input "AllR* Po" in all diy* tools returns internally data structure equivalent to PodRW PodRW, PodRR PodRW, and so on. This means that all are unfolded to the most primitive form.

We can also simplify the type definition a lot in edge.ml which now only contain individual primitive edge with precise associated behaviours.