aboutsummaryrefslogtreecommitdiff
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/lib/Transforms/Scalar/LICM.cpp26
-rw-r--r--llvm/test/Transforms/LICM/hoist-binop.ll161
2 files changed, 171 insertions, 16 deletions
diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp
index 5cf7c25..23e9c70 100644
--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -2803,15 +2803,14 @@ static bool hoistMulAddAssociation(Instruction &I, Loop &L,
/// Reassociate associative binary expressions of the form
///
-/// 1. "(LV op C1) op C2" ==> "LV op (C1 op C2)" if op is an associative BinOp
-/// 2. "(C1 op LV) op C2" ==> "LV op (C1 op C2)" if op is a commutative BinOp
+/// 1. "(LV op C1) op C2" ==> "LV op (C1 op C2)"
+/// 2. "(C1 op LV) op C2" ==> "LV op (C1 op C2)"
+/// 3. "C2 op (C1 op LV)" ==> "LV op (C1 op C2)"
+/// 4. "C2 op (LV op C1)" ==> "LV op (C1 op C2)"
///
-/// where LV is a loop variant, and C1 and C2 are loop invariants that we want
-/// to hoist.
-///
-/// TODO: This can be extended to more cases such as
-/// 1. "C1 op (C2 op LV)" ==> "(C1 op C2) op LV" if op an associative BinOp
-/// 2. "C1 op (LV op C2)" ==> "(C1 op C2) op LV" if op is a commutative BinOp
+/// where op is an associative BinOp, LV is a loop variant, and C1 and C2 are
+/// loop invariants that we want to hoist, noting that associativity implies
+/// commutativity.
static bool hoistBOAssociation(Instruction &I, Loop &L,
ICFLoopSafetyInfo &SafetyInfo,
MemorySSAUpdater &MSSAU, AssumptionCache *AC,
@@ -2825,19 +2824,20 @@ static bool hoistBOAssociation(Instruction &I, Loop &L,
if (Opcode != Instruction::Add && Opcode != Instruction::Mul)
return false;
- auto *BO0 = dyn_cast<BinaryOperator>(BO->getOperand(0));
+ bool LVInRHS = L.isLoopInvariant(BO->getOperand(0));
+ auto *BO0 = dyn_cast<BinaryOperator>(BO->getOperand(LVInRHS));
if (!BO0 || BO0->getOpcode() != Opcode || !BO0->isAssociative() ||
BO0->hasNUsesOrMore(3))
return false;
Value *LV = BO0->getOperand(0);
Value *C1 = BO0->getOperand(1);
- Value *C2 = BO->getOperand(1);
+ Value *C2 = BO->getOperand(!LVInRHS);
- if (L.isLoopInvariant(LV) && !L.isLoopInvariant(C1)) {
- assert(BO0->isCommutative() && "Associativity implies commutativity");
+ assert(BO->isCommutative() && BO0->isCommutative() &&
+ "Associativity implies commutativity");
+ if (L.isLoopInvariant(LV) && !L.isLoopInvariant(C1))
std::swap(LV, C1);
- }
if (L.isLoopInvariant(LV) || !L.isLoopInvariant(C1) || !L.isLoopInvariant(C2))
return false;
diff --git a/llvm/test/Transforms/LICM/hoist-binop.ll b/llvm/test/Transforms/LICM/hoist-binop.ll
index b0ee45a..a840e24 100644
--- a/llvm/test/Transforms/LICM/hoist-binop.ll
+++ b/llvm/test/Transforms/LICM/hoist-binop.ll
@@ -67,8 +67,8 @@ loop:
br label %loop
}
-
-; Hoist ADD and copy NUW if both ops have it. Commutative version.
+; Hoist ADD and copy NUW if both ops have it.
+; Version where operands are commuted.
define void @add_nuw_comm(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_nuw_comm(
; CHECK-NEXT: entry:
@@ -92,6 +92,83 @@ loop:
br label %loop
}
+; Hoist ADD and copy NUW if both ops have it.
+; Another version where operands are commuted.
+define void @add_nuw_comm2(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @add_nuw_comm2(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = add nuw i64 [[C1:%.*]], [[C2:%.*]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = add nuw i64 [[INDEX]], [[C1]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = add nuw i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = add nuw i64 %index, %c1
+ call void @use(i64 %step.add)
+ %index.next = add nuw i64 %c2, %step.add
+ br label %loop
+}
+
+; Hoist ADD and copy NUW if both ops have it.
+; Another version where operands are commuted.
+define void @add_nuw_comm3(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @add_nuw_comm3(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = add nuw i64 [[C1:%.*]], [[C2:%.*]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = add nuw i64 [[C1]], [[INDEX]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = add nuw i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = add nuw i64 %c1, %index
+ call void @use(i64 %step.add)
+ %index.next = add nuw i64 %c2, %step.add
+ br label %loop
+}
+
+; Hoist ADD and copy NUW if both ops have it.
+; A version where the LHS and RHS of the outer BinOp are BinOps.
+define void @add_nuw_twobinops(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @add_nuw_twobinops(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[C2_PLUS_2:%.*]] = add nuw i64 [[C2:%.*]], 2
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = add nuw i64 [[C1:%.*]], [[C2_PLUS_2]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = add nuw i64 [[C1]], [[INDEX]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = add nuw i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = add nuw i64 %c1, %index
+ call void @use(i64 %step.add)
+ %c2.plus.2 = add nuw i64 %c2, 2
+ %index.next = add nuw i64 %step.add, %c2.plus.2
+ br label %loop
+}
+
; Hoist MUL and drop NUW even if both ops have it.
define void @mul_nuw(i64 %c1, i64 %c2) {
; CHECK-LABEL: @mul_nuw(
@@ -116,7 +193,8 @@ loop:
br label %loop
}
-; Hoist MUL and drop NUW even if both ops have it. Commutative version.
+; Hoist MUL and drop NUW even if both ops have it.
+; Version where operands are commuted.
define void @mul_nuw_comm(i64 %c1, i64 %c2) {
; CHECK-LABEL: @mul_nuw_comm(
; CHECK-NEXT: entry:
@@ -140,6 +218,83 @@ loop:
br label %loop
}
+; Hoist MUL and drop NUW even if both ops have it.
+; Another version where operands are commuted.
+define void @mul_nuw_comm2(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @mul_nuw_comm2(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = mul i64 [[C1:%.*]], [[C2:%.*]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = mul nuw i64 [[INDEX]], [[C1]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = mul i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = mul nuw i64 %index, %c1
+ call void @use(i64 %step.add)
+ %index.next = mul nuw i64 %c2, %step.add
+ br label %loop
+}
+
+; Hoist MUL and drop NUW even if both ops have it.
+; Another version where operands are commuted.
+define void @mul_nuw_comm3(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @mul_nuw_comm3(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = mul i64 [[C1:%.*]], [[C2:%.*]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = mul nuw i64 [[C1]], [[INDEX]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = mul i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = mul nuw i64 %c1, %index
+ call void @use(i64 %step.add)
+ %index.next = mul nuw i64 %c2, %step.add
+ br label %loop
+}
+
+; Hoist MUL and drop NUW even if both ops have it.
+; A version where the LHS and RHS of the outer BinOp are BinOps.
+define void @mul_nuw_twobinops(i64 %c1, i64 %c2) {
+; CHECK-LABEL: @mul_nuw_twobinops(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[C2_PLUS_2:%.*]] = add nuw i64 [[C2:%.*]], 2
+; CHECK-NEXT: [[INVARIANT_OP:%.*]] = mul i64 [[C1:%.*]], [[C2_PLUS_2]]
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
+; CHECK-NEXT: [[STEP_ADD:%.*]] = mul nuw i64 [[C1]], [[INDEX]]
+; CHECK-NEXT: call void @use(i64 [[STEP_ADD]])
+; CHECK-NEXT: [[INDEX_NEXT_REASS]] = mul i64 [[INDEX]], [[INVARIANT_OP]]
+; CHECK-NEXT: br label [[LOOP]]
+;
+entry:
+ br label %loop
+
+loop:
+ %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
+ %step.add = mul nuw i64 %c1, %index
+ call void @use(i64 %step.add)
+ %c2.plus.2 = add nuw i64 %c2, 2
+ %index.next = mul nuw i64 %step.add, %c2.plus.2
+ br label %loop
+}
+
; Hoist ADD but don't copy NUW if only one op has it.
define void @add_no_nuw(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_no_nuw(
generated by cgit v1.1 at 2025-08-03 09:30:45 +0000