[Polly] Codegen for simple full function Scops

[manasij7479]

Summary

Code generation for full functions on -polly-detect-full-functions.
Not yet tested with functions having multiple returns or unreachables.

[manasij7479]

lib/CodeGen/BlockGenerators.cpp

890

Not sure what should be done for these.

lib/CodeGen/CodeGeneration.cpp

156

Might be a better idea to reuse the UnifyFunctionExitNodes pass.

[manasij7479]

lib/CodeGen/CodeGeneration.cpp

273

Probably not a good idea. OTOH, I can not figure out how to update the original DT properly.

[Meinersbur]

Nice work!

lib/CodeGen/BlockGenerators.cpp

890

There are no escaping uses if the SCoP covers the whole function, so these should not be necessary.

However, function may return (ret double %val) values. ScopDetection allows them for TopLevelRegions and must be handled somehow. UnifyFunctionExitNodes might handle this already, but we should have a test case.

lib/CodeGen/CodeGeneration.cpp

156

[Style] According to LLVM Coding Standards, functions start with a lower case letter.

Can this function be made static?

A doxygen description for what the function does would be nice.

160

[Serious] Please avoid duplicating code for special cases. It increases the burden of maintenance in that we have to fix the same bugs in multiple code paths.

170–182

Why is it necessary to have only a single unreachable terminator? AFAIK unreachable's are modelled as error blocks, i.e. are assumed to be not executed at all, so are never code-generated.

188

[Suggestion] A function without a return would be strange since we do not model infinite loops in SCoPs. We therefore could place an llvm_unreachable here.

197

[Style] Empty comment line.

199

[Suggestion] Usually block names for code generated by Polly has a polly. prefix to make it better distinguishable,

236

[Suggestion] It would be really nice if we could handle in generally not just for TopLevelRegions. It would allow us to get rid of the CodePreparationPass pass.

lib/CodeGen/Utils.cpp

24–32

[Style] When export a function in the header, please move the documentation to the declaration in the header.

test/Isl/CodeGen/full-function.ll

4–6

For a minimal explementary function we maybe should verify the entire function.

[bollu]

Thanks a lot for the patch! I have some stylistic comments to make. However, I do not understand the related codebase well enough, so I'll leave that for the others :).

lib/CodeGen/CodeGeneration.cpp

160

consider SmallVector? It should be more efficient than std::vector with a decent choice of a default, say, 4

206

Personal opinion: Use the IRBuilder for building this form of IR? I find it much cleaner to read IR that's built using IRBuilder.

221

Personal opinion: I would prefer extracting out the ReturnInst from the BB and then use eraseFromParent on that instruction.

for (BasicBlock *BB : ReturningBlocks) {
    ReturnInst *RI = cast<ReturnInst>(BB->getTerminatorInst());
    ...
    RI->eraseFromParent();
}

241

asserts usually have a message in polly.

285

From what I can tell, there is code duplication between this and IslNodeBuilder. Is there a way to unify these two branches of code?

[manasij7479]

Address some of the issues.

[manasij7479]

lib/CodeGen/CodeGeneration.cpp

160

This needs some more discussion.

[manasij7479]

Refactor to remove code duplication

[manasij7479]

Test CFG structure

include/polly/CodeGen/Utils.h

 ///              - The first element is a BBPair of (StartBlock, EndBlock).
 ///              - The second element is the BranchInst which conditionally
 ///                branches to the SCoP based on the RTC.
 ///
 std::pair<BBPair, llvm::BranchInst *>
 executeScopConditionally(Scop &S, llvm::Value *RTC, llvm::DominatorTree &DT,
                          llvm::RegionInfo &RI, llvm::LoopInfo &LI);
 
+std::pair<BBPair, llvm::BranchInst *>
+executeTopLevelScopConditionally(Scop &S, llvm::Value *RTC,
+                                 llvm::DominatorTree &DT, llvm::RegionInfo &RI,
+                                 llvm::LoopInfo &LI);
 } // namespace polly
 #endif

lib/CodeGen/BlockGenerators.cpp

for (Instruction *EUser : EscapeUsers) {
         }
     }
   }
 }
 
 void BlockGenerator::finalizeSCoP(Scop &S) {
   findOutsideUsers(S);
   createScalarInitialization(S);
+
+  if (!S.getRegion().isTopLevelRegion()) {
     createExitPHINodeMerges(S);
     createScalarFinalization(S);
+  }
+
   invalidateScalarEvolution(S);
 }
 
 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                            std::vector<LoopToScevMapT> &VLTS,
                                            isl_map *Schedule)
     : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
   assert(Schedule && "No statement domain provided");

lib/CodeGen/CodeGeneration.cpp

