[Polly] Iterate over explicit instruction list in CodeGen for block statements. NFC

[Meinersbur]

include/polly/ScopInfo.h

1161 ↗

(On Diff #100630)

This should not be public, but have an accessor that is public (Returning either a const std::vector& or an llvm::iterator_range, both ensure that the list is not modified from exterior)

[nandini12396]

Added a public accessor to the list of instructions, as suggested by Michael Sir.

[nandini12396]

Updated to polly format.

[Meinersbur]

LGTM.

I am going to commit sometime today.

lib/CodeGen/BlockGenerators.cpp

448–449 ↗

(On Diff #100710)

To keep a note for later refactoring (nothing to do atm):

The only other caller of copyBB is RegionGenerator. If it handles copyBB itself, then this copyBB will only ever be called on block stmts.

[Meinersbur]

I got a crash in the test Polly :: Isl/CodeGen/intrinsics_lifetime.ll on Linux, but not on Windows. So I do not commit until I found the issue. Does check-polly work on you machine?

[nandini12396]

No Sir. IslTests pass for me. However, I am getting failure of Polly :: ScopInfo/constant_functions_multi_dim.ll due to some other reason; I think unrelated to this patch.

[Meinersbur]

Valgrind output is:

==24313== Invalid read of size 1
==24313==    at 0x1327994: llvm::Value::getValueID() const (Value.h:459)
==24313==    by 0x1327A55: llvm::Instruction::getOpcode() const (Instruction.h:121)
==24313==    by 0x13C6A7F: llvm::Instruction::isTerminator() const (Instruction.h:124)
==24313==    by 0x2BF4ACA: polly::BlockGenerator::copyInstruction(polly::ScopStmt&, llvm::Instruction*, llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>, llvm::DenseMapInfo<llvm::AssertingVH<llvm::Value> >, llvm::detail::DenseMapPair<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value> > >&, llvm::DenseMap<llvm::Loop const*, llvm::SCEV const*, llvm::DenseMapInfo<llvm::Loop const*>, llvm::detail::DenseMapPair<llvm::Loop const*, llvm::SCEV const*> >&, isl_id_to_ast_expr*) (BlockGenerators.cpp:350)
==24313==    by 0x2BF51DF: polly::BlockGenerator::copyBB(polly::ScopStmt&, llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>, llvm::DenseMapInfo<llvm::AssertingVH<llvm::Value> >, llvm::detail::DenseMapPair<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value> > >&, llvm::DenseMap<llvm::Loop const*, llvm::SCEV const*, llvm::DenseMapInfo<llvm::Loop const*>, llvm::detail::DenseMapPair<llvm::Loop const*, llvm::SCEV const*> >&, isl_id_to_ast_expr*) (BlockGenerators.cpp:446)
==24313==    by 0x2BF50C2: polly::BlockGenerator::copyBB(polly::ScopStmt&, llvm::BasicBlock*, llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>, llvm::DenseMapInfo<llvm::AssertingVH<llvm::Value> >, llvm::detail::DenseMapPair<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value> > >&, llvm::DenseMap<llvm::Loop const*, llvm::SCEV const*, llvm::DenseMapInfo<llvm::Loop const*>, llvm::detail::DenseMapPair<llvm::Loop const*, llvm::SCEV const*> >&, isl_id_to_ast_expr*) (BlockGenerators.cpp:431)
==24313==    by 0x2BF4F05: polly::BlockGenerator::copyStmt(polly::ScopStmt&, llvm::DenseMap<llvm::Loop const*, llvm::SCEV const*, llvm::DenseMapInfo<llvm::Loop const*>, llvm::detail::DenseMapPair<llvm::Loop const*, llvm::SCEV const*> >&, isl_id_to_ast_expr*) (BlockGenerators.cpp:413)
==24313==    by 0x2C13EFB: IslNodeBuilder::createUser(isl_ast_node*) (IslNodeBuilder.cpp:905)
==24313==    by 0x2C140D3: IslNodeBuilder::create(isl_ast_node*) (IslNodeBuilder.cpp:939)
==24313==    by 0x2C13FCD: IslNodeBuilder::createBlock(isl_ast_node*) (IslNodeBuilder.cpp:919)
==24313==    by 0x2C140F3: IslNodeBuilder::create(isl_ast_node*) (IslNodeBuilder.cpp:942)
==24313==    by 0x2C11E71: IslNodeBuilder::createForSequential(isl_ast_node*, bool) (IslNodeBuilder.cpp:505)
==24313==  Address 0x7506148 is 88 bytes inside a block of size 144 free'd
==24313==    at 0x5D7F24B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==24313==    by 0x210466D: llvm::User::operator delete(void*) (User.cpp:190)
==24313==    by 0x21059F4: llvm::Value::deleteValue() (Instruction.def:190)
==24313==    by 0x1CED7C1: llvm::ilist_alloc_traits<llvm::Instruction>::deleteNode(llvm::Instruction*) (Instruction.h:648)
==24313==    by 0x1CEE1FE: llvm::iplist_impl<llvm::simple_ilist<llvm::Instruction>, llvm::SymbolTableListTraits<llvm::Instruction> >::erase(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, false>) (ilist.h:281)
==24313==    by 0x2BBC02A: (anonymous namespace)::removeLifetimeMarkers(llvm::Region*) (CodeGeneration.cpp:141)
==24313==    by 0x2BBC2A4: (anonymous namespace)::CodeGen(polly::Scop&, polly::IslAstInfo&, llvm::LoopInfo&, llvm::DominatorTree&, llvm::ScalarEvolution&, llvm::RegionInfo&) (CodeGeneration.cpp:181)
==24313==    by 0x2BBC9B1: (anonymous namespace)::CodeGeneration::runOnScop(polly::Scop&) (CodeGeneration.cpp:277)
==24313==    by 0x2BB337A: polly::ScopPass::runOnRegion(llvm::Region*, llvm::RGPassManager&) (ScopPass.cpp:26)
==24313==    by 0x19A9583: llvm::RGPassManager::runOnFunction(llvm::Function&) (RegionPass.cpp:97)
==24313==    by 0x209232D: llvm::FPPassManager::runOnFunction(llvm::Function&) (LegacyPassManager.cpp:1519)
==24313==    by 0x20924C6: llvm::FPPassManager::runOnModule(llvm::Module&) (LegacyPassManager.cpp:1540)
==24313==  Block was alloc'd at
==24313==    at 0x5D7E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==24313==    by 0x2104373: allocateFixedOperandUser (User.cpp:126)
==24313==    by 0x2104373: llvm::User::operator new(unsigned long, unsigned int, unsigned int) (User.cpp:148)
==24313==    by 0x13C7919: llvm::CallInst::Create(llvm::FunctionType*, llvm::Value*, llvm::ArrayRef<llvm::Value*>, llvm::ArrayRef<llvm::OperandBundleDefT<llvm::Value*> >, llvm::Twine const&, llvm::Instruction*) (Instructions.h:1456)
==24313==    by 0x2FFF6ED: llvm::LLParser::ParseCall(llvm::Instruction*&, llvm::LLParser::PerFunctionState&, llvm::CallInst::TailCallKind) (LLParser.cpp:6021)
==24313==    by 0x2FFA3E8: llvm::LLParser::ParseInstruction(llvm::Instruction*&, llvm::BasicBlock*, llvm::LLParser::PerFunctionState&) (LLParser.cpp:5136)
==24313==    by 0x2FF9C78: llvm::LLParser::ParseBasicBlock(llvm::LLParser::PerFunctionState&) (LLParser.cpp:4998)
==24313==    by 0x2FF990C: llvm::LLParser::ParseFunctionBody(llvm::Function&) (LLParser.cpp:4946)
==24313==    by 0x2FDA8A6: llvm::LLParser::ParseDefine() (LLParser.cpp:452)
==24313==    by 0x2FD9A33: llvm::LLParser::ParseTopLevelEntities() (LLParser.cpp:269)
==24313==    by 0x2FD806A: llvm::LLParser::Run() (LLParser.cpp:74)
==24313==    by 0x2FBE12F: llvm::parseAssemblyInto(llvm::MemoryBufferRef, llvm::Module&, llvm::SMDiagnostic&, llvm::SlotMapping*) (Parser.cpp:31)
==24313==    by 0x2FBE1F7: llvm::parseAssembly(llvm::MemoryBufferRef, llvm::SMDiagnostic&, llvm::LLVMContext&, llvm::SlotMapping*) (Parser.cpp:41)

The issue seems to be a llvm.lifetime.start marker which was removed from the BB, but still in the instruction list.

Can you remove ignored intrinsics (isIgnoreIntrinsic(Instruction*)) from the instructions list just like terminators? Use a separate patch, with a test case that contains one of the ignored intrinsics.

[nandini12396]

For the same input file, whose IR contains intrinsics, I tried generating IR again, but it did not contain intrinsics. Is there some flag required for generating intrinsics?

[Meinersbur]

In D33653#769688, @nandini12396 wrote:

For the same input file, whose IR contains intrinsics, I tried generating IR again, but it did not contain intrinsics. Is there some flag required for generating intrinsics?

The ignored intrinsics are never generated. That's not the problem we see here.

The issue is that the llvm.lifetime.start gets deleted between ScopInfo and BlockGenerator. Still accessing it causes a use-after-free error. Use Valgrind Memcheck or AddressSanitizer to find those.

[• zinob]

Why is Stmt.getInstruction() is introduced?

[nandini12396]

ScopStmt::getInstructions() is simply a public accessor member function which returns the explicit list of ScopStmt::Instructions. This patch is a step towards "Finer Statement Granularity".
Since we will no longer have a 1-to-1 mapping from statements to basic block, i.e. a statement does not comprise of all the instructions of a BB; instead of iterating over all instructions of the BB, we now traverse over only the explicit list of instructions contained in a SCoP statement. Hope this is helpful.

polly/trunk/include/polly/ScopInfo.h

public:
   const_iterator end() const { return MemAccs.end(); }
   size_t size() const { return MemAccs.size(); }
 
   unsigned getNumIterators() const;
 
   Scop *getParent() { return &Parent; }
   const Scop *getParent() const { return &Parent; }
 
+  const std::vector<Instruction *> &getInstructions() const {
+    return Instructions;
+  }
+
   const char *getBaseName() const;
 
   /// Set the isl AST build.
   void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
 
   /// Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 

polly/trunk/lib/CodeGen/BlockGenerators.cpp

BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
   return CopyBB;
 }
 
 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                             ValueMapT &BBMap, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses) {
   EntryBB = &CopyBB->getParent()->getEntryBlock();
 
+  if (Stmt.isBlockStmt())
+    for (Instruction *Inst : Stmt.getInstructions())
+      copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);
+  else
     for (Instruction &Inst : *BB)
       copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
 }
 
 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
   assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind");
 
   return getOrCreateAlloca(Access.getLatestScopArrayInfo());
 }