Page MenuHomePhabricator

[AggresiveInstCombine] Added support of select and ShuffleVector to TruncInstCombine expression pattern
Needs ReviewPublic

Authored by aaboud on Jan 25 2018, 7:06 AM.

Details

Summary

Added to TruncInstCombine class the support of SelectInst and ShuffleVectorInst instructions.

Diff Detail

Event Timeline

aaboud created this revision.Jan 25 2018, 7:06 AM

I apologize for not noticing this before, but do all of the tests here fail in regular instcombine because there's an instruction that uses the same value more than once? Or are there more complicated patterns?

If it's just the simpler case (or even if it's not), can we enhance instcombine to catch those cases like this:

Index: lib/Transforms/InstCombine/InstCombineCasts.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCasts.cpp	(revision 323427)
+++ lib/Transforms/InstCombine/InstCombineCasts.cpp	(working copy)
@@ -184,8 +184,14 @@
   case Instruction::Shl:
   case Instruction::UDiv:
   case Instruction::URem: {
-    Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
-    Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
+    Value *LHS, *RHS;
+    if (I->getOperand(0) == I->getOperand(1)) {
+      // Don't create an unnecessary value if the operands are repeated.
+      LHS = RHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
+    } else {
+      LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
+      RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
+    }
     Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
     break;
   }
@@ -315,9 +321,12 @@
       I->getOperand(0)->getType() == Ty)
     return true;
 
-  // We can't extend or shrink something that has multiple uses: doing so would
-  // require duplicating the instruction in general, which isn't profitable.
-  if (!I->hasOneUse()) return false;
+  // We can't extend or shrink something that has multiple uses -- unless those
+  // multiple uses are all in the same instruction -- doing so would require
+  // duplicating the instruction which isn't profitable.
+  if (!I->hasOneUse())
+    if (any_of(I->users(), [&](User *U) { return U != I->user_back(); }))
+      return false;
 
   unsigned Opc = I->getOpcode();
   switch (Opc) {

I apologize for not noticing this before, but do all of the tests here fail in regular instcombine because there's an instruction that uses the same value more than once? Or are there more complicated patterns?

Maybe, the test I added are for the simple case, but there are more complicated cases.
Consider this example:

define void @multi_uses_add(i32 %X, i32 %Y) {
  %Ax = zext i32 %X to i64
  %Ay = zext i32 %Y to i64
  %B = add i64 %Ax, %Ay
  %C = mul i64 %B, %Ax
  %T = trunc i64 %C to i32
  call i32 @use32(i32 %T)
  ret void
}

Also, remember that I will be adding the PHINode, in the coming patches, then we need to handle this case:

    A
 /     \
B       C
 \     /
 PHINode
define void @multi_uses_add(i32 %X, i32 %Y) {
  %Ax = zext i32 %X to i64
  %Ay = zext i32 %Y to i64
  %B = add i64 %Ax, %Ay
  %C = mul i64 %B, %Ax
  %T = trunc i64 %C to i32
  call i32 @use32(i32 %T)
  ret void
}

That's too easy - instcombine gets that. I think you need at least one more intermediate binop to show a case that instcombine can't handle.

We need to make sure aggressive-instcombine is showing its unique capability in each test. If you agree that the case with a repeated op is just an oversight for instcombine, lets:

  1. Move the existing tests over to instcombine
  2. Fix instcombine
  3. Add more complex tests for aggressive-instcombine's current functionality
  4. Enhance aggressive-instcombine for more opcodes/patterns.

That's too easy - instcombine gets that. I think you need at least one more intermediate binop to show a case that instcombine can't handle.

You are right, I forgot that instcombine algorithm can handle zext/sext with multi use in case they have same type as trunc instruction destination type.
Here is a better test suggestion:

define void @multi_uses_add(i32 %X) {
  %A = zext i32 %X to i64
  %B = add i64 %A, 5
  %M1 = mul i64 %B, 66
  %M2 = mul i64 %B, %A
  %C = and i64 %M1, %M2
  %T = trunc i64 %C to i32
  call i32 @use32(i32 %T)
  ret void
}

We need to make sure aggressive-instcombine is showing its unique capability in each test. If you agree that the case with a repeated op is just an oversight for instcombine, lets:

  1. Move the existing tests over to instcombine
  2. Fix instcombine

I agree that we should improve instcombine where ever it make sense, such as this case, but I am afraid that I have no time to do it myself.
So, if you would like to take this task, I will be happy to review the code.

  1. Add more complex tests for aggressive-instcombine's current functionality

Do you agree to the above example? I can duplicate it to handle all other instructions.

  1. Enhance aggressive-instcombine for more opcodes/patterns.

I will be adding more opcodes that trunc expression should support, and with each new opcode I will be adding more tests.
Also, I already added few tests that were driven from implementation bugs due to missing handle of constant expressions.
see https://reviews.llvm.org/D42622.

Yes, I'll take the task of fixing the gap in instcombine. (Hoping it's not too much more than what I posted already.)

For the tests, we don't need the extra-use helper function? The thing that regular instcombine can't see through is when an intermediate value has multiple uses:

define i32 @multi_uses_add(i32 %X) {
    %A = zext i32 %X to i64
    %B = add i64 %A, 5
    %M = mul i64 %B, %A
    %C = and i64 %B, %M
    %T = trunc i64 %C to i32
    ret i32 %T
  }