From 33a1b73600d5305efd122e61926319a9db20414c Mon Sep 17 00:00:00 2001 From: Mandeep Singh Grang Date: Thu, 1 Jun 2017 18:36:24 +0000 Subject: [PredicateInfo] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet Summary: Sort OpsToRename before iterating to make iteration order deterministic. Thanks to Daniel Berlin for the sorting logic. Reviewers: dberlin, RKSimon, efriedma, davide Reviewed By: dberlin, davide Subscribers: sanjoy, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D33265 llvm-svn: 304447 --- llvm/lib/Transforms/Utils/PredicateInfo.cpp | 35 ++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'llvm/lib/Transforms/Utils/PredicateInfo.cpp') diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp index 8877aeafecd..9e71cba4f1b 100644 --- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp +++ b/llvm/lib/Transforms/Utils/PredicateInfo.cpp @@ -541,7 +541,40 @@ Value *PredicateInfo::materializeStack(unsigned int &Counter, // // TODO: Use this algorithm to perform fast single-variable renaming in // promotememtoreg and memoryssa. -void PredicateInfo::renameUses(SmallPtrSetImpl &OpsToRename) { +void PredicateInfo::renameUses(SmallPtrSetImpl &OpSet) { + // Sort OpsToRename since we are going to iterate it. + SmallVector OpsToRename(OpSet.begin(), OpSet.end()); + std::sort(OpsToRename.begin(), OpsToRename.end(), [&](const Value *A, + const Value *B) { + auto *ArgA = dyn_cast_or_null(A); + auto *ArgB = dyn_cast_or_null(B); + + // If A and B are args, order them based on their arg no. + if (ArgA && !ArgB) + return true; + if (ArgB && !ArgA) + return false; + if (ArgA && ArgB) + return ArgA->getArgNo() < ArgB->getArgNo(); + + // Else, A are B are instructions. + // If they belong to different BBs, order them by the dominance of BBs. + auto *AInst = cast(A); + auto *BInst = cast(B); + if (AInst->getParent() != BInst->getParent()) + return DT.dominates(AInst->getParent(), BInst->getParent()); + + // Else, A and B belong to the same BB. + // Order A and B by their dominance. + auto *BB = AInst->getParent(); + auto LookupResult = OBBMap.find(BB); + if (LookupResult != OBBMap.end()) + return LookupResult->second->dominates(AInst, BInst); + + auto Result = OBBMap.insert({BB, make_unique(BB)}); + return Result.first->second->dominates(AInst, BInst); + }); + ValueDFS_Compare Compare(OBBMap); // Compute liveness, and rename in O(uses) per Op. for (auto *Op : OpsToRename) { -- cgit v1.2.3