PL Seminar

["Rastislav Bodik" <bodik@xxxxxxxxxxx>]

When:	Thursday, June 8, 4pm
Where:	cs2310

What:	ABCD: Eliminating Array Bounds Checks on Demand
Why:	a PLDI practice talk
Who:	Ras Bodik   (joint work with Rajiv Gupta and Vivek Sarkar)

Abstract:

  To guarantee typesafe execution, Java programs check each array
  access for array-bounds violations, incurring a performance penalty.
  Although the compiler can prove that some bounds checks will never
  fail, it is not allowed to remove them from the (typesafe) bytecode.
  This restriction effectively confines any bounds-check optimization
  into the run-time setting, for which the existing bounds-check
  optimizers are too heavy-weight.
  
  This talk will present ABCD, a light-weight bounds-check optimizer
  suitable for dynamic optimization.  ABCD is simple: it represents
  program constraints by adding just a few edges to the standard SSA
  value graph.  ABCD is efficient: it finds redundant checks via a
  simple traversal of the extended SSA graph.  ABCD is demand-driven:
  it can reduce optimization cost by targeting only the frequently
  executed checks.  Despite its simplicity, ABCD is surprisingly
  powerful. On our benchmarks, ABCD removes on average 45% of dynamic
  bounds checks.