[NFC] Remove extra headers included in Loop Unroll and LoopUnrollAndJam files

[anhtuyen]

Summary

I am working on refactoring Loop Unroll and Jam transformation, and noticed a number of header files can be safely removed.
I have tested and know that this removal will not cause any functional changes.

[dmgreen]

A lot of these are required, and I think will be included transitively if not included directly. Things like AssumptionCache and Dominators and Debug will all be made of use of inside these passes. It's probably better to be explicit about them and leave in those includes that are used (even if it compiles without).

Some of them like SimplifyIndVar and IntrinsicInst you are right can be removed.

Can you speak about some of the refactorings you are thinking of making? @Whitney has been recently making changes too, as in D73129 if you have seen.

[anhtuyen]

Thanks, David @dmgreen
You are right that many of the headers in my list are included transitively. Other than AssumptionCache and Dominators and Debug, can you give me names of those you like to be included explicitly even if the compilation can go without them? I will keep them untouched.
By the way, I am aware of what Whitney is working on. I am refactoring the LoopUnrollAndJam to three classes: 1. new pass manager 2. old pass manager 3. the actual implementation, which is used by both 1 and 2.

A side note, but I just noticed I had mistakenly added David Greene instead of you as a reviewer!

[dmgreen]

By the way, I am aware of what Whitney is working on. I am refactoring the LoopUnrollAndJam to three classes: 1. new pass manager 2. old pass manager 3. the actual implementation, which is used by both 1 and 2.

Sounds good. So long as you know what each other are up to.

You are essentially replacing tryToUnrollAndJamLoop with a class? As opposed to being static functions?

You are right that many of the headers in my list are included transitively. Other than AssumptionCache and Dominators and Debug, can you give me names of those you like to be included explicitly even if the compilation can go without them? I will keep them untouched.

Best bet is probably to keep all the ones that look like they are obviously used in the file, and I can let you know if any of the others that are still removed should be kept around.

[anhtuyen]

Based on suggestion by David @dmgreen, I un-delete the headers used obviously in the files.
The change is now much smaller than that of the initial patch, but I think it is fine.
Thanks again, David! Pls let me know how you think!

[dmgreen]

Thanks. I left some comments on files that it may be best to keep around. The others look like a good cleanup to remove.

LGTM.

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

14–17

These 4 are used in one way of another.

33–35

Intrinsics are used. Instructions too I guess, but that is unlikely to cause a problem.

40

This is used for things like dyn_cast and isa. It's probably fine to leave or remove, as it will be included from elsewhere in either case.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

29

There are some references to Intrinsics. Best to keep this one to be more robust.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

14

We still use this for the moment (although may not in the future).

29

Same as above, keep this one.

[rnk]

I don't have time to review all these headers, but I looked at 3, and 2/3 are used, and would cause build errors if they did not happen to be pulled in by transitive includes. Generally, code should include what it uses, so 2/3 of the changes I looked at seem undesirable.

If you want to meaningfully make the build faster, I would do it like this:

• extract the command line to recompile the source file of interest (rm lib/.../LoopUnrollAndJam.cpp.o ninja -v -n lib/.../LoopUnrollAndJam.cpp.o) Paste it in a shell script to easily rerun.
• compile the file, count the number of lines in the .d file to approximate how many includes it actually needed
• remove one include from the source file
• recompile, recount number of lines in .d file. If it did not get smaller, put the header back.
• repeat.

In this way, you only ever make changes that actually make the build faster. It is also best to start by focusing on header files instead of cpp files, since they introduce transitive includes. Because of that, removing an include from a header has more impact on the overall build time.

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

14

None is used in this file.

16

SmallPtrSet is used in this file.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

26

This seems good, it doesn't seem used, so far as I can tell.

[anhtuyen]

In D73498#1848429, @rnk wrote:

I don't have time to review all these headers, but I looked at 3, and 2/3 are used, and would cause build errors if they did not happen to be pulled in by transitive includes. Generally, code should include what it uses, so 2/3 of the changes I looked at seem undesirable.