while (InstIt != InstEnd) {
         }
       }
 
       InstIt = NextIt;
     }
   }
 }
 
 static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
                     ScalarEvolution &SE, RegionInfo &RI) {
   // Check if we created an isl_ast root node, otherwise exit.
   isl_ast_node *AstRoot = AI.getAst();
   if (!AstRoot)
     return false;
-
-  auto &DL = S.getFunction().getParent()->getDataLayout();
   Region *R = &S.getRegion();
-  assert(!R->isTopLevelRegion() && "Top level regions are not supported");
-
+  Function *F = R->getEntry()->getParent();
+  BasicBlock *StartBlock = nullptr, *ExitBlock = nullptr;
+  BBPair StartExitBlocks;
   ScopAnnotator Annotator;
+  PollyIRBuilder Builder = createPollyIRBuilder(R->getEntry(), Annotator);
+  auto &DL = S.getFunction().getParent()->getDataLayout();
 
+  if (R->isTopLevelRegion()) {
+    StartExitBlocks = std::get<0>(
+        executeTopLevelScopConditionally(S, Builder.getTrue(), DT, RI, LI));
+    StartBlock = std::get<0>(StartExitBlocks);
+    ExitBlock = std::get<1>(StartExitBlocks);
+  } else {
     simplifyRegion(R, &DT, &LI, &RI);
     assert(R->isSimple());
     BasicBlock *EnteringBB = S.getEnteringBlock();
     assert(EnteringBB);
-  PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
     // Only build the run-time condition and parameters _after_ having
     // introduced the conditional branch. This is important as the conditional
     // branch will guard the original scop from new induction variables that
     // the SCEVExpander may introduce while code generating the parameters and
     // which may introduce scalar dependences that prevent us from correctly
     // code generating this scop.
-  BBPair StartExitBlocks =
+    StartExitBlocks =
         std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI));
-  BasicBlock *StartBlock = std::get<0>(StartExitBlocks);
-  BasicBlock *ExitBlock = std::get<1>(StartExitBlocks);
-
+    StartBlock = std::get<0>(StartExitBlocks);
+    ExitBlock = std::get<1>(StartExitBlocks);
+  }
   removeLifetimeMarkers(R);
   auto *SplitBlock = StartBlock->getSinglePredecessor();
+  if (R->isTopLevelRegion()) {
+    SplitBlock = SplitBlock->getSinglePredecessor();
+  }
 
   IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
 
   // All arrays must have their base pointers known before
   // ScopAnnotator::buildAliasScopes.
   NodeBuilder.allocateNewArrays(StartExitBlocks);
   Annotator.buildAliasScopes(S);
 
   if (PerfMonitoring) {
-    PerfMonitor P(S, EnteringBB->getParent()->getParent());
+    PerfMonitor P(S, F->getParent());
     P.initialize();
     P.insertRegionStart(SplitBlock->getTerminator());
 
     BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();
     P.insertRegionEnd(MergeBlock->getTerminator());
   }
 
   // First generate code for the hoisted invariant loads and transitively the
   // parameters they reference. Afterwards, for the remaining parameters that
   // might reference the hoisted loads. Finally, build the runtime check
   // that might reference both hoisted loads as well as parameters.
   // If the hoisting fails we have to bail and execute the original code.
   Builder.SetInsertPoint(SplitBlock->getTerminator());
   if (!NodeBuilder.preloadInvariantLoads()) {
 
     // Patch the introduced branch condition to ensure that we always execute
     // the original SCoP.
     auto *FalseI1 = Builder.getFalse();
     auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
     SplitBBTerm->setOperand(0, FalseI1);
 
     // Since the other branch is hence ignored we mark it as unreachable and
     // adjust the dominator tree accordingly.
     auto *ExitingBlock = StartBlock->getUniqueSuccessor();
     assert(ExitingBlock);
     auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
     assert(MergeBlock);
     markBlockUnreachable(*StartBlock, Builder);
     markBlockUnreachable(*ExitingBlock, Builder);
     auto *ExitingBB = S.getExitingBlock();
     assert(ExitingBB);
     DT.changeImmediateDominator(MergeBlock, ExitingBB);
     DT.eraseNode(ExitingBlock);
 
     isl_ast_node_free(AstRoot);
   } else {
     NodeBuilder.addParameters(S.getContext().release());
     Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
 
     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
 
     // Explicitly set the insert point to the end of the block to avoid that a
     // split at the builder's current
     // insert position would move the malloc calls to the wrong BasicBlock.
     // Ideally we would just split the block during allocation of the new
     // arrays, but this would break the assumption that there are no blocks
     // between polly.start and polly.exiting (at this point).
     Builder.SetInsertPoint(StartBlock->getTerminator());
 
     NodeBuilder.create(AstRoot);
     NodeBuilder.finalize();
-    fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
+    fixRegionInfo(*F, *R->getParent(), RI);
   }
