[BOLT] Fix blocks layout reverse iterators

[yota9]

Summary

Use container's reverse iterators

[Amir]

Can you please add a unit test? It's a bit strange that there was this issue and we didn't see it – or were these reverse iterators unused?

[yota9]

@Amir Currently these iterators are almost unused - I see them used only under opts::ReportBadLayout right now. After I've tried to use them by my self I've found out that there are some problems with them, e.g. BBs hasInstructions() assert appeared. Anyway it does not look like it is right to use end() block iterator as an reverse begin...

[thakis]

This doesn't build: http://45.33.8.238/macm1/50229/step_4.txt

FAILED: obj/bolt/lib/Passes/Passes.MCF.o 
/Users/thakis/src/depot_tools/.cipd_bin/gomacc ../../chromeclang/bin/clang++ -MMD -MF obj/bolt/lib/Passes/Passes.MCF.o.d -o obj/bolt/lib/Passes/Passes.MCF.o -c ../../bolt/lib/Passes/MCF.cpp  -I../../llvm/include -Igen/llvm/include -I../../bolt/include -Igen/bolt/include -mmacos-version-min=10.10 -O3 -fdiagnostics-color -Wall -Wextra -Wno-unused-parameter -Wdelete-non-virtual-dtor -Wstring-conversion -Wno-nonportable-include-path -no-canonical-prefixes -Werror=date-time -isysroot ../../sysroot/MacOSX.sdk -Wpoison-system-directories -fPIC -Wcovered-switch-default -std=c++17 -fvisibility-inlines-hidden -fno-exceptions -fno-rtti
warning: include location '/usr/local/include' is unsafe for cross-compilation [-Wpoison-system-directories]
In file included from ../../bolt/lib/Passes/MCF.cpp:14:
In file included from ../../bolt/include/bolt/Core/BinaryFunction.h:28:
In file included from ../../bolt/include/bolt/Core/BinaryBasicBlock.h:18:
../../bolt/include/bolt/Core/FunctionLayout.h:309:12: error: no matching conversion for functional-style cast from 'llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'llvm::bolt::FunctionLayout::block_const_reverse_iterator' (aka 'reverse_iterator<pointer_iterator<pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>')
    return block_const_reverse_iterator(Blocks.rbegin());
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:34:28: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'reverse_iterator<llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_iterator>' to 'const reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>' for 1st argument
class _LIBCPP_TEMPLATE_VIS reverse_iterator
                           ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:34:28: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'reverse_iterator<llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_iterator>' to 'reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>' for 1st argument
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:76:14: note: candidate constructor not viable: no known conversion from 'llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>' for 1st argument
    explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
             ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:82:5: note: candidate template ignored: requirement 'is_convertible<llvm::bolt::BinaryBasicBlock *const *const &, llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>::value' was not satisfied [with _Up = llvm::bolt::BinaryBasicBlock *const *]
    reverse_iterator(const reverse_iterator<_Up>& __u)
    ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:73:5: note: candidate constructor not viable: requires 0 arguments, but 1 was provided
    reverse_iterator() : __t(), current() {}
    ^
In file included from ../../bolt/lib/Passes/MCF.cpp:14:
In file included from ../../bolt/include/bolt/Core/BinaryFunction.h:28:
In file included from ../../bolt/include/bolt/Core/BinaryBasicBlock.h:18:
../../bolt/include/bolt/Core/FunctionLayout.h:315:12: error: no matching conversion for functional-style cast from 'llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'llvm::bolt::FunctionLayout::block_const_reverse_iterator' (aka 'reverse_iterator<pointer_iterator<pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>')
    return block_const_reverse_iterator(Blocks.rend());
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:34:28: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'reverse_iterator<llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_iterator>' to 'const reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>' for 1st argument
class _LIBCPP_TEMPLATE_VIS reverse_iterator
                           ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:34:28: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'reverse_iterator<llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_iterator>' to 'reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>' for 1st argument
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:76:14: note: candidate constructor not viable: no known conversion from 'llvm::SmallVectorTemplateCommon<llvm::bolt::BinaryBasicBlock *>::const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>' for 1st argument
    explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
             ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:82:5: note: candidate template ignored: requirement 'is_convertible<llvm::bolt::BinaryBasicBlock *const *const &, llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>::value' was not satisfied [with _Up = llvm::bolt::BinaryBasicBlock *const *]
    reverse_iterator(const reverse_iterator<_Up>& __u)
    ^
../../chromeclang/bin/../include/c++/v1/__iterator/reverse_iterator.h:73:5: note: candidate constructor not viable: requires 0 arguments, but 1 was provided
    reverse_iterator() : __t(), current() {}
    ^