If you want to meaningfully make the build faster, I would do it like this:

• extract the command line to recompile the source file of interest (rm lib/.../LoopUnrollAndJam.cpp.o ninja -v -n lib/.../LoopUnrollAndJam.cpp.o) Paste it in a shell script to easily rerun.
• compile the file, count the number of lines in the .d file to approximate how many includes it actually needed
• remove one include from the source file
• recompile, recount number of lines in .d file. If it did not get smaller, put the header back.
• repeat.

In this way, you only ever make changes that actually make the build faster. It is also best to start by focusing on header files instead of cpp files, since they introduce transitive includes. Because of that, removing an include from a header has more impact on the overall build time.

Thanks, Reid @rnk for your planing out a detailed course of action. Below is my plan, and please let me know if you have objection.

1. Dave has done a very diligent review and I will further undelete (i.e. keep) all header files raised by him before committing the patch. I do not know the names of the 2/3 headers you think we better keep, but they will likely be kept based on Dave's comments. Since the chance of someone removes an include from a header file without checking if we can build is quite small, the chances of having build errors is negligible too. This patch, though it is small, does remove many redundant headers which Dave has pointed out and thus it's worth it.
2. Using something similar to what you described above, I will put up another patch after I am done with my current project.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

29

Thank you, Dave @dmgreen ! I will un-delete Intrinsics accordingly.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

14

Thanks, I will put it back.

29

Yes, I will keep it.

[anhtuyen]

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

14–17

Yes, I will put them back.

[rnk]

In D73498#1851997, @anhtuyen wrote:

Thanks, Reid @rnk for your planing out a detailed course of action. Below is my plan, and please let me know if you have objection.

1. Dave has done a very diligent review and I will further undelete (i.e. keep) all header files raised by him before committing the patch. I do not know the names of the 2/3 headers you think we better keep, but they will likely be kept based on Dave's comments. Since the chance of someone removes an include from a header file without checking if we can build is quite small, the chances of having build errors is negligible too. This patch, though it is small, does remove many redundant headers which Dave has pointed out and thus it's worth it.

I don't think I agree with that. The way I see things, the most valuable includes to remove are the ones in headers. Includes in .cpp files only affect one .cpp file: the file itself. Removing includes that are needed but happen to be satisfied transitively from other includes makes it more difficult to remove includes from headers, because other files depend on them. So, it is a low-value change that makes it more difficult to perform a high value change. This is the basis of "include what you use" (IWYU) style, which is what we aim to practice.

The three headers I mentioned were the lines I commented on inline: None.h, SmallPtrSet.h, and DataLayout.h.

[Meinersbur]

For reference: include-what-you-use suggests the following changes on current HEAD:

/home/meinersbur/src/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h should add these lines:
namespace llvm { class Function; }

/home/meinersbur/src/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h should remove these lines:

The full include-list for /home/meinersbur/src/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h:
#include "llvm/IR/PassManager.h"  // for FunctionAnalysisManager, PassInfoMixin
namespace llvm { class Function; }
---

/home/meinersbur/src/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp should add these lines:
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/PriorityWorklist.h"                // for SmallPriorityWo...
#include "llvm/PassAnalysisSupport.h"                 // for AnalysisUsage
#include "llvm/PassRegistry.h"                        // for PassRegistry
#include "llvm/PassSupport.h"                         // for INITIALIZE_PASS...
#include "llvm/Support/Compiler.h"                    // for llvm
#include "llvm/Transforms/Utils/LoopSimplify.h"       // for simplifyLoop
namespace llvm { class Function; }
namespace llvm { class Instruction; }
namespace llvm { class Value; }