-
-  Function *F = EnteringBB->getParent();
   verifyGeneratedFunction(S, *F, AI);
   for (auto *SubF : NodeBuilder.getParallelSubfunctions())
     verifyGeneratedFunction(S, *SubF, AI);
 
   // Mark the function such that we run additional cleanup passes on this
   // function (e.g. mem2reg to rediscover phi nodes).
   F->addFnAttr("polly-optimized");
   return true;
 }
 
 class CodeGeneration : public ScopPass {
 public:
   static char ID;
 
   CodeGeneration() : ScopPass(ID) {}
 
   /// The data layout used.
   const DataLayout *DL;
 
   /// @name The analysis passes we need to generate code.
   ///
   ///{
   LoopInfo *LI;
   IslAstInfo *AI;
   DominatorTree *DT;
   ScalarEvolution *SE;
   RegionInfo *RI;
   ///}
 
   /// Generate LLVM-IR for the SCoP @p S.
   bool runOnScop(Scop &S) override {
     // Skip SCoPs in case they're already code-generated by PPCGCodeGeneration.
     if (S.isToBeSkipped())
       return false;

lib/CodeGen/Utils.cpp

 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 
 // Alternative to llvm::SplitCriticalEdge.
 //
 // Creates a new block which branches to Succ. The edge to split is redirected
 // to the new block.
 //
 // The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
 // not critical.
 // The issue with llvm::SplitEdge is that it does not always create the middle
 // block, but reuses Prev/Succ if it can. We always want a new middle block.
 static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
                              const char *Suffix, DominatorTree *DT,
                              LoopInfo *LI, RegionInfo *RI) {
   assert(Prev && Succ);
 
   // Before:
   //   \    /     /   //
   //    Prev     /    //
polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT,
   //        |              |       //
   //    MergeBlock---------/       //
   //        |                      //
   //      ExitBB                   //
   //      /    \                   //
 
   return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr);
 }
+
+// Transforms F to have a single exit node by introducing a new basic block
+// and unconditional jumps from the existing nodes with return instructions.
+// The return value is obtained with a corresponding phi instruction.
+static BasicBlock *unifyFunctionExitNodes(Function &F) {
+  // Loop over all of the blocks in a function, tracking all of the blocks that
+  // return.
+  //
+  SmallVector<BasicBlock *, 4> ReturningBlocks;
+  BasicBlock *ReturnBlock = nullptr;
+  for (BasicBlock &I : F)
+    if (isa<ReturnInst>(I.getTerminator()))
+      ReturningBlocks.push_back(&I);
+
+  // Now handle return blocks.
+  if (ReturningBlocks.empty()) {
+    llvm_unreachable("Full function Scop does not return");
+  } else if (ReturningBlocks.size() == 1) {
+    ReturnBlock = ReturningBlocks.front(); // Already has a single return block
+    return ReturnBlock;
+  }
+
+  // Otherwise, we need to insert a new basic block into the function, add a PHI
+  // nodes (if the function returns values), and convert all of the return
+  // instructions into unconditional branches.
+  //
+  BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), "polly.ret", &F);
+
+  PHINode *PN = nullptr;
+  if (F.getReturnType()->isVoidTy()) {
+    ReturnInst::Create(F.getContext(), nullptr, NewRetBlock);
+  } else {
+    // If the function doesn't return void... add a PHI node to the block...
+    PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(),
+                         "UnifiedRetVal");
+
+    NewRetBlock->getInstList().push_back(PN);
+    ReturnInst::Create(F.getContext(), PN, NewRetBlock);
+  }
+
+  // Loop over all of the blocks, replacing the return instruction with an
+  // unconditional branch.
+  for (BasicBlock *BB : ReturningBlocks) {
+    // Add an incoming element to the PHI node for every return instruction that
+    // is merging into this new block...
+    if (PN)
+      PN->addIncoming(BB->getTerminator()->getOperand(0), BB);
+
+    BB->getTerminator()->eraseFromParent();
+    BranchInst::Create(NewRetBlock, BB);
+  }
+  return NewRetBlock;
+}
+
+std::pair<polly::BBPair, BranchInst *>
+polly::executeTopLevelScopConditionally(Scop &S, Value *RTC, DominatorTree &DT,
+                                        RegionInfo &RI, LoopInfo &LI) {
+  Region *R = &S.getRegion();
+  Function *F = R->getEntry()->getParent();
+
+  splitEntryBlockForAlloca(R->getEntry(), &DT, &LI, &RI);
+
+  BasicBlock *SingleExitBlock = unifyFunctionExitNodes(*F);
+
+  BasicBlock *ExitPred = SingleExitBlock->getSinglePredecessor();
+  assert(ExitPred && "Multiple predessors not yet supported.");
+
+  ScopAnnotator Annotator;
+  PollyIRBuilder Builder = createPollyIRBuilder(R->getEntry(), Annotator);
+
+  BasicBlock *SplitBlock =
+      BasicBlock::Create(F->getContext(), "polly.split", F);
+
+  BasicBlock *JoinBlock =
+      splitEdge(ExitPred, SingleExitBlock, "polly.merge", &DT, &LI, &RI);
+
+  BasicBlock *StartBlock =
+      BasicBlock::Create(F->getContext(), "polly.start", F);
+
+  BasicBlock *ExitingBlock =
+      BasicBlock::Create(F->getContext(), "polly.exiting", F);
+
+  Builder.SetInsertPoint(SplitBlock);
+  Builder.CreateBr(StartBlock);
+
+  Builder.SetInsertPoint(StartBlock);
+  Builder.CreateBr(ExitingBlock);
+
+  Builder.SetInsertPoint(ExitingBlock);
+  Builder.CreateBr(JoinBlock);
+
+  BasicBlock *EntrySucc = R->getEntry()->getSingleSuccessor();
+  assert(EntrySucc);
+  R->getEntry()->getTerminator()->eraseFromParent();
+  Builder.SetInsertPoint(R->getEntry());
+  BranchInst *CondBr = Builder.CreateCondBr(RTC, EntrySucc, SplitBlock);
+
+  DT.recalculate(*F);
+  // TODO : Update DT incrementally
+  if (Loop *L = LI.getLoopFor(SplitBlock)) {
+    L->addBasicBlockToLoop(StartBlock, LI);
+    L->addBasicBlockToLoop(ExitingBlock, LI);
+  }
+  return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr);
+}

