Collision in Register Allocation

[Jackcuii]

We still have some more issues on register allocation problems in our kernel.
Still take the gemm as an example.

- index_per_ii: 11
              operations:
                - opcode: "NOT"
                  id: 159
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                  dst_operands:
                    - operand: "$3"
                      color: "RED"
                    - operand: "$0"
                      color: "RED"
                    - operand: "$7"
                      color: "RED"
                    - operand: "$6"
                      color: "RED"
                    - operand: "NORTH"
                      color: "RED"
                    - operand: "$5"
                      color: "RED"
                    - operand: "SOUTH"
                      color: "RED"
                    - operand: "WEST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 105
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "WEST"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1480000
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$3"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 12
              operations:
                - opcode: "GRANT_PREDICATE"
                  id: 158
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                    - operand: "$1"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1780000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$7"
                      color: "RED"
                  dst_operands:
                    - operand: "WEST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1770000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$6"
                      color: "RED"
                  dst_operands:
                    - operand: "SOUTH"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1750000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$5"
                      color: "RED"
                  dst_operands:
                    - operand: "NORTH"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1460000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$4"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 13
              operations:
                - opcode: "ADD"
                  id: 182
                  time_step: 13
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                    - operand: "#1"
                      color: "RED"
                  dst_operands:
                    - operand: "NORTH"
                      color: "RED"
                    - operand: "$4"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1730002
                  time_step: 13
                  invalid_iterations: 0
                  src_operands:
                    - operand: "WEST"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 14
              operations:
                - opcode: "GRANT_PREDICATE"
                  id: 190
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$2"
                      color: "RED"
                    - operand: "$3"
                      color: "RED"
                  dst_operands:
                    - operand: "$1"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1790000
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 167
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "EAST"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"

in the IR above, the DATA_MOV(1790000) needs to consume the result of NOT(159) through $0. However, the $0 is overwritten for many times before the NOT can access it, including MOV(105) and GPRED(158), which is totally unrelated to this flow.

[ShangkunLi]

We still have some more issues on register allocation problems in our kernel. Still take the gemm as an example.

- index_per_ii: 11
              operations:
                - opcode: "NOT"
                  id: 159
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                  dst_operands:
                    - operand: "$3"
                      color: "RED"
                    - operand: "$0"
                      color: "RED"
                    - operand: "$7"
                      color: "RED"
                    - operand: "$6"
                      color: "RED"
                    - operand: "NORTH"
                      color: "RED"
                    - operand: "$5"
                      color: "RED"
                    - operand: "SOUTH"
                      color: "RED"
                    - operand: "WEST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 105
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "WEST"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1480000
                  time_step: 11
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$3"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 12
              operations:
                - opcode: "GRANT_PREDICATE"
                  id: 158
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                    - operand: "$1"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1780000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$7"
                      color: "RED"
                  dst_operands:
                    - operand: "WEST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1770000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$6"
                      color: "RED"
                  dst_operands:
                    - operand: "SOUTH"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1750000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$5"
                      color: "RED"
                  dst_operands:
                    - operand: "NORTH"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1460000
                  time_step: 12
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$4"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 13
              operations:
                - opcode: "ADD"
                  id: 182
                  time_step: 13
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                    - operand: "#1"
                      color: "RED"
                  dst_operands:
                    - operand: "NORTH"
                      color: "RED"
                    - operand: "$4"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1730002
                  time_step: 13
                  invalid_iterations: 0
                  src_operands:
                    - operand: "WEST"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
            - index_per_ii: 14
              operations:
                - opcode: "GRANT_PREDICATE"
                  id: 190
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$2"
                      color: "RED"
                    - operand: "$3"
                      color: "RED"
                  dst_operands:
                    - operand: "$1"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 1790000
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "$0"
                      color: "RED"
                  dst_operands:
                    - operand: "EAST"
                      color: "RED"
                - opcode: "DATA_MOV"
                  id: 167
                  time_step: 14
                  invalid_iterations: 0
                  src_operands:
                    - operand: "EAST"
                      color: "RED"
                  dst_operands:
                    - operand: "$0"
                      color: "RED"

in the IR above, the DATA_MOV(1790000) needs to consume the result of NOT(159) through $0. However, the $0 is overwritten for many times before the NOT can access it, including MOV(105) and GPRED(158), which is totally unrelated to this flow.

Hi~ @Jackcuii, as shown in the mapped ir:

......