/home/meinersbur/src/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp should remove these lines:
- #include <algorithm>  // lines 50-50
- #include <string>  // lines 53-53
- #include "llvm/ADT/STLExtras.h"  // lines 15-15
- #include "llvm/Analysis/LoopPass.h"  // lines 23-23
- #include "llvm/IR/CFG.h"  // lines 28-28
- #include "llvm/IR/Constant.h"  // lines 29-29
- #include "llvm/IR/Function.h"  // lines 32-32
- #include "llvm/IR/Instruction.h"  // lines 33-33
- #include "llvm/IR/IntrinsicInst.h"  // lines 35-35
- #include "llvm/Support/ErrorHandling.h"  // lines 43-43
- #include "llvm/Support/raw_ostream.h"  // lines 44-44
- #include "llvm/Transforms/Scalar/LoopPassManager.h"  // lines 46-46
- #include "llvm/Transforms/Utils.h"  // lines 47-47

The full include-list for /home/meinersbur/src/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp:
#include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
#include <cassert>                                    // for assert
#include <cstdint>                                    // for uint64_t
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/None.h"                            // for None
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/PriorityWorklist.h"                // for SmallPriorityWo...
#include "llvm/ADT/SmallPtrSet.h"                     // for SmallPtrSet
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/Analysis/AssumptionCache.h"            // for AssumptionAnalysis
#include "llvm/Analysis/CodeMetrics.h"                // for CodeMetrics
#include "llvm/Analysis/DependenceAnalysis.h"         // for DependenceAnalysis
#include "llvm/Analysis/LoopAnalysisManager.h"        // for getLoopPassPres...
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopAnalysis
#include "llvm/Analysis/OptimizationRemarkEmitter.h"  // for OptimizationRem...
#include "llvm/Analysis/ScalarEvolution.h"            // for ScalarEvolution
#include "llvm/Analysis/TargetTransformInfo.h"        // for TargetTransform...
#include "llvm/IR/BasicBlock.h"                       // for BasicBlock
#include "llvm/IR/Constants.h"                        // for ConstantInt
#include "llvm/IR/Dominators.h"                       // for DominatorTree (...
#include "llvm/IR/Instructions.h"                     // for LoadInst
#include "llvm/IR/Metadata.h"                         // for MDNode, MDString
#include "llvm/IR/PassManager.h"                      // for FunctionAnalysi...
#include "llvm/InitializePasses.h"                    // for initializeAssum...
#include "llvm/Pass.h"                                // for FunctionPass
#include "llvm/PassAnalysisSupport.h"                 // for AnalysisUsage
#include "llvm/PassRegistry.h"                        // for PassRegistry
#include "llvm/PassSupport.h"                         // for INITIALIZE_PASS...
#include "llvm/Support/Casting.h"                     // for dyn_cast
#include "llvm/Support/CommandLine.h"                 // for opt, desc, init
#include "llvm/Support/Compiler.h"                    // for llvm
#include "llvm/Support/Debug.h"                       // for LLVM_DEBUG
#include "llvm/Transforms/Scalar.h"                   // for createLoopUnrol...
#include "llvm/Transforms/Utils/LoopSimplify.h"       // for simplifyLoop
#include "llvm/Transforms/Utils/LoopUtils.h"          // for makeFollowupLoopID
#include "llvm/Transforms/Utils/UnrollLoop.h"         // for LoopUnrollResult
namespace llvm { class Function; }
namespace llvm { class Instruction; }
namespace llvm { class Value; }
---

[anhtuyen]

Thank you very much Reid @rnk and Michael @Meinersbur for introducing me to that IWYU tool!!!

[anhtuyen]

Based on comments from Reid @rnk and Michael @Meinersbur about IWYU, I have used the tools and adjusted removal/addition of the headers to meet the IWYU ideas. I also decided not to include the suggested llvm/IR/IntrinsicEnums.inc b/c it caused build errors.

Please let me know if you have any suggestion/objection!

