From 05f18920e11f9427201ff3f023d11a8863deac37 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 1 Dec 2008 02:34:36 +0000 Subject: [PATCH] Teach inst combine to merge GEPs through PHIs. This is really important because it is sinking the loads using the GEPs, but not the GEPs themselves. This triggers 647 times on 403.gcc and makes the .s file much much nicer. For example before: je LBB1_87 ## bb78 LBB1_62: ## bb77 leal 84(%esi), %eax LBB1_63: ## bb79 movl (%eax), %eax ... LBB1_87: ## bb78 movl $0, 4(%esp) movl %esi, (%esp) call L_make_decl_rtl$stub jmp LBB1_62 ## bb77 after: jne LBB1_63 ## bb79 LBB1_62: ## bb78 movl $0, 4(%esp) movl %esi, (%esp) call L_make_decl_rtl$stub LBB1_63: ## bb79 movl 84(%esi), %eax The input code was (and the GEPs are merged and the PHI is now eliminated by instcombine): br i1 %tmp233, label %bb78, label %bb77 bb77: %tmp234 = getelementptr %struct.tree_node* %t_addr.3, i32 0, i32 0, i32 22 br label %bb79 bb78: call void @make_decl_rtl(%struct.tree_node* %t_addr.3, i8* null) nounwind %tmp235 = getelementptr %struct.tree_node* %t_addr.3, i32 0, i32 0, i32 22 br label %bb79 bb79: %iftmp.12.0.in = phi %struct.rtx_def** [ %tmp235, %bb78 ], [ %tmp234, %bb77 ] %iftmp.12.0 = load %struct.rtx_def** %iftmp.12.0.in git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60322 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/InstructionCombining.cpp | 111 +++++++++++++++--- test/Transforms/InstCombine/phi.ll | 16 ++- 2 files changed, 110 insertions(+), 17 deletions(-) diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index 4e2e8a409bc..49e7fc07ac2 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -372,7 +372,8 @@ namespace { // inputs, and do the operation once, to the result of the PHI. Instruction *FoldPHIArgOpIntoPHI(PHINode &PN); Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN); - + Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN); + Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS, ConstantInt *AndRHS, BinaryOperator &TheAnd); @@ -9985,7 +9986,7 @@ Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) { // Scan to see if all operands are the same opcode, all have one use, and all // kill their operands (i.e. the operands have one use). - for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) { + for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) { Instruction *I = dyn_cast(PN.getIncomingValue(i)); if (!I || I->getOpcode() != Opc || !I->hasOneUse() || // Verify type of the LHS matches so we don't fold cmp's of different @@ -10010,6 +10011,7 @@ Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) { // If this is a GEP, and if the index (not the pointer) needs a PHI, bail out. // Indexes are often folded into load/store instructions, so we don't want to // hide them behind a phi. + // URR?? if (isa(FirstInst) && RHSVal == 0) return 0; @@ -10035,28 +10037,101 @@ Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) { } // Add all operands to the new PHIs. - for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { - if (NewLHS) { - Value *NewInLHS =cast(PN.getIncomingValue(i))->getOperand(0); - NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i)); - } - if (NewRHS) { - Value *NewInRHS =cast(PN.getIncomingValue(i))->getOperand(1); - NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i)); + if (NewLHS || NewRHS) { + for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { + Instruction *InInst = cast(PN.getIncomingValue(i)); + if (NewLHS) { + Value *NewInLHS = InInst->getOperand(0); + NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i)); + } + if (NewRHS) { + Value *NewInRHS = InInst->getOperand(1); + NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i)); + } } } if (BinaryOperator *BinOp = dyn_cast(FirstInst)) return BinaryOperator::Create(BinOp->getOpcode(), LHSVal, RHSVal); - else if (CmpInst *CIOp = dyn_cast(FirstInst)) + if (CmpInst *CIOp = dyn_cast(FirstInst)) return CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(), LHSVal, RHSVal); - else { - assert(isa(FirstInst)); - return GetElementPtrInst::Create(LHSVal, RHSVal); + assert(isa(FirstInst)); + return GetElementPtrInst::Create(LHSVal, RHSVal); +} + +Instruction *InstCombiner::FoldPHIArgGEPIntoPHI(PHINode &PN) { + GetElementPtrInst *FirstInst =cast(PN.getIncomingValue(0)); + + SmallVector FixedOperands(FirstInst->op_begin(), + FirstInst->op_end()); + + // Scan to see if all operands are the same opcode, all have one use, and all + // kill their operands (i.e. the operands have one use). + for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) { + GetElementPtrInst *GEP= dyn_cast(PN.getIncomingValue(i)); + if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() || + GEP->getNumOperands() != FirstInst->getNumOperands()) + return 0; + + // Compare the operand lists. + for (unsigned op = 0, e = FirstInst->getNumOperands(); op != e; ++op) { + if (FirstInst->getOperand(op) == GEP->getOperand(op)) + continue; + + // Don't merge two GEPs when two operands differ (introducing phi nodes) + // if one of the PHIs has a constant for the index. The index may be + // substantially cheaper to compute for the constants, so making it a + // variable index could pessimize the path. This also handles the case + // for struct indices, which must always be constant. + if (isa(FirstInst->getOperand(op)) || + isa(GEP->getOperand(op))) + return 0; + + if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType()) + return 0; + FixedOperands[op] = 0; // Needs a PHI. + } + } + + // Otherwise, this is safe to transform. Insert PHI nodes for each operand + // that is variable. + SmallVector OperandPhis(FixedOperands.size()); + + bool HasAnyPHIs = false; + for (unsigned i = 0, e = FixedOperands.size(); i != e; ++i) { + if (FixedOperands[i]) continue; // operand doesn't need a phi. + Value *FirstOp = FirstInst->getOperand(i); + PHINode *NewPN = PHINode::Create(FirstOp->getType(), + FirstOp->getName()+".pn"); + InsertNewInstBefore(NewPN, PN); + + NewPN->reserveOperandSpace(e); + NewPN->addIncoming(FirstOp, PN.getIncomingBlock(0)); + OperandPhis[i] = NewPN; + FixedOperands[i] = NewPN; + HasAnyPHIs = true; } + + + // Add all operands to the new PHIs. + if (HasAnyPHIs) { + for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { + GetElementPtrInst *InGEP =cast(PN.getIncomingValue(i)); + BasicBlock *InBB = PN.getIncomingBlock(i); + + for (unsigned op = 0, e = OperandPhis.size(); op != e; ++op) + if (PHINode *OpPhi = OperandPhis[op]) + OpPhi->addIncoming(InGEP->getOperand(op), InBB); + } + } + + Value *Base = FixedOperands[0]; + return GetElementPtrInst::Create(Base, FixedOperands.begin()+1, + FixedOperands.end()); } + /// isSafeToSinkLoad - Return true if we know that it is safe sink the load out /// of the block that defines it. This means that it must be obvious the value /// of the load is not changed from the point of the load to the end of the @@ -10134,8 +10209,7 @@ Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) { } else if (isa(FirstInst)) { if (FirstInst->getNumOperands() == 2) return FoldPHIArgBinOpIntoPHI(PN); - // Can't handle general GEPs yet. - return 0; + return FoldPHIArgGEPIntoPHI(PN); } else { return 0; // Cannot fold this operation. } @@ -10279,6 +10353,11 @@ Instruction *InstCombiner::visitPHINode(PHINode &PN) { // If all PHI operands are the same operation, pull them through the PHI, // reducing code size. if (isa(PN.getIncomingValue(0)) && + isa(PN.getIncomingValue(1)) && + cast(PN.getIncomingValue(0))->getOpcode() == + cast(PN.getIncomingValue(1))->getOpcode() && + // FIXME: The hasOneUse check will fail for PHIs that use the value more + // than themselves more than once. PN.getIncomingValue(0)->hasOneUse()) if (Instruction *Result = FoldPHIArgOpIntoPHI(PN)) return Result; diff --git a/test/Transforms/InstCombine/phi.ll b/test/Transforms/InstCombine/phi.ll index 6f0ef6b549e..4efbb79d9d4 100644 --- a/test/Transforms/InstCombine/phi.ll +++ b/test/Transforms/InstCombine/phi.ll @@ -1,7 +1,6 @@ ; This test makes sure that these instructions are properly eliminated. ; ; RUN: llvm-as < %s | opt -instcombine | llvm-dis | not grep phi -; END. define i32 @test1(i32 %A, i1 %b) { BB0: @@ -98,4 +97,19 @@ Exit: ; preds = %Loop ret i32 0 } +define i32* @test8({ i32, i32 } *%A, i1 %b) { +BB0: + %X = getelementptr { i32, i32 } *%A, i32 0, i32 1 + br i1 %b, label %BB1, label %BB2 + +BB1: + %Y = getelementptr { i32, i32 } *%A, i32 0, i32 1 + br label %BB2 + +BB2: + ;; Suck GEPs into phi + %B = phi i32* [ %X, %BB0 ], [ %Y, %BB1 ] + ret i32* %B +} + -- 2.34.1