Change Details

Currently, when we process the pattern like %cmp = icmp slt i64 %x, 0 select i1 %cmp, i32 -1, 32 1 We handle it in a general case with power of two being in the 3rd pard of select, and the generated code for this case looks like: %1 = lshr i64 %x, 62 %2 = trunc i64 %1 to i32 %3 = and i32 %2, 2 %4 = xor i32 %3, 2 %5 = add nsw i32 %4, -1 However we have a smarter logic specifically with comparison with zero in foldSelectInstWithICmp which did not apply because of type mismatch between `%x` and `1`. If we lift the restriction and handle this case separately, we end up with a better pattern: %1 = ashr i64 %x, 63 %2 = trunc i64 %1 to i32 %3 = or i32 %2, 1 This is 2 instructions less than what we have now. This patch relaxes the restricton on types, allowing now `%x` be wider than the result of select. We can in theory also allow `1` to be wider (no functional problems with that), however when I did, in some cases we end up with a worse code (see the comment). The problem looks irrelevant to this change which is a pure improvement. We can yield the last restriction when other problematic transforms are fixed.

Currently InstCombine tends to recognize patterns like %cmp = icmp slt iA %x, 0 %select = select i1 %cmp, iB %A, iB %B as bit-test against highest bit, and convert it into one of multiple shift-based patterns which may look differently depending on types `iA` and `iB` and values of `%A` and `%B`. It only happens if `%A` and `%B` are constants. We observe at least three possible sutiatons: Case 1: %c2 = icmp slt %a, 0 %select1 = select %c2, -1, %Greater converts into (%a s>> 31) | %Greater Case 2: %c2 = icmp slt i32 %a, 0 %select1 = select i1 %c2, i32 %Less, i32 %Greater converts into (%a s>> 31) - (%Less - %Greater) + %Greater or, if it is the equivalent, to (%a s>> 31) - (%Less - %Greater) | %Greater Case 3: %c2 = icmp slt i64 %a, 0 %select1 = select i1 %c2, i32 %Less, i32 %Greater converts to (trunc (%a s>> 63) to i32) - (%Less - %Greater) + %Greater There are possibly more variatons of this. The general idea is that select by comparison with `0` or `-1` gets transformed into multiple different patterns, and very small changes in conditions and constants may change this pattern. There is no clear benefits of that transforms, but the obvious downside of them is decanonicalization. For example, we have a matcher of three-ways comparison that expects to see the pattern of the following form: %c1 = icmp eq %a, 0 %c2 = icmp slt %a, 0 %select1 = select %c2, %Less, %Greater %select2 = select %c1, %Equal, %select2 This pattern is widely seen across the code: it is a canonical representation of three-ways comparators that return `-1`, `0` or `1` if `%a` is less, equal or greater than zero. In the result of transforms described in cases 1, 2, 3, the pair of `%c2` and `%select1` gets transformed into something different (with shifts, casts and different bit operations). So the three-way comparison pattern cannot be recognized anymore. This patch removes the transforms that make us replace select by comparison against zero with all this bit magic. We want to prefer selects over random bit magic as a more canonical form of doing that: select has more transparent semantics and other parts of InstCombine make use it rather than try to recognize that some sequence of non-trivial bit instructions actually represents a select by comparison against zero. It is codegen's work to turn selects into bit operations in the end of pipeline to calculate it efficiently if shifts are faster than cmoves, but doing so too early has no benifits and has obvious pessimization of other pattern matchers within instcombine. In this patch we only stop harmful transforms from happening. The code that turns all this bit magic back to selects will go in a separate patch.

Currently, when we process th InstCombine tends to recognize patterns like %cmp = icmp slt i64 %xiA %x, 0 %select = select i1 %cmp, i32 -1iB %A, 32 1iB %B We handle it in a general case with power of two being in the 3rd pard of selectas bit-test against highest bit, and convert it into one of multiple shift-based patterns the generated code for this case looks likewhich may look differently depending on types `iA` and `iB` and values of `%A` and `%B`. It only happens if `%A` and `%B` are constants. We observe at least three possible sutiatons: Case 1: %1 = lshr i64 %x%c2 = icmp slt %a, 620 %2 = trunc i64 %1 to i32%select1 = select %c2, -1, %Greater converts into (%a s>> 31) | %Greater Case 2: %3 = and%c2 = icmp slt i32 %2a, 20 %4 = xor%select1 = select i1 %c2, i32 %3Less, 2i32 %Greater converts into %5 = add nsw i32 %4, -1 However we have a smarter logic specifically with comparison with zero in foldSelectInstWithICmp(%a s>> 31) - (%Less - %Greater) + %Greater which did not apply because of type mismatch between `%x` and `1`.or, if it is the equivalent, If we lift the restriction andto handle this case separately, we end up with a better pattern: (%a s>> 31) - (%Less - %Greater) | %Greater Case 3: %1 = ashr%c2 = icmp slt i64 %xa, 630 %2 = trunc i64 %1 to%select1 = select i1 %c2, i32 %Less, i32 %Greater converts to %3 = or(trunc (%a s>> 63) to i32 %2, 1) - (%Less - %Greater) + %Greater This is 2 instructions less than what we have nowThere are possibly more variatons of this. The general idea is that select by comparison with `0` or `-1` gets transformed into multiple different patterns, and very small changes in conditions and constants may change this pattern. There is no clear benefits of that transforms, but the obvious downside of them is decanonicalization. For example, we have a matcher of three-ways comparison that expects to see the pattern of the following form: %c1 = icmp eq %a, 0 %c2 = icmp slt %a, 0 %select1 = select %c2, %Less, %Greater %select2 = select %c1, %Equal, %select2 This pattern is widely seen across the code: it is a canonical representation of three-ways comparators that return `-1`, `0` or `1` if `%a` is less, equal or greater than zero. In the result of transforms described in cases 1, 2, 3, the pair of `%c2` and `%select1` gets transformed into something different (with shifts, casts and different bit operations). So the three-way comparison pattern cannot be recognized anymore. This patch relaxmoves the restricton on types, allowing now `%x` be wider than the result of select.transforms that make us replace select by comparison against zero with all this bit We can in theory also allow `1` to be wider (no functional problems with that),magic. however when IWe want to prefer selects over random bit magic as a more canonical form of doing that: select did, in some cases we end up with a worse code (see the comment). The problem looks irrelevanthas more transparent semantics and other parts of InstCombine make use it rather than try to recognize to this change which is a pure improvementhat some sequence of non-trivial bit instructions actually represents a select by comparison against zero. It is codegen's work to turn selects into bit operations in the end of pipeline to calculate it efficiently if shifts are faster than cmoves, but doing so too early has no benifits and has obvious pessimization of other pattern matchers within instcombine. In this patch we only stop harmful transforms from happening. We can yield the last restriction when other problematicThe code that turns all this bit magic back transforms are fixedto selects will go in a separate patch.