I attached the log here for quick reference

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnroll.cpp should add these lines:
#include <assert.h>                                   // for assert
#include <algorithm>                                  // for remove, replace
#include <type_traits>                                // for enable_if<>::type
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/DenseMap.h"                        // for DenseMapBase
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/STLExtras.h"                       // for any_of
#include "llvm/ADT/SetVector.h"                       // for SmallSetVector
#include "llvm/ADT/SmallVector.h"                     // for SmallVector
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/ADT/Twine.h"                           // for operator+, Twine
#include "llvm/ADT/ilist_iterator.h"                  // for operator!=, ili...
#include "llvm/ADT/iterator_range.h"                  // for iterator_range
#include "llvm/Analysis/DomTreeUpdater.h"             // for DomTreeUpdater
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopInfo
#include "llvm/Config/abi-breaking.h"                 // for llvm
#include "llvm/IR/CFG.h"                              // for successors, pre...
#include "llvm/IR/CallSite.h"                         // for CallSite
#include "llvm/IR/Constants.h"                        // for ConstantInt
#include "llvm/IR/DebugLoc.h"                         // for DebugLoc
#include "llvm/IR/DiagnosticInfo.h"                   // for operator<<, Opt...
#include "llvm/IR/Function.h"                         // for Function, Funct...
#include "llvm/IR/Instruction.h"                      // for Instruction
#include "llvm/IR/Instructions.h"                     // for BranchInst, PHI...
#include "llvm/IR/IntrinsicEnums.inc"                 // for assume
#include "llvm/IR/Metadata.h"                         // for MDNode, MDString
#include "llvm/IR/Module.h"                           // for Module
#include "llvm/IR/Use.h"                              // for Use
#include "llvm/IR/User.h"                             // for User::op_range
#include "llvm/IR/ValueHandle.h"                      // for WeakTrackingVH
#include "llvm/IR/ValueMap.h"                         // for ValueMapIterato...
#include "llvm/Support/Casting.h"                     // for dyn_cast, cast
#include "llvm/Support/GenericDomTree.h"              // for DomTreeNodeBase
#include "llvm/Support/MathExtras.h"                  // for GreatestCommonD...
#include "llvm/Transforms/Utils/ValueMapper.h"        // for ValueToValueMapTy
namespace llvm { class DataLayout; }
namespace llvm { class Value; }

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnroll.cpp should remove these lines:
- #include "llvm/ADT/SmallPtrSet.h"  // lines 18-18
- #include "llvm/IR/DataLayout.h"  // lines 26-26
- #include "llvm/IR/LLVMContext.h"  // lines 30-30