lib/Support/ScopHelper.cpp

const SCEV *visitUnknown(const SCEVUnknown *E) {
 
     Instruction *Inst = dyn_cast<Instruction>(E->getValue());
     Instruction *IP;
     if (Inst && !R.contains(Inst))
       IP = Inst;
     else if (Inst && RTCBB->getParent() == Inst->getFunction())
       IP = RTCBB->getTerminator();
     else
-      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
+      IP = R.isTopLevelRegion()
+               ? R.getEntry()->getTerminator()
+               : RTCBB->getParent()->getEntryBlock().getTerminator();
 
     if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
                   Inst->getOpcode() != Instruction::SDiv))
       return visitGenericInst(E, Inst, IP);
 
     const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
     const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
 

test/Isl/CodeGen/full-function.ll

+; RUN: opt %loadPolly -polly-codegen -polly-detect-full-functions -S \
+; RUN:     < %s | FileCheck %s
+; CHECK: bb:
+; CHECK:  br i1 %3, label %bb.split, label %polly.split
+; CHECK:  bb.split:
+; CHECK:    br label %bb1
+; CHECK:  b1:
+; CHECK:    br i1 %exitcond, label %bb2, label %bb4polly.merge
+; CHECK:  bb2:
+; CHECK:    br label %bb3
+; CHECK:  bb3:
+; CHECK:    br label %bb1
+; CHECK:  bb4polly.merge:
+; CHECK:    br label %bb4
+; CHECK:  bb4:
+; CHECK:    ret void
+; CHECK:  polly.split:
+; CHECK:    br label %polly.start
+; CHECK:  polly.start:
+; CHECK:    br label %polly.loop_if
+; CHECK:  polly.loop_exit:
+; CHECK:    br label %polly.exiting
+; CHECK:  polly.exiting:
+; CHECK:    br label %bb4polly.merge
+; CHECK:  polly.loop_if:
+; CHECK:    br i1 %polly.loop_guard, label %polly.loop_preheader, label %polly.loop_exit
+; CHECK:  polly.loop_header:
+; CHECK:    br label %polly.stmt.bb2
+; CHECK:  polly.stmt.bb2:
+; CHECK:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
+; CHECK:  polly.loop_preheader:
+; CHECK:    br label %polly.loop_header
+
+@A = common global [1024 x i32] zeroinitializer, align 16 ; <[1024 x i32]*> [#uses=3]
+
+define void @bar(i64 %n) nounwind {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb3, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp, %bb3 ]       ; <i64> [#uses=3]
+  %scevgep = getelementptr [1024 x i32], [1024 x i32]* @A, i64 0, i64 %i.0 ; <i32*> [#uses=1]
+  %exitcond = icmp ne i64 %i.0, %n                ; <i1> [#uses=1]
+  br i1 %exitcond, label %bb2, label %bb4
+
+bb2:                                              ; preds = %bb1
+  store i32 1, i32* %scevgep
+  br label %bb3
+
+bb3:                                              ; preds = %bb2
+  %tmp = add nsw i64 %i.0, 1                      ; <i64> [#uses=1]
+  br label %bb1
+
+bb4:                                              ; preds = %bb1
+  ret void
+}