[stack-safety] Analysis documentation
Summary:
Basic documentation of the Stack Safety Analysis.
It will be improved during review and upstream of an implementation.
Reviewers: kcc, eugenis, vlad.tsyrklevich, glider
Reviewed By: vlad.tsyrklevich
Subscribers: arphaman, llvm-commits
Differential Revision: https://reviews.llvm.org/D53336
llvm-svn: 347612
diff --git a/llvm/docs/Passes.rst b/llvm/docs/Passes.rst
index 9ab2149..9a1b417 100644
--- a/llvm/docs/Passes.rst
+++ b/llvm/docs/Passes.rst
@@ -355,6 +355,15 @@
``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
-----------------------------------
diff --git a/llvm/docs/StackSafetyAnalysis.rst b/llvm/docs/StackSafetyAnalysis.rst
new file mode 100644
index 0000000..07112dc
--- /dev/null
+++ b/llvm/docs/StackSafetyAnalysis.rst
@@ -0,0 +1,57 @@
+==================================
+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.
+
diff --git a/llvm/docs/index.rst b/llvm/docs/index.rst
index df70de0..b60dacc 100644
--- a/llvm/docs/index.rst
+++ b/llvm/docs/index.rst
@@ -302,6 +302,7 @@
PDB/index
CFIVerify
SpeculativeLoadHardening
+ StackSafetyAnalysis
:doc:`WritingAnLLVMPass`
Information on how to write LLVM transformations and analyses.
@@ -438,6 +439,10 @@
: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
=================================