Record correct dominators in merge return#2760
Merged
s-perron merged 1 commit intoKhronosGroup:masterfrom Jul 24, 2019
Merged
Conversation
In merge return, we need to know the original dominator for a block in order to traverse code from the original dominator to the new dominator and add appropriate Phi nodes. The current code gets this wrong because the dominator tree is build as needed. The first time we get the immediate dominator for a function we just built the dominator tree and it takes into account that a block has been split. The second time it does not. This inconsistency needs to be fixed. We do that by recording the original dominator for all blocks at the start of the pass. If we were to record just the basic block, that could change if the block is split. We want to traverse the code in the body of the original dominator, whatever block it ends up in. To make this easy to track, we not save the terminator instruction to represent the original dominator. Fixes KhronosGroup#2745
alan-baker
reviewed
Jul 24, 2019
| ; CHECK-NOT: OpLabel | ||
| ; CHECK: OpBranchConditional {{%\w+}} {{%\w+}} [[old_merge:%\w+]] | ||
| ; CHECK: [[old_merge]] = OpLabel | ||
| ; CHECK-NEXT: OpConvertFToS %int [[phi]] |
Contributor
There was a problem hiding this comment.
Does this not get predicated if the loop's return has been taken?
Collaborator
Author
There was a problem hiding this comment.
Yes it does. The branch that was inserted to skip it is the OpBranchConditional 2 lines up.
Collaborator
Author
There was a problem hiding this comment.
Is there something you think I should change?
Contributor
There was a problem hiding this comment.
Not necessarily, I wanted to confirm my understanding. I think I was confused by the CHECK-NEXT. It makes sense if the predication selection is nested within the outer loop.
alan-baker
approved these changes
Jul 24, 2019
dneto0
pushed a commit
to dneto0/SPIRV-Tools
that referenced
this pull request
Sep 14, 2024
* Rolling 7 dependencies Also updates known_failures and fixes a broken build rule. Roll third_party/effcee/ b83b58d17..4bef5dbed (2 commits) google/effcee@b83b58d...4bef5db $ git log b83b58d17..4bef5dbed --date=short --no-merges --format='%ad %ae %s' 2019-07-08 dneto Require Python 3 2019-07-08 dneto Add Clang warning -Wextra-semi Roll third_party/glslang/ 4b4b41a..3cea2e5 (29 commits) KhronosGroup/glslang@4b4b41a...3cea2e5 $ git log 4b4b41a..3cea2e5 --date=short --no-merges --format='%ad %ae %s' 2019-08-02 cepheus Bump revision and give the bots another chance to work. 2019-08-01 rharrison Add in header for uint32_t definition 2019-07-30 rharrison Convert no RTTI rule to be compiler specific 2019-07-28 lryer Fix Clang compiler warning. 2019-07-28 lryer Fix location distribution not in order 2019-07-25 stevenperron Remove execute permission from LICENSE.txt 2019-07-25 lryer Fix memory init issue, to make sure the class members are init in order. 2019-07-23 cepheus Revert "Merge pull request KhronosGroup#1792 from Roy-AMD/automapping-opengl-location" 2019-07-22 alele Fix bugs in missing Builtin decoration for some NV builtins for tessellation control shaders. Fix bug in member remapping. 2019-07-22 cepheus SPV: Update to latest SPIR-V header. 2019-07-18 greg Update spirv-tools and spirv-headers known good. 2019-07-17 cepheus Build: shut up warning to add unnecessary parens. 2019-07-17 alele Fix bug in printing trailing comma when dumping AST for a structure. 2019-07-16 jmacnak Update known good SPIRV-Tools commit 2019-07-15 sparmar Allow unsized view array dimension for non-block perviewNV attributes 2019-07-15 cepheus ESSL: Fix KhronosGroup#1823: Conditions for when derivatives are in compute shader. 2019-07-15 rex.xu OpIsHelperInvocationEXT should declare relevant SPV extension and capability 2019-07-13 cepheus GLSL: Fix KhronosGroup#1833: Don't constant fold integer mix to a float. 2019-07-12 jmacnak spirv: Generate missing SampleMaskOverrideCoverageNV capability op 2019-07-12 rharrison Explicitly remove RTTI in the top-level build config 2019-07-10 aaron.hagan Add support for SPV_KHR_shader_clock 2019-07-10 jbolz Avoid generating 8/16-bit constants when 8/16-bit arithmetic extensions aren't enabled 2019-07-08 alanbaker Test updates 2019-07-08 alanbaker Update SPIRV-Tools revision 2019-07-06 rex.xu Change implementation of gl_SIMDGroupSizeAMD 2019-07-03 cepheus SPV: Fix KhronosGroup#1783: Don't do bounds checking for spec-const-expression size 2019-06-25 jbolz Handle SPIR-V type mismatch when constructing a composite 2019-06-07 lryer code format refine 2019-06-06 lryer Add interface symbol and uniform symbol location auto mapping for OpenGL shader. Roll third_party/googletest/ 437e1008c..b4961ab1c (60 commits) google/googletest@437e100...b4961ab $ git log 437e1008c..b4961ab1c --date=short --no-merges --format='%ad %ae %s' 2019-08-06 absl-team Googletest export 2019-08-05 misterg Googletest export 2019-08-05 misterg Googletest export 2019-08-02 absl-team Googletest export 2019-08-01 absl-team Googletest export 2019-08-01 absl-team Googletest export 2019-07-31 absl-team Googletest export 2019-07-31 absl-team Googletest export 2019-07-31 misterg Googletest export 2019-08-01 guillemglez Fix table formatting in advanced.md 2019-07-09 krystian.kuzniarek adjust a comment to the similar section in advanced.md 2019-07-31 anttsov Update README.md 2019-07-28 krystian.kuzniarek update pre-C++11 paragraphs 2019-07-26 krystian.kuzniarek fix typos 2019-07-26 krystian.kuzniarek fix numbering of ordered lists in Markdown 2019-07-25 krystian.kuzniarek remove trailing whitespaces 2019-07-30 anttsov Update README.md 2019-07-29 absl-team Googletest export 2019-07-29 misterg Googletest export 2019-07-29 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-29 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-11 adam.f.badura Correct CMake to cover Cygwin 2019-07-25 absl-team Googletest export 2019-07-25 absl-team Googletest export 2019-07-18 misterg Googletest export 2019-07-23 rytis.karpuska Fix small errors in primer.md 2019-07-19 chris.baish Moved explanation to single line as well 2019-07-19 chris.baish Moved table to single lines 2019-07-18 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-18 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-18 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-18 misterg Manual docs tweaks still in preparation for including docs with code pushes 2019-07-18 krystian.kuzniarek explicitly show overriding to align examples to their comments 2019-07-18 krystian.kuzniarek document a missing parent class 2019-07-18 43465319+ChrisBaish Update primer.md 2019-07-17 misterg remove outdated 2019-07-17 misterg remove outdated 2019-07-17 misterg Preparation for including docs in round-trip with OSS, Manual merge, review and merge docs internal-OSS 2019-07-17 absl-team Googletest export 2019-07-11 adam.f.badura Add missing <functional> include 2019-07-16 misterg Preparation for including docs in round-trip with OSS. Manual review and merge docs internal-OSS 2019-07-16 misterg Preparation for including docs in round-trip with OSS. Manual review and merge docs internal-OSS 2019-07-16 misterg Googletest export 2019-07-15 absl-team Googletest export 2019-07-10 absl-team Googletest export 2019-07-15 misterg Preparation for including docs in round-trip with OSS 2019-07-15 misterg Preparation for including docs in round-trip with OSS 2019-07-15 misterg Preparation for including docs in round-trip with OSS 2019-07-15 misterg Preparation for including docs in round-trip with OSS 2019-07-13 krystian.kuzniarek fix a broken link 2019-07-13 krystian.kuzniarek add missing references to DesignDoc and KnownIssues 2019-07-13 krystian.kuzniarek rename and apply snake_case on KnownIssues.md 2019-07-13 krystian.kuzniarek rename and apply snake_case on FrequentlyAskedQuestions.md 2019-07-13 krystian.kuzniarek rename and apply snake_case on ForDummies.md 2019-07-13 krystian.kuzniarek rename and apply snake_case on Documentation.md 2019-07-13 krystian.kuzniarek rename and apply snake_case on DesignDoc.md 2019-07-13 krystian.kuzniarek rename and apply snake_case on CheatSheet.md 2019-07-10 sam.sobell Fix bad advice in cook book (KhronosGroup#2308) 2019-07-01 cclauss Travis CI: The sudo: tag is now deprecated in Travis CI 2018-01-29 knut.omang Remove / from parameterized test names if base test name is empty Roll third_party/re2/ e356bd3f8..67bce690d (8 commits) google/re2@e356bd3...67bce69 $ git log e356bd3f8..67bce690d --date=short --no-merges --format='%ad %ae %s' 2019-07-31 junyer Switch from //... to //:all when building with Bazel. 2019-07-26 junyer Get rid of StringAppendF(). 2019-07-26 junyer Get rid of SStringPrintf(). 2019-07-25 junyer Oops, missed a couple. 2019-07-25 junyer Don't make the arraysize() macro cast to int. 2019-07-24 junyer One more tweak for Python 3. 2019-07-24 junyer Get the Unicode scripts working with Python 3. 2019-07-21 junyer Update Unicode data to 12.1.0. Roll third_party/spirv-cross/ 53ab2144b..4ce04480e (79 commits) KhronosGroup/SPIRV-Cross@53ab214...4ce0448 $ git log 53ab2144b..4ce04480e --date=short --no-merges --format='%ad %ae %s' 2019-08-01 post Fix severe performance issue with invariant expression invalidation. 2019-07-26 cdavis MSL: Unify the get_*_address_space() methods. 2019-07-26 post MSL: Cleanup temporary use with emit_uninitialized_temporary. 2019-07-26 post MSL: Deal with Modf/Frexp where output is access chain to scalar. 2019-07-26 post Do not force temporary unless continue-only for loop dominates. 2019-07-25 post Missed case where DoWhile continue block deals with Phi. 2019-07-25 post Vulkan GLSL: Support disabling samplerless texture function EXT. 2019-07-25 post Workaround MSVC 2013 compiler issues. 2019-07-22 cdavis MSL: Adjust BuiltInWorkgroupId for vkCmdDispatchBase(). 2019-07-24 post Fix some typos in comments. 2019-07-24 post Do not attempt to pack types which are already scalar. 2019-07-24 post HLSL query lod cleanups. 2019-07-24 post Do not eagerly invalidate all active variables on a branch. 2019-07-23 post Do not disable temporary forwarding when we suppress usage tracking. 2019-07-23 post Add another test for unpacking without load forwarding. 2019-07-23 post Look at pointee type when unpacking expressions. 2019-07-23 post Fix some warnings when building in MoltenVK. 2019-07-23 post Deal correctly with non-forwarded packed loads. 2019-07-23 post Test CompositeInsert/Extract/VectorShuffle on packed vectors. 2019-07-23 post Add test for array of scalar struct. 2019-07-23 post Recursively pack struct types when we find scalar packed structs. 2019-07-23 post Run format_all.sh. 2019-07-23 post Unpack vector expression in Matrix-Vector multiplies. 2019-07-23 post Test matrix multiplies in more complex scenarios. 2019-07-23 post Test implicit packing of struct members. 2019-07-23 post GLSL/HLSL: Verify member alignment for explicit offset as well. 2019-07-23 post Add tests for struct padding and self-alignment. 2019-07-23 post Use to_unpacked_row_major_expression to unify row-major in MSL/GLSL. 2019-07-23 post Simplify row-major matrix/vector multiplies. 2019-07-23 post Test array of std140 vectors. 2019-07-23 post Add struct size padding tests. 2019-07-22 post Add test for CompositeExtract from row-major loaded vector. 2019-07-22 post Add test for split access chain into row-major matrix. 2019-07-22 post Remove obsolete matrix workaround code. 2019-07-22 post Only transpose unpacked expressions. 2019-07-22 post Deal correctly with complete stores to row_major matrices. 2019-07-22 post Declare correct matrix type when unpacking. 2019-07-22 post Don't forget to register a write to LHS expression in certain case. 2019-07-22 post Deal with swizzled stores to std140 matrices. 2019-07-22 post Fix some row-major column store cases. 2019-07-22 post Fix more stray parens. 2019-07-22 post Fixup stray parent in output. 2019-07-22 post Correctly unpack row-major matrices when storing to LHS. 2019-07-22 post MSL: Add std140 and scalar matrix layouts. 2019-07-22 post MSL: Add std430 matrix access test. 2019-07-22 post MSL: Support storing to row-major column. 2019-07-22 post Tests run clean. 2019-07-19 post Fix unpacking of packed but not remapped types on load. 2019-07-19 post Traverse correct types when checking scalar layout. 2019-07-19 post Deal with scalar layout of entire structs. 2019-07-19 post Pass down row-major state to unpacking functions. 2019-07-19 post Deal with all forms of matrix writes ... 2019-07-19 post Can deal with std140 matrices now. 2019-07-18 post Start considering how to emit physical type ID. 2019-07-18 post Deal more cleanly with matrices and row-major. 2019-07-18 post Reintroduce struct_member_* MSL queries. 2019-07-18 post MSL: Begin rewrite of buffer packing logic. 2019-07-18 cdavis Don't forward uses of an OpIsHelperInvocationEXT op. 2019-07-13 cdavis Support the SPV_EXT_demote_to_helper_invocation extension. 2019-07-17 post Test glsl.std450 more exhaustively. 2019-07-11 cdavis MSL: Support the SPV_INTEL_shader_integer_functions2 extension. 2019-07-11 cdavis Update external repos. 2019-07-12 cdavis Support the SPV_KHR_device_group extension. 2019-07-11 cdavis MSL: Support the SPV_AMD_shader_trinary_minmax extension. 2019-07-12 post Run format_all.sh. 2019-07-12 post Deal correctly with return sign of bitscan operations. 2019-07-10 post MSVC 2015: Workaround bogus warning with move_backwards. 2019-07-10 post MSVC: Fix some warnings in C wrapper. 2019-07-10 cdavis MSL: Use the select() function for OpSelect. 2019-07-10 cdavis Support the SPV_KHR_post_depth_coverage extension. 2019-07-10 cdavis MSL: Handle coherent, volatile, and restrict. 2019-07-11 post GLSL: Need extension to use bitcast on GLSL < 330. 2019-07-11 lifeng.pan Remove unreasonable assertion for OpTypeImage Sampled parameter. 2019-07-10 cdavis MSL: Handle packed matrices. 2019-07-10 cdavis MSL: Fix alignment of packed types. 2019-07-10 post Forget loop variable enables after emitting block chain. 2019-07-10 post MSL: Re-roll array expressions in initializers. 2019-07-09 cdavis MSL: Support scalar block layout. 2019-07-09 post MSVC 2013: Work around another compiler bug with array init. Roll third_party/spirv-headers/ 29c1114..e4322e3 (2 commits) KhronosGroup/SPIRV-Headers@29c1114...e4322e3 $ git log 29c1114..e4322e3 --date=short --no-merges --format='%ad %ae %s' 2019-07-14 aaron.hagan Add SPV_KHR_shader_clock to spirv-headers 2019-07-12 michael.kinsner Reserve additional loop control bit for upcoming update to SPV_INTEL_fpga_loop_controls extension Roll third_party/spirv-tools/ b8ab808..698b56a (43 commits) KhronosGroup/SPIRV-Tools@b8ab808...698b56a $ git log b8ab808..698b56a --date=short --no-merges --format='%ad %ae %s' 2019-08-05 afdx Add 'copy object' transformation (KhronosGroup#2766) 2019-08-02 paulthomson fuzz: change output extension and fix usage string (KhronosGroup#2778) 2019-08-01 geoff Remove extra ';' after member function definition. (KhronosGroup#2780) 2019-07-31 zoddicus Update WebGPU validation rules of OpAtomic*s (KhronosGroup#2777) 2019-07-31 alanbaker Treat access chain indexes as signed in SROA (KhronosGroup#2776) 2019-07-30 dneto Add pass to inject code for robust-buffer-access semantics (KhronosGroup#2771) 2019-07-30 zoddicus Update OpMemoryBarriers rules for WebGPU (KhronosGroup#2775) 2019-07-30 dneto Add opt test fixture method SinglePassRunAndFail (KhronosGroup#2770) 2019-07-29 dneto Element type is const for analysis::Vector,Matrix,RuntimeArray (KhronosGroup#2765) 2019-07-29 dnovillo Protect against out-of-bounds references when folding OpCompositeExtract (KhronosGroup#2774) 2019-07-29 alanbaker Don't move debug or decorations when folding (KhronosGroup#2772) 2019-07-29 zoddicus Update OpControlBarriers rules for WebGPU (KhronosGroup#2769) 2019-07-26 dnovillo Fix KhronosGroup#2609 - Handle out-of-bounds scalar replacements. (KhronosGroup#2767) 2019-07-25 afdx Limit fuzzer tests so that they take less time to run (KhronosGroup#2763) 2019-07-25 stevenperron Fix check for unreachable blocks in merge-return (KhronosGroup#2762) 2019-07-25 afdx Transformation and fuzzer pass to add dead continues (KhronosGroup#2758) 2019-07-24 zoddicus Remove unneeded future imports (KhronosGroup#2739) 2019-07-24 stevenperron Process OpDecorateId in ADCE (KhronosGroup#2761) 2019-07-24 stevenperron Record correct dominators in merge return (KhronosGroup#2760) 2019-07-23 stevenperron SSA rewriter: Don't use trivial phis (KhronosGroup#2757) 2019-07-23 alanbaker Fix block depth rule priority (KhronosGroup#2755) 2019-07-23 alanbaker Case validation with repeated labels (KhronosGroup#2689) 2019-07-22 greg Bindless Instrument: Make init check depend solely on input_init_enabled (KhronosGroup#2753) 2019-07-22 kevin.petit Validate storage class OpenCL environment rules for atomics (KhronosGroup#2750) 2019-07-22 51214578+jmacnak-nv Allow LOD ops in compute shaders with derivative group execution modes (KhronosGroup#2752) 2019-07-18 dneto Document opt::Instruction::InsertBefore methods (KhronosGroup#2751) 2019-07-17 stevenperron Revert "Do not inline OpKill Instructions (KhronosGroup#2713)" (KhronosGroup#2749) 2019-07-16 jbolz For Vulkan, disallow structures containing opaque types (KhronosGroup#2546) 2019-07-16 stevenperron Fix bug in merge return (KhronosGroup#2734) 2019-07-15 51214578+jmacnak-nv Allow ray tracing shaders in inst bindle check pass. (KhronosGroup#2733) 2019-07-12 zoddicus Correctly implement WebGPU related flag exclusions (KhronosGroup#2737) 2019-07-12 greg Remove Common Uniform Elimination Pass (KhronosGroup#2731) 2019-07-12 cwallez BUILD.gn: Add deps and move files for `gn check` (KhronosGroup#2735) 2019-07-11 zoddicus Update execution scope rules for WebGPU (KhronosGroup#2730) 2019-07-11 33432579+alan-baker Extra small storage validation (KhronosGroup#2732) 2019-07-11 jbolz Add validation for SPV_EXT_demote_to_helper_invocation (KhronosGroup#2707) 2019-07-10 52076061+digit-google BUILD.gn: Add targets to build all command-line tools (KhronosGroup#2727) 2019-07-10 stevenperron Change the order branches are simplified in dead branch elim (KhronosGroup#2728) 2019-07-11 troughton Add —preserve-bindings and —preserve-spec-constants (KhronosGroup#2693) 2019-07-10 stevenperron Handle decorations better in some optimizations (KhronosGroup#2716) 2019-07-10 zoddicus Update memory scope rules for WebGPU (KhronosGroup#2725) 2019-07-08 33432579+alan-baker Remove extra semis (KhronosGroup#2717) 2019-07-08 33432579+alan-baker Validate usage of 8- and 16-bit types with only storage capabilities (KhronosGroup#2704) Created with: roll-dep third_party/effcee third_party/glslang third_party/googletest third_party/re2 third_party/spirv-cross third_party/spirv-headers third_party/spirv-tools
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
In merge return, we need to know the original dominator for a block in order to
traverse code from the original dominator to the new dominator and add
appropriate Phi nodes. The current code gets this wrong because the dominator
tree is build as needed. The first time we get the immediate dominator for a
function we just built the dominator tree and it takes into account that a
block has been split. The second time it does not.
This inconsistency needs to be fixed. We do that by recording the original
dominator for all blocks at the start of the pass.
If we were to record just the basic block, that could change if the block is
split. We want to traverse the code in the body of the original dominator,
whatever block it ends up in. To make this easy to track, we not save the
terminator instruction to represent the original dominator.
Fixes #2745