https://github.com/vpykhtin updated
https://github.com/llvm/llvm-project/pull/135180
>From b05781e3c0d7c7b06bf1cc6035b1e447d64a1bf1 Mon Sep 17 00:00:00 2001
From: Valery Pykhtin <valery.pykh...@amd.com>
Date: Thu, 10 Apr 2025 11:56:57 +0000
Subject: [PATCH] ssaupdaterbulk_add_phi_optimization
---
.../llvm/Transforms/Utils/SSAUpdaterBulk.h | 5 +-
llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp | 38 ++++++++++-
.../Transforms/Utils/SSAUpdaterBulkTest.cpp | 67 +++++++++++++++++++
3 files changed, 108 insertions(+), 2 deletions(-)
diff --git a/llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
b/llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
index b2cf29608f58b..d3dabaccc641f 100644
--- a/llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
+++ b/llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
@@ -13,7 +13,6 @@
#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H
#define LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H
-#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/PredIteratorCache.h"
@@ -77,6 +76,10 @@ class SSAUpdaterBulk {
/// vector.
void RewriteAllUses(DominatorTree *DT,
SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
+
+ /// Rewrite all uses and simplify the inserted PHI nodes.
+ /// Use this method to preserve behavior when replacing SSAUpdater.
+ void RewriteAndOptimizeAllUses(DominatorTree &DT);
};
} // end namespace llvm
diff --git a/llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp
b/llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp
index d7bf791a23edf..01704f04d45ee 100644
--- a/llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp
+++ b/llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp
@@ -11,13 +11,14 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
+#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
-#include "llvm/IR/Instructions.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
+#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
@@ -222,3 +223,38 @@ void SSAUpdaterBulk::RewriteAllUses(DominatorTree *DT,
}
}
}
+
+// Perform a single pass of simplification over the worklist of PHIs.
+static void simplifyPass(MutableArrayRef<PHINode *> Worklist,
+ const DataLayout &DL) {
+ for (PHINode *&PHI : Worklist) {
+ if (Value *Simplified = simplifyInstruction(PHI, DL)) {
+ PHI->replaceAllUsesWith(Simplified);
+ PHI->eraseFromParent();
+ PHI = nullptr; // Mark as removed.
+ }
+ }
+}
+
+static void deduplicatePass(ArrayRef<PHINode *> Worklist) {
+ SmallDenseMap<BasicBlock *, unsigned> BBs;
+ for (PHINode *PHI : Worklist) {
+ if (PHI)
+ ++BBs[PHI->getParent()];
+ }
+
+ for (auto [BB, NumNewPHIs] : BBs) {
+ auto FirstExistingPN = std::next(BB->phis().begin(), NumNewPHIs);
+ EliminateNewDuplicatePHINodes(BB, FirstExistingPN);
+ }
+}
+
+void SSAUpdaterBulk::RewriteAndOptimizeAllUses(DominatorTree &DT) {
+ SmallVector<PHINode *, 4> PHIs;
+ RewriteAllUses(&DT, &PHIs);
+ if (PHIs.empty())
+ return;
+
+ simplifyPass(PHIs, PHIs.front()->getParent()->getDataLayout());
+ deduplicatePass(PHIs);
+}
diff --git a/llvm/unittests/Transforms/Utils/SSAUpdaterBulkTest.cpp
b/llvm/unittests/Transforms/Utils/SSAUpdaterBulkTest.cpp
index 841f44cf6bfed..6f58fe6d3a44a 100644
--- a/llvm/unittests/Transforms/Utils/SSAUpdaterBulkTest.cpp
+++ b/llvm/unittests/Transforms/Utils/SSAUpdaterBulkTest.cpp
@@ -308,3 +308,70 @@ TEST(SSAUpdaterBulk, TwoBBLoop) {
EXPECT_EQ(Phi->getIncomingValueForBlock(Entry), ConstantInt::get(I32Ty, 0));
EXPECT_EQ(Phi->getIncomingValueForBlock(Loop), I);
}
+
+TEST(SSAUpdaterBulk, SimplifyPHIs) {
+ const char *IR = R"(
+ define void @main(i32 %val, i1 %cond) {
+ entry:
+ br i1 %cond, label %left, label %right
+ left:
+ %add = add i32 %val, 1
+ br label %exit
+ right:
+ %sub = sub i32 %val, 1
+ br label %exit
+ exit:
+ %phi = phi i32 [ %sub, %right ], [ %add, %left ]
+ %cmp = icmp slt i32 0, 42
+ ret void
+ }
+ )";
+
+ llvm::LLVMContext Context;
+ llvm::SMDiagnostic Err;
+ std::unique_ptr<llvm::Module> M = llvm::parseAssemblyString(IR, Err,
Context);
+ ASSERT_NE(M, nullptr) << "Failed to parse IR: " << Err.getMessage();
+
+ Function *F = M->getFunction("main");
+ auto *Entry = &F->getEntryBlock();
+ auto *Left = Entry->getTerminator()->getSuccessor(0);
+ auto *Right = Entry->getTerminator()->getSuccessor(1);
+ auto *Exit = Left->getSingleSuccessor();
+ auto *Val = &*F->arg_begin();
+ auto *Phi = &Exit->front();
+ auto *Cmp = &*std::next(Exit->begin());
+ auto *Add = &Left->front();
+ auto *Sub = &Right->front();
+
+ SSAUpdaterBulk Updater;
+ Type *I32Ty = Type::getInt32Ty(Context);
+
+ // Use %val directly instead of creating a phi.
+ unsigned ValVar = Updater.AddVariable("Val", I32Ty);
+ Updater.AddAvailableValue(ValVar, Left, Val);
+ Updater.AddAvailableValue(ValVar, Right, Val);
+ Updater.AddUse(ValVar, &Cmp->getOperandUse(0));
+
+ // Use existing %phi for %add and %sub values.
+ unsigned AddSubVar = Updater.AddVariable("AddSub", I32Ty);
+ Updater.AddAvailableValue(AddSubVar, Left, Add);
+ Updater.AddAvailableValue(AddSubVar, Right, Sub);
+ Updater.AddUse(AddSubVar, &Cmp->getOperandUse(1));
+
+ auto ExitSizeBefore = Exit->size();
+ DominatorTree DT(*F);
+ Updater.RewriteAndOptimizeAllUses(DT);
+
+#if 0 // Enable for debugging.
+ Exit->dump();
+ // Output:
+ // exit: ; preds = %right, %left
+ // %phi = phi i32 [ %sub, %right ], [ %add, %left ]
+ // %cmp = icmp slt i32 %val, %phi
+ // ret void
+#endif
+ EXPECT_EQ(Exit->size(), ExitSizeBefore);
+ ASSERT_EQ(&Exit->front(), Phi);
+ EXPECT_EQ(Val, Cmp->getOperand(0));
+ EXPECT_EQ(Phi, Cmp->getOperand(1));
+}
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
