Resolution of ambiguous type names (consider adding a warning)

[xphoniex]

When trying to make compile RV64ACDFIMSU_Piccolo_iverilog build of Piccolo:

/Piccolo/builds/RV64ACDFIMSU_Piccolo_iverilog$ make compile
INFO: Verilog RTL generation ...
bsc -u -elab -verilog  -vdir Verilog_RTL  -bdir build_dir  -info-dir build_dir  -D IVERILOG -D RV64 -D ISA_PRIV_M  -D ISA_PRIV_U  -D ISA_PRIV_S -D SV39 -D ISA_I  -D ISA_M  -D ISA_A  -D ISA_C -D ISA_F  -D ISA_D  -D INCLUDE_FDIV  -D INCLUDE_FSQRT -D SHIFT_BARREL -D MULT_SYNTH -D Near_Mem_Caches -D FABRIC64  -keep-fires -aggressive-conditions -no-warn-action-shadowing -no-show-timestamps -check-assert -suppress-warnings G0020 +RTS -K128M -RTS  -show-range-conflict  -p :../../src_Core/CPU:../../src_Core/ISA:../../src_Core/RegFiles:../../src_Core/Core:../../src_Core/Near_Mem_VM:../../src_Core/PLIC:../../src_Core/Near_Mem_IO:../../src_Core/Debug_Module:../../src_Core/BSV_Additional_Libs:../../src_Testbench/Top:../../src_Testbench/SoC:../../src_Testbench/Fabrics/AXI4:+  ../../src_Testbench/Top/Top_HW_Side.bsv
checking package dependencies
compiling ../../src_Core/CPU/FPU.bsv
Error: "../../src_Core/CPU/FPU.bsv", line 47, column 31: (T0080)
  Type error at the use of the following function:
    mkFloatingPointDivider

  The expected return type of the function:
    g__#(ClientServer::Server#(Tuple3#(FPU::FDouble, FPU::FDouble, ISA_Decls::RoundMode), FPU::FpuR))

  The return type according to the use:
    c__#(ClientServer::Server#(Tuple3#(FloatingPoint::FloatingPoint#(d__, e__),
                   FloatingPoint::FloatingPoint#(d__, e__),
                   FloatingPoint::RoundMode),
               Tuple2#(FloatingPoint::FloatingPoint#(d__, e__), FloatingPoint::Exception)))

../../builds/Resources/Include_iverilog.mk:20: recipe for target 'compile' failed
make: *** [compile] Error 1

using:

$ bsc -v
Bluespec Compiler (build 88d4eef)
$ iverilog -v
Icarus Verilog version 11.0 (stable) (v11_0-57-geaea6980-dirty)

I don't exactly understand the error, I've tried changing the typedef FloatingPoint#(11,52) FDouble; in FPU.bsv to FPU which doesn't make any sense and it's not compiling either. Any help what this means and how to solve it?

[quark17]

The mismatch is in the RoundMode type. It turns out that there are two places that define a type by this name, one in ISA_Decls (in Piccolo's src_core/ISA/ directory) and one in FloatingPoint (in BSC's libraries). If you replace RoundMode everywhere in the files FPU.bsv and FBox_core.bsv with FloatingPoint::RoundMode, then it compiles.

When there are a multiple packages (say A and B) that define the same name (say T), both names are in scope by their qualified names (A::T and B::T). When you refer to the name without a qualifier (T), BSC uses the one from the most recently imported package -- and if it is defined in the current package, then BSC uses that one. My guess is that the order of importing packages has changed, which is why this code compiled before but fails to compile now. (I can investigate what caused this, as it's not something I would have expected.)

Instead of adding a qualifier on all uses of RoundMode, another way to fix this would be to hide that name when importing ISA_Decls. This feature is available in Haskell and would be reasonable to have in BSV, but is not yet available -- issue #192 includes this enhancement.

It would also be helpful if BSC warned that we were using a name that is defined in multiple packages. Issue #193 is about warning on unused imports, but I think it could also be extended to include warnings on conflicting imports of names.

[quark17]

BSC's behavior changed in commit 2c1ed34, which removed unused imports from a number of libraries, including FloatingPoint.

BSC creates a dependency graph of the imports and flattens that into an order for reading the files in (and also to check that there are no cycles). This is done in sortImports (in BinUtils) using tsort (in SCC). This tsort function expects an Ord instance for the type of the nodes in the graph, and that is used for preserving a stable order. The Ord instance for Id is based on the Ord instance for FString which ultimately is based on the unique numbers in SpeedyString, which are based on the order in which the strings were created (which is not stable). I see that sortImports has a comment explaining that, instead of sorting on Id, it sorts on String, in order to avoid this problem:

-- We map the signatures to strings and sort a graph of strings,                                                                  
-- so that sorting is stable (the Ord instance for the tuple includes                                                             
-- Ids, whose Ord instance depends on when the Id was created)                                                                    

This ought to be a good ordering.

There may be some tricks that we can apply, to cause tsort to not unnecessarily jumble nodes that are not otherwise constrained. For example, in ASchedule, there are places where we take edge pairs (x,y) and convert them to (y,x), because of how tsort works. Perhaps that's all we need to do here.

The sort order is certainly stable across calls to BSC on the same files. The issue appears to be that the order changes when the file imports change. I'm not sure if we can ever prevent that, although maybe there are some properties of the sort order that we can guarantee won't change unnecessarily.

Ultimately, what we care about here is the resolution of conflicts in imported names. That's currently done based on the relative order of those packages in the flattened import order. This is because we populate the symbol table as we load in each import, and later imports overwrite any entries from previous imports. However, we could decouple this, so that the resolution in the symbol table is done in a controlled way, independent of the import order. That is, when we populate a name in the symbol table and discover that it already exists, instead of just overwriting, we can calculate which to keep. For example, we could choose the one whose package name comes earlier alphabetically -- in this case, the packages did not change names, so the order would not have changed if we'd used this decision function. We could also use the order in which the package is listed in the file -- again, since the source file had not changed, this order would not have changed.

[nanavati]

Stepping back, I wouldn't spend too much time on trying to mimic BSC's current, accidental resolution of conflicting imports and putting it on a more predictable footing. I think that's an implementation detail people shouldn't be relying on (even if they currently are).

As a user, I'd much rather have a good warning about when there is an ambiguity so that I can explicitly qualify any conflicting names. As things currently stand, that might get somewhat tedious, but users can always turn a new warning off. And if that becomes too annoying, that's good pressure to add better import-control mechanisms so there are fewer opportunities for conflicts.

[nanavati]

Making a good warning (that isn't over or under-inclusive) is probably tricky (especially since I think we should still allow overlaps where a package-local definition wins), but, in the bigger picture it would be more valuable than making the current behavior more stable.

[xphoniex]

Oh, I didn't realize the problem was RoundMode, I thought the compiler is asking me to change the package to FPU for FDouble which didn't make sense!!

It'd be helpful if there were rust-style error messages pointing exactly to where the issue lies, e.g.:

error[E0412]: cannot find type `int` in this scope
 --> src/main.rs:2:12
  |
2 | fn test(i: int) {
  |            ^^^ not found in this scope

So, yeah after changing all the RoundMode to FloatingPoint::RoundMode in both FPU.bsv and FBox_core.bsv it compiles now. Thanks!

I also tried to changing the order of import FloatingPoint :: *; and import ISA_Decls :: *; but that didn't change anything.

Another way was to add typedef FloatingPoint::RoundMode RoundMode; in FPU.bsv and without changing the FBox_core.bsv it compiles now. Do you want me to make a PR btw?

[quark17]

Another way was to add typedef FloatingPoint::RoundMode RoundMode; in FPU.bsv and without changing the FBox_core.bsv it compiles now.

That's clever! You're creating yet a third definition for the name, but the one guarantee that BSC does make is that a name defined in the current package will shadow definitions by the same name that are imported. So even though you've created a further conflicting definition, it's the one that BSC will pick.

Another way to fix this is to remove RoundMode from ISA_Decls, since that definition appears to never be used! (However, that code is common to several other CPU repos, and it might be used in some of those, so removing it may not be an option.)

Do you want me to make a PR btw?

I don't administer the Piccolo repo, but I've mentioned the issue to @rsnikhil who maintains it. You could file an issue on the Piccolo repo, as well, if you want, but I don't think that a PR is appropriate yet, since I'm unsure what the right resolution is.

[jrtc27]

We just deleted the struct in CHERI-Flute FWIW