Instcombine: try to avoid wasted work in ConstantFold

[escha]

Summary

This is a bit tricky, and if someone has a better idea, please feel free to suggest it!

InstCombine currently does the following:

1. Call ConstantFoldInstruction on the instruction, and replace it with a constant if appropriate. This involves (internally) iterating over its operands and optimizing each ConstantExpr operand with ConstantFoldConstantExpression, then calling ConstantFold on the instruction with operands.
2. If that didn't work, optimize each ConstantExpr operand with ConstantFoldConstantExpression.

However, if you have lots of instructions with ConstantExpr operands but which cannot be folded (ex: loads from constant locations in memory -- in our case, uniform buffers are a common case), this means you call ConstantFoldConstantExpression twice on every operand, every time, because the constant folding fails.

One possible solution (as written here) is to provide an option to ConstantFoldInstruction to tell it not to try to optimize the ConstantExpr arguments, and then to reorder 1) and 2) so that we optimize the ConstantExprs first. I don't know if this is the best option, but it saves ~3-4% of time in instcombine for us.

[reames]

Please upload with full context; I can't review this in the current form.

In general, I'm bothered by this change. Let me back up and ask a question, why do we need to fold the operand of the constant explicitly? Isn't the canonical form fully folded? (i.e. why isn't the argument already folded?) Is there some subtlety specific to constantexprs here?

[escha]

What git option do I use to get a diff with full context?

If it's already folded, why does InstCombine try to optimize it? I did this under the assumption that InstCombine was doing something reasonable (and just being redundant about it); are you saying InstCombine shouldn't be doing this at all?

[escha]

Updated diff with some context.

[reames]

In D18155#376016, @escha wrote:

If it's already folded, why does InstCombine try to optimize it? I did this under the assumption that InstCombine was doing something reasonable (and just being redundant about it); are you saying InstCombine shouldn't be doing this at all?

This is exactly what I'm asking. In general, our canonical form is to have constants fully folded. Given InstCombine is iterative, we only need to do a single folding step at a time to reach an optimal fixed point. Why does this code need to fold constantexprs specially? Is there a reason we can't have a loop per instruction which tries to fold constexpr operands and updates the instruction operands?

[escha]

I believe this code is in the initial portion of instcombine that creates the initial worklist; it isn't run iteratively at all, at least if I remember right.

[escha]

To try to be more clear, this code appears to:

1. Drop instructions that are dead.
2. If constant, fold the constant. [this step folds ConstExprs as part of its internals, because that's how ConstantFolding works]
3. If not constant-foldable, check to see if any ConstExpr operands are foldable [this is where we duplicate work]
4. Add to the initial instcombine worklist.

[reames]

In D18155#376087, @escha wrote:

To try to be more clear, this code appears to:

1. Drop instructions that are dead.
2. If constant, fold the constant. [this step folds ConstExprs as part of its internals, because that's how ConstantFolding works]
3. If not constant-foldable, check to see if any ConstExpr operands are foldable [this is where we duplicate work]
4. Add to the initial instcombine worklist.

Why not do the following:

1. Drop instructions that are dead.
2. Check to see if any ConstExpr operands are foldable, and update the instruction
3. If constant, fold the constant. [no longer needs to consider constexprs]
4. Add to the initial instcombine worklist.

Also, steps 1-3 are repeated inside the InstCombine run loop. See InstCombiner::run. I believe the code AddReachableCodeToWorklist is merely intended to be an optimization to avoid adding trivially constant instructions to the worklist (i.e. reduce the memory consumed by the worklist).

[escha]

Why not do the following:

1. Drop instructions that are dead.
2. Check to see if any ConstExpr operands are foldable, and update the instruction
3. If constant, fold the constant. [no longer needs to consider constexprs]
4. Add to the initial instcombine worklist.

that's literally what this patch does

[reames]

You're correct, I got confused by the changes to the ConstantFolding interface.

What happens if you *only* reorder the two steps? (i.e. do we see cases where we have non-foldable constant exprs?) What performance impact do you see there?

What's really confusing me about this code is that my expectation would be that constant expressions were fully folded *at construction* and that there would be very few places (linking two modules?) which would introduce new foldable constructs in a previously fully folded constant expr. If that's correct, why aren't we conicalizing in those presumable very rare places? (i.e. why is this code in ConstantFoldingInstruction at *all*?)

[escha]

Yeah, I don't understand that part either!

Reordering them alone isn't enough because the slow part isn't the creation of a new simplified ConstExpr; it's running the simplify function, which takes time even if it ends up doing nothing, AFAIK.

[escha]

Ah okay, I think now (looking at this a bit more) I understand why this cost keeps showing up in the profile. Like you said, it also happens during the main InstCombine run as well. Specifically, we have lots of loads and intrinsics with all constant operands that can't be folded (since they're runtime, not compile-time constants). So when running ConstantFoldInstruction, it's forced to call SimplifyConstantExpr on every operand, even though that ends up doing absolutely nothing. The results then get thrown away because you can't constant-fold a load to something whose value isn't known at compile time.

This cost shows up about 3 times in InstCombine:

1. ~4% of time: constantfoldinstruction on init (this patch tries to eliminate that cost)
2. ~4% of time: constantfoldconstantexpr on init (in this patch, but not saved)
3. ~4% of time: constantfoldinstruction during the main loop

My guess is most of these are doing absolutely nothing useful, but I don't know enough about constexprs or the design of instcombine to understand why it's done this way.

[reames]

In D18155#376179, @escha wrote:

My guess is most of these are doing absolutely nothing useful, but I don't know enough about constexprs or the design of instcombine to understand why it's done this way.

My suspicion is that you've stumbled onto a deeper issue with the design of constexpr canonicalization. I think it would be good to raise this on llvm-dev for further discussion. I suspect there's a better design here which could address InstCombine and all other users of ConstantFolding in a single go. In particular, it *really* bothers me that ConstantFolding is doing a recursive search in this case.

p.s. If you want to split out the reordering change, I'd be happy to sign off on that part without waiting for the broader design discussion. Just make sure you make the change in the main loop as well. That's obviously a good idea.

[reames]

Resigning from a stale review. Feel free to re-add if thread ever revived.

[nikic]

I know I'm a bit late here, but wondering if you have any IR / test case which can be used for perf testing? I've created D75634 as a different approach to this issue, but don't have a test case for this myself.

include/llvm/Analysis/ConstantFolding.h

 class Type;
 template <typename T> class ArrayRef;
 
 /// ConstantFoldInstruction - Try to constant fold the specified instruction.
 /// If successful, the constant result is returned, if not, null is returned.
 /// Note that this fails if not all of the operands are constant.  Otherwise,
 /// this function can only fail when attempting to fold instructions like loads
 /// and stores, which have no constant expression form.
+/// Only attempt to constant-fold ConstantExpr operands if FoldOperands
+/// is set to true; set this to false if they are already known to be folded.
 Constant *ConstantFoldInstruction(Instruction *I, const DataLayout &DL,
-                                  const TargetLibraryInfo *TLI = nullptr);
+                                  const TargetLibraryInfo *TLI = nullptr,
+                                  bool FoldOperands = true);
 
 /// ConstantFoldConstantExpression - Attempt to fold the constant expression
 /// using the specified DataLayout.  If successful, the constant result is
 /// result is returned, if not, null is returned.
 Constant *
 ConstantFoldConstantExpression(const ConstantExpr *CE, const DataLayout &DL,
                                const TargetLibraryInfo *TLI = nullptr);
 

lib/Analysis/ConstantFolding.cpp

 
 
 
 //===----------------------------------------------------------------------===//
 // Constant Folding public APIs
 //===----------------------------------------------------------------------===//
 
 Constant *llvm::ConstantFoldInstruction(Instruction *I, const DataLayout &DL,
-                                        const TargetLibraryInfo *TLI) {
+                                        const TargetLibraryInfo *TLI,
+                                        bool FoldOperands) {
   // Handle PHI nodes quickly here...
   if (PHINode *PN = dyn_cast<PHINode>(I)) {
     Constant *CommonValue = nullptr;
 
     for (Value *Incoming : PN->incoming_values()) {
       // If the incoming value is undef then skip it.  Note that while we could
       // skip the value if it is equal to the phi node itself we choose not to
       // because that would break the rule that constant folding only applies if
       // all operands are constants.
       if (isa<UndefValue>(Incoming))
         continue;
       // If the incoming value is not a constant, then give up.
       Constant *C = dyn_cast<Constant>(Incoming);
       if (!C)
         return nullptr;
       // Fold the PHI's operands.
-      if (ConstantExpr *NewC = dyn_cast<ConstantExpr>(C))
+      ConstantExpr *NewC = dyn_cast<ConstantExpr>(C);
+      if (NewC && FoldOperands)
         C = ConstantFoldConstantExpression(NewC, DL, TLI);
       // If the incoming value is a different constant to
       // the one we saw previously, then give up.
       if (CommonValue && C != CommonValue)
         return nullptr;
       CommonValue = C;
     }
 
 
     // If we reach here, all incoming values are the same constant or undef.
     return CommonValue ? CommonValue : UndefValue::get(PN->getType());
   }
 
   // Scan the operand list, checking to see if they are all constants, if so,
   // hand off to ConstantFoldInstOperandsImpl.
   if (!all_of(I->operands(), [](Use &U) { return isa<Constant>(U); }))
     return nullptr;
 
   SmallVector<Constant *, 8> Ops;
   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) {
     Constant *Op = cast<Constant>(*i);
     // Fold the Instruction's operands.
-    if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(Op))
+    ConstantExpr *NewCE = dyn_cast<ConstantExpr>(Op);
+    if (NewCE && FoldOperands)
       Op = ConstantFoldConstantExpression(NewCE, DL, TLI);
 
     Ops.push_back(Op);
   }
 
   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
     return ConstantFoldCompareInstOperands(CI->getPredicate(), Ops[0], Ops[1],
                                            DL, TLI);