The full include-list for /home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnroll.cpp:
#include <assert.h>                                   // for assert
#include <algorithm>                                  // for remove, replace
#include <type_traits>                                // for enable_if<>::type
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/DenseMap.h"                        // for DenseMapBase
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/STLExtras.h"                       // for any_of
#include "llvm/ADT/SetVector.h"                       // for SmallSetVector
#include "llvm/ADT/SmallVector.h"                     // for SmallVector
#include "llvm/ADT/Statistic.h"                       // for STATISTIC, Stat...
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/ADT/Twine.h"                           // for operator+, Twine
#include "llvm/ADT/ilist_iterator.h"                  // for operator!=, ili...
#include "llvm/ADT/iterator_range.h"                  // for iterator_range
#include "llvm/Analysis/AssumptionCache.h"            // for AssumptionCache
#include "llvm/Analysis/DomTreeUpdater.h"             // for DomTreeUpdater
#include "llvm/Analysis/InstructionSimplify.h"        // for SimplifyInstruc...
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopInfo
#include "llvm/Analysis/LoopIterator.h"               // for LoopBlocksDFS
#include "llvm/Analysis/OptimizationRemarkEmitter.h"  // for NV, Optimizatio...
#include "llvm/Analysis/ScalarEvolution.h"            // for ScalarEvolution
#include "llvm/Config/abi-breaking.h"                 // for llvm
#include "llvm/IR/BasicBlock.h"                       // for BasicBlock, Bas...
#include "llvm/IR/CFG.h"                              // for successors, pre...
#include "llvm/IR/CallSite.h"                         // for CallSite
#include "llvm/IR/Constants.h"                        // for ConstantInt
#include "llvm/IR/DebugInfoMetadata.h"                // for DILocation
#include "llvm/IR/DebugLoc.h"                         // for DebugLoc
#include "llvm/IR/DiagnosticInfo.h"                   // for operator<<, Opt...
#include "llvm/IR/Dominators.h"                       // for DominatorTree
#include "llvm/IR/Function.h"                         // for Function, Funct...
#include "llvm/IR/Instruction.h"                      // for Instruction
#include "llvm/IR/Instructions.h"                     // for BranchInst, PHI...
#include "llvm/IR/IntrinsicEnums.inc"                 // for assume
#include "llvm/IR/IntrinsicInst.h"                    // for IntrinsicInst
#include "llvm/IR/Metadata.h"                         // for MDNode, MDString
#include "llvm/IR/Module.h"                           // for Module
#include "llvm/IR/Use.h"                              // for Use
#include "llvm/IR/User.h"                             // for User::op_range
#include "llvm/IR/ValueHandle.h"                      // for WeakTrackingVH
#include "llvm/IR/ValueMap.h"                         // for ValueMapIterato...
#include "llvm/Support/Casting.h"                     // for dyn_cast, cast
#include "llvm/Support/CommandLine.h"                 // for opt, init, desc
#include "llvm/Support/Debug.h"                       // for dbgs, LLVM_DEBUG
#include "llvm/Support/GenericDomTree.h"              // for DomTreeNodeBase
#include "llvm/Support/MathExtras.h"                  // for GreatestCommonD...
#include "llvm/Support/raw_ostream.h"                 // for raw_ostream
#include "llvm/Transforms/Utils/BasicBlockUtils.h"    // for MergeBlockIntoP...
#include "llvm/Transforms/Utils/Cloning.h"            // for CloneBasicBlock
#include "llvm/Transforms/Utils/Local.h"              // for RecursivelyDele...
#include "llvm/Transforms/Utils/LoopSimplify.h"       // for simplifyLoop
#include "llvm/Transforms/Utils/LoopUtils.h"          // for formLCSSARecurs...
#include "llvm/Transforms/Utils/SimplifyIndVar.h"     // for simplifyLoopIVs
#include "llvm/Transforms/Utils/UnrollLoop.h"         // for UnrollLoopOptions
#include "llvm/Transforms/Utils/ValueMapper.h"        // for ValueToValueMapTy
namespace llvm { class DataLayout; }
namespace llvm { class Value; }
---

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp should add these lines:
#include <assert.h>                                   // for assert
#include <memory>                                     // for unique_ptr
#include <type_traits>                                // for enable_if<>::type
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/DenseMap.h"                        // for DenseMap, Dense...
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/STLExtras.h"                       // for reverse
#include "llvm/ADT/SmallVector.h"                     // for SmallVector
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/ADT/Twine.h"                           // for operator+, Twine
#include "llvm/ADT/iterator_range.h"                  // for iterator_range
#include "llvm/Analysis/DomTreeUpdater.h"             // for DomTreeUpdater
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopInfo
#include "llvm/Analysis/MustExecute.h"                // for SimpleLoopSafet...
#include "llvm/Config/abi-breaking.h"                 // for llvm
#include "llvm/IR/DebugLoc.h"                         // for DebugLoc
#include "llvm/IR/DiagnosticInfo.h"                   // for operator<<, Opt...
#include "llvm/IR/Function.h"                         // for Function, Funct...
#include "llvm/IR/Instruction.h"                      // for Instruction
#include "llvm/IR/Instructions.h"                     // for BranchInst, PHI...
#include "llvm/IR/IntrinsicEnums.inc"                 // for assume
#include "llvm/IR/Use.h"                              // for Use
#include "llvm/IR/User.h"                             // for User::op_range
#include "llvm/IR/Value.h"                            // for Value (ptr only)
#include "llvm/IR/ValueHandle.h"                      // for WeakTrackingVH
#include "llvm/IR/ValueMap.h"                         // for ValueMapIterato...
#include "llvm/Support/Casting.h"                     // for cast, dyn_cast
#include "llvm/Support/ErrorHandling.h"               // for llvm_unreachable
#include "llvm/Support/GenericDomTree.h"              // for DominatorTreeBa...
#include "llvm/Transforms/Utils/ValueMapper.h"        // for ValueToValueMapTy

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp should remove these lines:
- #include "llvm/Analysis/InstructionSimplify.h"  // lines 18-18
- #include "llvm/Analysis/LoopAnalysisManager.h"  // lines 19-19
- #include "llvm/Analysis/LoopPass.h"  // lines 21-21
- #include "llvm/Analysis/Utils/Local.h"  // lines 24-24
- #include "llvm/IR/DataLayout.h"  // lines 26-26
- #include "llvm/IR/LLVMContext.h"  // lines 30-30
- #include "llvm/Transforms/Utils/LoopSimplify.h"  // lines 35-35
- #include "llvm/Transforms/Utils/SimplifyIndVar.h"  // lines 37-37

The full include-list for /home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp:
#include <assert.h>                                   // for assert
#include <memory>                                     // for unique_ptr
#include <type_traits>                                // for enable_if<>::type
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/DenseMap.h"                        // for DenseMap, Dense...
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/STLExtras.h"                       // for reverse
#include "llvm/ADT/SmallPtrSet.h"                     // for SmallPtrSet
#include "llvm/ADT/SmallVector.h"                     // for SmallVector
#include "llvm/ADT/Statistic.h"                       // for STATISTIC, Stat...
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/ADT/Twine.h"                           // for operator+, Twine
#include "llvm/ADT/iterator_range.h"                  // for iterator_range
#include "llvm/Analysis/AssumptionCache.h"            // for AssumptionCache
#include "llvm/Analysis/DependenceAnalysis.h"         // for Dependence, Dep...
#include "llvm/Analysis/DomTreeUpdater.h"             // for DomTreeUpdater
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopInfo
#include "llvm/Analysis/LoopIterator.h"               // for LoopBlocksDFS
#include "llvm/Analysis/MustExecute.h"                // for SimpleLoopSafet...
#include "llvm/Analysis/OptimizationRemarkEmitter.h"  // for NV, Optimizatio...
#include "llvm/Analysis/ScalarEvolution.h"            // for ScalarEvolution
#include "llvm/Config/abi-breaking.h"                 // for llvm
#include "llvm/IR/BasicBlock.h"                       // for BasicBlock, Bas...
#include "llvm/IR/DebugInfoMetadata.h"                // for DILocation
#include "llvm/IR/DebugLoc.h"                         // for DebugLoc
#include "llvm/IR/DiagnosticInfo.h"                   // for operator<<, Opt...
#include "llvm/IR/Dominators.h"                       // for DominatorTree
#include "llvm/IR/Function.h"                         // for Function, Funct...
#include "llvm/IR/Instruction.h"                      // for Instruction
#include "llvm/IR/Instructions.h"                     // for BranchInst, PHI...
#include "llvm/IR/IntrinsicEnums.inc"                 // for assume
#include "llvm/IR/IntrinsicInst.h"                    // for IntrinsicInst
#include "llvm/IR/Use.h"                              // for Use
#include "llvm/IR/User.h"                             // for User::op_range
#include "llvm/IR/Value.h"                            // for Value (ptr only)
#include "llvm/IR/ValueHandle.h"                      // for WeakTrackingVH
#include "llvm/IR/ValueMap.h"                         // for ValueMapIterato...
#include "llvm/Support/Casting.h"                     // for cast, dyn_cast
#include "llvm/Support/Debug.h"                       // for dbgs, LLVM_DEBUG
#include "llvm/Support/ErrorHandling.h"               // for llvm_unreachable
#include "llvm/Support/GenericDomTree.h"              // for DominatorTreeBa...
#include "llvm/Support/raw_ostream.h"                 // for raw_ostream
#include "llvm/Transforms/Utils/BasicBlockUtils.h"    // for MergeBlockIntoP...
#include "llvm/Transforms/Utils/Cloning.h"            // for CloneBasicBlock
#include "llvm/Transforms/Utils/LoopUtils.h"          // for hasIterationCou...
#include "llvm/Transforms/Utils/UnrollLoop.h"         // for simplifyLoopAft...
#include "llvm/Transforms/Utils/ValueMapper.h"        // for ValueToValueMapTy
---

/home/anhtuyen/BUILD/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h should add these lines:
namespace llvm { class Function; }

/home/anhtuyen/BUILD/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h should remove these lines:

The full include-list for /home/anhtuyen/BUILD/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h:
#include "llvm/IR/PassManager.h"  // for FunctionAnalysisManager, PassInfoMixin
namespace llvm { class Function; }
---

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp should add these lines:
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/PriorityWorklist.h"                // for SmallPriorityWo...
#include "llvm/PassAnalysisSupport.h"                 // for AnalysisUsage
#include "llvm/PassRegistry.h"                        // for PassRegistry
#include "llvm/PassSupport.h"                         // for INITIALIZE_PASS...
#include "llvm/Support/Compiler.h"                    // for llvm
#include "llvm/Transforms/Utils/LoopSimplify.h"       // for simplifyLoop
namespace llvm { class Instruction; }
namespace llvm { class Value; }

/home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp should remove these lines:
- #include <algorithm>  // lines 50-50
- #include <string>  // lines 53-53
- #include "llvm/ADT/STLExtras.h"  // lines 15-15
- #include "llvm/Analysis/LoopPass.h"  // lines 23-23
- #include "llvm/IR/CFG.h"  // lines 28-28
- #include "llvm/IR/Constant.h"  // lines 29-29
- #include "llvm/IR/Instruction.h"  // lines 33-33
- #include "llvm/IR/IntrinsicInst.h"  // lines 35-35
- #include "llvm/Support/ErrorHandling.h"  // lines 43-43
- #include "llvm/Transforms/Scalar/LoopPassManager.h"  // lines 46-46
- #include "llvm/Transforms/Utils.h"  // lines 47-47

The full include-list for /home/anhtuyen/BUILD/llvm-project/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp:
#include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
#include <cassert>                                    // for assert
#include <cstdint>                                    // for uint64_t
#include <vector>                                     // for vector
#include "llvm/ADT/ArrayRef.h"                        // for ArrayRef
#include "llvm/ADT/None.h"                            // for None
#include "llvm/ADT/Optional.h"                        // for Optional
#include "llvm/ADT/PriorityWorklist.h"                // for SmallPriorityWo...
#include "llvm/ADT/SmallPtrSet.h"                     // for SmallPtrSet
#include "llvm/ADT/StringRef.h"                       // for StringRef
#include "llvm/Analysis/AssumptionCache.h"            // for AssumptionAnalysis
#include "llvm/Analysis/CodeMetrics.h"                // for CodeMetrics
#include "llvm/Analysis/DependenceAnalysis.h"         // for DependenceAnalysis
#include "llvm/Analysis/LoopAnalysisManager.h"        // for getLoopPassPres...
#include "llvm/Analysis/LoopInfo.h"                   // for Loop, LoopAnalysis
#include "llvm/Analysis/OptimizationRemarkEmitter.h"  // for OptimizationRem...
#include "llvm/Analysis/ScalarEvolution.h"            // for ScalarEvolution
#include "llvm/Analysis/TargetTransformInfo.h"        // for TargetTransform...
#include "llvm/IR/BasicBlock.h"                       // for BasicBlock
#include "llvm/IR/Constants.h"                        // for ConstantInt
#include "llvm/IR/Dominators.h"                       // for DominatorTreeAn...
#include "llvm/IR/Function.h"                         // for Function
#include "llvm/IR/Instructions.h"                     // for LoadInst
#include "llvm/IR/Metadata.h"                         // for MDNode, MDString
#include "llvm/IR/PassManager.h"                      // for FunctionAnalysi...
#include "llvm/InitializePasses.h"                    // for initializeAssum...
#include "llvm/Pass.h"                                // for FunctionPass
#include "llvm/PassAnalysisSupport.h"                 // for AnalysisUsage
#include "llvm/PassRegistry.h"                        // for PassRegistry
#include "llvm/PassSupport.h"                         // for INITIALIZE_PASS...
#include "llvm/Support/Casting.h"                     // for dyn_cast
#include "llvm/Support/CommandLine.h"                 // for opt, desc, init
#include "llvm/Support/Compiler.h"                    // for llvm
#include "llvm/Support/Debug.h"                       // for dbgs, LLVM_DEBUG
#include "llvm/Support/raw_ostream.h"                 // for raw_ostream
#include "llvm/Transforms/Scalar.h"                   // for createLoopUnrol...
#include "llvm/Transforms/Utils/LoopSimplify.h"       // for simplifyLoop
#include "llvm/Transforms/Utils/LoopUtils.h"          // for makeFollowupLoopID
#include "llvm/Transforms/Utils/UnrollLoop.h"         // for LoopUnrollResult
namespace llvm { class Instruction; }
namespace llvm { class Value; }
---

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

15–17

Did you run clang-format over it? It typically moves the std headers to the end. Might behave different if there are empty lines between blocks of #include

[anhtuyen]

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

15–17

I did run clang-format over it, but since there was a line between blocks of #include, they were not moved to the end. Let me re-reformat it without the empty lines.

[anhtuyen]

As pointed out by Michael @Meinersbur, the existence of an empty line between 2 blocks of #include had prevented clang-format from acting properly. I removed the empty lines, and reran clang-format on the affected files.

[Meinersbur]

#include "llvm/Config/abi-breaking.h is weird. Is it included for the llvm namespace? I think it can be removed.

Otherwise, LGTM. @rnk ?

[anhtuyen]

Remove llvm/Config/abi-breaking.h

[rnk]

So, IWYU is in theory a useful tool, but in practice, it makes some odd choices. In any case, these includes look good to me.

llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h

 //===- LoopUnrollAndJamPass.h -----------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H
 
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+class Function;
 
 /// A simple loop rotation transformation.
 class LoopUnrollAndJamPass : public PassInfoMixin<LoopUnrollAndJamPass> {
   const int OptLevel;
 
 public:
   explicit LoopUnrollAndJamPass(int OptLevel = 2) : OptLevel(OptLevel) {}
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

 //===- LoopUnrollAndJam.cpp - Loop unroll and jam pass --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass implements an unroll and jam pass. Most of the work is done by
 // Utils/UnrollLoopAndJam.cpp.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/CFG.h"
-#include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
-#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
+#include "llvm/PassAnalysisSupport.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/PassSupport.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
-#include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/UnrollLoop.h"
-#include <algorithm>
 #include <cassert>
 #include <cstdint>
-#include <string>
+#include <vector>
+
+namespace llvm {
+class Instruction;
+class Value;
+} // namespace llvm
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll-and-jam"
 
 /// @{
 /// Metadata attribute names
 static const char *const LLVMLoopUnrollAndJamFollowupAll =

llvm/lib/Transforms/Utils/LoopUnroll.cpp

 // actual pass or policy, but provides a single function to perform loop
 // unrolling.
 //
 // The process of unrolling can produce extraneous basic blocks linked with
 // unconditional branches.  This will be corrected in the future.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/ADT/ilist_iterator.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/Transforms/Utils/UnrollLoop.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <algorithm>
+#include <assert.h>
+#include <type_traits>
+#include <vector>
+
+namespace llvm {
+class DataLayout;
+class Value;
+} // namespace llvm
+
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll"
 
 // TODO: Should these be here or in LoopUnroll?
 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
 STATISTIC(NumUnrolledWithHeader, "Number of loops unrolled without a "

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

 //===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements loop unroll and jam as a routine, much like
 // LoopUnroll.cpp implements loop unroll.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
-#include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
-#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
-#include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
-#include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/Transforms/Utils/UnrollLoop.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <assert.h>
+#include <memory>
+#include <type_traits>
+#include <vector>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll-and-jam"
 
 STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");
 STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");
 
 typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet;