[MergeICmp] Split blocks that do other work.
Summary:
We do not try to move the instructions and split the block till we
know the blocks can be split, i.e. BCE-cmp-insts can be separated from
non-BCE-cmp-insts.
Reviewers: davide, courbet
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D44443
llvm-svn: 329564
diff --git a/llvm/lib/Transforms/Scalar/MergeICmps.cpp b/llvm/lib/Transforms/Scalar/MergeICmps.cpp
index e24ad3e..5c630d9 100644
--- a/llvm/lib/Transforms/Scalar/MergeICmps.cpp
+++ b/llvm/lib/Transforms/Scalar/MergeICmps.cpp
@@ -110,6 +110,10 @@
}
// A basic block with a comparison between two BCE atoms.
+// The block might do extra work besides the atom comparison, in which case
+// doesOtherWork() returns true. Under some conditions, the block can be
+// split into the atom comparison part and the "other work" part
+// (see canSplit()).
// Note: the terminology is misleading: the comparison is symmetric, so there
// is no real {l/r}hs. What we want though is to have the same base on the
// left (resp. right), so that we can detect consecutive loads. To ensure this
@@ -144,19 +148,83 @@
// Returns true if the block does other works besides comparison.
bool doesOtherWork() const;
+ // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
+ // instructions in the block.
+ bool canSplit() const;
+
+ // Return true if this all the relevant instructions in the BCE-cmp-block can
+ // be sunk below this instruction. By doing this, we know we can separate the
+ // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
+ // block.
+ bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &) const;
+
+ // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
+ // instructions. Split the old block and move all non-BCE-cmp-insts into the
+ // new parent block.
+ void split(BasicBlock *NewParent) const;
+
// The basic block where this comparison happens.
BasicBlock *BB = nullptr;
// The ICMP for this comparison.
ICmpInst *CmpI = nullptr;
// The terminating branch.
BranchInst *BranchI = nullptr;
+ // The block requires splitting.
+ bool RequireSplit = false;
- private:
+private:
BCEAtom Lhs_;
BCEAtom Rhs_;
int SizeBits_ = 0;
};
+bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
+ DenseSet<Instruction *> &BlockInsts) const {
+ // If this instruction has side effects and its in middle of the BCE cmp block
+ // instructions, then bail for now.
+ // TODO: use alias analysis to tell whether there is real interference.
+ if (Inst->mayHaveSideEffects())
+ return false;
+ // Make sure this instruction does not use any of the BCE cmp block
+ // instructions as operand.
+ for (auto BI : BlockInsts) {
+ if (is_contained(Inst->operands(), BI))
+ return false;
+ }
+ return true;
+}
+
+void BCECmpBlock::split(BasicBlock *NewParent) const {
+ DenseSet<Instruction *> BlockInsts(
+ {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
+ llvm::SmallVector<Instruction *, 4> OtherInsts;
+ for (Instruction &Inst : *BB) {
+ if (BlockInsts.count(&Inst))
+ continue;
+ assert(canSinkBCECmpInst(&Inst, BlockInsts) && "Split unsplittable block");
+ // This is a non-BCE-cmp-block instruction. And it can be separated
+ // from the BCE-cmp-block instruction.
+ OtherInsts.push_back(&Inst);
+ }
+
+ // Do the actual spliting.
+ for (Instruction *Inst : reverse(OtherInsts)) {
+ Inst->moveBefore(&*NewParent->begin());
+ }
+}
+
+bool BCECmpBlock::canSplit() const {
+ DenseSet<Instruction *> BlockInsts(
+ {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
+ for (Instruction &Inst : *BB) {
+ if (!BlockInsts.count(&Inst)) {
+ if (!canSinkBCECmpInst(&Inst, BlockInsts))
+ return false;
+ }
+ }
+ return true;
+}
+
bool BCECmpBlock::doesOtherWork() const {
AssertConsistent();
// All the instructions we care about in the BCE cmp block.
@@ -241,6 +309,17 @@
return {};
}
+static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
+ BCECmpBlock &Comparison) {
+ DEBUG(dbgs() << "Block '" << Comparison.BB->getName() << "': Found cmp of "
+ << Comparison.SizeBits() << " bits between "
+ << Comparison.Lhs().Base() << " + " << Comparison.Lhs().Offset
+ << " and " << Comparison.Rhs().Base() << " + "
+ << Comparison.Rhs().Offset << "\n");
+ DEBUG(dbgs() << "\n");
+ Comparisons.push_back(Comparison);
+}
+
// A chain of comparisons.
class BCECmpChain {
public:
@@ -266,9 +345,9 @@
// Merges the given comparison blocks into one memcmp block and update
// branches. Comparisons are assumed to be continguous. If NextBBInChain is
// null, the merged block will link to the phi block.
- static void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
- BasicBlock *const NextBBInChain, PHINode &Phi,
- const TargetLibraryInfo *const TLI);
+ void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
+ BasicBlock *const NextBBInChain, PHINode &Phi,
+ const TargetLibraryInfo *const TLI);
PHINode &Phi_;
std::vector<BCECmpBlock> Comparisons_;
@@ -295,12 +374,28 @@
DEBUG(dbgs() << "block '" << Comparison.BB->getName()
<< "' does extra work besides compare\n");
if (Comparisons.empty()) {
- // TODO(courbet): The initial block can do other things, and we should
- // split them apart in a separate block before the comparison chain.
- // Right now we just discard it and make the chain shorter.
- DEBUG(dbgs()
- << "ignoring initial block '" << Comparison.BB->getName()
- << "' that does extra work besides compare\n");
+ // This is the initial block in the chain, in case this block does other
+ // work, we can try to split the block and move the irrelevant
+ // instructions to the predecessor.
+ //
+ // If this is not the initial block in the chain, splitting it wont
+ // work.
+ //
+ // As once split, there will still be instructions before the BCE cmp
+ // instructions that do other work in program order, i.e. within the
+ // chain before sorting. Unless we can abort the chain at this point
+ // and start anew.
+ //
+ // NOTE: we only handle block with single predecessor for now.
+ if (Comparison.canSplit()) {
+ DEBUG(dbgs() << "Split initial block '" << Comparison.BB->getName()
+ << "' that does extra work besides compare\n");
+ Comparison.RequireSplit = true;
+ enqueueBlock(Comparisons, Comparison);
+ } else {
+ DEBUG(dbgs() << "ignoring initial block '" << Comparison.BB->getName()
+ << "' that does extra work besides compare\n");
+ }
continue;
}
// TODO(courbet): Right now we abort the whole chain. We could be
@@ -328,13 +423,7 @@
// We could still merge bb1 and bb2 though.
return;
}
- DEBUG(dbgs() << "Block '" << Comparison.BB->getName()<< "': Found cmp of "
- << Comparison.SizeBits() << " bits between "
- << Comparison.Lhs().Base() << " + " << Comparison.Lhs().Offset
- << " and " << Comparison.Rhs().Base() << " + "
- << Comparison.Rhs().Offset << "\n");
- DEBUG(dbgs() << "\n");
- Comparisons.push_back(Comparison);
+ enqueueBlock(Comparisons, Comparison);
}
// It is possible we have no suitable comparison to merge.
@@ -416,9 +505,11 @@
}
// Point the predecessors of the chain to the first comparison block (which is
- // the new entry point).
- if (EntryBlock_ != Comparisons_[0].BB)
+ // the new entry point) and update the entry block of the chain.
+ if (EntryBlock_ != Comparisons_[0].BB) {
EntryBlock_->replaceAllUsesWith(Comparisons_[0].BB);
+ EntryBlock_ = Comparisons_[0].BB;
+ }
// Effectively merge blocks.
int NumMerged = 1;
@@ -450,6 +541,14 @@
LLVMContext &Context = BB->getContext();
if (Comparisons.size() >= 2) {
+ // If there is one block that requires splitting, we do it now, i.e.
+ // just before we know we will collapse the chain. The instructions
+ // can be executed before any of the instructions in the chain.
+ auto C = std::find_if(Comparisons.begin(), Comparisons.end(),
+ [](const BCECmpBlock &B) { return B.RequireSplit; });
+ if (C != Comparisons.end())
+ C->split(EntryBlock_);
+
DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
const auto TotalSize =
std::accumulate(Comparisons.begin(), Comparisons.end(), 0,