René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Branching design for Tier 2 (uops) interpreter","articleBody":"This issue is part of the larger epic of gh-104584. In PR gh-106393 I tried to implement branching, but it was premature. Here's a better design, following @markshannon's [guidance](https://github.com/python/cpython/pull/106393#discussion_r1252794047).\r\n\r\nWe have the following jump instructions (not counting the instrumented versions):\r\n\r\nUnconditional jumps:\r\n\r\n- [x] JUMP_BACKWARD\r\n- [ ] JUMP_BACKWARD_NO_INTERRUPT\r\n- [x] JUMP_FORWARD\r\n\r\nBranches, a.k.a. conditional jumps:\r\n\r\n- [x] POP_JUMP_IF_FALSE, POP_JUMP_IF_TRUE, ~POP_JUMP_IF_NONE, POP_JUMP_IF_NOT_NONE~\r\n- [x] FOR_ITER's specializations:\r\n  - [x] FOR_ITER_LIST\r\n  - [x] FOR_ITER_TUPLE\r\n  - [x] FOR_ITER_RANGE\r\n- [ ] FOR_ITER_GEN\r\n- [ ] SEND\r\n\r\n- [ ] Add counters to to POP_JUMP_IF_{FALSE,TRUE} to determine likeliness\r\n\r\nThe translation strategies could be as follows:\r\n\r\n## Unconditional jumps\r\n\r\n### **JUMP_BACKWARD**\r\n\r\n- If this jumps to exactly the top of the current trace, emit a Tier 2 JUMP_TO_TOP uop, and stop projecting (i.e., exit the trace generation loop). The JUMP_TO_TOP uop implementation should include a CHECK_EVAL_BREAKER call.\r\n- If this jumps anywhere else, emit a SAVE_IP uop with the destination of the jump, followed by an EXIT_TRACE uop, and stop projecting.\r\n\r\n### **JUMP_BACKWARD_NO_INTERRUPT**\r\n\r\n- Since this is typically only used in special circumstances, just emit a SAVE_IP instruction with the destination and an EXIT_TRACE uop, and stop projecting.\r\n- Alternatively, we could make CHECK_EVAL_BREAKER a separate UOP that is inserted for JUMP_BACKWARD but not for JUMP_BACKWARD_NO_INTERRUPT, and otherwise treat the two backward jumps the same.\r\n\r\n### **JUMP_FORWARD**\r\n\r\n- Emit a SAVE_IP uop with the destination of the jump, and continue projecting from there (i.e. set `instr` to the destination of the jump).\r\n\r\n## Conditional jumps (branches)\r\n\r\n### **POP_JUMP_IF_FALSE** and friends\r\n\r\nConsider the following Python code:\r\n```py\r\nif cond:\r\n    block\r\nrest\r\n```\r\nThis translates roughly to the following Tier 1 bytecode (using B1, B2, ... to label Tier 1 instructions, and `\u003ccond\u003e`, `\u003cblock\u003e` etc. to represent code blocks that evaluate or execute the corresponding Python fragments):\r\n```\r\nB1: \u003ccond\u003e\r\nB2: POP_JUMP_IF_FALSE B4\r\nB3: \u003cblock\u003e\r\nB4: \u003crest\u003e\r\nB5:\r\n```\r\nI propose the following translation into Tier 2 uops, assuming the branch is \"unlikely\":\r\n```\r\n    SAVE_IP B1\r\n    \u003ccond\u003e\r\n    SAVE_IP B2\r\n    JUMP_IF_FALSE stub\r\n    POP_TOP\r\n    SAVE_IP B3\r\n    \u003cblock\u003e\r\n    SAVE_IP B4\r\n    EXIT_TRACE\r\n\r\nstub:\r\n    POP_TOP\r\n    SAVE_IP B4\r\n    EXIT_TRACE\r\n```\r\nWhere JUMP_IF_FALSE inspects the top of stack but doesn't pop it, and has an argument that executes a jump in the Tier 2 uop instruction sequence.\r\n\r\nIf the branch is \"likely\", we do this instead:\r\n```\r\n    SAVE_IP B1\r\n    \u003ccond\u003e\r\n    SAVE_IP B2\r\n    JUMP_IF_TRUE stub\r\n    POP_TOP\r\n    SAVE_IP B4\r\n    \u003crest\u003e\r\n    SAVE_IP B5\r\n    EXIT_TRACE\r\n\r\nstub:\r\n    POP_TOP\r\n    SAVE_IP B3\r\n    EXIT_TRACE\r\n```\r\nNote how in this case, `\u003crest\u003e` is projected as part of the trace, while `\u003cblock\u003e` is not, since the likely case is that we jump over `\u003cblock\u003e` to `\u003crest\u003e`.\r\n\r\nFor the other simple conditional jumps (POP_JUMP_IF_TRUE, ~POP_JUMP_IF_NONE, POP_JUMP_IF_NOT_NONE~) we do the same: if the jump is unlikely, emit a JUMP_IF_XXX uop and a stub; if the jump is likely, emit the inverse JUMP_IF_NOT_XXX uop and a different stub, and continue projecting at the destination of the original jump bytecode.\r\n\r\nI propose to have hand-written cases both in the superblock generator and in the Tier 2 interpreter for these, since the translations are too irregular to fit easily in the macro expansion data structure. The stub generation will require additional logic and data structures in `translate_bytecode_to_trace()` to keep track of the stubs required so far, the available space for those, and the back-patching required to set the operands for the JUMP_IF_XXX uops.\r\n\r\n### **FOR_ITER** and (especially) its specializations\r\n\r\nThe common case for these is not to jump. The bytecode definitions are too complex to duplicate in hand-written Tier 2 uops. My proposal is to change these in bytecodes.c so that, instead of using the `JUMPBY(n)` macro, they use `JUMPBY_POP_DISPATCH(n)`, which in Tier 1 translates into just `JUMPBY(n)`, but in Tier 2 translates into roughly\r\n```cc\r\nframe-\u003eprev_instr += (x);\r\nPY_DECREF(stack_pointer[-1]);\r\nstack_pointer -= 1;\r\ngoto exit;\r\n```\r\nthereby exiting the trace when the corresponding for-loop terminates.\r\n\r\nI am assuming here that most loops have several iterations. I don't think it's worth special-casing the occasional for-loop that almost always immediately terminates.\r\n\r\n### **SEND**\r\n\r\nPossibly we could treat this the same as FOR_ITER. But right now I propose to just punt here, and when we encounter it, stop projecting, as we do with any other unsupported bytecode instruction.\r\n\r\n\u003c!-- gh-linked-prs --\u003e\r\n### Linked PRs\r\n* gh-106542\r\n* gh-106543\r\n* gh-106551\r\n* gh-106599\r\n* gh-106613\r\n* gh-106638\r\n* gh-106651\r\n* gh-106696\r\n* gh-106756\n* gh-106796\n* gh-112134\n* gh-112214\n\u003c!-- /gh-linked-prs --\u003e\r\n","author":{"url":"https://github.com/gvanrossum","@type":"Person","name":"gvanrossum"},"datePublished":"2023-07-07T18:47:24.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":22},"url":"https://github.com/106529/cpython/issues/106529"}