1 warning and 2 errors generated.

Reverting for now.

[yota9]

Actually I'm not quite sure why this problem appeared on osx. @Amir Have you got any ideas?

[Amir]

Fix Mac/libcxx build

[Amir]

ping @yota9

[yota9]

Thanks @Amir I'm not that deep in the C++ to be honest, but it looks OK. But I still have some problems using these iterators with this patch, resulting in SIGSEGV :( I've found out that if I replace (addition to this patch):

1. In class FunctionFragment iterator types to
   
   using iterator = BasicBlockListType::iterator;
   
   using const_iterator = BasicBlockListType::const_iterator;
2. In class FunctionLayout
   
   using block_const_iterator = BasicBlockListType::const_iterator;

Everything works fine. What do you think about it?

[Amir]

clang-format

[Amir]

In D139335#3979241, @yota9 wrote:

Thanks @Amir I'm not that deep in the C++ to be honest, but it looks OK. But I still have some problems using these iterators with this patch, resulting in SIGSEGV :( I've found out that if I replace (addition to this patch):

1. In class FunctionFragment iterator types to
   
   using iterator = BasicBlockListType::iterator;
   
   using const_iterator = BasicBlockListType::const_iterator;
2. In class FunctionLayout
   
   using block_const_iterator = BasicBlockListType::const_iterator;

Everything works fine. What do you think about it?

I'm not an expert either. Your proposed changes make sense to me, submit them as a diff and I'll test it.

[yota9]

Fix iterator types

[yota9]

@Amir Done, seems every test is passed.
@thakis Could you please check this diff?

[Amir]

Tested on a mac with libcxx std library and with NFC checks on linux.

bolt/include/bolt/Core/FunctionLayout.h

 };
 
 /// A freestanding subset of contiguous blocks of a function.
 class FunctionFragment {
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
   using FragmentListType = SmallVector<unsigned, 0>;
 
 public:
-  using iterator = raw_pointer_iterator<BasicBlockListType::const_iterator,
-                                        BinaryBasicBlock>;
-  using const_iterator =
-      raw_pointer_iterator<BasicBlockListType::const_iterator,
-                           const BinaryBasicBlock>;
+  using iterator = BasicBlockListType::iterator;
+  using const_iterator = BasicBlockListType::const_iterator;
 
 private:
   FunctionLayout *Layout;
   FragmentNum Num;
   unsigned StartIndex;
   unsigned Size = 0;
 
   /// Output address for the fragment.
private:
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
 
 public:
   using fragment_iterator = pointee_iterator<FragmentListType::const_iterator>;
   using fragment_const_iterator =
       pointee_iterator<FragmentListType::const_iterator,
                        const FunctionFragment>;
   using block_iterator = BasicBlockListType::iterator;
-  using block_const_iterator =
-      raw_pointer_iterator<BasicBlockListType::const_iterator,
-                           const BinaryBasicBlock>;
+  using block_const_iterator = BasicBlockListType::const_iterator;
   using block_reverse_iterator = std::reverse_iterator<block_iterator>;
   using block_const_reverse_iterator =
       std::reverse_iterator<block_const_iterator>;
 
 private:
   FragmentListType Fragments;
   BasicBlockListType Blocks;
 
public:
   }
   iterator_range<block_iterator> blocks() {
     return {block_begin(), block_end()};
   }
   iterator_range<block_const_iterator> blocks() const {
     return {block_begin(), block_end()};
   }
   block_reverse_iterator block_rbegin() {
-    return block_reverse_iterator(block_end());
+    return block_reverse_iterator(Blocks.rbegin());
   }
   block_const_reverse_iterator block_rbegin() const {
-    return block_const_reverse_iterator(block_end());
+    return block_const_reverse_iterator(
+        std::make_reverse_iterator(block_end()));
   }
   block_reverse_iterator block_rend() {
-    return block_reverse_iterator(block_begin());
+    return block_reverse_iterator(Blocks.rend());
   }
   block_const_reverse_iterator block_rend() const {
-    return block_const_reverse_iterator(block_begin());
+    return block_const_reverse_iterator(
+        std::make_reverse_iterator(block_begin()));
   }
   iterator_range<block_const_reverse_iterator> rblocks() const {
     return {block_rbegin(), block_rend()};
   }
 
 private:
   block_const_iterator findBasicBlockPos(const BinaryBasicBlock *BB) const;
   block_iterator findBasicBlockPos(const BinaryBasicBlock *BB);
 
   friend class FunctionFragment;
 };
 
 } // namespace bolt
 } // namespace llvm
 
 #endif