lib/Transforms/InstCombine/InstructionCombining.cpp

for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
       // DCE instruction if trivially dead.
       if (isInstructionTriviallyDead(Inst, TLI)) {
         ++NumDeadInst;
         DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
         Inst->eraseFromParent();
         continue;
       }
 
-      // ConstantProp instruction if trivially constant.
-      if (!Inst->use_empty() &&
-          (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
-        if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
-          DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: "
-                       << *Inst << '\n');
-          Inst->replaceAllUsesWith(C);
-          ++NumConstProp;
-          Inst->eraseFromParent();
-          continue;
-        }
-
       // See if we can constant fold its operands.
       for (User::op_iterator i = Inst->op_begin(), e = Inst->op_end(); i != e;
            ++i) {
         ConstantExpr *CE = dyn_cast<ConstantExpr>(i);
         if (CE == nullptr)
           continue;
 
         Constant *&FoldRes = FoldedConstants[CE];
         if (!FoldRes)
           FoldRes = ConstantFoldConstantExpression(CE, DL, TLI);
         if (!FoldRes)
           FoldRes = CE;
 
         if (FoldRes != CE) {
           *i = FoldRes;
           MadeIRChange = true;
         }
       }
 
+      // ConstantProp instruction if trivially constant.
+      if (!Inst->use_empty() &&
+          (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
+        if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI, false  )) {
+          DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: "
+                       << *Inst << '\n');
+          Inst->replaceAllUsesWith(C);
+          ++NumConstProp;
+          Inst->eraseFromParent();
+          continue;
+        }
+
       InstrsForInstCombineWorklist.push_back(Inst);
     }
 
     // Recursively visit successors.  If this is a branch or switch on a
     // constant, only visit the reachable successor.
     TerminatorInst *TI = BB->getTerminator();
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {