Thanks for @DianQK and @nikic! This patch will be submitted as Github PR (It seems that doc
about submitting by Phabricator has been removed).

Polish comments.

Keep order when updating dom-tree.

Polish comment and fix when to print log.

Reduce irrelevant formatting

In D155940#4641865, @DianQK wrote:

LGTM. But before landing, you'd better request @nikic approval for this.

If possible, however, it would be better if there is any other available option that does not modify the original IR.

I don't know. The purpose of your transformation is to tweak this test case.

In D156657#4639867, @goldstein.w.n wrote:

In D156657#4639543, @XChy wrote:

ping.

nikic is on vacation for the next week, since he requested changes plan to let him get to it when he comes back.
Might have time to review later in the week, however.

ping.

Insert use function into jump-table-islands.ll to avoid unrelated transform.

In D155940#4636482, @DianQK wrote:

I read the history of jump-table-islands.ll.
This test checks for oversized jump tables jumping over each other.
You transform changes from

end:                                              ; preds = %complex, %simple
  %val = phi i8500 [ %l, %complex ], [ -1, %simple ]
  br label %common.ret

to

end:                                              ; preds = %complex
  br label %common.ret

The test was to check disappears.
Increasing BigInt makes no sense.
Sorry I don't know how to create a friendly diff display.
You could remove -arm-atomic-cfg-tidy=0 and change the end bb to:

end:
  %val = phi %BigInt [ %l, %complex ], [ -1, %simple ]
  %val2 = add %BigInt %val, 1
  ret %BigInt %val2
}

https://reviews.llvm.org/differential/diff/555646/

I feel the SKIP_TABLE name is confusing and should be changed to CONTINUE_TABLE/ISLAND_JUMP?

Simplify LazyGetIndex function, and ready to be reviewed.

In D155940#4633497, @DianQK wrote:

Too much irrelevant formatting. It causes review to become complicated. It also affects other people blame related changes.
Could you ignore this formatting?

In fact, I'm not sure why. It could be that some commits are not formatted, or it could be a change in formatting rules. Or something else.
My formatting workflow is:

• Ignore all irrelevant formatting if present.
• Add and commit.
• git clang-format HEAD~1
• Since the latest submission is my own. Then I just run git add . and git clang-format HEAD~1.

Drop unnecessary formatting.

Remove unnecessary helper function

LGTM. May commit it if no changes are requested by others in one day.

ping.

Eliminate boundary-check.

Update tests and FIXME: Boundary-check

In D156657#4550996, @XChy wrote:

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Complete basically correct fold.

In D156657#4547304, @nikic wrote:

It would be better to base this on collectOffset() and work in offset representation. Especially if you're interested in handling Rust, the type of the global and the GEP / loads will typically not line up (constant globals in Rust are usually i8 arrays, regardless of "real" type.)

Update tests.

Update tests

Extends foldCmpLoadFromIndexedGlobal to fold.

Extend foldCmpLoadFromIndexedGlobal and use load-cmp.ll as test file.

In D156657#4546067, @nikic wrote:

This should be handled by the foldCmpLoadFromIndexedGlobal() fold, by first converting the icmp(load(gep(g, idx))) into icmp(idx) and then folding that icmp against the dominating condition.

That fold currently requires a very specific GEP source element type, but should be easy to generalize.

Update AArch64's codegen tests.

[Clang-format]
It seems perform correctly and well in most cases.

Nice work to me! Just some nits here.
Can you create two patches to better show the difference before/after transform?
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes your optimized testcases and your code for the fold. (Your second commit, which is based on your first commit)
And then let the first patch be the parent revision of the second patch through "Edit Related Revisions".

Update codesize-loop.ll

Add test for generalization.

• Add complete positive tests
• Fix bugs about preserving domtree

• Refactor TryToSimplifyUncondBranchFromEmptyBlock to merge phis between BB and Succ with a common predecessor. Logic correctly embedded (OK in Local tests), but not efficient currently.
• A regression found, in switch-simplify-crash2.ll. But InstCombine would solve it.
• Testcases not added now, incoming. And ARM/jump-islands-table.ll doesn't test well still.

