Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -1235,6 +1235,53 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I); +// Given a conditional branch BI that goes to BB1 and BB2, which are the +// basic blocks of the instructions I1 and I2 respectively, hoist I1 and +// I2 up into the branch block. The caller of this function guarantees +// that I1->isIdenticalToWhenDefined(I2) and that BI's block dominates +// BB1 and BB2. +static void HoistThenElseInstructionToIf(BranchInst *BI, Instruction *I1, + Instruction *I2) { + // Move I1 to right before the branch, then replace all uses of I2. + BI->getParent()->getInstList().splice(BI->getIterator(), + I1->getParent()->getInstList(), I1); + if (!I2->use_empty()) + I2->replaceAllUsesWith(I1); + I1->andIRFlags(I2); + unsigned KnownIDs[] = {LLVMContext::MD_tbaa, + LLVMContext::MD_range, + LLVMContext::MD_fpmath, + LLVMContext::MD_invariant_load, + LLVMContext::MD_nonnull, + LLVMContext::MD_invariant_group, + LLVMContext::MD_align, + LLVMContext::MD_dereferenceable, + LLVMContext::MD_dereferenceable_or_null, + LLVMContext::MD_mem_parallel_loop_access}; + combineMetadata(I1, I2, KnownIDs); + + // I1 and I2 are being combined into a single instruction. Its debug + // location is the merged locations of the original instructions. + I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc()); + + I2->eraseFromParent(); +} + +// Scan the basic block BB of an instruction I, which is candidate for hoisting, +// to make sure there are no instructions before I that may write to memory. +// First check that the instruction I itself doesn't write to memory. +static bool isSafeToHoistInstruction(BasicBlock *BB, Instruction *I) { + if (I->mayWriteToMemory()) + return false; + + for (BasicBlock::iterator IT = BB->begin(), ITE = BasicBlock::iterator(I); + IT != ITE; ++IT) + if (IT->mayWriteToMemory()) + return false; + + return true; +} + /// Given a conditional branch that goes to BB1 and BB2, hoist any common code /// in the two blocks up into the branch block. The caller of this function /// guarantees that BI's block dominates BB1 and BB2. @@ -1248,6 +1295,42 @@ BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. BasicBlock *BB2 = BI->getSuccessor(1); // The false destination + bool Changed = false; + + // Before we start scanning the two side blocks, we first identify if + // there's a diamond structure. We try to hoist common instructions + // from the side blocks to the entry if they are used by PHI-nodes of + // the exit block. This might enable PHI-node reduction which in turn + // could trigger further CFG simplifications like if-conversion. + // + // FIXME: GVNHoist could do it for us but it's currently disabled. + BasicBlock *IfEnd = BB1->getSingleSuccessor(); + if (IfEnd && (IfEnd == BB2->getSingleSuccessor())) { + + for (PHINode &PN : IfEnd->phis()) { + auto *I1 = dyn_cast(PN.getIncomingValueForBlock(BB1)); + auto *I2 = dyn_cast(PN.getIncomingValueForBlock(BB2)); + + if (I1 && I1->getParent() == BB1 && + I2 && I2->getParent() == BB2 && + I1->isIdenticalToWhenDefined(I2)) { + + // We don't preserve alias analysis therefore we have to make sure + // it's legal to hoist instructions. + // + // We scan all the instructions of BB1 up to I1 inclusive and bail + // if we find anything that might write to memory. Then we do the + // same for BB2. + if (!isSafeToHoistInstruction(BB1, I1) || + !isSafeToHoistInstruction(BB2, I2)) + continue; + + HoistThenElseInstructionToIf(BI, I1, I2); + Changed = true; + } + } + } + BasicBlock::iterator BB1_Itr = BB1->begin(); BasicBlock::iterator BB2_Itr = BB2->begin(); @@ -1267,7 +1350,6 @@ BasicBlock *BIParent = BI->getParent(); - bool Changed = false; do { // If we are hoisting the terminator instruction, don't move one (making a // broken BB), instead clone it, and remove BI. @@ -1302,28 +1384,7 @@ // For a normal instruction, we just move one to right before the branch, // then replace all uses of the other with the first. Finally, we remove // the now redundant second instruction. - BIParent->getInstList().splice(BI->getIterator(), - BB1->getInstList(), I1); - if (!I2->use_empty()) - I2->replaceAllUsesWith(I1); - I1->andIRFlags(I2); - unsigned KnownIDs[] = {LLVMContext::MD_tbaa, - LLVMContext::MD_range, - LLVMContext::MD_fpmath, - LLVMContext::MD_invariant_load, - LLVMContext::MD_nonnull, - LLVMContext::MD_invariant_group, - LLVMContext::MD_align, - LLVMContext::MD_dereferenceable, - LLVMContext::MD_dereferenceable_or_null, - LLVMContext::MD_mem_parallel_loop_access}; - combineMetadata(I1, I2, KnownIDs); - - // I1 and I2 are being combined into a single instruction. Its debug - // location is the merged locations of the original instructions. - I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc()); - - I2->eraseFromParent(); + HoistThenElseInstructionToIf(BI, I1, I2); Changed = true; } Index: test/Transforms/SimplifyCFG/HoistThenElseCodeToIf.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/HoistThenElseCodeToIf.ll @@ -0,0 +1,139 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +define void @isLegalToHoist_x_z(i1 %cmp, i32* %x, i32* %y, i32* %z) { +; CHECK-LABEL: @isLegalToHoist_x_z( +; CHECK: entry: +; CHECK: [[X:%.*]] = load i32, i32* %x, align 4 +; CHECK: [[Z:%.*]] = load i32, i32* %z, align 4 +; CHECK: if.then: +; CHECK-NOT: load i32, i32* %x, align 4 +; CHECK-NOT: load i32, i32* %z, align 4 +; CHECK: if.else: +; CHECK-NOT: load i32, i32* %x, align 4 +; CHECK-NOT: load i32, i32* %z, align 4 +; CHECK: if.end: +; CHECK: phi i32 [ [[X]], %if.else ], [ [[X]], %if.then ] +; CHECK: phi i32 [ [[Z]], %if.else ], [ [[Z]], %if.then ] +; +entry: + br i1 %cmp, label %if.else, label %if.then + +if.then: + %0 = getelementptr inbounds i32, i32* %y, i64 1 + %1 = getelementptr inbounds i32, i32* %y, i64 2 + %2 = load i32, i32* %x, align 4 + %3 = load i32, i32* %z, align 4 + store i32 %2, i32* %0, align 4 + store i32 %3, i32* %1, align 4 + br label %if.end + +if.else: + %4 = getelementptr inbounds i32, i32* %y, i64 2 + %5 = getelementptr inbounds i32, i32* %y, i64 1 + %6 = load i32, i32* %x, align 4 + %7 = load i32, i32* %z, align 4 + store i32 %6, i32* %4, align 4 + store i32 %7, i32* %5, align 4 + br label %if.end + +if.end: + %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ] + %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ] + %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ] + %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ] + %12 = add i32 %10, %11 + store i32 %12, i32* %8, align 4 + store i32 %12, i32* %9, align 4 + ret void +} + +define void @isLegalToHoist_x(i1 %cmp, i32* %x, i32* %y, i32* %z) { +; CHECK-LABEL: @isLegalToHoist_x( +; CHECK: entry: +; CHECK: [[X:%.*]] = load i32, i32* %x, align 4 +; CHECK-NOT: load volatile i32, i32* %z, align 4 +; CHECK: if.then: +; CHECK-NOT: load i32, i32* %x, align 4 +; CHECK: load volatile i32, i32* %z, align 4 +; CHECK: if.else: +; CHECK-NOT: load i32, i32* %x, align 4 +; CHECK: load volatile i32, i32* %z, align 4 +; CHECK: if.end: +; CHECK: phi i32 [ [[X]], %if.else ], [ [[X]], %if.then ] +; +entry: + br i1 %cmp, label %if.else, label %if.then + +if.then: + %0 = getelementptr inbounds i32, i32* %y, i64 1 + %1 = getelementptr inbounds i32, i32* %y, i64 2 + %2 = load i32, i32* %x, align 4 + %3 = load volatile i32, i32* %z, align 4 + store i32 %2, i32* %0, align 4 + store i32 %3, i32* %1, align 4 + br label %if.end + +if.else: + %4 = getelementptr inbounds i32, i32* %y, i64 2 + %5 = getelementptr inbounds i32, i32* %y, i64 1 + %6 = load i32, i32* %x, align 4 + %7 = load volatile i32, i32* %z, align 4 + store i32 %6, i32* %4, align 4 + store i32 %7, i32* %5, align 4 + br label %if.end + +if.end: + %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ] + %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ] + %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ] + %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ] + %12 = add i32 %10, %11 + store i32 %12, i32* %8, align 4 + store i32 %12, i32* %9, align 4 + ret void +} + +define void @isIllegalToHoist(i1 %cmp, i32* %x, i32* %y, i32* %z) { +; CHECK-LABEL: @isIllegalToHoist( +; CHECK: entry: +; CHECK-NOT: load volatile i32, i32* %x, align 4 +; CHECK-NOT: load i32, i32* %z, align 4 +; CHECK: if.then: +; CHECK: load volatile i32, i32* %x, align 4 +; CHECK: load i32, i32* %z, align 4 +; CHECK: if.else: +; CHECK: load volatile i32, i32* %x, align 4 +; CHECK: load i32, i32* %z, align 4 +; CHECK: if.end: +; +entry: + br i1 %cmp, label %if.else, label %if.then + +if.then: + %0 = getelementptr inbounds i32, i32* %y, i64 1 + %1 = getelementptr inbounds i32, i32* %y, i64 2 + %2 = load volatile i32, i32* %x, align 4 + %3 = load i32, i32* %z, align 4 + store i32 %2, i32* %0, align 4 + store i32 %3, i32* %1, align 4 + br label %if.end + +if.else: + %4 = getelementptr inbounds i32, i32* %y, i64 2 + %5 = getelementptr inbounds i32, i32* %y, i64 1 + %6 = load volatile i32, i32* %x, align 4 + %7 = load i32, i32* %z, align 4 + store i32 %6, i32* %4, align 4 + store i32 %7, i32* %5, align 4 + br label %if.end + +if.end: + %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ] + %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ] + %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ] + %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ] + %12 = add i32 %10, %11 + store i32 %12, i32* %8, align 4 + store i32 %12, i32* %9, align 4 + ret void +}