%134 = "neura.not"(%133) {dfg_id = 159 : i32, mapping_locs = [{id = 5 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, resource = "tile", time_step = 11 : i32, x = 1 : i32, y = 1 : i32}]} : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
%135 = "neura.data_mov"(%129) {dfg_id = 126 : i32, mapping_locs = [{id = 162 : i32, index_per_ii = 9 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 2 : i32, resource = "register", time_step = 9 : i32}, {id = 162 : i32, index_per_ii = 10 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 2 : i32, resource = "register", time_step = 10 : i32}, {id = 162 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 2 : i32, resource = "register", time_step = 11 : i32}, {id = 162 : i32, index_per_ii = 12 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 2 : i32, resource = "register", time_step = 12 : i32}, {id = 162 : i32, index_per_ii = 13 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 2 : i32, resource = "register", time_step = 13 : i32}]} : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
%136 = "neura.data_mov"(%134) {dfg_id = 180 : i32, mapping_locs = [{id = 163 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 3 : i32, resource = "register", time_step = 11 : i32}, {id = 163 : i32, index_per_ii = 12 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 3 : i32, resource = "register", time_step = 12 : i32}, {id = 163 : i32, index_per_ii = 13 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 3 : i32, resource = "register", time_step = 13 : i32}]} : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
%137 = neura.grant_predicate %135, %136 {dfg_id = 190 : i32, mapping_locs = [{id = 5 : i32, index_per_ii = 14 : i32, invalid_iterations = 0 : i32, resource = "tile", time_step = 14 : i32, x = 1 : i32, y = 1 : i32}]} : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>
......

%159 = "neura.data_mov"(%101) {dfg_id = 105 : i32, mapping_locs = [{id = 10 : i32, index_per_ii = 10 : i32, invalid_iterations = 0 : i32, resource = "link", time_step = 10 : i32}, {id = 160 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 0 : i32, resource = "register", time_step = 11 : i32}]} : (!neura.data<i64, i1>) -> !neura.data<i64, i1>
%160 = "neura.data_mov"(%132) {dfg_id = 150 : i32, mapping_locs = [{id = 161 : i32, index_per_ii = 10 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 1 : i32, resource = "register", time_step = 10 : i32}, {id = 161 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 1 : i32, resource = "register", time_step = 11 : i32}]} : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
%161 = neura.grant_predicate %159, %160 {dfg_id = 158 : i32, mapping_locs = [{id = 5 : i32, index_per_ii = 12 : i32, invalid_iterations = 0 : i32, resource = "tile", time_step = 12 : i32, x = 1 : i32, y = 1 : i32}]} : !neura.data<i64, i1>, !neura.data<i1, i1> -> !neura.data<i64, i1>

The result of not(dfg_id = 159) op is passed to the grant_predicate (dfg_id = 190) through register per_tile_register_id = 3 : i32.

And operands of grant_predicate (dfg_id = 158) are passed to the consumer op through per_tile_register_id = 0 : i32 and per_tile_register_id = 1 : i32, respectively, which should not overwrite the value stored in the per_tile_register_id = 3 : i32.

Do you think there's any problem with the mapping result?

[Jackcuii]

Thanks Shangkun @ShangkunLi

Emmm Maybe our version is slightly different?

In my version, the dataflow is like NOT(159) -> MOV(1790000) -> MOV(179) -> GPRED(189)

And the problem starts from 17900000.

@n0thingNoob can you check if the kernels in the Zeonica_Bench are up-to-date?

[n0thingNoob]

The problem is in codegen,
%139 = "neura.data_mov"(%134) {dfg_id = 179 : i32, mapping_locs = [{id = 168 : i32, index_per_ii = 11 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 11 : i32}, {id = 161 : i32, index_per_ii = 12 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 1 : i32, resource = "register", time_step = 12 : i32}, {id = 160 : i32, index_per_ii = 13 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 0 : i32, resource = "register", time_step = 13 : i32}, {id = 14 : i32, index_per_ii = 14 : i32, invalid_iterations = 0 : i32, resource = "link", time_step = 14 : i32}, {id = 200 : i32, index_per_ii = 15 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 15 : i32}, {id = 200 : i32, index_per_ii = 16 : i32, invalid_iterations = 0 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 16 : i32}, {id = 200 : i32, index_per_ii = 0 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 17 : i32}, {id = 200 : i32, index_per_ii = 1 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 18 : i32}, {id = 200 : i32, index_per_ii = 2 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 19 : i32}, {id = 200 : i32, index_per_ii = 3 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 20 : i32}, {id = 200 : i32, index_per_ii = 4 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 21 : i32}, {id = 200 : i32, index_per_ii = 5 : i32, invalid_iterations = 1 : i32, per_tile_register_id = 8 : i32, resource = "register", time_step = 22 : i32}]} : (!neura.data<i1, i1>) -> !neura.data<i1, i1>
In codegen, it only assumes there is one register in the data_mov src tile side and only deals with the last one, which is reg 0 in the src tile. I need to add such a case in the code gen, but the destination side is correct.