Stack Safety Analysis documentation

[vitalybuka]

Summary

Basic documentation of the Stack Safety Analysis.
It will be improved during review and upstream of an implementation.

[vlad.tsyrklevich]

I sent you my StackSafetyAnalysis.rst edits over e-mail because the s/// format got tricky.

llvm/docs/Passes.rst

365

s/analysis/analysis'/
s/it/is to/

llvm/docs/index.rst

443

s/design/the design/
s/stack/the stack/

[vitalybuka]

In D53336#1266890, @vlad.tsyrklevich wrote:

I sent you my StackSafetyAnalysis.rst edits over e-mail because the s/// format got tricky.

Thank you. Done.

[vitalybuka]

apply edits of @vlad.tsyrklevich

[vlad.tsyrklevich]

llvm/docs/StackSafetyAnalysis.rst

13

Oops: s/ofscope/of-scope/

[kcc]

llvm/docs/StackSafetyAnalysis.rst

14

I'd like to see the use-of-uninitialized-memory mentioned here explicitly as well, and treated as one of the primary design goals.

[eugenis]

llvm/docs/Passes.rst

363

I think we should distinguish the analysis itself which simply lets you query safety of variables, and the wrapper pass that sets the metadata. The primary usage mode of this thing should be by query, not by metadata IMHO.

[vlad.tsyrklevich]

llvm/docs/Passes.rst

363

I just wanted to chime in and say that in the ThinLTO case I think we have to annotate allocas with metadata since the global analysis has to run before any transformations occur. That said, the interface can be as you said where we just hide the logic to check metadata or otherwise run the analysis.

[vitalybuka]

+use-of-uninitialized-memory

[vitalybuka]

Removed reference to !stack-safety

[vitalybuka]

Fix quotes

llvm/docs/Passes.rst

 
 This differs from traditional loop dependence analysis in that it tests for
 dependencies within a single iteration of a loop, rather than dependencies
 between different iterations.
 
 ``ScalarEvolution`` has a more complete understanding of pointer arithmetic
 than ``BasicAliasAnalysis``' collection of ad-hoc analyses.
 
+``-stack-safety``: Stack Safety Analysis
+------------------------------------------------
+
+The ``StackSafety`` analysis can be used to determine if stack allocated
+variables can be considered safe from memory access bugs.
+
+This analysis' primary purpose is to be used by sanitizers to avoid unnecessary
+instrumentation of safe variables.
+
 ``-targetdata``: Target Data Layout
 -----------------------------------
 
 Provides other passes access to information on how the size and alignment
 required by the target ABI for various data types.
 
 Transform Passes
 ================

llvm/docs/StackSafetyAnalysis.rst

+==================================
+Stack Safety Analysis
+==================================
+
+
+Introduction
+============
+
+The Stack Safety Analysis determines if stack allocated variables can be
+considered 'safe' from memory access bugs.
+
+The primary purpose of the analysis is to be used by sanitizers to avoid
+unnecessary instrumentation of 'safe' variables. SafeStack is going to be the
+first user.
+
+'safe' variables can be defined as variables that can not be used out-of-scope
+(e.g. use-after-return) or accessed out of bounds. In the future it can be
+extended to track other variable properties. E.g. we plan to extend
+implementation with a check to make sure that variable is always initialized
+before every read to optimize use-of-uninitialized-memory checks.
+
+How it works
+============
+
+The analysis is implemented in two stages:
+
+The intra-procedural, or 'local', stage performs a depth-first search inside
+functions to collect all uses of each alloca, including loads/stores and uses as
+arguments functions. After this stage we know which parts of the alloca are used
+by functions itself but we don't know what happens after it is passed as
+an argument to another function.
+
+The inter-procedural, or 'global', stage, resolves what happens to allocas after
+they are passed as function arguments. This stage performs a depth-first search
+on function calls inside a single module and propagates allocas usage through
+functions calls.
+
+When used with ThinLTO, the global stage performs a whole program analysis over
+the Module Summary Index.
+
+Testing
+=======
+
+The analysis is covered with lit tests.
+
+We expect that users can tolerate false classification of variables as
+'unsafe' when in-fact it's 'safe'. This may lead to inefficient code. However, we
+can’t accept false 'safe' classification which may cause sanitizers to miss actual
+bugs in instrumented code. To avoid that we want additional validation tool.
+
+AddressSanitizer may help with this validation. We can instrument all variables
+as usual but additionally store stack-safe information in the
+``ASanStackVariableDescription``. Then if AddressSanitizer detects a bug on
+a 'safe' variable we can produce an additional report to let the user know that
+probably Stack Safety Analysis failed and we should check for a bug in the
+compiler.
+

llvm/docs/index.rst

.. toctree::
    Coroutines
    GlobalISel
    XRay
    XRayExample
    XRayFDRFormat
    PDB/index
    CFIVerify
    SpeculativeLoadHardening
+   StackSafetyAnalysis
 
 :doc:`WritingAnLLVMPass`
    Information on how to write LLVM transformations and analyses.
 
 :doc:`WritingAnLLVMBackend`
    Information on how to write LLVM backends for machine targets.
 
 :doc:`CodeGenerator`
:doc:`The Microsoft PDB File Format <PDB/index>`
   A detailed description of the Microsoft PDB (Program Database) file format.
 
 :doc:`CFIVerify`
   A description of the verification tool for Control Flow Integrity.
 
 :doc:`SpeculativeLoadHardening`
   A description of the Speculative Load Hardening mitigation for Spectre v1.
 
+:doc:`StackSafetyAnalysis`
+  This document describes the design of the stack safety analysis of local
+  variables.
+
 Development Process Documentation
 =================================
 
 Information about LLVM's development process.
 
 .. toctree::
    :hidden: