• Escape_analysis

Please feel free to comment on absolutely anything at all. Anything marked (??) I don't really know much about, and would be very happy to hear comments/opinions about, or links to more information.

General

• Student: Paul Biggar
• Mentor: Daniel Berlin

• Abstract

• Full Application and Prototype

• References

  • OOPSLA99

  • rc22340

  • TOPLAS03

Progress So Far

• Implemented almost all of intraprocedural analysis on Java sample from the Choi papers

TODO list

High Priority (Must be done to progress further)

• Sort out copyright assignment
  • Sent off forms
• Propagate escape status (set to UNINIT, initially)
  • working on that now
    • Going to wait til ipa is done. Nearly there.
• Bypass any deferred edges (All nodes need to keep a target though, even if the edge is deferred)
• Do iteration properly

  • This one is put on the back burner. I could spend the summer making flow-sensitve right, and not get anything else done. Going with flow-insensitive for now.

  • For flow-sensitive analysis, I need to iterate over loops multiple times (probably around 10)
  • I also need to know the difference between a loop that can iterate 0-or-more times, and a loop that iterates 1-or-more times

    • Currently reading Chapter 12 of gcc-internals and this thread

  • From DB: Call loop_optimizer_init, and it will return array of current loops in the function

  • From DB: Can work out innermost loop a bb belongs to using bb->loop_father

  • From DB: estimate_number_of_iterations gives a 'conservatively correct estimate of the number of iterations in the loop'. Excellent
  • From DB: Zero-trip loops arent marked seperately, but could be
  • Before giving up, heres what I had: no point using loops, cause have to deal with complicated flow control that arent loops.
    • Could use loops as an improvment, esp. combined with estimating_number_of_iterations

    • basically, foreach_BB { foreach_edge { process_bb(edge->target) } }, with an iteration count in process_bb, and a dirty flag. Not quite good enough, but on the way

• How do I do interprocedural analysis?
  • This is mostly done. Moved the pass to ipa

    • (??)Strange bug that -O2 isnt sufficient. I also need -funit-at-a-time to make it run

  • Need to handle recursion (loops in the call graph)
    • Do I? Its mentioned in choi99. reread the ipa bit
  • Need to traverse the graph in reverse order
    • I get this for free
  • From DB: Otherwise can be done on ipa-branch
    • Interprocedural SSA doesnt run aliasing

      • The analysis will be available when it does, and I wont have to merge it

    • Way around this: do the full escape analysis on with interprocedural for stack replacement/sync removal; and the intra-procedural only for may_alias

      • Aha, but the ipa runs before all the other opts
      • Escape analysis is a tad sensitive on other opts, since it just slightly alters the code, and relies on its escape property not changing at a later stage.

• Set argEscape for parameters

  • This is bad/inaccurate, since they may not be actually used, and therefore could be noEscape but until interprocedural is set up, I cant tell

  • Except for constructors
  • Not going to do this, since I dont need it for ipa

Medium Priority (Must be done before finished)

• Test on big java projects. Probably on big C/C++ projects to check for side-effects
  • There seems to be a standard suite that Choi et al and Whalley/Rinard used

• (??) Where exactly do I put the analysis?

  • Before ipa_type_escape

  • Before each pass_may_alias()so it can fill in is_escape_site()

    • For speed, this could be intraprocedural only, (and maybe flow-insensitive)

      • (??) Benchmark to see differences in compile-time and run-time

  • Final pass at the end to do stack replacement

    • (??) Or can I trust the initial analysis results.

• (??) Figure out how to move the object onto the stack

• (??) Gracefully handle C++ and C aswell

• (??) Figure out whether intra-procedural is O² or worse. That could be annoying.

  • Look at the proof in the the TOPLAS paper, which suggests O³ to O⁶

• (??) A nice heuristic from DB: SSA vars arent allowed escape directly through function calls. They can only escape by being pointer vars, and being assigned to escaping vars that are also pointers.

  • Is this two ways to do that they can escape, or 1 way with 2 conditions.
  • Doesnt bother me really

Low Priority (Not part of the initial spec; do at a later date, if at all)

• Investigate using DEF-USE chains. Compare to iteration method.
• Investigate combining points-to with
• Read references from Sam Guyer's PLDI slides; see if they're relevant/useful
• How to integrate with call clobbering

Finished TODOs

High

• Add return nodes argEscape, and merge them all

• Correctly choose all memory allocations, not just _jv_alloc_no_finalizer

  • From DB: with a CALL_EXPR tree t, call_expr_flags(t) & (ECF_MALLOC || ECF_MAY_BE_ALLOCA)

    • Remember that nodes with finalizers are automatically globalEscape

    • Doesnt actualy work. DB is alerting the java maintainers

Medium

• Switch to SVN HEAD from release 4.1
• Switch to GNU style, and go through GCC and GNU coding guidelines

Low