Skip to content

ir3: reduce mark_kill_path run time in pathological cases

Danylo Piliaiev requested to merge Danil/mesa:ir3/fix/mark-kill-path-complexity into master

mark_kill_path() is happy to take exponential time to finish when presented with such chains of instructions:

  ...
 stib.base0 imm[0.000000,0,0x0], ssa_233, ssa_234, false-deps:ssa_231, ssa_231
 stib.base0 imm[0.000000,0,0x0], ssa_237, ssa_238, false-deps:ssa_235, ssa_235
 stib.base0 imm[0.000000,0,0x0], ssa_241, ssa_242, false-deps:ssa_239, ssa_239
 stib.base0 imm[0.000000,0,0x0], ssa_245, ssa_246, false-deps:ssa_243, ssa_243
 stib.base0 imm[0.000000,0,0x0], ssa_249, ssa_250, false-deps:ssa_247, ssa_247
 stib.base0 imm[0.000000,0,0x0], ssa_105, ssa_253, false-deps:ssa_251, ssa_251
 stib.base0 imm[0.000000,0,0x0], ssa_109, ssa_256, false-deps:ssa_254, ssa_254
 stib.base0 imm[0.000000,0,0x0], ssa_113, ssa_259, false-deps:ssa_257, ssa_257
 stib.base0 imm[0.000000,0,0x0], ssa_117, ssa_262, false-deps:ssa_260, ssa_260
 stib.base0 imm[0.000000,0,0x0], ssa_265, ssa_266, false-deps:ssa_263, ssa_263
 stib.base0 imm[0.000000,0,0x0], ssa_269, ssa_270, false-deps:ssa_267, ssa_267
 stib.base0 imm[0.000000,0,0x0], ssa_273, ssa_274, false-deps:ssa_271, ssa_271
  ...

Fixes tests:

 dEQP-VK.geometry.layered.cube_array.36_36_12.secondary_cmd_buffer_inherit_framebuffer
 dEQP-VK.geometry.layered.3d.64_64_8.secondary_cmd_buffer_inherit_framebuffer
 dEQP-VK.geometry.layered.cube_array.64_64_12.secondary_cmd_buffer_inherit_framebuffer
Edited by Danylo Piliaiev

Merge request reports