Index: lib/CodeGen/CodeGenPrepare.cpp =================================================================== --- lib/CodeGen/CodeGenPrepare.cpp +++ lib/CodeGen/CodeGenPrepare.cpp @@ -156,6 +156,10 @@ cl::desc("The number of loads per basic block for inline expansion of " "memcmp that is only being compared against zero.")); +static cl::opt +AddrSinkNewPhis("addr-sink-new-phis", cl::Hidden, cl::init(false), + cl::desc("Allow creation of Phis in Address sinking.")); + namespace { typedef SmallPtrSet SetOfInstrs; typedef PointerIntPair TypeIsSExt; @@ -2610,6 +2614,11 @@ (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) && (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale); } + bool EqualsIgnoreBase(const ExtAddrMode &O) const { + return (ScaledReg == O.ScaledReg) && (BaseGV == O.BaseGV) && + (BaseOffs == O.BaseOffs) && (HasBaseReg == O.HasBaseReg) && + (Scale == O.Scale); + } }; #ifndef NDEBUG @@ -4243,6 +4252,287 @@ return I->getParent() != BB; return false; } +typedef std::pair ValueInBasicBlock; +typedef DenseMap FoldAddrToBaseMapping; +typedef std::pair PHIPair; + +// Keep track of simplification of Phi nodes. +// Accept the set of all phi nodes and erase phi node from this set +// if it is simplified. +class PhiSimplificationTracker { + DenseMap Storage; + const SimplifyQuery &SQ; + SmallPtrSetImpl &AllPhiNodes; + +public: + PhiSimplificationTracker(const SimplifyQuery &sq, + SmallPtrSetImpl &APN) + : SQ(sq), AllPhiNodes(APN) {} + + Value *Get(Value *V) { + do { + auto SV = Storage.find(V); + if (SV == Storage.end()) + return V; + V = SV->second; + } while (true); + } + + Value *Simplify(PHINode *PHI) { + SmallVector WorkList; + SmallPtrSet Visited; + WorkList.push_back(PHI); + while (!WorkList.empty()) { + auto P = WorkList.pop_back_val(); + if (!Visited.insert(P).second) + continue; + if (Value *V = SimplifyInstruction(P, SQ)) { + for (auto *U : P->users()) + WorkList.push_back(cast(U)); + Put(P, V); + P->replaceAllUsesWith(V); + AllPhiNodes.erase(P); + P->eraseFromParent(); + } + } + return Get(PHI); + } + + void Put(Value *From, Value *To) { + Storage.insert({ From, To }); + } +}; + +// Starting from value recursively iterates over predecessors up to known ending +// values. for each traversed block inserts a place holder PHI. +// Report all new created Phi nodes by adding them to set. +// Also reports and order in what basic blocks have been traversed. +static void +InsertPhiPlaceholders(FoldAddrToBaseMapping &AddrToBase, + ValueInBasicBlock Start, + SmallVectorImpl &TraverseOrder, + SmallPtrSetImpl &NewPhiNodes, Type *T) { + SmallVector Worklist; + assert(isa(Start.first) && "Address must be a Phi node"); + Worklist.push_back(Start); + while (!Worklist.empty()) { + auto Current = Worklist.pop_back_val(); + // if it is already visited or it is an ending value then skip it. + if (AddrToBase.count(Current)) + continue; + TraverseOrder.push_back(Current); + + Value *CurrentValue = Current.first; + BasicBlock *CurrentBlock = Current.second; + unsigned PredCount = + std::distance(pred_begin(CurrentBlock), pred_end(CurrentBlock)); + assert(PredCount && "Unreachable block?!"); + // Create new Phi node for merge of bases. + PHINode *PHI = + PHINode::Create(T, PredCount, "sunk_phi", &CurrentBlock->front()); + AddrToBase.insert({ Current, PHI }); + NewPhiNodes.insert(PHI); + + // Add all predecessors in work list. + auto CurrentPhi = dyn_cast(CurrentValue); + bool IsDefinedInThisBB = + CurrentPhi && CurrentPhi->getParent() == CurrentBlock; + for (auto B : predecessors(CurrentBlock)) + Worklist.push_back({ IsDefinedInThisBB + ? CurrentPhi->getIncomingValueForBlock(B) + : CurrentValue, + B }); + } +} + +// Fill the place holder Phis with values from predecessors and simplify it. +static void +FillPhiPlaceholders(FoldAddrToBaseMapping &AddrToBase, + SmallVectorImpl &TraverseOrder, + PhiSimplificationTracker &ST) { + while (!TraverseOrder.empty()) { + auto Current = TraverseOrder.pop_back_val(); + assert(AddrToBase.find(Current) != AddrToBase.end() && + "No Phi To merge!!!"); + PHINode *PHI = cast(AddrToBase[Current]); + + Value *CurrentValue = Current.first; + BasicBlock *CurrentBlock = Current.second; + // Fill the Phi node with values from predecessors. + auto CurrentPhi = dyn_cast(CurrentValue); + bool IsDefinedInThisBB = + CurrentPhi && CurrentPhi->getParent() == CurrentBlock; + for (auto B : predecessors(CurrentBlock)) { + ValueInBasicBlock item = { IsDefinedInThisBB + ? CurrentPhi->getIncomingValueForBlock(B) + : CurrentValue, + B }; + assert(AddrToBase.find(item) != AddrToBase.end() && + "No predecessor Value!"); + PHI->addIncoming(ST.Get(AddrToBase[item]), B); + } + + // Simplify PHI if possible. + AddrToBase[Current] = ST.Simplify(PHI); + } +} + +// Try to match PHI node to Candidate. Matcher tracks the matched Phi nodes. +static bool MatchPhiNode(PHINode *PHI, PHINode *Candidate, + DenseSet &Matcher, + SmallPtrSetImpl &PhiNodesToMatch) { + SmallVector WorkList; + Matcher.insert({ PHI, Candidate }); + WorkList.push_back({ PHI, Candidate }); + SmallSet Visited; + while (!WorkList.empty()) { + auto Item = WorkList.pop_back_val(); + if (!Visited.insert(Item).second) + continue; + // We iterate over all incoming values to Phi to compare them. + // If values are different and both of them Phi and the first one is a + // Phi we added (subject to match) and both of them is in the same basic + // block then we can match our pair if values match. So we state that + // these values match and add it to work list to verify that. + for (auto B : Item.first->blocks()) { + Value *FirstValue = Item.first->getIncomingValueForBlock(B); + Value *SecondValue = Item.second->getIncomingValueForBlock(B); + if (FirstValue == SecondValue) + continue; + + PHINode *FirstPhi = dyn_cast(FirstValue); + PHINode *SecondPhi = dyn_cast(SecondValue); + + // One of them is not Phi or + // The first one is not Phi node from the set we'd like to match or + // Phi nodes from different basic blocks then + // we will not be able to match. + if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) || + FirstPhi->getParent() != SecondPhi->getParent()) + return false; + + // If we already matched them then continue. + if (Matcher.count({ FirstPhi, SecondPhi })) + continue; + // So the values are different and does not match. So we need them to + // match. + Matcher.insert({ FirstPhi, SecondPhi }); + // But me must check it. + WorkList.push_back({ FirstPhi, SecondPhi }); + } + } + return true; +} + +// For the given set of PHI nodes try to find their equivalents. +// Returns false if this matching fails and creation of new Phi is disabled. +bool MatchPhiSet(SmallPtrSetImpl &PhiNodesToMatch, + PhiSimplificationTracker &ST) { + DenseSet Matched; + SmallPtrSet WillNotMatch; + while (PhiNodesToMatch.size()) { + PHINode *PHI = *PhiNodesToMatch.begin(); + + // Add us, if no Phi nodes in the basic block we do not match. + WillNotMatch.clear(); + WillNotMatch.insert(PHI); + + // Traverse all Phis until we found equivalent or fail to do that. + bool IsMatched = false; + for (auto &P : PHI->getParent()->phis()) { + if (&P == PHI) + continue; + if ((IsMatched = MatchPhiNode(PHI, &P, Matched, PhiNodesToMatch))) + break; + // If it does not match, collect all Phi nodes from matcher. + // if we end up with no match, them all these Phi nodes will not match + // later. + for (auto M : Matched) + WillNotMatch.insert(M.first); + Matched.clear(); + } + if (IsMatched) { + // Replace all matched values and erase them. + for (auto MV : Matched) { + MV.first->replaceAllUsesWith(MV.second); + PhiNodesToMatch.erase(MV.first); + ST.Put(MV.first, MV.second); + MV.first->eraseFromParent(); + } + Matched.clear(); + continue; + } + // If we are not allowed to create new nodes then bail out. + if (!AddrSinkNewPhis) + return false; + // Just remove all seen values in matcher. They will not match anything. + for (auto P : WillNotMatch) + PhiNodesToMatch.erase(P); + } + return true; +} + +// Utility function for optimizeMemoryInst to find the common base for found +// set of addresses. +// VIBB represents the address observed in some basic block. Traversing by Phi +// nodes +// we ended up in a set of non-phi addresses with corresponding bases. +// AddrToBase represents this mapping, address in some basic block corresponds +// to base. +// T is type of the base, SQ is used for simplifyInstruction. +// The function answers to the question what is the value of the base in basic +// block specified in VIBB. +// If option addr-sink-new-phis is true then function may build required Phi +// nodes. +// The simple example looks as follows: +// BB1: +// p1 = b1 + 40 +// br cond BB2, BB3 +// BB2: +// p2 = b2 + 40 +// br BB3 +// BB3: +// p = phi [p1, BB1], [p2, BB2] +// v = load p +// Input is +// -> b1 +// -> b2 +// Request is +// -> ? +// The function tries to find or build phi [b1, BB1], [b2, BB2] in BB3 +static Value *FindCommonBase(FoldAddrToBaseMapping &AddrToBase, Type *T, + ValueInBasicBlock VIBB, const SimplifyQuery &SQ) { + // Tracks of new created Phi nodes. + SmallPtrSet NewPhiNodes; + // Tracks the simplification of new created phi nodes. The reason we use this + // mapping is because we will add new created Phi nodes in AddrToBase. + // Simplification of Phi nodes is recursive, so some Phi node may + // be simplified after we added it to AddrToBase. + // Using this mapping we can find the current value in AddrToBase. + PhiSimplificationTracker ST(SQ, NewPhiNodes); + + // First step, DFS to create PHI nodes for all intermediate blocks. + // Also fill traverse order for the second step. + SmallVector TraverseOrder; + InsertPhiPlaceholders(AddrToBase, VIBB, TraverseOrder, NewPhiNodes, T); + + // Second Step, fill PHI nodes by merged values and simplify if possible. + FillPhiPlaceholders(AddrToBase, TraverseOrder, ST); + + // Now we'd like to match New Phi nodes to existed ones. + if (!MatchPhiSet(NewPhiNodes, ST)) { + // Clean-up before bailout - remove all created Phi. + // For safe erasing, replace the Phi with dummy value first. + auto Dummy = UndefValue::get(T); + for (auto PHI : NewPhiNodes) { + PHI->replaceAllUsesWith(Dummy); + PHI->eraseFromParent(); + } + return nullptr; + } + // We are done, return answer. + return ST.Get(AddrToBase.find(VIBB)->second); +} /// Sink addressing mode computation immediate before MemoryInst if doing so /// can be done without increasing register pressure. The need for the @@ -4271,6 +4561,7 @@ // unprofitable PRE transformations. SmallVector worklist; SmallPtrSet Visited; + FoldAddrToBaseMapping AddrToBase; worklist.push_back(Addr); // Use a worklist to iteratively look through PHI nodes, and ensure that @@ -4278,6 +4569,7 @@ // are equivalent. bool AddrModeFound = false; bool PhiSeen = false; + bool DifferentBasesSeen = false; SmallVector AddrModeInsts; ExtAddrMode AddrMode; TypePromotionTransaction TPT(RemovedInsts); @@ -4315,6 +4607,17 @@ V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *TRI, InsertedInsts, PromotedInsts, TPT); + // Track the mapping between addr and its found base. We will need this + // if address mode is the same except base. + if (NewAddrMode.HasBaseReg) { + BasicBlock *BB = nullptr; + if (Instruction *I = dyn_cast(V)) + BB = I->getParent(); + else + BB = &MemoryInst->getParent()->getParent()->getEntryBlock(); + AddrToBase.insert({ { V, BB }, NewAddrMode.BaseReg }); + } + if (!AddrModeFound) { AddrModeFound = true; AddrMode = NewAddrMode; @@ -4322,11 +4625,33 @@ } if (NewAddrMode == AddrMode) continue; + // Last chance, if difference only in bases we could sunk only if + // we find common base later. + if (AddrMode.EqualsIgnoreBase(NewAddrMode)) + // All bases must be of the same type. + if (AddrMode.BaseReg->getType() == NewAddrMode.BaseReg->getType()) { + DifferentBasesSeen = true; + continue; + } AddrModeFound = false; break; } + if (AddrModeFound && DifferentBasesSeen) { + // We do not want to do a complex analysis if AddrMode contains only base. + // Finding the common base most probably ends up with the same + // phi as address is represented by. + AddrModeFound = AddrMode.BaseGV || AddrMode.BaseOffs || AddrMode.Scale; + if (AddrModeFound) + // If we cannot find common phi for bases then bail out, otherwise use + // this phi as new base. + if (!(AddrMode.BaseReg = FindCommonBase( + AddrToBase, AddrMode.BaseReg->getType(), + { Addr, MemoryInst->getParent() }, { *DL, TLInfo }))) + AddrModeFound = false; + } + // If the addressing mode couldn't be determined, or if multiple different // ones were determined, bail out now. if (!AddrModeFound) { Index: test/Transforms/CodeGenPrepare/X86/sink-addrmode-base.ll =================================================================== --- /dev/null +++ test/Transforms/CodeGenPrepare/X86/sink-addrmode-base.ll @@ -0,0 +1,389 @@ +; RUN: opt -S -codegenprepare -addr-sink-new-phis=true %s | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-YES +; RUN: opt -S -codegenprepare -addr-sink-new-phis=false %s | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-NO +target datalayout = +"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" +target triple = "x86_64-unknown-linux-gnu" + +; Can we sink for different base if there is no phi for base? +define i32 @test1(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test1 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; Can we sink for different base if there is phi for base? +define i32 @test2(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test2 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK: getelementptr i8, {{.+}} 40 + %b = phi i64* [%b1, %entry], [%b2, %if.then] + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; Can we sink for different base if there is phi for base but not valid one? +define i32 @test3(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test3 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %b = phi i64* [%b2, %entry], [%b1, %if.then] + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; Can we sink for different base if both addresses are in the same block? +define i32 @test4(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test4 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; Can we sink for different base if there is phi for base? +; Both addresses are in the same block. +define i32 @test5(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test5 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + br label %fallthrough + +fallthrough: +; CHECK: getelementptr i8, {{.+}} 40 + %b = phi i64* [%b1, %entry], [%b2, %if.then] + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; Can we sink for different base if there is phi for base but not valid one? +; Both addresses are in the same block. +define i32 @test6(i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test6 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %b = phi i64* [%b2, %entry], [%b1, %if.then] + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %v = load i32, i32* %c, align 4 + ret i32 %v +} + +; case with a loop. No phi node. +define i32 @test7(i32 %N, i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test7 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-YES: sunk_phi + %iv = phi i32 [0, %entry], [%iv.inc, %fallthrough] + %c3 = phi i32* [%c1, %entry], [%c, %fallthrough] + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %c = phi i32* [%c3, %loop], [%c2, %if.then] + %v = load volatile i32, i32* %c, align 4 + %iv.inc = add i32 %iv, 1 + %cmp = icmp slt i32 %iv.inc, %N + br i1 %cmp, label %loop, label %exit + +exit: + ret i32 %v +} + +; case with a loop. There is phi node. +define i32 @test8(i32 %N, i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test8 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br label %loop + +loop: + %iv = phi i32 [0, %entry], [%iv.inc, %fallthrough] + %c3 = phi i32* [%c1, %entry], [%c, %fallthrough] + %b3 = phi i64* [%b1, %entry], [%b, %fallthrough] + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK: getelementptr i8, {{.+}} 40 + %c = phi i32* [%c3, %loop], [%c2, %if.then] + %b = phi i64* [%b3, %loop], [%b2, %if.then] + %v = load volatile i32, i32* %c, align 4 + %iv.inc = add i32 %iv, 1 + %cmp = icmp slt i32 %iv.inc, %N + br i1 %cmp, label %loop, label %exit + +exit: + ret i32 %v +} + +; case with a loop. There is phi node but it does not fit. +define i32 @test9(i32 %N, i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test9 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-YES: sunk_phi + %iv = phi i32 [0, %entry], [%iv.inc, %fallthrough] + %c3 = phi i32* [%c1, %entry], [%c, %fallthrough] + %b3 = phi i64* [%b1, %entry], [%b2, %fallthrough] + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %c = phi i32* [%c3, %loop], [%c2, %if.then] + %b = phi i64* [%b3, %loop], [%b2, %if.then] + %v = load volatile i32, i32* %c, align 4 + %iv.inc = add i32 %iv, 1 + %cmp = icmp slt i32 %iv.inc, %N + br i1 %cmp, label %loop, label %exit + +exit: + ret i32 %v +} + +; Case through a loop. No phi node. +define i32 @test10(i32 %N, i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test10 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: br + %c = phi i32* [%c1, %entry], [%c2, %if.then] + br label %loop + +loop: + %iv = phi i32 [0, %fallthrough], [%iv.inc, %loop] + %iv.inc = add i32 %iv, 1 + %cmp = icmp slt i32 %iv.inc, %N + br i1 %cmp, label %loop, label %exit + +exit: +; CHECK-YES: sunkaddr + %v = load volatile i32, i32* %c, align 4 + ret i32 %v +} + +; Case through a loop. There is a phi. +define i32 @test11(i32 %N, i1 %cond, i64* %b1, i64* %b2) { +; CHECK-LABEL: @test11 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK: phi +; CHECK: phi +; CHECK: br + %c = phi i32* [%c1, %entry], [%c2, %if.then] + %b = phi i64* [%b1, %entry], [%b2, %if.then] + br label %loop + +loop: + %iv = phi i32 [0, %fallthrough], [%iv.inc, %loop] + %iv.inc = add i32 %iv, 1 + %cmp = icmp slt i32 %iv.inc, %N + br i1 %cmp, label %loop, label %exit + +exit: +; CHECK: sunkaddr + %v = load volatile i32, i32* %c, align 4 + ret i32 %v +} + +; Complex case with address value from previous iteration. +define i32 @test12(i32 %N, i1 %cond, i64* %b1, i64* %b2, i64* %b3) { +; CHECK-LABEL: @test12 +entry: + %a1 = getelementptr inbounds i64, i64* %b1, i64 5 + %c1 = bitcast i64* %a1 to i32* + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-YES: sunk_phi +; CHECK-NO: phi +; CHECK-NO: phi +; CHECK-NO: phi +; CHECK-NO: br + %iv = phi i32 [0, %entry], [%iv.inc, %backedge] + %c3 = phi i32* [%c1, %entry], [%c, %backedge] + %b4 = phi i64* [%b1, %entry], [%b5, %backedge] + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %a2 = getelementptr inbounds i64, i64* %b2, i64 5 + %c2 = bitcast i64* %a2 to i32* + br label %fallthrough + +fallthrough: +; CHECK-LABEL: fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO: phi +; CHECK-NO: phi +; CHECK-NO: load + %c = phi i32* [%c3, %loop], [%c2, %if.then] + %b6 = phi i64* [%b4, %loop], [%b2, %if.then] + %v = load volatile i32, i32* %c, align 4 + %a4 = getelementptr inbounds i64, i64* %b4, i64 5 + %c4 = bitcast i64* %a4 to i32* + %cmp = icmp slt i32 %iv, 20 + br i1 %cmp, label %backedge, label %if.then.2 + +if.then.2: + br label %backedge + +backedge: + %b5 = phi i64* [%b4, %fallthrough], [%b6, %if.then.2] + %iv.inc = add i32 %iv, 1 + %cmp2 = icmp slt i32 %iv.inc, %N + br i1 %cmp2, label %loop, label %exit + +exit: + ret i32 %v +} + + +%struct.S = type {i32, i32} +; Case with index +define i32 @test13(i1 %cond, %struct.S* %b1, %struct.S* %b2, i64 %Index) { +; CHECK-LABEL: @test13 +entry: + %a1 = getelementptr inbounds %struct.S, %struct.S* %b1, i64 %Index, i32 1 + br i1 %cond, label %if.then, label %fallthrough + +if.then: + %i2 = mul i64 %Index, 2 + %a2 = getelementptr inbounds %struct.S, %struct.S* %b2, i64 %Index, i32 1 + br label %fallthrough + +fallthrough: +; CHECK-YES: sunk_phi +; CHECK-NO-LABEL: fallthrough: +; CHECK-NO: phi +; CHECK-NO: load + %a = phi i32* [%a1, %entry], [%a2, %if.then] + %v = load i32, i32* %a, align 4 + ret i32 %v +}