Commit Graph

9 Commits

Author SHA1 Message Date
Erik Eckstein
0f0aa0c17b Optimizer: require that there are no unreachable blocks and infinite loops in OSSA
These two new invariants eliminate corner cases which caused bugs if optimization didn't handle them.
Also, it will significantly simplify lifetime completion.

The implementation basically consists of these changes:
* add a flag in SILFunction which tells optimization if they need to take care of infinite loops
* add a utility to break infinite loops
* let all optimizations remove unreachable blocks and break infinite loops if necessary
* add verification to check the new SIL invariants

The new `breakIfniniteLoops` utility breaks infinite loops in the control flow by inserting an "artificial" loop exit to a new dead-end block with an `unreachable`.
It inserts a `cond_br` with a `builtin "infinite_loop_true_condition"`:
```
bb0:
  br bb1
bb1:
  br bb1              // back-end branch
```
->
```
bb0:
  br bb1
bb1:
  %1 = builtin "infinite_loop_true_condition"() // always true, but the compiler doesn't know
  cond_br %1, bb2, bb3
bb2:                  // new back-end block
  br bb1
bb3:                  // new dead-end block
  unreachable
```
2026-01-22 17:41:23 +01:00
Erik Eckstein
c822615dc2 Optimizer: convert the UpdateBorrowedFromPass pass to a test
And remove the now empty TestPasses directory.
2025-12-15 10:01:51 +01:00
Erik Eckstein
e14c1d1f62 SIL, Optimizer: update and handle borrowed-from instructions
Compute, update and handle borrowed-from instruction in various utilities and passes.
Also, used borrowed-from to simplify `gatherBorrowIntroducers` and `gatherEnclosingValues`.
Replace those utilities by `Value.getBorrowIntroducers` and `Value.getEnclosingValues`, which return a lazily computed Sequence of borrowed/enclosing values.
2024-04-10 13:38:10 +02:00
Meghana Gupta
d5f6b12830 Avoid generating address phis in LoopUnroll 2022-09-12 11:25:55 -07:00
Erik Eckstein
383c52aa35 SIL: rename dealloc_ref [stack] -> dealloc_stack_ref
Introduce a new instruction `dealloc_stack_ref ` and remove the `stack` flag from `dealloc_ref`.

The `dealloc_ref [stack]` was confusing, because all it does is to mark the deallocation of the stack space for a stack promoted object.
2022-01-07 16:20:27 +01:00
Andrew Trick
70d09b511b OSSA: Disable cond_br arguments
In OSSA, there is no reason for the cond_br instruction to take arguments.

In OSSA utilities, we have two types of block arguments: terminator
results and phis. cond_br arguments don't fit into either one of these
categories. Supporting them would be prohibitively complex. In fact, I
have no idea model it.

I have already made the assumption in several places that we don't
support cond_br args. It would be impossible to test all the code that
makes this assumption, so even if we wanted to support cond_br args,
they would always be broken in practice.

Simply mark them illegal in the SILVerifier and make sure no OSSA
passes generate them.
2021-02-12 22:19:19 -08:00
Meghana Gupta
3b60184f53 "[NFC] Add tests for LoopUnroll on OSSA""
Reland #35423
2021-01-20 22:26:18 -08:00
Ben Barham
16d614412a Revert "[NFC] Add tests for LoopUnroll on OSSA" 2021-01-19 09:00:36 +10:00
Meghana Gupta
e10ffb79b2 Add tests for LoopUnroll on OSSA 2021-01-14 10:31:07 -08:00