AMDGPU: Limit the search in finding the instruction pattern for v_swap generation.
authorChangpeng Fang <changpeng.fang@gmail.com>
Fri, 7 Feb 2020 19:06:33 +0000 (11:06 -0800)
committerChangpeng Fang <changpeng.fang@gmail.com>
Fri, 7 Feb 2020 19:06:33 +0000 (11:06 -0800)
commit6370c7c13e6d7cfa70197e9a45033e2b845e1b9e
tree05a3a978c7fd9102ec2cfa7b95dc3a87b4dc114e
parent4a1a0690ad6813a4c8cdb8dc20ea6337aa1f61e0
AMDGPU: Limit the search in finding the instruction pattern for v_swap generation.

Summary:
  Current implementation of matchSwap in SIShrinkInstructions searches the entire
use_nodbg_operands set to find the possible pattern to generate v_swap instruction.
This approach will lead to a O(N^3) in compile time for SIShrinkInstructions.

But in reality, the matching pattern only exists within nearby instructions in the
same basic block. This work limits the search to a maximum of 16 instructions, and has
a linear compile time comsumption.

Reviewers:
  rampitec, arsenm

Differential Revision: https://reviews.llvm.org/D74180
llvm/lib/Target/AMDGPU/SIShrinkInstructions.cpp
llvm/test/CodeGen/AMDGPU/v_swap_b32.mir