Static Analysis


  • lexical :: every inner level can access its outer levels - widely accepted to be the correct scoping decision.
  • dynamic :: functions access the latest definition of a local variable - not deducible at compile time level. This means that for some f wth the body x = 3, call g, g has x = 3 in scope.

from "history of t"

[]some of these notes are prompted by this

intro functional languages: rabbit (first scheme compiler), sussman/steele lambda papers, FP languages su ch as Hope, Miranda and Scheme. franz lisp? Bliss language - c-level language from CMU?

pdp-10 hack: remove cons cell from freelist, updated freelist, and branching if the freelist was exhauste d to the gc in a single instruction!

premature optimization is bad, no matter what. do not take shortcuts to simplify what is an already well- designed system! One key tip-off phrase is always something of the form, "We'll throw out all the old cru ft, start over fresh, and just Do Things Right."

fixnum :: a 'fixed number', or native machine word building a compiler 'self-hosted', or incrementally -- hosting one in another. how is it done?

maclisp on -10 has mark and sweep run on the register set - "bibop" scheme with all objects boxed, and se gregated by type into pages of memory stop and copy garbage collector: Cheney garbage collection algorithm - does bfs of heap to find everythin g. t used Clark algorithm: dfs traversal, uses heap to provide a search stack

can implement mark and sweep with same costs as stop and copy! norman ramsey

'good' schemes use a range of implementations for lambas. depending on what we know about them at compile time. some turn into nothing, some are control flow, some are stack frames, some cause heap allocation. must understand how compiler handles everything, and scheme is built on this lambda structure

lexemes :: construction of lexical meaning underlying words related through inflection. the lemma is one forn of the lexeme standard procedure :: standardized code for a procedure? TODO

compiler implementation as a tree of objects that could link back to their parents? whoah


these things are relatively communicative but i am not sure what they mean

DFA :: data-flow analysis - ? loop-invariant hoisting :: - ?

global register allocation :: - ? global common subexpression elimination :: - ? find two things that are alpha-equivalent then make them a single expression

copy propagation :: - ? induction-variable elimination :: - ?

learn how to do more things with computer graphics! this area sounds super interesting but i do not know much about it.

assemblers :: norman adams. graph structure? linear text scheme? serializing graph to minimize the span f rom jmps to the things they jump to. push and pop vs push and a generational garbage collector

assemblers :: norman adams. graph structure? linear text scheme? serializing graph to minimize the span f rom jmps to the things they jump to.

push and pop vs push and a generational garbage collector

beta-substitution :: - ?

four classic analyses:

  • go over programs forwards and backwards
  • unions and intersections
  • - union, intersection = always, might_possibly

keywords to google

  • available expressiosn
  • - forwards intersection
  • very busy expressions
  • - backwards intersection
  • reaching definitions
  • - forwards union
  • live variables
  • - backwards union

specific optimizations

  • dead code elimination :: removes code not impacting program results. this shrinks program size and avoids irrelevant operations. this involves code that will never be executed and code that only effects dead variables -- those that are nedver read from again. we can use this as opposed to optional code inclusion via a preprocessor that would perform the same task. much of the dead code this finds is created by other transformations: for example, strength reduction -- we must ensure that the order of analyses is performed in the right way. historically, this is performed using information derived from data-flow analysis with an algorithm based on single assignment form.
  • dynamic dead code elimination :: some code sections represent dead or unreachable code only under specific conditions. we can accumulate conditions at runtime to determine what processes or loadings to eliminate while we evaluate an expression.
  • strength reduction :: most of a program's execution time is spent in a small section of code (the 'hot spot') and that code is inside a loop over and over. the compiler looks to recognize things inside the loop. this records loop invariants: values that do not change within the body of the loop, and induction variables: values iterated each time through the loop. induction variables change by known amounts. we can replace multiplication with successive weaker additions often which is an optimization. we can hoist invariants outside of the loop, such as registers. these are some good examples of strength reduction that can be used: []
  • dataflow analysis :: gathering information about values calculated at points during a computer program. set up dataflow equations for each node of the cfg, then solve them by repeatedly calculating the output from the input, locally at each node until a fixpoint is reached -- kildall's method. []

basic blocks :: - ?

dynamic software updating :: - ?

hot patching :: - ?

maurice wilkes -- helped build the electronic delay storage automatic calculator -- cool guy

[Loop-invariant code motion - Wikipedia]

[Improve Software Debugging with Binary Analysis | some guy’s blog]

[Program analysis resources]


  • parametric polymorphism :: allows a function or data type to be written generically so that it can handle values identically without depending on their type these are generic functions, generic datatypes respectively. type of 'append' is generic but is *parameratized* with types rank 1.
  • polymorphism :: type variables cannot be instantiated with polymorphic types.
  • rank k polymorphism :: rank k polymorphism enforces that the quantifier may not appear ot the left of k or more arrows type inference is decidable for rank 2, but not for rank 3 or above
  • rank-n polymorphism :: polymorphism in which quantifiers can appear to the left of arbitrarily many arrows
2022-11-01 58a9b56
2022-11-01 b0115e4
2021-09-22 52a677b
2021-09-21 7732812
2021-08-19 87d9551
2021-05-26 005a0c7
2021-02-26 9ac6ea5
2021-02-25 8d94bb1
2021-02-25 247b36c
2021-01-20 35e386e
2020-11-15 a0eccac