diff options
| -rw-r--r-- | include/llvm/Support/PatternMatch.h | 19 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombine.h | 2 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstructionCombining.cpp | 69 | ||||
| -rw-r--r-- | test/Transforms/InstCombine/malloc-free-delete.ll | 29 |
4 files changed, 119 insertions, 0 deletions
diff --git a/include/llvm/Support/PatternMatch.h b/include/llvm/Support/PatternMatch.h index 386380c6bc..9fbe4349b3 100644 --- a/include/llvm/Support/PatternMatch.h +++ b/include/llvm/Support/PatternMatch.h @@ -781,6 +781,25 @@ inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } // Matchers for control flow. // +struct br_match { + BasicBlock *&Succ; + br_match(BasicBlock *&Succ) + : Succ(Succ) { + } + + template<typename OpTy> + bool match(OpTy *V) { + if (BranchInst *BI = dyn_cast<BranchInst>(V)) + if (BI->isUnconditional()) { + Succ = BI->getSuccessor(0); + return true; + } + return false; + } +}; + +inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } + template<typename Cond_t> struct brc_match { Cond_t Cond; diff --git a/lib/Transforms/InstCombine/InstCombine.h b/lib/Transforms/InstCombine/InstCombine.h index a207bce0d5..38c636462c 100644 --- a/lib/Transforms/InstCombine/InstCombine.h +++ b/lib/Transforms/InstCombine/InstCombine.h @@ -76,6 +76,7 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner TargetLibraryInfo *TLI; bool MadeIRChange; LibCallSimplifier *Simplifier; + bool MinimizeSize; public: /// Worklist - All of the instructions that need to be simplified. InstCombineWorklist Worklist; @@ -87,6 +88,7 @@ public: static char ID; // Pass identification, replacement for typeid InstCombiner() : FunctionPass(ID), TD(0), Builder(0) { + MinimizeSize = false; initializeInstCombinerPass(*PassRegistry::getPassRegistry()); } diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index 5e4274c7f7..6f24cdd738 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -1475,6 +1475,62 @@ Instruction *InstCombiner::visitAllocSite(Instruction &MI) { return 0; } +/// \brief Move the call to free before a NULL test. +/// +/// Check if this free is accessed after its argument has been test +/// against NULL (property 0). +/// If yes, it is legal to move this call in its predecessor block. +/// +/// The move is performed only if the block containing the call to free +/// will be removed, i.e.: +/// 1. it has only one predecessor P, and P has two successors +/// 2. it contains the call and an unconditional branch +/// 3. its successor is the same as its predecessor's successor +/// +/// The profitability is out-of concern here and this function should +/// be called only if the caller knows this transformation would be +/// profitable (e.g., for code size). +static Instruction * +tryToMoveFreeBeforeNullTest(CallInst &FI) { + Value *Op = FI.getArgOperand(0); + BasicBlock *FreeInstrBB = FI.getParent(); + BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor(); + + // Validate part of constraint #1: Only one predecessor + // FIXME: We can extend the number of predecessor, but in that case, we + // would duplicate the call to free in each predecessor and it may + // not be profitable even for code size. + if (!PredBB) + return 0; + + // Validate constraint #2: Does this block contains only the call to + // free and an unconditional branch? + // FIXME: We could check if we can speculate everything in the + // predecessor block + if (FreeInstrBB->size() != 2) + return 0; + BasicBlock *SuccBB; + if (!match(FreeInstrBB->getTerminator(), m_UnconditionalBr(SuccBB))) + return 0; + + // Validate the rest of constraint #1 by matching on the pred branch. + TerminatorInst *TI = PredBB->getTerminator(); + BasicBlock *TrueBB, *FalseBB; + ICmpInst::Predicate Pred; + if (!match(TI, m_Br(m_ICmp(Pred, m_Specific(Op), m_Zero()), TrueBB, FalseBB))) + return 0; + if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE) + return 0; + + // Validate constraint #3: Ensure the null case just falls through. + if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB)) + return 0; + assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) && + "Broken CFG: missing edge from predecessor to successor"); + + FI.moveBefore(TI); + return &FI; +} Instruction *InstCombiner::visitFree(CallInst &FI) { @@ -1493,6 +1549,16 @@ Instruction *InstCombiner::visitFree(CallInst &FI) { if (isa<ConstantPointerNull>(Op)) return EraseInstFromFunction(FI); + // If we optimize for code size, try to move the call to free before the null + // test so that simplify cfg can remove the empty block and dead code + // elimination the branch. I.e., helps to turn something like: + // if (foo) free(foo); + // into + // free(foo); + if (MinimizeSize) + if (Instruction *I = tryToMoveFreeBeforeNullTest(FI)) + return I; + return 0; } @@ -2393,6 +2459,9 @@ public: bool InstCombiner::runOnFunction(Function &F) { TD = getAnalysisIfAvailable<DataLayout>(); TLI = &getAnalysis<TargetLibraryInfo>(); + // Minimizing size? + MinimizeSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, + Attribute::MinSize); /// Builder - This is an IRBuilder that automatically inserts new /// instructions into the worklist when they are created. diff --git a/test/Transforms/InstCombine/malloc-free-delete.ll b/test/Transforms/InstCombine/malloc-free-delete.ll index 4e3217dc2d..cd12b29b11 100644 --- a/test/Transforms/InstCombine/malloc-free-delete.ll +++ b/test/Transforms/InstCombine/malloc-free-delete.ll @@ -91,3 +91,32 @@ define void @test5(i8* %ptr, i8** %esc) { store volatile i8 4, i8* %g ret void } + +;; When a basic block contains only a call to free and this block is accessed +;; through a test of the argument of free against null, move the call in the +;; predecessor block. +;; Using simplifycfg will remove the empty basic block and the branch operation +;; Then, performing a dead elimination will remove the comparison. +;; This is what happens with -O1 and upper. +; CHECK: @test6 +define void @test6(i8* %foo) minsize { +; CHECK: %tobool = icmp eq i8* %foo, null +;; Call to free moved +; CHECK-NEXT: tail call void @free(i8* %foo) +; CHECK-NEXT: br i1 %tobool, label %if.end, label %if.then +; CHECK: if.then: +;; Block is now empty and may be simplified by simplifycfg +; CHECK-NEXT: br label %if.end +; CHECK: if.end: +; CHECK-NEXT: ret void +entry: + %tobool = icmp eq i8* %foo, null + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %entry + tail call void @free(i8* %foo) + br label %if.end + +if.end: ; preds = %entry, %if.then + ret void +} |