Add -arm-atomic-cfg-tidy=0 option.

In D155940#4538561, @nikic wrote:

Do you have any particular issues this could cause in mind?

Sure, something like FoldTwoEntryPHINode/HoistThenElseToIf may miss/delay. Or some Phi to Select may be delayed/sunk. I haven't constructed counter-examples here. (Maybe it's my intuitive fault, I actually constructed some examples optimized well).
I think the probitability can be tested by the existing testcases here. I'll try to generalize TryToSimplifyUncondBranchFromEmptyBlock to perform the tests.

I think even if we don't always perform the transform, we should still express it generically, and then have a profitability heuristic on top: E.g. say that the one common predecessor must have a switch terminator. That way we can clearly separate correctness from profitability requirements.

I agree with you. The generalization is indeed necessary. It may take some time to complete it. At that time can we determine what profitability heuristic shoud be.

Edit: Just for reference, this is an example of the non-switch CFG I have in mind where such a transform should be possible: https://gist.github.com/nikic/8f22ef4e366fd3041c7e150c228f9673

Thanks! That could serve as a testcase to be expanded/reduced.

Emphasize ordering.

Omit jump-table-islands.ll test temporarily. (Sorry, I'm not familiar with ARM and unable to update it)
Contact related committers to update if this patch is approved.

• Fix the nits
• Change the order of checks to increase efficiency.

Here is an optimized example related to the lookup table optimization in the issue in summary:
add 1

• Fix the nits
• Clear the logic

Thanks for your review! I understand your framing and it clear my mind. This framing is much general, not just for switch. And as you analyse, actually, a large part of the logic of this patch is copied from TryToSimplifyUncondBranchFromEmptyBlock, specified for switch. I restrict this fold in a narrow situation. Though this transformation is not directly related to switch, but I didn't apply such mergence to all BasicBlocks, since it's not always worthwhile as you say.

In D154791#4527350, @nikic wrote:

LGTM

• Add m_OneUse guard to zext(icmp).

• Fix all the nits.
• Extract the logic of canMergePhisOfCase

Maybe you need to create two patch.
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes optimized testcases and the code for the fold. (Your second commit, which is based on your first commit)
And then you should let the first patch be the parent revision of the second patch through "Edit Related Revisions".

• Apply m_OneUse guard to lshr.
• Fix nits

ping.

Fix the bugs of merging the phis from the BasicBlock out of switch.

• Preserve domtree

Avoid infinite loops

• Avoid infinite loops

Produce zext(bitwise(icmp.icmp))

ping.

Limit the fold for multiuse cases

Add xor tests

In D154791#4497148, @XChy wrote:

I update the diff to ensure that we fold exactly what can be folded by foldXorOfICmps and foldAndOrOfICmps.

However, I'm not sure what unexpected result the code below may bring.

// remove the deferred 2 instructions : 
// icmp slt A, 0
// bitwise (A < 0, icmp) 
// otherwise there will be infinite loops of combining
Worklist.popDeferred()->eraseFromParent();
Worklist.popDeferred()->eraseFromParent();

I update the diff to ensure that we fold exactly what can be folded by foldXorOfICmps and foldAndOrOfICmps.

[clang-format]

In D154791#4483474, @nikic wrote:

The basic idea here is reasonable, but you need to be very careful about infinite loops: If you replace the shift with zext+icmp and it does *not* get folded afterwards, it will be converted back to the shift, and so on. I don't think the fold is guaranteed to happen, e.g. due to some unlucky interaction with shouldOptimizeCast().

I would recommend to instead directly produce the zext(binop(icmp, icmp)) sequence, rather than letting the following fold handle it.

Please add:

• Multi-use test.
• Test where we do not get any beneficial fold out of converting the lshr back into an icmp.

Depending on how the latter case looks like, we might want to further limit this -- e.g. does it make sense to do this if the lshr and icmp work on different variables or not?