diff --git a/mlir/include/mlir/Analysis/Liveness.h b/mlir/include/mlir/Analysis/Liveness.h --- a/mlir/include/mlir/Analysis/Liveness.h +++ b/mlir/include/mlir/Analysis/Liveness.h @@ -129,6 +129,16 @@ /// provided (must be referenced in this block). Operation *getEndOperation(Value value, Operation *startOperation) const; + /// Get the set of values that are currently live (if any) for the current op. + /// This analysis takes an expansive view of "live" in that if a value is + /// defined by or within the operation or is fully consumed (as in last user) + /// by or within the operation the value is considered "live". The values in + /// the list are not ordered. + /// + /// This check is quite expensive as it does not cache the results of the + /// computation, so the currently live values have to be recomputed for each op. + ValueSetT currentlyLiveValues(Operation *op) const; + private: /// The underlying block. Block *block = nullptr; diff --git a/mlir/lib/Analysis/Liveness.cpp b/mlir/lib/Analysis/Liveness.cpp --- a/mlir/lib/Analysis/Liveness.cpp +++ b/mlir/lib/Analysis/Liveness.cpp @@ -307,7 +307,7 @@ os << "\n"; // Print liveness intervals. - os << "// --- BeginLiveness"; + os << "// --- BeginLivenessIntervals"; for (Operation &op : *block) { if (op.getNumResults() < 1) continue; @@ -327,7 +327,21 @@ } } } - os << "\n// --- EndLiveness\n"; + os << "\n// --- EndLivenessIntervals\n"; + + // Print currently live values. + os << "// --- BeginCurrentlyLive\n"; + for (Operation &op : *block) { + auto currentlyLive = liveness->currentlyLiveValues(&op); + if (currentlyLive.empty()) + continue; + os << "// "; + op.print(os); + os << " ["; + printValueRefs(currentlyLive); + os << "\b]\n"; + } + os << "// --- EndCurrentlyLive\n"; }); os << "// -------------------\n"; } @@ -377,3 +391,65 @@ } return endOperation; } + +/// Return the values that are currently live as of the given operation. +LivenessBlockInfo::ValueSetT +LivenessBlockInfo::currentlyLiveValues(Operation *op) const { + ValueSetT liveSet; + + // Given a value, check which ops are within its live range. For each of + // those ops, add the value to the set of live values as-of that op. + auto addValueToCurrentlyLiveSets = [&](Value value) { + // Determine the live range of this value inside this block. + Operation *startOfLiveRange = value.getDefiningOp(); + Operation *endOfLiveRange = nullptr; + // If it's a live in or a block argument, then the start is the beginning + // of the block. + if (isLiveIn(value) || value.isa()) + startOfLiveRange = &block->front(); + else + startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange); + + // If it's a live out, then the end is the back of the block. + if (isLiveOut(value)) + endOfLiveRange = &block->back(); + + // We must have at least a startOfLiveRange at this point. Given this, we + // can use the existing getEndOperation to find the end of the live range. + if (startOfLiveRange && !endOfLiveRange) + endOfLiveRange = getEndOperation(value, startOfLiveRange); + + assert(endOfLiveRange && "Must have endOfLiveRange at this point!"); + // If this op is within the live range, insert the value into the set. + if (!(op->isBeforeInBlock(startOfLiveRange) || + endOfLiveRange->isBeforeInBlock(op))) + liveSet.insert(value); + }; + + // Handle block arguments if any. + for (Value arg : block->getArguments()) + addValueToCurrentlyLiveSets(arg); + + // Handle live-ins and live outs. + for (Value in : inValues) + addValueToCurrentlyLiveSets(in); + for (Value out : outValues) + addValueToCurrentlyLiveSets(out); + + // Now walk the block and handle all values used in the block and values + // defined by the block. + block->walk([&](Operation *walkOp) { + for (auto operand : walkOp->getOperands()) + addValueToCurrentlyLiveSets(operand); + for (auto result : walkOp->getResults()) + addValueToCurrentlyLiveSets(result); + + // Stop iterating if we hit the op in question. + if (op == walkOp) + return WalkResult::interrupt(); + + return WalkResult::advance(); + }); + + return liveSet; +} diff --git a/mlir/test/Analysis/test-liveness.mlir b/mlir/test/Analysis/test-liveness.mlir --- a/mlir/test/Analysis/test-liveness.mlir +++ b/mlir/test/Analysis/test-liveness.mlir @@ -5,8 +5,10 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: BeginLivenessIntervals + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK-NEXT: EndCurrentlyLive return } @@ -17,18 +19,28 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut: arg0@0 arg1@0 - // CHECK-NEXT: BeginLiveness - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: BeginLivenessIntervals + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: cf.br + // CHECK-SAME: arg0@0 arg1@0 + // CHECK-NEXT: EndCurrentlyLive cf.br ^exit ^exit: // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg0@0 arg1@0 // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK: val_2 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: return - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg1@0 val_2 + // CHECK: return + // CHECK-SAME: val_2 + // CHECK-NEXT EndCurrentlyLive %result = arith.addi %arg0, %arg1 : i32 return %result : i32 } @@ -40,28 +52,47 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut: arg1@0 arg2@0 - // CHECK-NEXT: BeginLiveness - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: BeginLivenessIntervals + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: cf.cond_br + // CHECK-SAME: arg0@0 arg1@0 arg2@0 + // CHECK-NEXT: EndCurrentlyLive cf.cond_br %cond, ^bb1, ^bb2 ^bb1: // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg1@0 arg2@0 // CHECK-NEXT: LiveOut: arg1@0 arg2@0 + // CHECK: BeginCurrentlyLive + // CHECK: cf.br + // COM: arg0@0 had its last user in the previous block. + // CHECK-SAME: arg1@0 arg2@0 + // CHECK-NEXT: EndCurrentlyLive cf.br ^exit ^bb2: // CHECK: Block: 2 // CHECK-NEXT: LiveIn: arg1@0 arg2@0 // CHECK-NEXT: LiveOut: arg1@0 arg2@0 + // CHECK: BeginCurrentlyLive + // CHECK: cf.br + // CHECK-SAME: arg1@0 arg2@0 + // CHECK-NEXT: EndCurrentlyLive cf.br ^exit ^exit: // CHECK: Block: 3 // CHECK-NEXT: LiveIn: arg1@0 arg2@0 // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK: val_3 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: return - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg1@0 arg2@0 val_3 + // CHECK: return + // CHECK-SAME: val_3 + // CHECK-NEXT: EndCurrentlyLive %result = arith.addi %arg1, %arg2 : i32 return %result : i32 } @@ -73,24 +104,36 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut: arg1@0 + // CHECK: BeginCurrentlyLive + // CHECK: arith.constant + // CHECK-SAME: arg0@0 arg1@0 val_2 + // CHECK: cf.br + // CHECK-SAME: arg0@0 arg1@0 val_2 + // CHECK-NEXT: EndCurrentlyLive %const0 = arith.constant 0 : i32 cf.br ^loopHeader(%const0, %arg0 : i32, i32) ^loopHeader(%counter : i32, %i : i32): // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg1@0 // CHECK-NEXT: LiveOut: arg1@0 arg0@1 - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_5 // CHECK-NEXT: %2 = arith.cmpi // CHECK-NEXT: cf.cond_br - // CHECK-NEXT: EndLiveness + // CHECK-NEXT: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.cmpi + // CHECK-SAME: arg1@0 arg0@1 arg1@1 val_5 + // CHECK: cf.cond_br + // CHECK-SAME: arg1@0 arg0@1 arg1@1 val_5 + // CHECK-NEXT: EndCurrentlyLive %lessThan = arith.cmpi slt, %counter, %arg1 : i32 cf.cond_br %lessThan, ^loopBody(%i : i32), ^exit(%i : i32) ^loopBody(%val : i32): // CHECK: Block: 2 // CHECK-NEXT: LiveIn: arg1@0 arg0@1 // CHECK-NEXT: LiveOut: arg1@0 - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_7 // CHECK-NEXT: %c // CHECK-NEXT: %4 = arith.addi @@ -99,7 +142,17 @@ // CHECK-NEXT: %4 = arith.addi // CHECK-NEXT: %5 = arith.addi // CHECK-NEXT: cf.br - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.constant + // CHECK-SAME: arg1@0 arg0@1 arg0@2 val_7 + // CHECK: arith.addi + // CHECK-SAME: arg1@0 arg0@1 arg0@2 val_7 val_8 + // CHECK: arith.addi + // CHECK-SAME: arg1@0 arg0@1 val_7 val_8 val_9 + // CHECK: cf.br + // CHECK-SAME: arg1@0 val_8 val_9 + // CHECK-NEXT: EndCurrentlyLive %const1 = arith.constant 1 : i32 %inc = arith.addi %val, %const1 : i32 %inc2 = arith.addi %counter, %const1 : i32 @@ -108,6 +161,12 @@ // CHECK: Block: 3 // CHECK-NEXT: LiveIn: arg1@0 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg1@0 arg0@3 val_11 + // CHECK: return + // CHECK-SAME: val_11 + // CHECK-NEXT: EndCurrentlyLive %result = arith.addi %sum, %arg1 : i32 return %result : i32 } @@ -119,7 +178,7 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut: arg2@0 val_9 val_10 - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_4 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: %c @@ -156,7 +215,25 @@ // CHECK-NEXT: %5 = arith.addi // CHECK-NEXT: cf.cond_br // CHECK-NEXT: %7 - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg3@0 val_4 + // CHECK: arith.constant + // CHECK-SAME: arg0@0 arg2@0 arg3@0 val_4 val_5 + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg2@0 arg3@0 val_4 val_5 val_6 + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg2@0 arg3@0 val_4 val_5 val_6 val_7 + // CHECK: arith.muli + // CHECK-SAME: arg0@0 arg2@0 val_4 val_5 val_6 val_7 val_8 + // CHECK: arith.muli + // CHECK-SAME: arg0@0 arg2@0 val_5 val_7 val_8 val_9 + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg2@0 val_5 val_9 val_10 + // CHECK: cf.cond_br + // CHECK-SAME: arg0@0 arg2@0 val_9 val_10 + // CHECK-NEXT: EndCurrentlyLive %0 = arith.addi %arg1, %arg2 : i32 %const1 = arith.constant 1 : i32 %1 = arith.addi %const1, %arg2 : i32 @@ -170,6 +247,14 @@ // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg2@0 val_9 // CHECK-NEXT: LiveOut: arg2@0 + // CHECK: BeginCurrentlyLive + // CHECK: arith.constant + // CHECK-SAME: arg2@0 val_9 + // CHECK: arith.muli + // CHECK-SAME: arg2@0 val_9 + // CHECK: cf.br + // CHECK-SAME: arg2@0 + // CHECK-NEXT: EndCurrentlyLive %const4 = arith.constant 4 : i32 %6 = arith.muli %4, %const4 : i32 cf.br ^exit(%6 : i32) @@ -178,6 +263,14 @@ // CHECK: Block: 2 // CHECK-NEXT: LiveIn: arg2@0 val_9 val_10 // CHECK-NEXT: LiveOut: arg2@0 + // CHECK: BeginCurrentlyLive + // CHECK: arith.muli + // CHECK-SAME: arg2@0 val_9 val_10 + // CHECK: arith.addi + // CHECK-SAME: arg2@0 + // CHECK: cf.br + // CHECK-SAME: arg2@0 + // CHECK: EndCurrentlyLive %7 = arith.muli %4, %5 : i32 %8 = arith.addi %4, %arg2 : i32 cf.br ^exit(%8 : i32) @@ -186,6 +279,12 @@ // CHECK: Block: 3 // CHECK-NEXT: LiveIn: arg2@0 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg2@0 + // CHECK: return + // CHECK-NOT: arg2@0 + // CHECK: EndCurrentlyLive %result = arith.addi %sum, %arg2 : i32 return %result : i32 } @@ -201,7 +300,7 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_7 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: %1 = arith.addi @@ -212,13 +311,35 @@ // CHECK-NEXT: %1 = arith.addi // CHECK-NEXT: scf.for // CHECK: // func.return %1 - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7 + // CHECK: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8 + // CHECK: scf.for + // CHECK-NEXT: arith.addi + // CHECK-NEXT: arith.addi + // CHECK-NEXT: memref.store + // COM: The values that are live/consumed in the loop body are considered live for the loop. + // CHECK-NEXT: arg5@0 arg6@0 val_7 val_8 val_10 val_11 + // CHECK: return + // CHECK-SAME: val_8 + // CHECK-NEXT: EndCurrentlyLive %0 = arith.addi %arg3, %arg4 : i32 %1 = arith.addi %arg4, %arg5 : i32 scf.for %arg6 = %arg0 to %arg1 step %arg2 { // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg5@0 arg6@0 val_7 arg0@1 val_10 + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg6@0 val_7 val_10 val_11 + // CHECK-NEXT: memref.store + // CHECK-SAME: arg6@0 val_11 + // CHECK-NEXT: EndCurrentlyLive %2 = arith.addi %0, %arg5 : i32 %3 = arith.addi %2, %0 : i32 memref.store %3, %buffer[] : memref @@ -234,7 +355,7 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_7 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: %1 = arith.addi @@ -246,7 +367,21 @@ // CHECK-NEXT: %1 = arith.addi // CHECK-NEXT: scf.for // CHECK: // func.return %1 - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7 + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8 + // CHECK-NEXT: scf.for {{.*}} + // CHECK-NEXT: arith.addi + // CHECK-NEXT: scf.for {{.*}} { + // CHECK-NEXT: arith.addi + // CHECK-NEXT: memref.store + // CHECK-NEXT: } + // CHECK-NEXT: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 val_8 val_10 val_12 + // CHECK-NEXT: return + // CHECK-SAME: val_8 %arg0 : index, %arg1 : index, %arg2 : index, %arg3 : i32, %arg4 : i32, %arg5 : i32, %buffer : memref) -> i32 { @@ -256,14 +391,28 @@ // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 // CHECK-NEXT: LiveOut:{{ *$}} - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_10 // CHECK-NEXT: %2 = arith.addi // CHECK-NEXT: scf.for // CHECK: // %3 = arith.addi - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 arg0@1 val_10 + // CHECK-NEXT: scf.for {{.*}} + // CHECK-NEXT: arith.addi + // CHECK-NEXT: memref.store + // CHECK-NEXT: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_10 val_12 %2 = arith.addi %0, %arg5 : i32 scf.for %arg7 = %arg0 to %arg1 step %arg2 { + // CHECK: Block: 2 + // CHECK: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg6@0 val_7 val_10 arg0@2 val_12 + // CHECK-NEXT: memref.store + // CHECK-SAME: arg6@0 val_12 + // CHECK: EndCurrentlyLive %3 = arith.addi %2, %0 : i32 memref.store %3, %buffer[] : memref } @@ -279,7 +428,7 @@ // CHECK: Block: 0 // CHECK-NEXT: LiveIn:{{ *$}} // CHECK-NEXT: LiveOut: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8 - // CHECK-NEXT: BeginLiveness + // CHECK-NEXT: BeginLivenessIntervals // CHECK-NEXT: val_7 // CHECK-NEXT: %0 = arith.addi // CHECK-NEXT: %1 = arith.addi @@ -288,7 +437,18 @@ // CHECK-NEXT: %2 = arith.addi // CHECK-NEXT: scf.for // CHECK: // %2 = arith.addi - // CHECK: EndLiveness + // CHECK: EndLivenessIntervals + // CHECK-NEXT: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7 + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8 + // CHECK-NEXT: scf.for + // COM: Skipping the body of the scf.for... + // CHECK: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 val_8 val_10 + // CHECK-NEXT: cf.br + // CHECK-SAME: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8 + // CHECK-NEXT: EndCurrentlyLive %arg0 : index, %arg1 : index, %arg2 : index, %arg3 : i32, %arg4 : i32, %arg5 : i32, %buffer : memref) -> i32 { @@ -298,6 +458,12 @@ // CHECK: Block: 1 // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg5@0 arg6@0 val_7 arg0@1 val_10 + // CHECK-NEXT: memref.store + // CHECK-SAME: arg6@0 val_10 + // CHECK-NEXT: EndCurrentlyLive %2 = arith.addi %0, %arg5 : i32 memref.store %2, %buffer[] : memref } @@ -307,10 +473,22 @@ // CHECK: Block: 2 // CHECK-NEXT: LiveIn: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK: scf.for + // CHECK: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8 val_12 + // CHECK-NEXT: return + // CHECK-SAME: val_8 + // CHECK-NEXT: EndCurrentlyLive scf.for %arg7 = %arg0 to %arg1 step %arg2 { // CHECK: Block: 3 // CHECK-NEXT: LiveIn: arg6@0 val_7 val_8 // CHECK-NEXT: LiveOut:{{ *$}} + // CHECK: BeginCurrentlyLive + // CHECK-NEXT: arith.addi + // CHECK-SAME: arg6@0 val_7 val_8 arg0@3 val_12 + // CHECK-NEXT: memref.store + // CHECK-SAME: arg6@0 val_12 + // CHECK-NEXT: EndCurrentlyLive %2 = arith.addi %0, %1 : i32 memref.store %2, %buffer[] : memref }