From b5ead7c450de20242c1d0828dfa6cbd999ce2b4c Mon Sep 17 00:00:00 2001 From: Tim Northover Date: Fri, 13 Jan 2017 23:11:37 +0000 Subject: [PATCH] [GlobalISel] track predecessor mapping during switch lowering. Correctly populating Machine PHIs relies on knowing exactly how the IR level CFG was lowered to MachineIR. This needs to be tracked by any translation phases that meddle (currently only SwitchInst handling). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@291973 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/CodeGen/GlobalISel/IRTranslator.h | 24 +++++++- lib/CodeGen/GlobalISel/IRTranslator.cpp | 55 +++++++++++++------ .../AArch64/GlobalISel/arm64-irtranslator.ll | 49 +++++++++++++++++ 3 files changed, 110 insertions(+), 18 deletions(-) diff --git a/include/llvm/CodeGen/GlobalISel/IRTranslator.h b/include/llvm/CodeGen/GlobalISel/IRTranslator.h index 26ba5c67beb..9182fa3727a 100644 --- a/include/llvm/CodeGen/GlobalISel/IRTranslator.h +++ b/include/llvm/CodeGen/GlobalISel/IRTranslator.h @@ -70,6 +70,9 @@ private: // lives. DenseMap BBToMBB; + typedef std::pair CFGEdge; + DenseMap> MachinePreds; + // List of stubbed PHI instructions, for values and basic blocks to be filled // in once all MachineBasicBlocks have been created. SmallVector, 4> PendingPHIs; @@ -390,10 +393,27 @@ private: /// the type being accessed (according to the Module's DataLayout). unsigned getMemOpAlignment(const Instruction &I); - /// Get the MachineBasicBlock that represents \p BB. - /// If such basic block does not exist, it is created. + /// Get the MachineBasicBlock that represents \p BB. Specifically, the block + /// returned will be the head of the translated block (suitable for branch + /// destinations). If such basic block does not exist, it is created. MachineBasicBlock &getOrCreateBB(const BasicBlock &BB); + /// Record \p NewPred as a Machine predecessor to `Edge.second`, corresponding + /// to `Edge.first` at the IR level. This is used when IRTranslation creates + /// multiple MachineBasicBlocks for a given IR block and the CFG is no longer + /// represented simply by the IR-level CFG. + void addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred); + + /// Returns the Machine IR predecessors for the given IR CFG edge. Usually + /// this is just the single MachineBasicBlock corresponding to the predecessor + /// in the IR. More complex lowering can result in multiple MachineBasicBlocks + /// preceding the original though (e.g. switch instructions). + ArrayRef getMachinePredBBs(CFGEdge Edge) { + auto RemappedEdge = MachinePreds.find(Edge); + if (RemappedEdge != MachinePreds.end()) + return RemappedEdge->second; + return &getOrCreateBB(*Edge.first); + } public: // Ctor, nothing fancy. diff --git a/lib/CodeGen/GlobalISel/IRTranslator.cpp b/lib/CodeGen/GlobalISel/IRTranslator.cpp index 89a042ffc47..b17acd917e5 100644 --- a/lib/CodeGen/GlobalISel/IRTranslator.cpp +++ b/lib/CodeGen/GlobalISel/IRTranslator.cpp @@ -12,6 +12,7 @@ #include "llvm/CodeGen/GlobalISel/IRTranslator.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/GlobalISel/CallLowering.h" #include "llvm/CodeGen/Analysis.h" @@ -134,6 +135,11 @@ MachineBasicBlock &IRTranslator::getOrCreateBB(const BasicBlock &BB) { return *MBB; } +void IRTranslator::addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred) { + assert(NewPred && "new edge must be a real MachineBasicBlock"); + MachinePreds[Edge].push_back(NewPred); +} + bool IRTranslator::translateBinaryOp(unsigned Opcode, const User &U, MachineIRBuilder &MIRBuilder) { // FIXME: handle signed/unsigned wrapping flags. @@ -209,30 +215,36 @@ bool IRTranslator::translateSwitch(const User &U, const SwitchInst &SwInst = cast(U); const unsigned SwCondValue = getOrCreateVReg(*SwInst.getCondition()); + const BasicBlock *OrigBB = SwInst.getParent(); LLT LLTi1 = LLT(*Type::getInt1Ty(U.getContext()), *DL); for (auto &CaseIt : SwInst.cases()) { const unsigned CaseValueReg = getOrCreateVReg(*CaseIt.getCaseValue()); const unsigned Tst = MRI->createGenericVirtualRegister(LLTi1); MIRBuilder.buildICmp(CmpInst::ICMP_EQ, Tst, CaseValueReg, SwCondValue); - MachineBasicBlock &CurBB = MIRBuilder.getMBB(); - MachineBasicBlock &TrueBB = getOrCreateBB(*CaseIt.getCaseSuccessor()); + MachineBasicBlock &CurMBB = MIRBuilder.getMBB(); + const BasicBlock *TrueBB = CaseIt.getCaseSuccessor(); + MachineBasicBlock &TrueMBB = getOrCreateBB(*TrueBB); - MIRBuilder.buildBrCond(Tst, TrueBB); - CurBB.addSuccessor(&TrueBB); + MIRBuilder.buildBrCond(Tst, TrueMBB); + CurMBB.addSuccessor(&TrueMBB); + addMachineCFGPred({OrigBB, TrueBB}, &CurMBB); - MachineBasicBlock *FalseBB = + MachineBasicBlock *FalseMBB = MF->CreateMachineBasicBlock(SwInst.getParent()); - MF->push_back(FalseBB); - MIRBuilder.buildBr(*FalseBB); - CurBB.addSuccessor(FalseBB); + MF->push_back(FalseMBB); + MIRBuilder.buildBr(*FalseMBB); + CurMBB.addSuccessor(FalseMBB); - MIRBuilder.setMBB(*FalseBB); + MIRBuilder.setMBB(*FalseMBB); } // handle default case - MachineBasicBlock &DefaultBB = getOrCreateBB(*SwInst.getDefaultDest()); - MIRBuilder.buildBr(DefaultBB); - MIRBuilder.getMBB().addSuccessor(&DefaultBB); + const BasicBlock *DefaultBB = SwInst.getDefaultDest(); + MachineBasicBlock &DefaultMBB = getOrCreateBB(*DefaultBB); + MIRBuilder.buildBr(DefaultMBB); + MachineBasicBlock &CurMBB = MIRBuilder.getMBB(); + CurMBB.addSuccessor(&DefaultMBB); + addMachineCFGPred({OrigBB, DefaultBB}, &CurMBB); return true; } @@ -736,11 +748,21 @@ void IRTranslator::finishPendingPhis() { // won't create extra control flow here, otherwise we need to find the // dominating predecessor here (or perhaps force the weirder IRTranslators // to provide a simple boundary). + SmallSet HandledPreds; + for (unsigned i = 0; i < PI->getNumIncomingValues(); ++i) { - assert(BBToMBB[PI->getIncomingBlock(i)]->isSuccessor(MIB->getParent()) && - "I appear to have misunderstood Machine PHIs"); - MIB.addUse(getOrCreateVReg(*PI->getIncomingValue(i))); - MIB.addMBB(BBToMBB[PI->getIncomingBlock(i)]); + auto IRPred = PI->getIncomingBlock(i); + if (HandledPreds.count(IRPred)) + continue; + + HandledPreds.insert(IRPred); + unsigned ValReg = getOrCreateVReg(*PI->getIncomingValue(i)); + for (auto Pred : getMachinePredBBs({IRPred, PI->getParent()})) { + assert(Pred->isSuccessor(MIB->getParent()) && + "incorrect CFG at MachineBasicBlock level"); + MIB.addUse(ValReg); + MIB.addMBB(Pred); + } } } } @@ -794,6 +816,7 @@ void IRTranslator::finalizeFunction() { ValToVReg.clear(); FrameIndices.clear(); Constants.clear(); + MachinePreds.clear(); } bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) { diff --git a/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll b/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll index 15b4012f383..aa5a07dad4a 100644 --- a/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll +++ b/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll @@ -168,6 +168,55 @@ return: ret i32 %res } + ; The switch lowering code changes the CFG, which means that the original + ; %entry block is no longer a predecessor for the phi instruction. We need to + ; use the correct lowered MachineBasicBlock instead. +; CHECK-LABEL: name: test_cfg_remap + +; CHECK: bb.5.entry: +; CHECK-NEXT: successors: %[[PHI_BLOCK:bb.[0-9]+.phi.block]] +; CHECK: G_BR %[[PHI_BLOCK]] + +; CHECK: [[PHI_BLOCK]]: +; CHECK-NEXT: PHI %{{.*}}(s32), %bb.5.entry +define i32 @test_cfg_remap(i32 %in) { +entry: + switch i32 %in, label %phi.block [i32 1, label %next + i32 57, label %other] + +next: + br label %phi.block + +other: + ret i32 undef + +phi.block: + %res = phi i32 [1, %entry], [42, %next] + ret i32 %res +} + +; CHECK-LABEL: name: test_cfg_remap_multiple_preds +; CHECK: PHI [[ENTRY:%.*]](s32), %bb.{{[0-9]+}}.entry, [[ENTRY]](s32), %bb.{{[0-9]+}}.entry +define i32 @test_cfg_remap_multiple_preds(i32 %in) { +entry: + switch i32 %in, label %odd [i32 1, label %next + i32 57, label %other + i32 128, label %phi.block + i32 256, label %phi.block] +odd: + unreachable + +next: + br label %phi.block + +other: + ret i32 undef + +phi.block: + %res = phi i32 [1, %entry], [1, %entry], [42, %next] + ret i32 12 +} + ; Tests for or. ; CHECK-LABEL: name: ori64 ; CHECK: [[ARG1:%[0-9]+]](s64) = COPY %x0 -- 2.40.0