Optimize joins by separating block-local origins from cross-block persistent origins

[usx95]

Prevent block-local origins from participating in Join operations

The lifetime analysis currently performs join operations on all origins at every block boundary, which is expensive. However, many origins are block-local: they are created and destroyed within a single block, existing only to propagate loans between persistent origins across temporary declarations.

Proposed optimization:

1. Classify origins into two categories during analysis:

   • Block-local origins: start and die within the same block
   • Persistent origins: visible across multiple blocks

2. During join operations at block boundaries, only join the persistent origins and skip block-local ones entirely

Benefits:

• Significantly reduces join complexity, especially in functions with many temporary locals
• Performance improvement scales with the ratio of temporary to persistent origins

Considerations:

• Need a pre-pass to correctly classify origins
• Loan propagation for block-local origins must still work correctly within their block

Implementation:
Split the loan propagation lattice into two separate maps:

1. Persistent origins map: for origins visible across multiple blocks
2. Block-local origins map: for origins confined to a single block

At block entries (after joining), the block-local map would be empty. During block execution, both maps are populated and used for loan propagation. At block boundaries, only the persistent map participates in join operations. Block-local map naturally empties at block entries.

Credits to @Xazax-hun for this idea.

[llvmbot]

@llvm/issue-subscribers-clang-temporal-safety

Author: Utkarsh Saxena (usx95)

Prevent block-local origins from participating in Join operations

The lifetime analysis currently performs join operations on all origins at every
block boundary, which is expensive. However, many origins are block-local: they
are created and destroyed within a single block, existing only to propagate loans
between persistent origins across temporary declarations.

Proposed optimization:

1. Classify origins into two categories during analysis:

   • Block-local origins: start and die within the same block
   • Persistent origins: visible across multiple blocks

2. During join operations at block boundaries, only join the persistent origins
   and skip block-local ones entirely

Benefits:

• Significantly reduces join complexity, especially in functions with many
  temporary locals
• Performance improvement scales with the ratio of temporary to persistent origins

Considerations:

• Need a pre-pass to correctly classify origins
• Loan propagation for block-local origins must still work correctly within
  their block

Implementation:
Split the loan propagation lattice into two separate maps:

1. Persistent origins map: for origins visible across multiple blocks
2. Block-local origins map: for origins confined to a single block

At block entries (after joining), the block-local map would be empty. During
block execution, both maps are populated and used for loan propagation. At block
boundaries, only the persistent map participates in join operations.
Block-local map naturally empties at block entries.

Credits to @Xazax-hun for this idea.