►
From YouTube: Overview of Value Propagation Compiler Optimization
Description
Vijay Sundaresan gives an overview of the value propagation optimization in the OMR compiler. There are no slides, just useful information!
B
Yeah,
so
the
summary
of
the
value
propagation,
opt-in,
the
emergent
compiler.
So
what
is
value
propagation?
It's
one
of
our
most
powerful
ops.
It
does
several
optimizations
and
analyses
that
you
might
find
in
literature
all
at
once,
so
in
literature,
it's
kind
of
hard
to
find
something.
That's
literally
called
value
propagation.
Instead,
you
hear
references
to
type
propagation,
you'll,
see
references
to
constant
propagation
range,
propagation,
that
sort
of
stuff
and
VP
kind
of
combines
it
all
into
one
optimization
in
our
compiler.
B
So
our
value
propagation,
past
propagates
information
about
types
or
references,
it
propagates
information
about
ranges
of
values
that
a
particular
int
or
long
can
take
and
all
manner
of
other
information,
that's
considered
relevant
as
well.
So
a
couple
of
examples:
I
will
give
of
other
information
propagates
around
information
around
whether
an
object,
a
reference
is
now
or
not,
or
it's
possible
for
it
to
be
null
or
not.
The
novelist
information
is
one
other
piece.
That's
tracked.
B
If
it's
a
constant
string
object,
it
tracks
more
than
just
the
type.
Obviously,
the
type
is
Java
line
string
in
that
case,
but
if
it's
a
constant
string
attack
tracks
more
useful
information
like
what
is
the
constant
value
so
that
one
can
use
it
later
on.
If
there
are
operations
happening
on
that
constant
string,
the
constraint
comes
in
handy
there.
So
really
it's
several
apps
and
one
as
I
said,
and
so
it's
one
of
our
most
powerful
office,
not
the
most
powerful
lot
in
the
compiler.
B
There
are
several
ways
of
getting
into
the
basics,
so
let
me
start
with
the
prerequisites.
So
value
propagation,
as
the
name
suggests,
is
based
on
values
and
in
particular
this
notion
of
value
numbers,
which
is
a
well-known
analysis.
You
can
search
for
Google,
for
it
value
numbering
is
a
well-known
analysis
in
compiler
theory,
so
the
whole
value
propagation
framework
is
built
on
value
numbering
so
there's
a
prerequisite
that
every
opt
can
ask
for
certain
analyses
to
be
done
ahead
of
time
before
it
runs
now.
The
propagation
request
value
numbering
baton,
so
energy.
B
In
a
nutshell,
what
value
numbering
does
is
it
picks
sort
of
the
nodes
that
are
known
to
have
the
same
value,
probably
known,
to
have
the
same
value
and
assigns
them
the
same
value
number
note
that
two
values
that
may
be
the
same
need
not
always
have
the
same
value
number
it's
only
in
cases
that
it
can
prove
it
that
it
assigns
the
same
value
number.
So
if
two
values
are
different,
they
will
not
have
the
same
value.
Number
I
mean
that's
kind
of
a
very
intuitive
sense.
B
I'll
give
you
so
value
numbering
encompasses
kind
of
things
like
definitions
and
uses.
So
so,
if
you
take
a
value,
store
it
to
a
temporary
ys4
and
then
load
it
several
blocks
later,
it
is
capable
of
realizing
that
it's
the
same
value
flowing
through
all
those
areas.
So
it'll
give
the
same
value
number
to
the
right-hand
side
of
the
store.
It'll,
give
the
same
value
number
to
the
store
and
will
give
the
same
value
number
to
all
the
loads
that
are
fed
uniquely
by
that
store.
B
It's
neither
one
of
those
if
it
could
be
either
one
of
those
two
values,
so
you
cannot
give
it
either
one
of
those
values
you
give
it
another
unique
third
value
number,
basically,
that's
kind
of
what
happens
in
value
numbering
in
that
case.
So
that's
a
very
poor
man,
sort
of
very
high
level
way
of
talking
about
value
numbering,
but
you
can
read
this
here,
e
more
behind
it
in
a
book.
This
is
not
a
talk
on
value
numbering
its
value
propagation.
B
What
is
a
question
you
may
have
so
value
propagation
value,
propagation,
common
dot,
CVP
hold
much
of
the
sort
of
general
infrastructure
of
the
optimization,
so
things
like
how
to
how
to
merge
two
lists
of
constraints
and
how
to
even
iterate
over
the
trees
and
launch
analysis
of
each
node
in
each
tree
kind
of
all
that
infrastructural
stuff
to
drive
the
analysis
to
initialize
it
to
create
the
object.
The
value
propagation
object,
sits
and
value
propagation
value,
propagation,
common
dot,
CVP.
B
There
are
a
lot
of
routines
there
that
well
I,
don't
think
are
the
best
way
to
start
sort
of
reading
value
propagation
code,
because
there's
a
lot
of
similar-sounding
routines
there
that'll
confuse
you,
probably
the
better
way
to
I
think
get
into
the
code
is
through
VP
handlers
and
VP
constraint.
Those
are
two
other
files
that
are
easier
to
wrap
one's
head
around
VP
handlers
is
a
file
that
has
basically
routines
for
almost
all
the
opcodes.
B
In
particular,
the
supported
off
codes
from
a
VP
perspective,
where
we
do
something
special
for
each
opcode,
it's
recognized
and
something
is
done
for
it
all.
Those
routines
are
in
VP
handlers
or
CVP.
So
oftentimes,
you
give
you
an
example
like
you'll
see
a
routine
like
constrain,
bound
check
or
constrain
int
load
or
constraint
in
store
constrain
call.
These
are
all
routines,
but
really
there's
I
would
say
easily
dozens
of
routines.
B
Therefore,
the
many
op
codes
that
we
have
and
usually
they're
kind
of,
very,
very
specific,
so
they're
easier
to
read
and
wrap
one's
head
head
around
that
you
look
at
the
constraint
at,
for
example,
and
you
know
kind
of
it's
got
two
values
that
it
has
to
deal
with
and
it's
trying
to
add
those
two
values
and
trying
to
create
a
new
constraint
for
the
added
result.
Basically,
that's
what
you
expect
there.
B
If
you
have
a
constant
value
and
for
both
the
arguments
of
an
add,
it
will
recognize
that
again
and
it
will
say
here's
the
result
of
operating
on
two
constant
values.
This
add
can
be
folded
into
a
constant
as
well,
and
you
will
see
that
evaporation.
Take
place
in
in
in
VP
handlers
a
lot
a
lot
of
the
transformations
are
done
in
line
and
of
just
as
we're
analyzing
things.
B
The
other
file
for
this
VP
constraint
file
also
easy
to
navigate,
especially
if
you
look
at
the
HVP
start
at
the
HVP.
Is
it
lists
all
the
constraint
classes?
So
that's
the
fundamental
sort
of
object,
that's
flown
around
or
flowed
around
by
the
analysis
itself.
So
when
it
looks
at
a
node,
looks
at
its
value
number
and
says:
hey.
This
is
a
let's
say:
picker
and
an
OP
cordial
icon
store
something
there's
an
icon
snowed
here.
It
has
a
certain
value
number.
Let
me
create
an
INT
constraint
for
it,
which.
C
B
A
const
constraint
and
the
value
of
the
constant
is
5,
so
it'll
put
that
into
the
constraint
object.
It
will
associate
that
constraint
with
the
value
number
of
the
node
and
it'll
say.
I
have
seen
this
node
I've
seen
this
value
number
its
value
is
blah
represented
by
the
constraint
and
so
the
next
time
you
see
that
same
value
number.
B
You
can
use
that
constraint
that
flowed
through
to
that
point
so
to
expand
on
that
particular
example
a
bit
more
if
you
have
a
store
which
has
a
Const
I've
on
the
right-hand
side
and
then
a
load
that
is
fed
by
that
store,
then,
when
you
get
to
the
load,
which
is
not
a
constant,
you
can
look
at
the
constraint
associated
with
that
value.
Number
it'll
be
the
same
value
number
as
the
store,
which
will
be
the
same
value
number
as
the
right
hand,
side,
which
was
the
Const.
B
B
Essentially
you
can
have
X,
plus
five
and
say
Y,
plus
five,
where
x
and
y
are
known
to
be
equal
over
a
particular
range
and
X
plus
five
will
have
the
same
value
number
as
y
plus
five.
So
that's
another
thing
to
keep
in
mind
that
this
is
not
just
all
trivial
sort
of
used,
F
chains
and
parent-child
sort
of
things
as
well.
It
is
it
does.
It
is
more
powerful
than
that
you
can
have
different
nodes,
have
the
same
value
number?
B
No,
that
don't
particularly
look
alike
having
the
same
value
number
so
so
yeah
easier
to
start
in
VP
handlers
and
VP
constraint
for
sure.
Once
you
wrap
your
head
around
that
your
curiosity
will
be
peaked
anyway
and
that
you
will
see
some
things
there.
That
will
probably
drive
you
into
the
more
complex
infrastructural
pieces
that
I
talked
about.
Are
there
in
value
propagation,
not
CVP?
So
in?
Let's,
let's
see
what
you
might
be
curious
about.
If
you
look
at
the
constraint
classes,
every
constraint
will
have
a
routine
called
intersect.
B
It'll
have
a
routine
called
merge,
so
these
are
good
concepts
to
kind
of
realize.
First,
so
an
intersect
routine
or
an
intersect
operation
on
a
constraint
basically
makes
the
constraint
more
more
refined.
So
it
makes
a
constraint
better.
So
an
example
is,
if
you
came
in
to
an
if,
knowing
that
X
is
less
than
10
and
if
was
if
X
less
than
5,
then
going
past
that
if
you
can
refine
the
constraint
on
X,
you
can
say
I
used
to
know
that
it
was
between
minute
and
10.
B
Now
that
I've
seen
X
less
than
5
I
can
change
that
to
minute
to
5
instead
and
the
way
that
happens
is
kind
of
based
on
taking
your
original
constraint
and
intersecting
it
with
the
with
with
one
of
with
the
new
operation.
That's
going
on
right
now.
The
operation
that
you're
analyzing
and
as
a
result
of
the
intersection
is
a
better
constraint
or
more
refined
constraint
that
comes
out.
B
So
an
intersection
is
done,
sort
of
as
you're
going
along.
So
it's
almost
like
a
straight
line
thing.
You
can
imagine
you
start
out
with
some
information
and
future
intersections
on
top
of
that
initial
information
that
you
had
initial
constraint
that
you
had
are
only
making
it
either
better
or
keeping
it
at
the
level
that
it
was
to
begin
with.
B
If
you
didn't,
learn
anything
new
and
the
original
one
stays
so,
but
but
it's
the
way
that
you
learn
progressively
as
you
go
along
a
merge
operation,
on
the
other
hand,
is
invariably
headed
in
the
opposite
direction.
So
it's
the
result
of
a
merge
can't
be
better
than
what
you've
started
with
it
can
only
be
worse
or
the
same
as
what
you
started.
B
A
typical
example
of
when
a
merge
operation
is
done
is
when
there
is
a
control
flow,
join
point,
for
example,
so
that
if
then
else
example,
let's
say
you
knew
that
he
was
assigned
five
on
one
side.
He
was
assigned
10
on
the
other
side,
and
then
you
merged
and
came
back
to
a
single
point
in
the
control
flow.
Well,
at
that
point
you
know
that
T
could
either
be
5
or
it
could
be
10
so
kind
of
that's
the
general
sense
I'll
give
you
four
how
merge
works?
It's
like
you.
B
You
have
a
something
known
on
one
side,
for
a
value
number,
something
known
on
the
other
side
for
a
value
number
and
you
combine
those
two
together
to
form
a
larger
range
and
then
propagate
that
forward,
so
they're
opposites
in
a
sense
intersects
only
improved
constraints.
Merge
only
makes
them
sort
of
less
specific,
so
more
general
in.
B
Yeah
they're
mostly
only
used
in
that
context,
trying
to
remember
if
there
is
any
other
use
case
for
it
and
I,
don't
I,
don't
think
there
is
so
the
things
like
back
edges
and
yeah
just
like.
If
you
have
multiple
definitions
of
a
load,
imagine
that
you
would
go
through
all
the
definitions
and
look
at
all
the
constraints
that
you
know
about
for
the
definitions
and
merge
them
all
together
and
say:
the
merged
value
is
what
I
about
a
load
or
a
use.
That
is
bad
by
that
definition.
B
Okay,
I'm,
so
that's
a
good
question.
There
is
a
notion
if
you
look
in
the
VP
constraint,
without
HPP
you'll
find
upwards
of
a
dozen
class
constraint
classes.
There
is
a
notion
of
a
merged
constraint
in
that
as
well.
So
there's
a
TR,
VP
merged
constraint
and
a
VP
merged
constraint
would
actually
is
a
is
a
set
of
ranges.
So
in
that
case
you
could
express
it
as
five
comma
10,
you
don't
have
to
say
5.10.
So
it's
not
saying
that
there
is
the
range
is
five
to
ten.
B
You
are
able
to
express
why
I
merge
constrain,
that
it
is
two
distinct
ranges
where
the
ranges
are
really
constant,
so
so
yeah,
but
but
you
only
can
access
those
multiple
ranges.
If
you
downcast
the
constraint
into
emerged
constraint,
if
you
just
looked
at
the
merged
constraint
as
it
is,
in
fact
all
of
the
int
and
long
constraints
have
particular
API
is
that
they
answer
to
like
get
low
and
get
high
so
get
low
means.
B
What's
the
low
range
of
the
value
that
you
have
I'm
is:
what's
the
high
range
of
the
value
that
you
have
now?
That's
a
general
API
that
you
can
call
on
any
in
constraint.
However,
there
are
specific
int
where
you
can
go
beyond
right,
like
if
the
constant
I
know
that
low
is
the
same
as
high
without
necessarily
even
calling
low
and
high
and
then
checking
the
value.
There
is
an
inter
constants
trained
class
that
you
can
just
use
to
say.
Are
you?
Are
you
one
of
these?
B
In
which
case
you
are
a
constant,
similarly
for
the
range
that
you
talked
about
like
if
you
say,
if
you
didn't
downcast
it
or
if
you
weren't
aware
of
the
fact
that
there
are
multiple
ranges
here,
you
can
call
get
low
on
the
merge,
constrain.
It'll
give
you
five,
you
can
say,
get
high
on
the
merge
constraint.
It'll
give
you
ten
and
and
you
you
could
be
misled
into
believing
that
the
value
is
five
to
ten,
which
is
still
correct.
B
I
mean
it's
conservatively
correct,
it's
just
not
accurate
or
not
as
accurate
as
it
could
have
been
so
the
better
option.
There
is
to
be
aware
that
you
may
be
dealing
with
a
merged
constraint
and
if
you
are
then
ask
that
question
and
get
the
different
ranges
and
look
at
the
ranges
individually
for
low
and
high
as
well,
that
make
sense,
yeah
so
same
sort
of
thing.
So
so
there
are
int
classes
of
constraints,
there's
long
constrained
classes
as
well
there.
B
Basically,
as
the
name
suggests
there
for
those
data
types,
the
address
constraint
types
get
more
complex.
So
there's
a
as
I
said
at
the
outset.
There's
many
different
kinds
of
information.
You
could
flow
about
a
reference
value.
One
is
so
you'll
see
something
called
VP
fixed
class,
a
VP
resolves
class
VP
unresolved
class.
So
when
you
have
an
a
value
you
it's
possible
to
express
the
type
in
a
different
sort
of
terms.
One
way
to
express
it
is
I
know
it's
definitely
this
type,
because
I've
seen
the
allocation,
for
example
and
I'm.
B
There's,
no
doubt
I
know
it's
of
type
T,
so
that
fact
is
expressed
through
what
is
called
a
fixed
class,
meaning
it's
a
T,
and
only
is
he
not
a
subclass
is
not
possible.
Resolved
class
constraints,
on
the
other
hand,
could
say
I'm
a
result,
class
type
constraint
off
type
T
and
that
merely
means
that
it's
a
tea
or
a
subclass
of
T.
That's
all
you
know,
you
don't
know
it's
precisely
a
object,
so
result.
Class
constrain,
for
example,
could
be
created
if
you
are
doing
a
cast.
If.
C
B
Did
a
cast
or
an
instance
off
after
that
point,
you
know
that
it's
in
this
hierarchy,
because
we've
just
checked,
are
you
an
instance
of
T?
But
if
there
are
many
subclasses
of
T,
the
instance
off
doesn't
tell
you
anything
about
which
subclass
of
T
it
actually
is,
but
you
still
did
learn
something
from
the
instance
of
it.
Earlier
than
that,
all
you
may
have
known
was.
It
was
an
object,
but
now
you
know
that
it's
at
least
a
team,
and
that
fact
can
be
used
useful
on
occasions
as
well.
B
To
do
it,
maybe
there's
another
type
check
on
T
somewhere
downstream,
and
we
can
eliminate
that,
for
example,
an
unresolved
class
constraint
is
just
saying:
it's
unresolved,
I,
don't
have
a
class
for
this
value
right
now.
It
may
need
to
be
loaded
at
runtime,
but
I'll
tell
you
what
the
name
of
the
type
is,
so
it
just
kind
of
flows
around
a
constant
pool.
B
Entry
in
essence,
which
is
really
a
string
in
the
class
that
is
flowing
around
representing
the
name
of
the
unresolved
class
pipe,
is,
is
one
type
of
information
for
a
reference.
Then
there's
null
Nisour
not
null
or
not,
which
is
represented
through
VP
non
null
and
VP
null
constraint,
classes,
and-
and
there
are
other
things
as
I
said
at
the
outset-
the
example
I
used.
Is
it
a
constant
string
if
it
is
a
constant
ring?
What
are
the
values
associated
with
it?
B
Is
it
a
type
that
is
known
to
pre
exist
this
method,
meaning
the
type
was
loaded
guaranteed
before
you
entered
this
method
up,
so
there's
a
bunch
of
different
sort
of
constraint,
classes
that
represent
different
properties.
Now,
one
class,
one
constraint
class
that
you
should
be
aware
of
special
in
a
sense,
is
the
VP
class
constraint
not
particularly
well
named
because
really
sound
all
that
exciting.
But
really,
if
you
look
at
the
VP
class
constraint,.
B
You'll
have
several
fields
in
it,
one
for
type
info,
one
for
nominal
sinful
one
for
this
or
that,
so
all
those
disparate
types
of
information
you
can
propagate
for
a
reference
they're
all
sort
of
collected
together.
If
you
will,
in
this
VP
class
constraint
book,
if
you
know
that
an
object
is
of
type
T
and
na
now,
you'll
need
to
create
a
VP
class
and
strain
for
it
to
store
those
two
distinct
pieces
of
information
in
one
place
right,
rather
than
just
separately
flow,
a
constraint
for
type
and
separately
flow,
a
constraint
for
the
nullus.
B
B
B
All
right,
so
that's
a
good
point.
So
one
of
the
so
when
I
said
that
value
numbering
happens
before
the
is
done
so
value
numbering
analysis
is
done.
It
associates
a
value
number
with
each
node
and
there's
a
sort
of
data
structure
created
for
number
info.
That
is,
that
is
around.
It's
hung
off
of
the
compilation,
object
or
the
optimizer
object.
I
forget
some
off
somewhere.
B
Now,
as
we
are
doing
the
optimization
value
propagation,
we
are
not
updating
the
value
number
in,
so
it
is
what
it
is
to
begin
with.
So
we
have
to
be
a
little
bit
careful
because
in
some
cases
we
are
doing
transformations
in
certain
scenarios.
We
will
end
up
changing
the
trees
ourselves
right
as
we
are
doing
the
optimization.
B
So
you
don't
want
to
change
the
tree.
Add
a
new
node,
for
example,
which
didn't
have
a
representative
in
the
value
number
info.
That
was
computed
upfront,
because
if
you
did,
then
you
may
value
propagation
can
iterate
around
a
loop.
For
example,
it
may
analyze
a
single
block
more
than
once
so,
let's
say
you
went
through
the
block.
The
first
time
you
created
a
bunch
of
nodes
that
are
new
at
that
point
that
were
not
represented
in
the
value
numbering.
B
Then
you
came
around
and
analyzed
that
same
block
a
second
time
now
you
have
in
your
hands
a
node
which
doesn't
have
any
value.
Numbering
and
I
would
hop
the
analysis
or
that's
not.
That's
not
good.
It
expects
every
node
to
every
relevant
note
to
have
been
sort
of
tracked
through
value
numbering
and
having
a
representative
there.
So
there
are
certain
transformations
that
are
quite
trivial,
for
example,
going
and
removing
a
null
check,
for
example,
because
you
can
prove
that
the
object
is
not
now.
B
To
start
with
is
changing
systems
ordered
a
copy
calls
into
our
own
il
representation,
which
is
an
opcode
called
array
copy,
so
that
is
done
in
value,
propagation
and
I.
Don't
think
we
should
linger
on
the
reasons
why
that's
suitable
to
do
in
value
propagation.
Suffice
to
say
that
all
the
context,
information
that's
available
in
value
propagation
from
all
the
constraints,
makes
it
practically
the
best
place
to
do
that
transformation,
but
creating
an
array
copy
node
is
obviously
a
quite
a
drastic
step.
B
We
are
expanding
out
what
was
one
tree
into
potentially
multiple
trees,
representing
various
checks
that
have
to
be
done
like
if
you
look
at
the
system,
dot
array
copy
API,
for
example,
all
sorts
of
exceptions
can
come
out
of
system,
dot
array
copy,
UNIX
out
of
bounds,
null
pointer
exceptions.
I
could
mismatch
this
or
that
right.
So
it's
actually
quite
a
complex
operation
represented
by
the
call,
and
our
operation
is
broken
down
into
individual
steps
when
we
lower
it
into
our
own
opcode.
B
So
there's
the
array
copy
tree
itself,
but
before
it
goes
a
host
of
checks
that
need
to
be
done
in
order
to
safely
do
an
array
copy
if
all
those
checks
pass
so
yeah,
so
we're
creating
nodes
in
numbers
there,
who's
going
to
assign
value
numbers
to
those
num
nodes,
one
answer
as
well
just
give
them
a
new
value
number
that
doesn't
match
anything
else
and
get
on
with
life.
We
could
have
done
that
possibly
would
have
even
been
a
better
option.
I
won't
use
this
opportunity
to
get
into
the
pros
and
cons
of
it.
B
What
we
did
do
for
those
kinds
of
non-trivial
transformations,
we
have
deferred
transformation,
steps
so
to
speak,
so
value
propagation,
says
I'll,
just
add
the
system
array
copy
call
to
a
list
and
we
will
process
the
list
once
we've
completed
the
analysis
of
every
block
for
the
last
time.
So
once
we
are
done
with
the
analysis,
completely
a
queue
of
transformations
has
been
set
up.
You
go
and
process
the
queue
of
transformations
and
do
whatever
transformation.
You
need
it's
all
safe
at
that
point,
because
nobody
is
looking
at
value
numbers
anymore.
B
B
I
know
what
to
do
in
process
them
one
by
one
and
does
whatever
needs
to
be
done.
So
so
that's
a
subtle
point.
You
might
be
wondering
why,
starting
to
a
list
in
the
middle
of
this
handler,
why
can't
it
just
do
the
transformation
and
because
of
this
more
subtle
unfortunate
issue
with
not
having
the
ability
to
just
spontaneously
mock
up
value
numbers
as
we're
going
along
for
new
nodes?
B
What
else
are
so
so?
Maybe
we
should
walk
through
the
flow
of
how
things
run
so
that
you
have
a
better
idea
of
that
as
well,
so
propagation
itself
can
be
run
in
two
different
modes.
The
important
ilvl
point
the
code
base
is
shared
across
these
two
modes,
so
there's
local
value,
propagation
and
there's
global
propagation.
C
B
You
look
at
the
cpp
files,
the
core
value,
propagation
CVD
files.
You
will
see
separate,
perform,
routines,
140,
r-value
propagation
phone
perform
and
140
our
local
value
propagation,
full
moon
perform,
but
they're,
both
as
I
say,
they're
derived
out
of
the
same
base
class.
They
share
all
of
the
handlers
they
share
all
of
the
constraint
code.
B
The
the
limitation
of
local
VP
is
that
it
will
forget
all
the
constraints
that
it
knows
about
once
it's
done
with
its
unit,
which
is
a
one
block
or
one
extended
block,
depending
on
where
you
are
there's
no
constraints
flowing
in
at
the
start
of
its
unit
of
work.
So
you
only
know
what
you
know
from
analyzing
that
one
block
that's
obviously
less
powerful
than
global
value
propagation,
which
does
transmit
constraints
across
block
boundaries,
as
the
name
suggests
its
global
in
scope.
That
means,
of
course,
in
a
JIT
context.
B
Whenever
we
say
the
word
global,
it
means
within
one
compilation,
scope,
there's
no
notion
of
a
cross
compilation,
scope,
nothing
is
propagated
there,
but
global
is
across
basic
blocks
in
the
methods
that
you're
compiling
you
have
information
being
propagated
across
blocks,
so
in
in
the
in
case
of
local
value
propagation.
You
don't
even
really
need
to
do
value
numbering
as
such,
because
within
a
block
the
identity
of
a
node
is
well
established.
You
don't
need
to
say,
assign
value
numbers.
Local
CSC
will
common
up
different
accesses.
B
That
are
to
the
same
thing,
and
you
will
have
one
node
in
a
representing
particular
value
within
a
block
anyway,
if
it's
just
repeated,
if
you
load
X
twice,
there's
no
store
of
X
in
between
local
CC
would
have
common
that
up
to
a
single
load
of
X
anyway.
So
so
you
just
use
node
identity.
That's
your
value
number
in
local
value,
number
local
value,
propagation,
the
the
get
value
number
API
essentially
is
just
a
sham,
is
in
local
value
propagation,
if
you
say
get
value
number
all
it
does.
B
Let
me
give
you
the
nodes
global
index,
which
is
just
a
field
sitting
on
the
node,
is
returns
that
so
very
cheap
to
run,
which
is
why
it
exists.
It
is
run
several
times
on
even
at
cold.
It
is
run
I,
think
more
than
once
definitely
run
more
than
once
at
warm
global
value.
Propagation,
on
the
other
hand,
requires
a
global
analysis.
It
requires
used.
F
requires
global
value
numbering
and
then
it
itself,
of
course,
is
accumulating
constraints
as
it's
going
along
through
the
method,
because
it's
propagating
across
blocks.
B
So
some
of
the
constrained
lists
can
be
quite
long.
Some
of
the
operations
therefore
can
take
more
time
because
you
have
to
you
say,
find
me
the
entry,
the
constraint
for
this
value
number
in
your
current
list
of
value
number.
Well,
there's
ten
thousand
valid
numbers
that
you're
carrying
constraints
around
for
at
a
given
time.
B
Let's
say
you
have
to
go
through
that
list
and
find
your
entry
and
pull
it
out
and
then
use
it,
whereas
within
a
block
when
local
value
propagation,
maybe
you
only
have
a
hundred
entries
flying
around
so
easier
to
just
find
your
entry,
so
everything
is
faster
in
local
value
prop,
but
also
it's
not
as
effective
as
as
global
is.
But,
as
I
said,
the
handlers
are
all
using
the
same
code.
B
The
only
traces
of
global
versus
local
you
will
find
are
in
a
couple
of
queries
that
are
don't
even
make
it
all
that
there
aren't
in
your
face.
A
large
majority
of
the
code
is
not
actually
dealing
with
global
versus
local
in
places
like
PP
handlers.
You'll
find
the
odd
reference
to
it's
like
underscore
is
global
or
something
is
the
name
of
the
check
that
you'll
see
from
time
to
time.
B
But
it's
by
no
means
littered
all
over
the
place
most
of
the
time
the
operation
you
need
to
do
is
it
is
what
it
is,
whether
it's
global
or
local.
You
just
look
at
the
constraints
and
you
do
what
you
have
to
do
doesn't
matter
where,
where
they
came
from,
but
there
are
occasions
in
which
you
need
to
recognize
if
you're,
in
global
or
local
and
there's
a
check
for
that
loops
are
handled
specially
in
global
value,
propagation.
C
C
B
Unfortunately,
I
do
have
to
talk
about
I
feel
even
in
the
first
presentation
on
it,
which
is
this
notion
of
store
constraints
versus
normal
constraints,
and
what's
the
best
way
to
talk
about
it,
so
so
value
prop
as
a
whole.
If
it
doesn't
know
something
about
a
particular
value,
it
doesn't
create
a
constraint
for
it.
So
the
lack
of
a
constraint
means
that
you
don't
know
something
about
a
particular
value
number.
That's
the
convention
used
in
value
no
value
propagation.
B
This
saves
some
memory
as
you're
going
along.
You
don't
need
a
constraint
that
says
no,
nothing
right,
that
you
don't
need
to
allocate
a
constraint
to
new
nothing.
It's
just
implied,
however,
for
stores,
because
you
could
be
dealing
with
loops,
you
may
not
have
analyzed
all
the
stores
that
could
feed
a
particular
load
when
you
hit
the
load,
so,
let's
say
you're
walking
forward
through
the
trees,
as
the
analyses
do
even
global
or
local.
B
B
Don't
fold
this
away
right
now,
because
you
there
are
deaths
that
are
unseen
at
this
point,
so
it
uses
the
fact
that
a
store
constraint
for
I
plus
plus
hasn't
even
been
seen
yet
as
a
sign
that
I
hasn't
analyzed
it
yet
so
so
for
stores,
even
if
you
know
absolutely
nothing
about
the
value
of
the
store.
So,
even
if
I
pass
plus
said,
I.
C
B
Just
have
no
idea
what
this
resulting
value
is.
It
could
be
min
inch
to
maxint
any
value
in
between.
You
still
generate
a
store
constraint
for
that
store,
saying,
I
know
nothing
which
is
kind
of
what
we
were
trying
to
avoid
in
the
general
case,
just
to
represent
the
fact
that
yes,
I
have
seen
that
store
and
I
have
analyzed
it,
and
so
you
can
sort
of
take
into
account
the
fact
that
it
has
a
null
constraint.
B
It
means
I,
know
nothing
and
you
have
to
make
the
load
conservatively,
no,
nothing
as
well
at
that
point.
So
this
is
a
point
that
very
likely
is
too
subtle
for
this
stage
in
the
discussion,
but
I
I'll
say
it
one
more
time
and
then
move
on
from
it
is
the
presence
of
a
store
like
the
fact
that
you've
analyzed
it
or
not
needs
to
be
flagged,
and
it
cannot
be
flagged.
B
If,
if
you
have,
this
notion
of
the
constraint,
may
not
even
exist
if
I
know
nothing
about
the
value,
even
if
you
know
nothing
about
the
value,
whether
you've
seen
the
store
or
not
needs
to
be
flagged
to
the
analysis
and
if
you're
interested
in,
why
that
is,
we
can
talk
about
that
offline.
So
this
is
why
you
will
see
store
constraints
being
talked
about
in
the
value
propagation,
CVP
and
common
CBP
dot.
B
C
B
Five
is
an
example
of
an
absolute
constraint
saying
that
this
reference
is
a
knew
of
this
type
is
an
absolute
constraint
even
saying
that
I,
this
I
is
in
the
range
five
to
ten
is
an
absolute
constraint.
A
relative
constraint,
on
the
other
hand,
is
a
constraint
that
connects
one
value
number
to
another
value
number.
So
it's
like
it
isn't
saying
something
about
this
value
number
in
the
sentence
or
in
the
conversation
is
another
value
number.
B
So
yeah,
it's
like
saying,
I
know
that
I
plus
one
is
one
more
than
the
value
number
of
I
right,
so
I,
I,
plus
one
is
one
more
than
the
value
number
for
I
plus
1
is
has
value.
That
is
one
more
than
the
value
number
for
I
right,
so
that
is
those
kinds
of
relationships,
and
also
things
like,
if
you
see
X,
if
X
less
than
Y
and
neither
X
nor
Y
or
constant,
is
to
say
that
on
this
path,
I
know
that
value
number
for
X
is
less
than
value
number
for
y.
B
So
fundamentally,
there
are
two
value
numbers
involved:
that's
what
makes
it
a
relative
constraint.
So
those
kinds
of
constraints
are
also
created
as
we
go
along.
It's
not
just
absolute
constraints
that
are
relevant,
it
is
I
mean
you
could
be
doing
if
X
less
than
Y
once
and
then
repeat,
if
X
less
than
Y-
and
you
want
to
be
able
to
fold
away
the
latter
occurrence,
even
though
you
have
no
idea
what
x
and
y
are,
but
you
do
know
that
X
is
less
than
Y.
You've
checked
that
one.
B
So
you
want
to
propagate
that
fact.
So
that's
the
difference
between
relative
and
absolute
constraints,
there's
also
a
notion
of
global
constraint
versus
not
lien
on
global
constraint,
also
known
as
a
block
constraint,
I
believe
in
the
code.
It
refers
to
it
as
a
block
constraint.
A
global
constraint
is
one
that
is
just
going
to
be
true
throughout
the
methods,
so
you
don't
need
to
propagate
it
through
every
block
in
every
list
for
every
block.
So
let's
say
you
saw
in
the
very
first
block.
B
You
saw
I
equals
5
now
after
that
block
it
ends
in
an
if
it's
got
2
successor
blocks,
rather
than
propagates
of
value,
saying
it's.
This
value
number
is
5
along
this
edge
and
also
this
value
is
5
along
that
edge,
the
two
successors
and
then
carry
that
information
around
in
two
different
blocks.
Why
bother
you
know
that
the
value
is
5
nothing's
going
to
change
it?
It's
the
con.
It's
a
constant
node.
B
You
may
as
well
just
stick
it
in
one
list
somewhere
and
that's
the
global
constraint
list
browser
and
having
copies
of
it
floating
around.
So
it's
really
nothing
to
get
intimidated
about
it's
just
a
short
form
single
place
for
certain
very
trivial
and
simple
types
of
constraints
to
go
into
and
not
having
copies
floating
around
so
you'll
see
that
sort
of
global
constraint
list
being
touched
as
well.
B
The
second
time
you're,
going
through
the
loop
saying
Oh,
have
I
cashed,
something
for
this
value
number
on
the
back
edge
constrains.
Yes,
okay,
let
me
put
you
pick
it
up
from
there
and
use
it
so
blocks
inside
loops
and
therefore
nodes
inside
loops
are
analyzed
twice
and
everything
else
is
analyzed
once
outside.
B
B
Is
that
returns
true
within
the
first,
so
so
yeah
you're
just
making
a
forward
traversal
over
the
graph
over
control
flow
graph
over
the
blocks,
each
node
you're
going
bottom-up,
as
as
you
would
in
pretty
much
any
analysis
in
our
compiler,
you
would
go
child
first
analyze.
It
work
your
way
to
the
top
and
then
move
on
to
the
next
free
top
go
child
first
work
your
way
to
the
top,
although
control
flow,
edges
and
really
kind
of
think
of
it
as
a
the
forward
traversal
through
the
entire
control
flow
graph.
B
A
B
B
Calls
can
throw
exceptions
too,
rather
than
have
individual
little
blocks
chopped
up
at
every
place,
where
there's
a
car,
where
there's
a
check
and
express
its
explicitly
in
the
control
flow
as
an
if
guessed,
what
we
chose
to
do
early
on
was
to
keep
them
as
check
nodes
which
are
not
like
if
tests
so
there's
a
null
check.
Node,
there's
a
bound
check,
node
the
bound
check
isn't
expressed
as
to
its
comparing
the
lower
and
upper
bounds.
It's
just
a
single
node.
It
doesn't
break
the
block.
B
However,
it
is
true
that
control
flow
can
escape
that
block.
At
this
exception
point
right.
Each
one
of
these
exception
point
exception.
Points
is
a
place
where
you
can
get
out
of
the
block,
so
null
check
could
fail
and
you
could
end
up
in
a
cache
block.
A
bound
check
could
fail,
you
can
end
up
in
a
cache
block
and
all
check
would
fail
and
you
should
leave
the
method
entirely,
there's
no
cache
block
and
so
on.
B
So
this
fact
needs
to
be
expressed
from
how
so
it
gets
expressed
by
a
single
exception
edge
from
a
block
to
its
catch
block.
If
there
is,
if
there
is
a
cache
block,
and
not
all
methods
require
you
to
declare
a
cache
block,
but
if
there
is
a
cache
block,
you'll
draw,
in
an
exception,
egde
from
all
the
blocks
that
are
in
the
try
to
that
cache
block,
representing
the
fact
that
exceptions
are
possible
here,
I
could
be
going
from
block
a
to
block
B.
B
Why
an
exception
event,
and
that
needs
to
be
expressed
in
the
CFG
somehow,
because
we
didn't
blow
it
up
into
individual
blocks.
The
burden
is
then,
on
the
analyses
with
interflow
analysis
engine
in
in
the
compiler,
as
well
as
ops
like
value
propagation
that
are
walking
trees.
They
need
to
sort
of
take
into
account
that
exception
edge
every
time.
There
is
a
check,
for
example.
So
let's
say
value
prop
is
walking
forward.
It's
a
null
check.
A
B
Needs
to
pump
the
constraints
down
to
the
cache
block,
as
it
was
at
that
point
at
the
null
check,
because
that
may
be
the
point
where
control
actually
goes
to
the
catwalk,
so
it
needs
to
send
those
constraints
as
they
are
at
that
point,
let's
say
after
the
null
checks
and
two
trees
are
later
there's
a
bound
check.
It
needs
to
look
at
the
constraints
at
that
point
which
may
have
changed
slightly
because
they
were
intermediate
trees
in
between
the
null
check
and
the
bound
check.
B
It
needs
to
look
at
the
constraints
and
that
later
point
and
now
flow
those
in
to
that
exception,
cache
block
as
well.
So
essentially
that
will
be
a
place
where
a
merge
operation
happens.
So
the
list
of
constraints
that
we
had
from
the
first
point,
the
exception
point,
gets
merged
with
the
list
of
constraints,
at
the
second
exception
point,
and
that
becomes
the
constraints
flowing
through
to
the
catch
block
and
so
on
and
so
forth.
B
As
it's
walking
the
block
at
every
exception
point,
it
will
take
the
current
constraint
list
and
merge
it
into
the
insect
going
into
the
cache
block.
That
is
the
exception
successor,
so
it's
essentially
kind
of
it
has
to
model
these
n
different
program
points
as
reaching
the
cache
block
itself,
as
it's
doing
the
analysis,
because
in
a
CFG
there's
only
one
edge
representing
it,
so
so
it
does
n
merges
as
it's
going
along
and
at
the
end
of
the
day,
the
right
conservative
value
is
intact.
B
That
cache
block
representing
the
fact
that
you
could
come
there
from
here
here
here
or
here,
all
the
different
checks
that
are
there
in
that
block.
They're
all
points
that
would
take
you
there
yeah
so
does
that
make
sense
to
you
guys
on
the
phone
anyway
in
the
last
few
minutes
of
the
call
here.
So
maybe
I
should
just
pause
and
ask
for
questions
unless
I
was
so
wonderful
that
there
are
no
questions.
A
B
So
obviously
there's
code
inside
the
try
region,
it
could
be
several
basic
blocks.
It
could
be
a
lot
of
different
ifs
and
loops
and
whatnot.
So
there's
a
see
if
there's
a
part
of
the
CFG,
that's
inside
the
try
region
that
that's
for
blocks
that
are
inside
the
try
region,
every
one
of
those
blocks
will
have
an
exception
edge
to
the
cache
block,
representing
the
fact
that
control.
If
there
is
an
except
exception
thrown
from
anyplace
in
this
try
region,
it
is
capable
of
reaching
the
cache
ma.
B
The
edge
does
not
say
that
you
will
definitely
reach
there.
It
represents
merely
the
possibility
that
you
may
reach
there
so
so
an
edge
is
there
from
every
block.
Imagine
in
the
Tri
region
to
this
cache
block
now
as
you're
walking
through
each
basic
block.
There
could
be
multiple
check
nodes
in
each
basic
block,
because
we
don't
break
a
block
off
when
we
see
a
check
node,
you
can
have
several
checks
in
there.
B
Each
one
of
those
is
a
point
where
control
flow
can
be
transferred
from
the
try
block
to
the
cache
wall,
and
so
you
need
to
be
able
to
represent
that
fact
right.
The
constraints
that
are
flowing
into
the
catch
block
I
mean
the
cache
block
is
just
more
code
right.
It's
just
il
there
as
well.
You
need
to
accurately
capture
what
is
the
state
flowing
into
the
track
into
the
cash
flow,
and
in
order
to
do
that,
you
need
to
merge
all
the
constraints
from
all
the
points.
All
the
different
exception
points
individually.
B
You
need
to
merge
them
again
and
again
as
you're
going
that
they
could
be
flowing
into
the
catch
block,
because
there's
only
one
edge
otherwise
from
the
entire
block.
What
point
are
you
going
to
flow
constraints
that
are
coming
through?
That
block
into
the
cache
block?
Is
it
at
the
start?
This
is
the
end
that
could
be
the
confusion
right
because
you
only
have
one
exception
edge
and
what
I'm
saying
is
it's
not
at
the
start,
it's
not
at
the
end
as
you're
going
through.
You
flow
a
constraint.