Tier 2 optimizer's abstract interpreter

Linked PRs

We need a lattice of values that embodies type information, NULLness, Noneness, constant values, version numbers, at the least.

The lattice should look something like this:

graph BT;
    t("True");
    f("False");
    bl("bool");
    nnull(not NULL);
    nnone(not None);
    ot(other types);
    oc(other constants);
    b("bottom(unknown)");
    b-->NULL;
    b-->nnull;
    nnull-->nnone;
    nnull-->None;
    nnone-->ot;
    nnone-->bl;
    ot-->oc;
    oc-->top;
    None-->top;
    NULL-->top;
    bl-->t;
    bl-->f;
    t-->top;
    f-->top;

There should be edges from all the nodes (except bottom) to top, but I've omitted those to avoid the diagram becoming a mess

gh-114058: Foundations of the Tier2 redundancy eliminator (GH-115085)

gh-114058: Fix flaky globals to constant test (#115423)

pythongh-114058: Foundations of the Tier2 redundancy eliminator (pyth…

pythongh-114058: Fix flaky globals to constant test (python#115423)

There should be edges from all the nodes (except bottom) to top, but I've omitted those to avoid the diagram becoming a mess

Maybe top needn't be part of the diagram at all? It ought to be unreachable (IIUC it represents an impossible condition). Might as well simplify the diagram a bit further.

gh-114058: More robust method handling in redundancy eliminator (GH-1…

gh-114058: Improve method information in redundancy eliminator (GH-11…

According to Wikipedia, in type theory, Bottom (⊥) is the type that has no values, whereas Top (⊤) is the type that encompasses all values. Maybe we should switch to this terminology, and swap top and bottom in the diagram above, so that "unknown" is named "top" and there is an arrow from every other nod to "bottom"? (Possibly also just flipping the diagram upside down so that "top" is drawn at the top and "bottom" at the bottom?)

graph TB;
    t("True");
    f("False");
    bl("bool");
    nnull(not NULL);
    nnone(not None);
    ot(other types);
    oc(other constants);
    top("top (unknown)");
    bottom("bottom (contradiction)");
    top-->NULL;
    top-->nnull;
    nnull-->nnone;
    nnull-->None;
    nnone-->ot;
    nnone-->bl;
    ot-->oc;
    oc-->bottom;
    None-->bottom;
    NULL-->bottom;
    bl-->t;
    bl-->f;
    t-->bottom;
    f-->bottom;

Offline we agreed that Top is the universal type and Bottom is the empty type, like in my latest diagram. I will update diagrams and text where these terms are used.

See faster-cpython/ideas#658

pythongh-114058: More robust method handling in redundancy eliminator (…

pythongh-114058: Improve method information in redundancy eliminator (p…

pythongh-114058: More robust method handling in redundancy eliminator (…

pythongh-114058: Improve method information in redundancy eliminator (p…

pythongh-114058: More robust method handling in redundancy eliminator (…

pythongh-114058: Improve method information in redundancy eliminator (p…

Navigation Menu

Repository navigation

Tier 2 optimizer's abstract interpreter #114058

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Tier 2 optimizer's abstract interpreter #114058

Description

Linked PRs

Activity

markshannon commented on Feb 8, 2024

markshannon commented on Feb 8, 2024

gvanrossum commented on Feb 21, 2024

gvanrossum commented on Feb 25, 2024

gvanrossum commented on Feb 25, 2024

gvanrossum commented on Feb 26, 2024

gvanrossum commented on Feb 26, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions