VPR fails to place long carry chains on xc7

[kazkojima]

Hi,

I've added 256 to the bit-width parameter list of tests/7-carry_stress test

diff --git a/tests/7-carry_stress/CMakeLists.txt b/tests/7-carry_stress/CMakeLists.txt
index 1995e5d0..969fd84a 100644
--- a/tests/7-carry_stress/CMakeLists.txt
+++ b/tests/7-carry_stress/CMakeLists.txt
@@ -1,6 +1,6 @@
 
 get_target_property_required(PYTHON3 env PYTHON3)
-foreach(CARRY_DEPTH 1 2 3 4 7 8 9 15 16 17 31 32)
+foreach(CARRY_DEPTH 1 2 3 4 7 8 9 15 16 17 31 32 256)
     set(CARRY_TEST carry_test_${CARRY_DEPTH}_init0.v)
     add_custom_command(
         OUTPUT ${CARRY_TEST}

and run "make 7-carry_stress_init_fabric_depth_256_dummy_artix7_xc7a50t-basys3_test_route".
The placement failed with the following message.

File: /home/runner/work/conda-eda/conda-eda/workdir/conda-env/conda-bld/vtr-optimized_1642201887903/work/vpr/src/place/initial_placement.cpp
Line: 413
Message: Initial placement failed.
Could not place macro length 64 with head block $auto$alumacc.cc:485:replace_alu$1426.genblk1.slice[0].genblk1.carry4 (#0); not enough free locations of type(s) {BLK-TL-CLBLL_L, BLK-TL-CLBLL_R, BLK-TL-CLBLM_L, BLK-TL-CLBLM_R}.
Please manually size the FPGA because VPR can't do this yet.

[kazkojima]

FYI, nextpnr-xilinx has a similar issue
gatecat/nextpnr-xilinx#34

[programmerjake]

Copying a comment from the nextpnr-xilinx issue that applies to VPR too:
Luke (the person at Libre-SOC who originally encountered this bug) thinks this bug is best fixed fixed by making yosys split long carry4 chains. imho vpr and nextpnr-xilinx are where that would be handled since they know the details of how many carry4 blocks are available and should be able to insert the necessary routing between them. imho yosys is the wrong place to try to fix that.

additional context: https://libre-soc.org/irclog/%23libre-soc.2022-03-11.log.html#t2022-03-11T18:23:08

Contents of email Luke (lkcl) asked me to post

<lkcl> marzoul: fyi the same bug in symbiflow related to CARRY4, which
i discussed with acomodi when this was the #symbiflow channel, is also
present in nextpnr-xilinx
<lkcl> gatecat ^
<lkcl> it does not show up when using RISC-V 32-bit cores because
those never create carry-chains of more than 23-25 CARRY4 blocks
<lkcl> only if you attempt a 64-bit core using e.g. a divide unit with
128-bit remainder/quotients e.g. in Power ISA 64-bit do you run smack
into this problem
<lkcl> toshywoshy, as discussed yesterday ^
<lkcl> the symptoms for symbiflow are that it bombs out with an error
<lkcl> the symptoms for nextpnr-xilinx are that it completely locks up
and fails to complete, going into an infinite loop
<lkcl> as long as you stay below about 4x23-or-so (95) bit add,
subtract or compare, you're "fine"
<lkcl> the "workaround" is to use "-nocarry" to yosys "synth_xilinx"
<lkcl>     -nocarry
<lkcl>         do not use XORCY/MUXCY/CARRY4 cells in output netlist
<lkcl> the proper solution is to fix the synth_xilinx techmap so that
it splits anything above 95-or-thereabouts bits into separate
adds/subs/cmps with an explicit carry-signal
<lkcl> x[128], y[128]
<lkcl> add(x, y)
<lkcl> -->
<lkcl> z[0:97] = add(x[0:96], y[0:96])
<lkcl> z[96:128] = add(z[96], x[96:128], y[96:128])
<lkcl> you get the general idea i'm sure

[mithro]

The easiest short term fix is for Yosys to split long carry4 chains.

As you point out this is probably not the best place to do this however and the place and route tooling has a much better idea of the constraints around placement and hence when the carry can and can't be used. However, that is probably going to require quite a bit of work (at least it will in vpr -- don't know about nextpnr) so the short term fix is probably worth still landing.