Commit Graph

6 Commits

Author SHA1 Message Date
Erik Eckstein
f9b524b1cb AliasAnalysis: a complete overhaul of alias- and memory-behavior analysis
The main changes are:

*) Rewrite everything in swift. So far, parts of memory-behavior analysis were already implemented in swift. Now everything is done in swift and lives in `AliasAnalysis.swift`. This is a big code simplification.

*) Support many more instructions in the memory-behavior analysis - especially OSSA instructions, like `begin_borrow`, `end_borrow`, `store_borrow`, `load_borrow`. The computation of end_borrow effects is now much more precise. Also, partial_apply is now handled more precisely.

*) Simplify and reduce type-based alias analysis (TBAA). The complexity of the old TBAA comes from old days where the language and SIL didn't have strict aliasing and exclusivity rules (e.g. for inout arguments). Now TBAA is only needed for code using unsafe pointers. The new TBAA handles this - and not more. Note that TBAA for classes is already done in `AccessBase.isDistinct`.

*) Handle aliasing in `begin_access [modify]` scopes. We already supported truly immutable scopes like `begin_access [read]` or `ref_element_addr [immutable]`. For `begin_access [modify]` we know that there are no other reads or writes to the access-address within the scope.

*) Don't cache memory-behavior results. It turned out that the hit-miss rate was pretty bad (~ 1:7). The overhead of the cache lookup took as long as recomputing the memory behavior.
2024-07-29 17:33:46 +02:00
Erik Eckstein
8cb2caa5ab tests: remove unneeded SIL comments and fix check-lines in alias-analysis tests
*) remove `// users: ...` comments
*) replace some `CHECK:` with `CHECK-NEXT:` lines. Otherwise the test could pass although the result is wrong
2024-07-29 17:33:45 +02:00
Erik Eckstein
beb46eb624 Use the new escape and side effects in alias analysis 2022-12-21 17:41:46 +01:00
Josh Soref
730b16c569 Spelling siloptimizer
* access
* accessed
* accesses
* accessor
* acquiring
* across
* activated
* additive
* address
* addresses'
* aggregated
* analysis
* and
* appropriately
* archetype
* argument
* associated
* availability
* barriers
* because
* been
* beginning
* belongs
* beneficial
* blocks
* borrow
* builtin
* cannot
* canonical
* canonicalize
* clazz
* cleanup
* coalesceable
* coalesced
* comparisons
* completely
* component
* computed
* concrete
* conjunction
* conservatively
* constituent
* construct
* consuming
* containing
* covered
* creates
* critical
* dataflow
* declaration
* defined
* defining
* definition
* deinitialization
* deliberately
* dependencies
* dependent
* deserialized
* destroy
* deterministic
* deterministically
* devirtualizes
* diagnostic
* diagnostics
* differentiation
* disable
* discipline
* dominate
* dominates
* don't
* element
* eliminate
* eliminating
* elimination
* embedded
* encounter
* epilogue
* epsilon
* escape
* escaping
* essential
* evaluating
* evaluation
* evaluator
* executing
* existential
* existentials
* explicit
* expression
* extended
* extension
* extract
* for
* from
* function
* generic
* guarantee
* guaranteed
* happened
* heuristic
* however
* identifiable
* immediately
* implementation
* improper
* include
* infinite
* initialize
* initialized
* initializer
* inside
* instruction
* interference
* interferes
* interleaved
* internal
* intersection
* intractable
* intrinsic
* invalidates
* irreducible
* irrelevant
* language
* lifetime
* literal
* looks
* materialize
* meaning
* mergeable
* might
* mimics
* modification
* modifies
* multiple
* mutating
* necessarily
* necessary
* needsmultiplecopies
* nonetheless
* nothing
* occurred
* occurs
* optimization
* optimizing
* original
* outside
* overflow
* overlapping
* overridden
* owned
* ownership
* parallel
* parameter
* paths
* patterns
* pipeline
* plottable
* possible
* potentially
* practically
* preamble
* precede
* preceding
* predecessor
* preferable
* preparation
* probably
* projection
* properties
* property
* protocol
* reabstraction
* reachable
* recognized
* recursive
* recursively
* redundant
* reentrancy
* referenced
* registry
* reinitialization
* reload
* represent
* requires
* response
* responsible
* retrieving
* returned
* returning
* returns
* rewriting
* rewritten
* sample
* scenarios
* scope
* should
* sideeffects
* similar
* simplify
* simplifycfg
* somewhat
* spaghetti
* specialization
* specializations
* specialized
* specially
* statistically
* substitute
* substitution
* succeeds
* successful
* successfully
* successor
* superfluous
* surprisingly
* suspension
* swift
* targeted
* that
* that our
* the
* therefore
* this
* those
* threshold
* through
* transform
* transformation
* truncated
* ultimate
* unchecked
* uninitialized
* unlikely
* unmanaged
* unoptimized key
* updataflow
* usefulness
* utilities
* villain
* whenever
* writes

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>
2022-10-03 18:31:33 -04:00
Erik Eckstein
74a702630c AliasAnalysis: fix a bug where an index_addr with zero offset can result in a false no-alias result
When building a projection path we _must_ ignore zero-indexing projections so that alias analysis
recognizes an "alias" between two addresses where one has such an `index_addr 0` instruction and the other doesn't.
2022-04-13 09:47:28 +02:00
Andrew Trick
0f428c2c06 alias-analysis test 2020-10-16 15:00:10 -07:00